Gaussian and Gauss-Jordan elimination explained

Row echelon form, reduced row echelon form, pivots and the three elementary row operations, worked through on a concrete matrix.

Elimination is the single most useful algorithm in linear algebra. Rank, determinant, inverse and the solution of a linear system all fall out of it. It rests on three elementary row operations, none of which changes the solution set of the underlying system:

1. Swap two rows: R(i) ↔ R(j)
2. Multiply a row by a non-zero scalar: R(i) → k·R(i)
3. Add a multiple of one row to another: R(i) → R(i) + k·R(j)

Row echelon form

A matrix is in row echelon form (REF) when:

• all-zero rows sit at the bottom;
• each leading non-zero entry (the pivot) is strictly to the right of the pivot above it;
• everything below a pivot is zero.

Reduced row echelon form

RREF goes further: every pivot equals 1 and is the only non-zero entry in its column. Crucially, every matrix has exactly one RREF — the answer does not depend on the order you did the operations in.

The algorithm, step by step

1. Start at the top-left. Find the largest entry in the current column — this is partial pivoting, and it keeps rounding errors small.
2. If the whole column is zero, move one column right and try again.
3. Swap that row up into pivot position.
4. Divide the pivot row by the pivot so the pivot becomes 1.
5. Subtract multiples of the pivot row from every other row to zero out the rest of the column.
6. Move down one row and right one column, and repeat.

Stopping after step 5 only for rows below the pivot gives Gaussian elimination (REF). Clearing the rows above as well gives Gauss-Jordan (RREF).

Reading off the solutions

• Unique solution: every column of the coefficient matrix has a pivot.
• Infinitely many: some column has no pivot — those variables are free.
• No solution: a row reads 0 0 0 | c with c ≠ 0, which claims 0 = c.