Gaussian elimination uses reversible row operations to solve systems, test invertibility, and compute inverses. We work through the calculations, then prove why they preserve the information we need.
Let \(\mathbb K\) be a field and \(M_n(\mathbb K)\) its square matrices, with \(n\geq1\). Write \(I_n\) for the identity and \(R_i\) for row \(i\). The arguments use exact arithmetic.
1. The row-reduction procedure
Definition 1.1. Elementary row operations
An elementary row operation is one of:
- Swap two distinct rows: \(R_i\leftrightarrow R_j\).
- Scale a row by a nonzero scalar: \(R_i\leftarrow cR_i\), with \(c\neq0\).
- Add a multiple of a different row: \(R_i\leftarrow R_i+cR_j\), with \(i\neq j\).
Matrices related by a finite sequence of these operations are row equivalent.
Definition 1.2. Echelon forms and pivots
A matrix is in row echelon form when its zero rows are at the bottom, the first nonzero entry of each nonzero row lies strictly to the right of the one above it, and entries below these leading entries are zero. Each leading entry is a pivot.
It is in reduced row echelon form (RREF) when every pivot is \(1\) and is the only nonzero entry in its column. Columns without pivots correspond to free variables when the matrix is used as a coefficient matrix.
Scan columns from left to right. Swap a nonzero entry from the remaining rows into the next pivot position; skip columns where none exists. Clear below the pivot by row additions, then move down. For RREF, normalize pivots and clear above them from bottom to top.
Proposition 1.3. Elimination terminates
Gaussian elimination produces an echelon form; Gauss–Jordan elimination produces an RREF. For square matrices, either uses \(O(n^3)\) field operations. Back-substitution takes \(O(n^2)\).
Proof.
Each pivot moves down and right, so there are at most \(n\). Later operations preserve earlier pivot-column zeros. The reverse sweep clears above the pivots while retaining those zeros.
At each pivot, \(O(n)\) rows receive \(O(n)\) entry updates, including an appended vector or identity block. At most \(n\) pivots give \(O(n^3)\) arithmetic operations. Back-substitution handles \(n\) equations with at most \(n\) entries each.
□2. Three worked examples
These numerical examples use \(\mathbb R\).
Example 2.1. Testing invertibility
Take \(A=\begin{bmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{bmatrix}\). Subtract \(2\times\)row 1 from row 2 and \(4\times\)row 1 from row 3, then \(3\times\)row 2 from row 3:
\[ \begin{bmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{bmatrix} \longrightarrow \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 3 & 5 \end{bmatrix} \longrightarrow \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{bmatrix}. \]There is a pivot in every column, so \(A\) is invertible. For a square matrix, this is equivalent to its RREF being \(I_n\), as proved in Theorem 3.5.
Example 2.2. Computing the inverse
Append \(I_3\) to \(A\) and perform the same row operations on both blocks:
\[ \left[\begin{array}{ccc|ccc} 2 & 1 & 1 & 1 & 0 & 0 \\ 4 & 3 & 3 & 0 & 1 & 0 \\ 8 & 7 & 9 & 0 & 0 & 1 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|ccc} 2 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & -2 & 1 & 0 \\ 0 & 0 & 2 & 2 & -3 & 1 \end{array}\right]. \]For Gauss–Jordan elimination, scale rows 1 and 3 by \(\tfrac12\), clear column 3 using \(R_2\leftarrow R_2-R_3\) and \(R_1\leftarrow R_1-\tfrac12R_3\), then clear column 2 using \(R_1\leftarrow R_1-\tfrac12R_2\):
\[ \left[\begin{array}{ccc|ccc} 2 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & -2 & 1 & 0 \\ 0 & 0 & 2 & 2 & -3 & 1 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|ccc} 1 & 0 & 0 & \tfrac32 & -\tfrac12 & 0 \\ 0 & 1 & 0 & -3 & \tfrac52 & -\tfrac12 \\ 0 & 0 & 1 & 1 & -\tfrac32 & \tfrac12 \end{array}\right]. \]The right block is \(A^{-1}\):
\[ A^{-1} = \begin{bmatrix} \tfrac32 & -\tfrac12 & 0 \\ -3 & \tfrac52 & -\tfrac12 \\ 1 & -\tfrac32 & \tfrac12 \end{bmatrix} \]The right block records the operations applied to the identity; Corollary 3.6 proves why it becomes the inverse.
Example 2.3. Solving a system by back-substitution
For \(x_1+2x_2-x_3=2\), \(2x_1+3x_2+x_3=11\), and \(x_1-x_2+2x_3=5\), append the right-hand side and use \(R_2\leftarrow R_2-2R_1\), \(R_3\leftarrow R_3-R_1\), then \(R_3\leftarrow R_3-3R_2\):
\[ \left[\begin{array}{ccc|c} 1 & 2 & -1 & 2 \\ 2 & 3 & 1 & 11 \\ 1 & -1 & 2 & 5 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|c} 1 & 2 & -1 & 2 \\ 0 & -1 & 3 & 7 \\ 0 & 0 & -6 & -18 \end{array}\right]. \]Solve from the bottom up by back-substitution:
\[ -6x_3 = -18 \implies x_3 = 3, \qquad -x_2 + 9 = 7 \implies x_2 = 2, \qquad x_1 + 4 - 3 = 2 \implies x_1 = 1. \]Thus \(x=(1,2,3)\), and substitution gives \(Ax=(2,11,5)\). No inverse was needed.
These calculations do not require determinants. Their connection to elimination is developed in A proper introduction to determinants.
3. Why the row operations are safe
Left multiplication combines rows. If a matrix \(B\) has rows \(R_1,\dots,R_n\), then
\[\text{row}_i(EB)=\sum_{j=1}^n E_{ij}R_j.\]Row \(i\) of \(E\) gives the coefficients of this linear combination. Each elementary matrix selects the row operation we want.
Definition 3.1. Elementary matrices
An elementary matrix is obtained by applying one elementary row operation to \(I_n\). Writing \(e_i\) for the standard column vectors, its three types are:
- \(S_{ij}\): exchange rows \(i,j\) of \(I_n\).
- \(D_i(c)\): replace diagonal entry \(i\) of \(I_n\) by \(c\neq0\).
- \(T_{ij}(c)=I_n+ce_ie_j^{\mathsf T}\), for \(i\neq j\).
Proposition 3.2. Row operations are left multiplication
Multiplication by \(S_{ij}\) swaps rows, by \(D_i(c)\) scales row \(i\), and by \(T_{ij}(c)\) replaces row \(i\) by \(R_i+cR_j\). This applies to every column of an augmented matrix as well.
Proof.
The modified rows of \(S_{ij}\) select \(R_j,R_i\); of \(D_i(c)\), \(cR_i\); and of \(T_{ij}(c)\), \(R_i+cR_j\). Unmodified identity rows select the original rows.
□Lemma 3.3. Elementary matrices are invertible
Proof.
Swap twice, scale by \(c\) then \(c^{-1}\), or add \(cR_j\) then subtract it. These inverse row operations restore every row, so their matrices multiply to \(I_n\) in either order.
□Corollary 3.4. A whole reduction is one invertible multiplication
If successive operations have matrices \(E_1,\dots,E_k\), then their combined effect is
\[B\longmapsto EB,\qquad E=E_k\cdots E_1,\]and \(E\) is invertible.
Proof.
The formula follows by successive left multiplication. A product of invertible matrices is invertible, with \(E^{-1}=E_1^{-1}\cdots E_k^{-1}\).
□Theorem 3.5. The pivot criterion for invertibility
For \(A\in M_n(\mathbb K)\), the following are equivalent: \(A\) is invertible; its echelon form has a pivot in every column; and its RREF is \(I_n\).
Proof.
Let \(Q=EA\) be its RREF. If every column has a pivot, echelon order places them on the diagonal, and the reduced conditions force \(Q=I_n\). Then \(A=E^{-1}\) is invertible.
If a column has no pivot, set that free variable to \(1\) and the other free variables to \(0\); the pivot equations determine the remaining coordinates of a nonzero vector \(x\) with \(Qx=0\). Since \(E\) is invertible, \(Ax=0\) too, so \(A\) cannot have an inverse.
□Corollary 3.6. The augmented inverse algorithm
If \(A\) is invertible, row reduction gives
\[[A\mid I_n]\longrightarrow[I_n\mid A^{-1}].\]If the left block cannot be reduced to \(I_n\), \(A\) is singular, meaning it is not invertible.
Proof.
The combined operation sends the blocks to \([EA\mid E]\). If \(EA=I_n\), then \(A=E^{-1}\) and \(E=A^{-1}\). The pivot criterion determines whether this can happen.
□4. Solutions and the null space
Definition 4.1. Augmented systems and null space
The augmented matrix \([A\mid b]\) records the coefficients and right-hand side of \(Ax=b\). The system is consistent if a solution exists. The null space is
\[N(A)=\{x\in\mathbb K^n:Ax=0\}.\]It is a subspace: if \(Au=Av=0\), then \(A(ru+sv)=0\) for any scalars \(r,s\).
Proposition 4.2. Reduction preserves all solutions
Row reduction of \([A\mid b]\) to \([Q\mid d]\), with \(Q=EA\) and \(d=Eb\), preserves the solution set:
\[Ax=b\iff Qx=d.\]In particular, \(N(A)=N(Q)\).
Proof.
Multiplying \(Ax=b\) by \(E\) gives \(EAx=Eb\). Multiplying the latter by \(E^{-1}\) gives the reverse implication. This argument does not require \(A\) to be invertible.
□The null space measures what the matrix loses: \(Ax=Ay\) exactly when \(x-y\in N(A)\). Moving along a null-space direction changes the input without changing the output.
Theorem 4.3. One solution plus the null space
If \(Ax_p=b\), every solution is of the form
\[x=x_p+z,\qquad z\in N(A).\]Proof.
\[ \begin{aligned} Ax=b &\iff A(x-x_p)=0\\ &\iff x-x_p\in N(A). \end{aligned} \] □Proposition 4.4. Consistency and free variables
In \([Q\mid d]\) with \(Q\) in RREF, a zero row of \(Q\) paired with \(d_i\neq0\) makes the system inconsistent. Otherwise the system is consistent: choose values for the nonpivot variables and solve for the pivot variables.
If there are \(r\) pivots, a consistent system has \(n-r\) independent free parameters. Over an infinite field this gives infinitely many solutions when \(r<n\); over a finite field with \(q\) elements it gives \(q^{n-r}\) solutions.
Proof.
A contradictory row reads \(0=d_i\). Without such a row, each nonzero row has its own pivot variable, and every other entry in that pivot column is zero. Thus any assignment to the free variables determines exactly one assignment to the pivot variables. There are \(n-r\) free variables, giving the stated count over a finite field.
□Example 4.5. A singular matrix can give a family or no solution
Over \(\mathbb R\), let \(B=\begin{bmatrix}1&2\\2&4\end{bmatrix}\). Subtract twice the first row from the second:
\[ \left[\begin{array}{cc|c}1&2&3\\2&4&6\end{array}\right] \longrightarrow \left[\begin{array}{cc|c}1&2&3\\0&0&0\end{array}\right]. \]The solutions are \((3-2t,t)=(3,0)+t(-2,1)\), with \(t\in\mathbb R\). The direction \((-2,1)\) spans \(N(B)\). Replacing the right-hand side by \((3,7)\) instead gives a final row \([0\ 0\mid1]\), so there is no solution.
5. Rank–nullity (optional)
The dimension argument explains the free parameters. For the linear map \(T(x)=Ax\), the kernel contains directions sent to zero; the image contains the reachable outputs.
Matrices and linear maps
A matrix represents a linear map after bases have been chosen. Its \(j\)-th column contains the coordinates of \(T(v_j)\), where \(v_j\) is the \(j\)-th domain basis vector. In standard coordinates, \(T(e_j)\) is exactly column \(j\) of \(A\).
The vectors need not be numerical columns: they could be polynomials, matrices, or functions in a finite-dimensional space. A basis turns their coordinates, and the action of a linear map, into matrix calculations.
Definition 5.1. Rank and nullity
For a linear map \(T:V\to W\) with \(V\) finite-dimensional,
\[\ker T=\{v:T(v)=0\},\qquad\operatorname{im}T=\{T(v):v\in V\},\] \[\operatorname{nullity}T=\dim\ker T,\qquad\operatorname{rank}T=\dim\operatorname{im}T.\]For \(T(x)=Ax\), the image is the span of the columns of \(A\), so matrix rank is the dimension of this column space.
Alphabeta Math: kernel and image · rank and nullity · matrix rank
Theorem 5.2. Rank–nullity
For a linear map \(T:V\to W\) with \(V\) finite-dimensional,
\[\dim V=\dim\ker T+\dim\operatorname{im}T.\]Proof.
Choose a basis \(u_1,\dots,u_k\) of \(\ker T\) and extend it to a basis \(u_1,\dots,u_k,w_1,\dots,w_m\) of \(V\). The vectors \(Tw_1,\dots,Tw_m\) span the image: applying \(T\) to a basis expansion kills the \(u_i\) terms.
They are independent too. If \(\sum_j c_jTw_j=0\), then \(\sum_j c_jw_j\in\ker T\), so it is a combination of the \(u_i\). Independence of the extended basis forces all \(c_j=0\). Thus \(\dim\operatorname{im}T=m\), and \(\dim V=k+m\).
□Corollary 5.3. Rank, pivots, and uniqueness
For \(A\in M_n(\mathbb K)\),
\[\operatorname{rank}A+\dim N(A)=n.\]Rank equals the pivot count. A consistent system therefore has \(n-\operatorname{rank}A\) free parameters. The following are equivalent: \(A\) is invertible, \(N(A)=\{0\}\), and \(Ax=b\) has exactly one solution for every \(b\).
Alphabeta Math: matrix rank–nullity · pivot count · invertibility
Proof.
Apply rank–nullity to \(T(x)=Ax\). Solving \(Qx=0\) in RREF gives one independent null-space vector for each nonpivot variable, so \(\dim N(A)=n-r\), where \(r\) is the pivot count. Hence \(\operatorname{rank}A=r\). The equivalences follow from the pivot criterion and the solution-set formula.
□Each missing pivot leaves one input direction undetermined. Consistent systems have solution families precisely along these lost directions.
There is also a quotient interpretation: the map \(v+\ker T\mapsto T(v)\) is a well-defined linear isomorphism \(V/\ker T\cong\operatorname{im}T\). It is well defined because changing \(v\) by a kernel vector leaves \(T(v)\) unchanged, injective because equal outputs differ by a kernel vector, and surjective by the definition of the image.
Sources and further reading
Alphabeta Math collects the cited items in Gaussian Elimination and Row Reduction and Linear Maps, Rank–Nullity and Quotient Spaces.
Comments