Gaussian and Gauss-Jordan elimination

You know a system Ax=bA\mathbf x=\mathbf b is consistent from rank and the Rouché–Capelli criterion — now you need the actual solution. Gauss elimination and Gauss–Jordan elimination are the two standard hand algorithms for that job, both built from the same elementary row operations on the augmented matrix [A ∣ b][A\,|\,\mathbf b], differing only in how far the reduction goes. Gauss elimination stops at upper-triangular form and finishes with back substitution; Gauss–Jordan pushes all the way to the identity matrix and reads the answer straight off. This article works both methods on the same 3×33\times3 system side by side, so you can see exactly where they diverge and why Gauss–Jordan costs more arithmetic. It sits directly after row operations and rank in the "Matrices, systems, and numerical linear algebra" sub-chapter, and feeds into Gauss–Seidel iteration next — the iterative alternative to these two direct methods.

The core insight

Row-reduce [A ∣ b][A\,|\,\mathbf b] to upper-triangular form and back-substitute (Gauss), or keep reducing to [I ∣ x][I\,|\,\mathbf x] and read the answer off directly (Gauss–Jordan) — both direct methods solving the same Ax=bA\mathbf x=\mathbf b.

The core idea

Both algorithms operate on the augmented matrix [A ∣ b][A\,|\,\mathbf b] using the three elementary row operations (swap two rows, scale a row by a nonzero constant, add a multiple of one row to another). They agree completely through forward elimination and part company after.

Gauss elimination has two phases. Forward elimination zeroes every entry below the diagonal, leaving

(u11u12⋯u1n0u22⋯u2n⋮⋱⋮00⋯unn)(x1x2⋮xn)=(c1c2⋮cn),\begin{pmatrix}u_{11}&u_{12}&\cdots&u_{1n}\\0&u_{22}&\cdots&u_{2n}\\ \vdots&&\ddots&\vdots\\0&0&\cdots&u_{nn}\end{pmatrix}\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}c_1\\c_2\\\vdots\\c_n\end{pmatrix},

where: uiju_{ij} are the reduced coefficients, cic_i the reduced right-hand side, and nn the number of unknowns. Back substitution then solves from the bottom up: xn=cn/unnx_n=c_n/u_{nn}, then xn−1x_{n-1} from row n−1n-1 using the now-known xnx_n, and so on to x1x_1.

Gauss–Jordan elimination continues past upper-triangular form: it also eliminates the entries above each pivot and scales every pivot to 11, turning the coefficient block into the identity,

[A ∣ b] →row ops [I ∣ x].[A\,|\,\mathbf b]\ \xrightarrow{\text{row ops}}\ [I\,|\,\mathbf x].

where: the right-hand column of the fully reduced augmented matrix is the solution vector x\mathbf x — no separate back-substitution pass is needed, at the cost of roughly 50%50\% more arithmetic than plain Gauss elimination. A practical refinement for both algorithms is partial pivoting: before eliminating a column, swap rows so the largest-magnitude available entry becomes the pivot. This avoids division by an exact zero and, for decimal computation, curbs round-off growth from dividing by a tiny pivot — dividing by a very small number amplifies whatever error already sits in that row, and every later row inherits it. For the exact-fraction examples typical of this course, pivoting mainly guards against a zero pivot, but defaulting to it is good habit even when no pivot is exactly zero, since a small-but-nonzero pivot produces awkward fractions that are far more error-prone by hand than a larger pivot swapped in from a row below. Operation counts: Gauss elimination is O(n3)O(n^3) for forward elimination and O(n2)O(n^2) for back substitution, so for large nn forward elimination dominates the cost; Gauss–Jordan's extra above-pivot elimination is also O(n3)O(n^3) but with a larger constant — the precise sense in which it does "more work," even though both scale the same way with system size. Both methods are direct methods: barring rounding error, they produce the exact solution in a finite, predictable number of steps, unlike an iterative method that only converges toward the answer over repeated passes. That distinction matters for the next article in this sub-chapter, Gauss–Seidel iteration, which solves the same Ax=bA\mathbf x=\mathbf b by repeated approximation instead of a finite sequence of row operations, and is preferred for very large, sparse systems where a full elimination would be too costly.

