Definition:Gaussian Elimination
Definition
Let $\mathbf A$ be a matrix over a field $K$.
Let $\mathbf E$ be a reduced echelon matrix which is row equivalent to $\mathbf A$.
The Gaussian elimination method is a technique for converting $\mathbf A$ into $\mathbf E$ by means of a sequence of elementary row operations.
Procedure
Let $\mathbf A$ be a matrix over a field $F$.
Let $\mathbf E$ be a reduced echelon matrix which is row equivalent to $\mathbf A$.
Let the first column of $\mathbf A$ containing a non-zero element be column $j$.
Let a non-zero element in row $i$ be distinguished.
This element $a_{i j} \ne 0$ is called the pivot element.
Perform the elementary row operation:
- $(1): \quad r_1 \leftrightarrow r_i$
This moves the pivot element to $a_{1 j}$.
Then perform the elementary row operation:
- $(2): \quad r_1 \to \dfrac {r_1} {a_{1 j} }$
that is, divide all the elements of row $1$ by the pivot element.
This gives a matrix with $1$ in the $\tuple {1, j}$ position:
- $\begin {bmatrix} 0 & \cdots & 0 & 1 & b_{1, j + 1} & \cdots & b_{1 n} \\ 0 & \cdots & 0 & b_{2 j} & b_{2, j + 1} & \cdots & b_{2 n} \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & b_{m j} & b_{m, j + 1} & \cdots & b_{m n} \\ \end {bmatrix}$
Now the elementary row operations $r_k \to r_k - b_{k j} r_1, k \in \set {2, 3, \ldots, m}$ gives the matrix:
- $\begin{bmatrix} 0 & \cdots & 0 & 1 & c_{1, j + 1} & \cdots & c_{1 n} \\ 0 & \cdots & 0 & 0 & c_{2, j + 1} & \cdots & c_{2 n} \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & 0 & c_{m, j + 1} & \cdots & c_{m n} \\ \end{bmatrix}$
If some zero rows have appeared, do some further elementary row operations, that is row interchanges, to put them at the bottom.
We now repeat the process with the remaining however-many-there-are rows:
- $\begin{bmatrix} \cdots & 0 & 1 & d_{1, j + 1} & \cdots & d_{1, k - 1} & d_{1 k} & d_{1, k + 1} & \cdots & d_{1 n} \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 1 & d_{2, k + 1} & \cdots & d_{2 n} \\ \cdots & 0 & 0 & 0 & \cdots & 0 & d_{3 k} & d_{3, k + 1} & \cdots & d_{3 n} \\ \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \cdots & 0 & 0 & 0 & \cdots & 0 & d_{n k} & d_{m, k + 1} & \cdots & d_{m n} \\ \end{bmatrix}$
Then we can get the reduced echelon form by:
- $r_i \to r_i - d_{i k} r_2, i \in \set {1, 3, 4, \ldots, m}$
as follows:
- $\begin{bmatrix} \cdots & 0 & 1 & {e_{1, j + 1 } } & \cdots & {e_{1, k - 1} } & 0 & {e_{1, k + 1} } & \cdots & {e_{1 n} } \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 1 & {e_{2, k + 1} } & \cdots & {e_{2 n} } \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & {e_{3, k + 1} } & \cdots & {e_{3 n} } \\ \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & {e_{m, k + 1} } & \cdots & {e_{m n} } \\ \end{bmatrix}$
Thus we progress, until the entire matrix is in reduced echelon form.
Also defined as
Some sources do not insist that $\mathbf E$ be a reduced echelon matrix at the end of the Gaussian elimination process, but merely an echelon matrix.
Also known as
Some sources refer to the technique of Gaussian elimination as Gauss elimination.
Gaussian elimination is sometimes seen referred to as pivotal condensation.
Examples
Arbitrary Matrix $1$
Let $\mathbf A$ denote the matrix:
- $\mathbf A = \begin {bmatrix} 0 & 0 & 5 & 35 & -24 & 1 \\ 0 & 2 & 1 & -1 & 1 & 0 \\ 0 & 3 & 2 & 2 & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 5 & 3 & 1 & 0 & 1 \end {bmatrix}$
The reduced echelon form of $\mathbf A$ is:
- $\mathbf E = \begin {bmatrix} 0 & 1 & 0 & -4 & 0 & 26 \\ 0 & 0 & 1 & 7 & 0 & -43 \\ 0 & 0 & 0 & 0 & 1 & -9 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end {bmatrix}$
Arbitrary Matrix $2$
Let $\mathbf A$ denote the matrix:
- $\mathbf A = \begin {bmatrix} 1 & -1 & 2 & 1 \\ 2 & 1 & -1 & 1 \\ 1 & -2 & 1 & 1 \\ \end {bmatrix}$
The reduced echelon form of $\mathbf A$ is:
- $\mathbf E = \begin {bmatrix} 1 & 0 & 0 & \dfrac 5 8 \\ 0 & 1 & 0 & -\dfrac 1 8 \\ 0 & 0 & 1 & \dfrac 1 8 \\ \end {bmatrix}$
Arbitrary Matrix $3$
Let $\mathbf A$ denote the matrix:
- $\mathbf A = \begin {bmatrix} 1 & 1 & -1 \\ 1 & -1 & 2 \\ 2 & 0 & 2 \\ 2 & 1 & -1 \\ \end {bmatrix}$
The reduced echelon form of $\mathbf A$ is:
- $\mathbf E = \begin {bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end {bmatrix}$
Also see
- Results about Gaussian elimination can be found here.
Source of Name
This entry was named for Carl Friedrich Gauss.
Sources
- 1982: A.O. Morris: Linear Algebra: An Introduction (2nd ed.) ... (previous) ... (next): Chapter $1$: Linear Equations and Matrices: $1.2$ Elementary Row Operations on Matrices: Theorem $1.5$
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Gaussian elimination
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): numerical analysis
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Gaussian elimination
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): numerical analysis