Gaussian elimination

For the mathematical background, please read the Wikipedia page on the Gaussian elimination.

Definitions

Row pivot element

For a given nonzero row of the matrix $A$, the pivot element is its first non-zero entry.

Row echelon form

The matrix $A$ is in row echelon form if

• all nonzero rows are above any rows of all zeroes, and
• the pivot of a nonzero row is always strictly to the right of the pivot of the row above it

Example: $\left[ \begin{array}{ccccc} 1 & a_0 & a_1 & a_2 & a_3 \\ 0 & 0 & 2 & a_4 & a_5 \\ 0 & 0 & 0 & 1 & a_6 \end{array} \right]$

Row reduction

Assume $a_{ij}\neq 0$. We say that the row $k$ is reduced by row $i$ w.r.t. the $(i,j)$ entry, if a scalar multiple of row $i$ is substracted from row $k$ such that the $(k,j)$ entry becomes $0$.

Gaussian elimination

• Let $A$ be a matrix with $m$ rows and $n$ columns. Rows can be labeled as "completed" or "uncompleted".
• Initially, all rows are labeled as "uncompleted".
• For $i=0,\ldots,m-1$ do:
• Let $a_{st}$ be the leftmost nonzero elements of the uncompleted rows.
• ($a_{st}$ is well defined if and only if not all uncompleted rows are zero.)
• If $a_{st}$ is well defined, then label the $s$th row as completed and reduce all uncompleted rows by the $s$th row.
• If $a_{st}$ is not well defined, then label the first uncompleted row as "completed".

Demonstration

Matrix dimensions = x.

Precision = digits. Magnitude of matrix entries = .

Permuted rows [hide/show]

The parameters [hide/show]

Copyright by © Gábor P. Nagy, 2017.