Figure
Two augmented matrices side by side, Gauss stopping at upper triangular form with an arrow to back substitution, Gauss-Jordan continuing to the identity matrix with an arrow reading straight off
Same forward elimination, two different stopping points Gauss elimination u11 u12 u13 | c1 0 u22 u23 | c2 0 0 u33 | c3 back substitution x3, then x2, then x1 Gauss-Jordan elimination 1 0 0 | x1 0 1 0 | x2 0 0 1 | x3 read off directly no back substitution same forward elimination
Derivation AReducing a 3x3 system to identity form with Gauss-Jordan elimination

The goal is to show, step by step and with every row operation stated explicitly, how continuing Gauss elimination's upper-triangular result past the point where back substitution would normally begin — first scaling each pivot to 11, then clearing every entry above it, working from the bottom pivot up to the top — mechanically forces the coefficient block into the identity matrix II so the augmented column becomes the solution vector with no further computation.

Step 1. Start from the upper-triangular form already reached by forward elimination on 2x+y−z=8, −3x−y+2z=−11, −2x+y+2z=−32x+y-z=8,\ -3x-y+2z=-11,\ -2x+y+2z=-3:

[21−1800.50.5100−11].\left[\begin{array}{ccc|c}2&1&-1&8\\0&0.5&0.5&1\\0&0&-1&1\end{array}\right].

Gauss elimination would back-substitute from here; Gauss–Jordan instead keeps row-reducing.

Step 2. Scale each pivot to 11. R2→2R2R_2\to 2R_2 gives (0,1,1 ∣ 2)(0,1,1\,|\,2); R3→−R3R_3\to -R_3 gives (0,0,1 ∣ −1)(0,0,1\,|\,-1):

[21−180112001−1].\left[\begin{array}{ccc|c}2&1&-1&8\\0&1&1&2\\0&0&1&-1\end{array}\right].

Step 3. Eliminate above the bottom pivot using row 3. R2→R2−R3R_2\to R_2-R_3 gives (0,1,0 ∣ 3)(0,1,0\,|\,3); R1→R1+R3R_1\to R_1+R_3 gives (2,1,0 ∣ 7)(2,1,0\,|\,7):

[21070103001−1].\left[\begin{array}{ccc|c}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}\right].

Step 4. Eliminate above the row-2 pivot, then rescale row 1 to a leading 11. R1→R1−R2R_1\to R_1-R_2 gives (2,0,0 ∣ 4)(2,0,0\,|\,4); then R1→12R1R_1\to\tfrac12R_1 gives (1,0,0 ∣ 2)(1,0,0\,|\,2):

[10020103001−1].\left[\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}\right].

The left block is II, so the right column is read off directly: x=2, y=3, z=−1x=2,\ y=3,\ z=-1.

Worked example

Step 1. Solve 2x+y−z=8, −3x−y+2z=−11, −2x+y+2z=−32x+y-z=8,\ -3x-y+2z=-11,\ -2x+y+2z=-3 by Gauss elimination. Augmented matrix:

[21−18−3−12−11−212−3].\left[\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}\right].

Step 2. Forward eliminate below the pivot in column 1. R2→R2+32R1R_2\to R_2+\tfrac32R_1 gives (0, 0.5, 0.5 ∣ 1)(0,\,0.5,\,0.5\,|\,1); R3→R3+R1R_3\to R_3+R_1 gives (0, 2, 1 ∣ 5)(0,\,2,\,1\,|\,5):

[21−1800.50.510215].\left[\begin{array}{ccc|c}2&1&-1&8\\0&0.5&0.5&1\\0&2&1&5\end{array}\right].

