51. Gauss–Jordan Elimination
An extension of Gaussian elimination that takes the matrix all the way to Reduced Row Echelon Form (RREF) — not just to upper-triangular REF.
51.1. Two phases
- Forward elimination (same as Gaussian elimination): pivot to get zeros below each pivot, achieve REF (upper-triangular form).
- Back-substitution turned into elimination: pivot upward to also clear above each pivot, and scale each pivot row so the pivot equals .
Result: each pivot is , with all-zero columns above and below it — the canonical RREF.
51.2. Why bother going past REF?
After full Gauss–Jordan, the solution to can be read directly off the right-hand side of the augmented matrix — no back substitution needed.
Also useful for:
- Computing the inverse: row-reduce to
- Finding a basis for the null space
- Reading off rank (number of pivots) and linearly independent columns (the pivot columns)
Example
Apply Gauss–Jordan to:
Forward: gives
Backward: gives
Read the solution off: .
51.3. Inverse via Gauss–Jordan
To compute for an invertible matrix, form and row-reduce until the left half is the identity:
Example
. Augment with :
Row-reduce to :
51.4. Cost
Gauss–Jordan is — same asymptotic complexity as Gaussian elimination + back substitution, but with a slightly larger constant. For solving a single system, plain Gaussian elimination with back-substitution is marginally faster; for the inverse or RREF directly, Gauss–Jordan is the natural choice.
51.5. See also
- Gaussian Elimination — the forward phase only
- REF / RREF
- Matrix Inverse