Gauss-Jordan elimination is a constructive method for solving linear systems, classifying their solution sets, computing matrix rank, and building matrix inverses. The method acts on an augmented matrix and uses row operations that preserve solution equivalence.
Model: Linear Systems as Augmented Matrices
A linear system with unknown vector \(x\in\mathbb{F}^n\) has the form
\[ Ax=b, \qquad A\in\mathbb{F}^{m\times n},\ b\in\mathbb{F}^m. \]
We represent it as the augmented matrix
\[ [A\mid b]. \]
Row operations transform \([A\mid b]\) into an equivalent system with the same solution set.
Elementary Row Operations
Over a field \(\mathbb{F}\), the allowed operations are:
- \(R_i\leftrightarrow R_j\): swap two rows.
- \(R_i\leftarrow \alpha R_i\) with \(\alpha\ne 0\): scale one row.
- \(R_i\leftarrow R_i+\alpha R_j\): add a multiple of another row.
Each operation is invertible, so it preserves equivalence of linear systems.
REF and RREF
Two canonical shapes are central:
- Row echelon form (REF): pivots move strictly to the right when going down, and all zero rows are at the bottom.
- Reduced row echelon form (RREF): REF plus each pivot equals 1 and is the only nonzero entry in its column.
For every matrix, the RREF is unique. This uniqueness gives a canonical algebraic description of all solutions.
Pivots, Rank, and Degrees of Freedom
In RREF, pivot columns correspond to basic variables. Non-pivot columns correspond to free variables. If \(r\) is the number of pivots, then
\[ \operatorname{rank}(A)=r, \qquad \dim\ker(A)=n-r. \]
So rank controls both consistency structure and the number of free parameters.
Gauss vs. Gauss-Jordan
Gaussian elimination usually stops at REF and then uses back-substitution. Gauss-Jordan continues to RREF by also clearing entries above pivots. This extra work removes back-substitution and exposes the solution directly.
Algorithm (Practical Form)
Input: [A|b] with m rows, n variable columns
pivotRow = 0
for col = 0 .. n-1:
choose a row r >= pivotRow with nonzero entry in column col
if no such row exists:
continue
swap row r with row pivotRow
scale pivotRow so pivot entry becomes 1
for each row i != pivotRow:
row i <- row i - (entry in col of row i) * pivotRow
pivotRow = pivotRow + 1
Output: RREF([A|b]) In floating-point arithmetic, one uses partial pivoting (choose largest absolute pivot candidate in the current column) to reduce numerical error.
Worked Example: Unique Solution
Solve
\[ \begin{aligned} x+y+z&=6,\\ 2x-y+z&=3,\\ x+2y-z&=3. \end{aligned} \]
Start with
\[ \left[\begin{array}{ccc|c} 1&1&1&6\\ 2&-1&1&3\\ 1&2&-1&3 \end{array}\right]. \]
\[ \begin{aligned} R_2&\leftarrow R_2-2R_1,\\ R_3&\leftarrow R_3-R_1 \end{aligned} \Rightarrow \left[\begin{array}{ccc|c} 1&1&1&6\\ 0&-3&-1&-9\\ 0&1&-2&-3 \end{array}\right]. \]
\[ R_2\leftrightarrow R_3 \Rightarrow \left[\begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-3\\ 0&-3&-1&-9 \end{array}\right]. \]
\[ R_3\leftarrow R_3+3R_2 \Rightarrow \left[\begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-3\\ 0&0&-7&-18 \end{array}\right]. \]
\[ R_3\leftarrow -\tfrac{1}{7}R_3 \Rightarrow \left[\begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-3\\ 0&0&1&\tfrac{18}{7} \end{array}\right]. \]
Clear above pivot 3:
\[ \begin{aligned} R_1&\leftarrow R_1-R_3,\\ R_2&\leftarrow R_2+2R_3 \end{aligned} \Rightarrow \left[\begin{array}{ccc|c} 1&1&0&\tfrac{24}{7}\\ 0&1&0&\tfrac{15}{7}\\ 0&0&1&\tfrac{18}{7} \end{array}\right]. \]
Clear above pivot 2:
\[ R_1\leftarrow R_1-R_2 \Rightarrow \left[\begin{array}{ccc|c} 1&0&0&\tfrac{9}{7}\\ 0&1&0&\tfrac{15}{7}\\ 0&0&1&\tfrac{18}{7} \end{array}\right]. \]
Hence the unique solution is \(x=\tfrac{9}{7},\ y=\tfrac{15}{7},\ z=\tfrac{18}{7}\).
Classification of Solution Sets
Let \(r=\operatorname{rank}(A)\) and \(r' = \operatorname{rank}([A\mid b])\). Then:
- \(r<r'\): inconsistent, no solution.
- \(r=r'=n\): unique solution.
- \(r=r'<n\): infinitely many solutions with \(n-r\) free variables.
This is the rank criterion (Rouche-Capelli theorem).
Inconsistent Pattern in RREF
A row of the form \([0\ \cdots\ 0\mid c]\) with \(c\ne 0\) represents \(0=c\), so the system is inconsistent.
Underdetermined Pattern in RREF
Missing pivots in variable columns create free parameters. The solution set is an affine subspace.
Computing an Inverse with Gauss-Jordan
For a square matrix \(A\in\mathbb{F}^{n\times n}\), augment with identity:
\[ [A\mid I_n]. \]
If elimination yields \([I_n\mid B]\), then \(B=A^{-1}\). If a pivot fails in the left block, \(A\) is singular and has no inverse. The matrix inverse chapter gives additional geometric and numerical context: matrix inverse.
Determinant and Operation Accounting
During elimination, determinant updates are:
- Row swap: multiplies determinant by \(-1\).
- Row scaling by \(\alpha\): multiplies determinant by \(\alpha\).
- Row replacement \(R_i\leftarrow R_i+\alpha R_j\): determinant unchanged.
So elimination also provides a systematic determinant computation when these factors are tracked.
Numerical Perspective
Exact symbolic arithmetic and floating-point arithmetic behave differently. In floating-point settings, pivoting is essential. Near-zero pivots can amplify roundoff error and produce unstable results.
For large systems, factorization-based solvers (for example LU with pivoting) are usually preferred over full Gauss-Jordan reduction, while Gauss-Jordan remains ideal for teaching, structural analysis, and exact small-to-medium systems.
Key Takeaways
- Gauss-Jordan transforms \([A\mid b]\) to RREF using invertible row operations.
- RREF gives direct access to consistency, rank, pivots, and free variables.
- The rank criterion classifies systems into none, unique, or infinitely many solutions.
- The same method computes inverses through \([A\mid I]\to[I\mid A^{-1}]\).