Elimination, replayed
In Volume I you ran Gaussian elimination on an augmented matrix to solve one system. The work — the row operations — was thrown away once you had the answer. Factorization saves that work. Every elimination step that subtracts a multiple of one row from another is itself a matrix multiply, and the product of all those steps is exactly what turns A into upper-triangular form.
The multipliers you used to clear each column slot neatly into a lower-triangular matrix L (with 1s on the diagonal); the cleared result is upper-triangular U. That is the whole content of LU decomposition: A = LU, where L records *how* you eliminated and U records *what was left*.
A = [ 2 1 1 ; L = [ 1 0 0 ; U = [ 2 1 1 ;
4 3 3 ; 2 1 0 ; 0 1 1 ;
8 7 9 ] 4 3 1 ] 0 0 2 ]
# row2 -= 2*row1, row3 -= 4*row1, then row3 -= 3*row2.
# the multipliers 2, 4, 3 are exactly the sub-diagonal of L.
# check: L @ U reproduces A, entry by entry.Why bother — solve once, reuse forever
Once A = LU is stored, solving Ax = b for any new b costs almost nothing: solve Ly = b by forward substitution (top down), then Ux = y by back substitution (bottom up). The expensive O(n^3) elimination happens once; each later right-hand side is only O(n^2). For a structural engineer loading the same bridge a thousand ways, this is the difference between minutes and milliseconds.
- Factor once: A = LU (the O(n^3) cost).
- Forward-solve Ly = b for y — L is lower-triangular, so y_1 comes free, then cascade down.
- Back-solve Ux = y for x — U is upper-triangular, so x_n comes free, then cascade up.
Pivoting: don't divide by (nearly) zero
Plain LU breaks the instant a pivot is zero, and degrades long before that: dividing by a tiny pivot amplifies round-off. The fix is partial pivoting — before clearing each column, swap up the row with the largest entry in that column. Those swaps are recorded in a permutation matrix P, giving the form you will actually use: PA = LU. Pivoting keeps every multiplier in L bounded by 1, which keeps the factorization numerically honest.
Without a pivoting rule, LU is not even unique — many L,U pairs reproduce a given A under different row orders. Fix L to have unit diagonal and fix the pivot rule, and the factorization becomes unique. Uniqueness is the recurring theme of this whole track: a factorization only earns its keep once you have nailed down what makes it *the* factorization.