Gauss–Jordan Elimination

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 $1$ .

Result: each pivot is $1$ , 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 $𝐴 \vec{𝑥} = \vec{𝑏}$ can be read directly off the right-hand side of the augmented matrix $[𝐴 | \vec{𝑏}]$ — no back substitution needed.

Also useful for:

Computing the inverse: row-reduce $[𝐴 | 𝐼]$ to $[𝐼 | 𝐴^{- 1}]$
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:

[\begin{matrix} 1 & 2 & 5 \\ 3 & 7 & 16 \end{matrix}]

Forward: $𝑅_{2} \to 𝑅_{2} - 3 𝑅_{1}$ gives

[\begin{matrix} 1 & 2 & 5 \\ 0 & 1 & 1 \end{matrix}]

Backward: $𝑅_{1} \to 𝑅_{1} - 2 𝑅_{2}$ gives

[\begin{matrix} 1 & 0 & 3 \\ 0 & 1 & 1 \end{matrix}]

Read the solution off: $𝑥_{1} = 3, 𝑥_{2} = 1$ .

51.3. Inverse via Gauss–Jordan

To compute $𝐴^{- 1}$ for an $𝑛 \times 𝑛$ invertible matrix, form $[𝐴 | 𝐼_{𝑛}]$ and row-reduce until the left half is the identity:

[𝐴 | 𝐼_{𝑛}] ⟶ [𝐼_{𝑛} | 𝐴^{- 1}]

Example

$𝐴 = [\begin{matrix} 2 & 1 \\ 5 & 3 \end{matrix}]$ . Augment with $𝐼_{2}$ :

[\begin{matrix} 2 & 1 & 1 & 0 \\ 5 & 3 & 0 & 1 \end{matrix}]

Row-reduce to $[𝐼 | 𝐴^{- 1}]$ :

[\begin{matrix} 1 & 0 & 3 & - 1 \\ 0 & 1 & - 5 & 2 \end{matrix}]

𝐴^{- 1} = [\begin{matrix} 3 & - 1 \\ - 5 & 2 \end{matrix}]

51.4. Cost

Gauss–Jordan is $𝑂 (𝑛^{3})$ — 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