Gaussian elimination transforms a linear system into a simpler equivalent form by systematically applying row operations. Forward elimination creates zeros below each pivot, producing row echelon form. Back substitution then solves from the bottom up. The algorithm handles every case — unique solutions, infinitely many solutions, and inconsistent systems — within a single unified framework.
The Goal
The input is an augmented matrix [A∣b] representing a linear system Ax=b. The output is an equivalent system — one with exactly the same solution set — in a form simple enough that the solution can be read off directly or obtained with minimal effort.
The "simple form" is echelon form: a staircase pattern where the leading entry of each row is to the right of the leading entry of the row above, and everything below each leading entry is zero. Once the augmented matrix is in echelon form, the solution is extracted by back substitution — solving from the last equation upward.
Optionally, the reduction can continue to reduced row echelon form (RREF), where each leading entry is 1 and is the only nonzero entry in its column. In RREF, the solution is visible by inspection.
The Three Elementary Row Operations
Gaussian elimination uses three operations, each of which transforms the augmented matrix without changing the solution set.
Row swap (Ri↔Rj): interchange two rows. This reorders the equations — a cosmetic change that is sometimes necessary to place a nonzero entry in the pivot position.
Row scaling (kRi→Ri, k=0): multiply every entry in a row by a nonzero scalar. This rescales one equation. Multiplying by zero is forbidden because it would destroy information.
Row addition (Ri+cRj→Ri): add c times row j to row i, replacing row i with the result. This is the operation that actually eliminates entries — by choosing c appropriately, a targeted entry becomes zero.
Each operation is reversible: swapping the same pair undoes the swap, scaling by 1/k undoes scaling by k, and subtracting c times row j from row i undoes the addition. Reversibility guarantees that no solutions are created or lost. Each operation also corresponds to left-multiplication by an elementary matrix, connecting the algorithm to the theory of matrix factorization.
Forward Elimination
Forward elimination is the first phase of the algorithm. It sweeps through the augmented matrix from left to right, top to bottom, creating zeros below each pivot.
Start with the leftmost column that contains a nonzero entry. Identify a nonzero entry in that column to serve as the pivot — if the entry in the current top row is zero, swap that row with a row below that has a nonzero entry in this column. Then use row addition to eliminate every entry below the pivot: for each row i below the pivot row, add −apjaij times the pivot row to row i, zeroing out the (i,j) entry.
Move one column to the right and one row down, and repeat the process on the submatrix below and to the right of the current pivot. Continue until no rows or columns remain to process.
The result is a matrix in row echelon form: a staircase of pivots descending from upper-left to lower-right, with zeros filling in below and to the left of each pivot. Any rows that are entirely zero sit at the bottom.
Pivots and Pivot Positions
A pivot is the leading (leftmost) nonzero entry in each row of the echelon form. The column containing a pivot is a pivot column; every other column is a free column.
The number of pivots equals the rank of the coefficient matrix. Pivot columns correspond to determined variables (pivot variables) whose values are fixed once the free variables are assigned. Free columns correspond to free variables (parameters) that can take any real value.
If every column of A is a pivot column, the system has no free variables and the solution (if it exists) is unique. If at least one column is free, the solution set (if nonempty) is infinite, parametrized by the free variables. The distinction between pivot and free columns is the structural core of the algorithm — it determines both the form and the dimension of the solution set.
Back Substitution
Once the augmented matrix is in row echelon form, the solution is obtained by solving from the bottom row upward.
The last nonzero row contains the fewest unknowns — typically one pivot variable in terms of free variables and a constant. Solve for that pivot variable. Substitute the result into the row above, which now also becomes solvable for its pivot variable. Continue upward until every pivot variable is expressed in terms of the free variables and the constants from b.
Worked Example
200−1403−259610
The bottom row gives 5x3=10, so x3=2. The middle row gives 4x2−2(2)=6, so 4x2=10 and x2=5/2. The top row gives 2x1−5/2+3(2)=9, so 2x1=9+5/2−6=11/2 and x1=11/4.
Each step required only previously solved variables. The process terminates in n steps, with the solution fully determined.
Gauss-Jordan Elimination
Gauss-Jordan elimination extends the forward pass with a backward pass that creates zeros above each pivot as well, and scales each pivot to 1. The result is reduced row echelon form (RREF), where every pivot variable is already isolated in its row.
After forward elimination produces REF, continue by working from the bottom pivot upward. For each pivot, add appropriate multiples of its row to the rows above to eliminate all entries above the pivot. Then scale the pivot row so the pivot entry becomes 1.
The payoff is that in RREF, the solution is visible by direct inspection — no back substitution is needed. Each pivot row reads "xi=(expression in free variables and constants)." The trade-off is that the backward pass requires additional row operations, roughly doubling the total work compared to forward elimination alone.
For hand computation, the choice between back substitution (stop at REF) and Gauss-Jordan (continue to RREF) is a matter of preference. For computer implementations, both approaches are standard.
Worked Example: Unique Solution
Solve the system
x1+2x2−x3=3,2x1+5x2+x3=8,3x1+8x2+2x3=13
Form the augmented matrix and apply forward elimination:
Three pivots in three columns — unique solution. Back substitution: row 3 gives −x3=0, so x3=0. Row 2 gives x2+3(0)=2, so x2=2. Row 1 gives x1+2(2)−0=3, so x1=−1.
Verification: −1+4−0=3, −2+10+0=8, −3+16+0=13. All three equations are satisfied.
Worked Example: Infinitely Many Solutions
Solve the system
x1−x2+2x3+x4=3,2x1−2x2+5x3+4x4=8
Two equations in four unknowns — more unknowns than equations, so the solution (if it exists) cannot be unique. Form and reduce:
(12−1−2251438)R2−2R1(10−10211232)
Pivots in columns 1 and 3. Columns 2 and 4 are free. Let x2=s and x4=t. Row 2 gives x3=2−2t. Row 1 gives x1=3+s−2(2−2t)−t=−1+s+3t.
The general solution in parametric vector form:
x=−1020+s1100+t30−21
The solution set is a two-dimensional plane in R4, passing through (−1,0,2,0) and spanned by two direction vectors.
Worked Example: No Solution
Solve the system
x1+x2=2,2x1+2x2=3
Form and reduce:
(121223)R2−2R1(10102−1)
The second row reads 0x1+0x2=−1, which is the equation 0=−1. This is a contradiction — no values of x1 and x2 can satisfy it.
The system is inconsistent. Geometrically, the two equations represent parallel lines in R2: x1+x2=2 and x1+x2=3/2 (the second equation, after dividing by 2). Parallel lines with different intercepts never intersect.
Inconsistency is always detectable in echelon form: a row [00⋯0∣d] with d=0 means rank([A∣b])>rank(A), and by the Rouché-Capelli theorem, no solution exists.
Computational Cost
Forward elimination on an n×n system requires roughly 32n3 arithmetic operations (multiplications and additions). The cost comes from the nested loop structure: for each of the n pivot columns, elimination involves O(n) rows, each requiring O(n) operations.
Back substitution requires roughly n2 operations — a negligible addition compared to forward elimination. Gauss-Jordan elimination (continuing to RREF) raises the total to roughly n3, because the backward pass does comparable work to the forward pass.
These costs are dramatically better than the alternatives for large systems. Cramer's rule requires n+1determinant evaluations, each costing O(n3) via row reduction or O(n!) via cofactor expansion — orders of magnitude slower. Computing the inverse explicitly costs roughly 2n3 operations. Gaussian elimination is the standard baseline against which all other direct methods are measured.
Partial Pivoting
In exact arithmetic, any nonzero entry can serve as a pivot. In floating-point arithmetic, the choice matters. A very small pivot amplifies rounding errors — dividing by a number close to zero magnifies any imprecision in the numerator.
Partial pivoting addresses this by modifying the pivot selection step. At each stage, instead of using whatever nonzero entry happens to sit in the pivot position, the algorithm scans the entries below (and including) the current position in the pivot column and swaps the row with the largest absolute value into the pivot position. This keeps the multipliers −aij/apj small, which limits the accumulation of rounding error.
Partial pivoting does not change the mathematical structure of Gaussian elimination — it only changes which row swaps are performed. The echelon form, the rank, the pivots, and the solution are all the same in exact arithmetic. The difference is entirely numerical: partial pivoting makes the computation stable.
Every serious numerical implementation of Gaussian elimination uses partial pivoting by default. In the LU decomposition, the row swaps are recorded in a permutation matrix P, giving the factorization PA=LU.