Chapter 6 · Transform-and-Conquer
Gaussian Elimination
Transform the system into an equivalent one that is easy to solve: zero out everything below the diagonal with row operations, then read the answer from the bottom up. Along the way you get an LU (Lower–Upper) decomposition and the determinant for free.
Augmented matrix [A | b]. Type integers, decimals or fractions like 2/3. Press Solve.
pivot A[i, i]
pivot row
being compared / used
just changed
solved value
How to read this
- The big matrix
- Rows R1..Rn are the equations; the column after the vertical bar is the right-hand side b. The orange note to the right of a row names the operation applied to it, e.g. “R2 − (2)·R1”.
- Three legal moves
- Swap two rows, scale a row by a nonzero number, or subtract a multiple of one row from another. None of them changes the solution set, which is why the transformed system is “equivalent”.
- L and U
- U is the upper-triangular matrix left in place of A. L has 1s on its diagonal and, under it, the multipliers used to create each zero. Multiplying L·U gives back A (or the row-swapped P·A when pivoting moved rows).
- Counters
- “Elimination mults” counts executions of the innermost line A[j, k] ← A[j, k] − A[i, k] * temp. Levitin §6.2 sums this to exactly n(n − 1)(2n + 5)/6 ≈ n³/3. Back substitution adds only about n²/2 more.
Try this
- Book check. Solve the default system. The multipliers are 2, ½ and ½, the upper-triangular result has diagonal 2, 3, 2, and the answer is x = (1, 0, −1). The determinant is 2·3·2 = 12.
- Count. For n = 3 the elimination multiplication counter must end at 3·2·11/6 = 11. Switch to n = 5 and predict before pressing Solve: 5·4·15/6 = 50.
- Zero pivot. Press “Zero-pivot system”. Without pivoting the algorithm must still swap rows (it cannot divide by 0). Turn on partial pivoting and compare: it swaps whenever a lower row has a bigger |A[j, i]|, so every multiplier has |temp| ≤ 1.
- Determinant sign. With pivoting on, watch the row-swap counter. Each swap flips the determinant's sign; the final value is (−1)swaps × the product of the pivots, and it matches the no-pivoting run.
- Singular system. Make row 3 equal to row 1 + row 2 and solve. Elimination produces a zero row, the determinant is 0, and there is no unique solution.