Step 3. Eliminate below the pivot in column 2. R3→R3−4R2R_3\to R_3-4R_2 gives (0, 0, −1 ∣ 1)(0,\,0,\,-1\,|\,1):

[21−1800.50.5100−11].\left[\begin{array}{ccc|c}2&1&-1&8\\0&0.5&0.5&1\\0&0&-1&1\end{array}\right].

This is upper-triangular, so forward elimination is done.

Step 4. Back-substitute. Row 3: −z=1⇒z=−1-z=1\Rightarrow z=-1. Row 2: 0.5y+0.5(−1)=1⇒y=30.5y+0.5(-1)=1\Rightarrow y=3. Row 1: 2x+3−(−1)=8⇒x=22x+3-(-1)=8\Rightarrow x=2. Solution: (x,y,z)=(2,3,−1)(x,y,z)=(2,3,-1).

Step 5. Check in equation 2: −3(2)−3+2(−1)=−6−3−2=−11-3(2)-3+2(-1)=-6-3-2=-11, matching the given right-hand side.

Competitive stretch

The same matrix, pushed on to Gauss–Jordan (worked in full in the derivation above), gives [I ∣ x][I\,|\,\mathbf x] with x=2, y=3, z=−1x=2,\ y=3,\ z=-1 — identical to the Gauss-elimination answer, exactly as it must be, since both algorithms solve the same consistent, unique-solution system.

Common traps

  • Forgetting to check for a zero pivot during forward elimination — swap in a nonzero entry from a row below (partial pivoting) before continuing, or the elimination formulas break down.
  • Applying a row operation to the coefficient columns but forgetting the augmented b\mathbf b column — a common source of a "close but wrong" final answer.
  • Stopping Gauss–Jordan at upper-triangular form — that is just Gauss elimination — instead of continuing to clear above the pivots and scale to II.
  • Assuming the mechanical steps apply verbatim when rank⁡(A)<n\operatorname{rank}(A)<n: a zero row, or a row like 0=c≠00=c\neq0, appearing during elimination signals infinitely many solutions or inconsistency instead.
  • Skipping partial pivoting when a small but technically nonzero pivot appears — the arithmetic still "works" formally, but hand calculations with awkward fractions become far more error-prone than if a larger pivot from a lower row had been swapped in first.

Ask the tutor: want to practice a 4×44\times4 system with a tricky zero pivot, or see the Gauss vs. Gauss–Jordan operation counts compared side by side for a general nn?

Why bother with Gauss-Jordan if Gauss elimination already gives the answer

Gauss–Jordan does more arithmetic — roughly 50%50\% more operations than plain Gauss elimination — so for a single system, Gauss elimination plus back substitution is usually the cheaper route. Gauss–Jordan earns its keep when you want the answer without writing a separate back-substitution routine, or when you apply the same reduction to [A ∣ I][A\,|\,I] to compute A−1A^{-1} directly, which Gauss elimination alone cannot hand you.

Does partial pivoting change the final solution

No. Swapping two rows (or swapping a row with a linear combination of itself and another) is one of the three elementary row operations, and elementary row operations never change the solution set of the system — they only change how you arrive at it. Partial pivoting is purely a computational safeguard: it avoids dividing by zero and, for decimal arithmetic, keeps the multipliers small so rounding errors don't blow up. The exact-fraction answer at the end is identical whether or not you pivoted.

How do I tell from the row-reduced matrix whether a system has no solution or infinitely many

Watch what happens to the rows during elimination. If a row reduces to something like 0=c0=c with c≠0c\neq0 — all coefficients zero but a nonzero right-hand side — the system is inconsistent and has no solution. If instead a row reduces to all zeros including the right-hand side (0=00=0), that equation carries no information, rank⁡(A)<n\operatorname{rank}(A)<n, and the system has infinitely many solutions, with the leftover unknown(s) becoming free parameters. Only when every row keeps a nonzero pivot does the mechanical back-substitution or read-off step give a single unique solution.

Before this

Where this leads