2.5 Matrix factorizations

Big idea

A factorization writes one matrix as a product of matrices that are easier to work with. Nothing is lost, since the product rebuilds the original, but the factors expose structure the original hides and let an algorithm take a shortcut.

The first one is LU. Run elimination on a square matrix without swapping rows and you produce an upper triangular $U$. The multipliers you used along the way are exactly the entries of a lower triangular $L$, so $A = LU$ falls out of a computation you were doing anyway. The whole point is that triangular systems are cheap: you read a triangular system off top to bottom or bottom to top with no searching and no fractions beyond the divisions by pivots.

That turns one expensive setup into many cheap solves. Factor once. Then each new right-hand side costs two triangular sweeps instead of a full reduction. Engineering problems where the same physical system is driven by hundreds of different loads are the reason this matters, and it is why numerical libraries factor rather than invert.

Decoder

Reducing $A$ to echelon form by row replacements alone produces $U$, and the multipliers, placed in the positions they cleared, produce $L$.

Plain version: when you eliminate, you repeatedly say “subtract $m$ times row $i$ from row $j$”. Write that number $m$ into position $(j,i)$ of a lower triangular matrix with $1$s on its diagonal. Do that for every elimination step and you have built $L$. The sign is the one that surprises people: you subtract $m$ during elimination and you store $+m$, because $L$ has to undo what you did.

“Unit lower triangular” means lower triangular with every diagonal entry equal to $1$. $L$ is always unit lower triangular here, so its diagonal carries no information and only the multipliers below it do.

Definitions and results

Factorization. An equation $A = BC$ with $B$ and $C$ chosen for their structure. In transformation language, a factorization splits one map into a sequence of simpler maps.

LU factorization. If $A$ is $m \times n$ and can be reduced to echelon form using only row replacements that add a multiple of a row to a row below it, then $A = LU$ where $L$ is $m \times m$ unit lower triangular and $U$ is the $m \times n$ echelon form. When $A$ is square and invertible, $U$ is upper triangular with nonzero diagonal entries.

Building the factors. Reduce $A$ to $U$, recording each multiplier. Place the multiplier used to clear position $(j,i)$ into position $(j,i)$ of $L$, put $1$s on the diagonal of $L$, and fill the rest with zeros. No extra arithmetic is needed beyond the elimination itself.

Why it works. Each row replacement is left multiplication by an elementary matrix, so the elimination says $E_k \cdots E_2E_1A = U$. Every $E_i$ here is unit lower triangular, so the product $E_k \cdots E_1$ is too, and so is its inverse. Setting $L = (E_k \cdots E_1)^{-1}$ gives $A = LU$. The recorded multipliers are the entries of that inverse, which is why they can be written down with no further work.

Solving with the factors. To solve $A\mathbf{x} = \mathbf{b}$, write it as $L(U\mathbf{x}) = \mathbf{b}$. Solve $L\mathbf{y} = \mathbf{b}$ downward for $\mathbf{y}$, then solve $U\mathbf{x} = \mathbf{y}$ upward for $\mathbf{x}$. The first sweep is forward substitution, the second is back substitution, and neither needs a pivot search.

Cost. Factoring a dense $n \times n$ matrix takes on the order of $\tfrac{2}{3}n^3$ arithmetic operations, and each triangular pair of solves takes on the order of $2n^2$. Computing $A^{-1}$ costs several times the factorization and then each solve still costs a matrix-vector product, with worse rounding behaviour. For a large system, factor and substitute; never invert.

When row swaps are needed. Some matrices cannot be reduced without interchanging rows, and those have no LU factorization as stated. The repair is a permutation matrix $P$ that reorders the rows in advance, giving $PA = LU$. Practical software always does this, both for matrices that need it and for numerical accuracy on matrices that do not.

Other factorizations. The same idea reappears throughout the subject with different factors chosen for different purposes: a rank factorization from the column-row expansion, an orthogonal factorization for least squares, a diagonalization built from eigenvectors, and the singular value decomposition. LU is the introduction to a technique, not an isolated trick.

Worked examples

Factoring a three-by-three matrix

Let

$$ A = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} $$

Eliminate below the first pivot. Row $2$ minus $2$ times row $1$ gives $(0, 1, 1)$, so the multiplier is $2$. Row $3$ minus $(-1)$ times row $1$ gives $(0, 1, 5)$, so the multiplier is $-1$. Now eliminate below the second pivot: row $3$ minus $1$ times row $2$ gives $(0, 0, 4)$, so the multiplier is $1$.

$$ U = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{bmatrix}, \qquad L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 1 & 1 \end{bmatrix} $$

The three multipliers $2$, $-1$, $1$ sit in positions $(2,1)$, $(3,1)$, $(3,2)$, the positions they cleared.

Check by multiplying. Row $2$ of $L$ against the columns of $U$ gives $2(2) + 1(0) = 4$, then $2(4) + 1(1) = 9$, then $2(-2) + 1(1) = -3$. That is row $2$ of $A$. Row $3$ gives $-1(2) + 1(0) + 1(0) = -2$, then $-1(4) + 1(1) + 1(0) = -3$, then $-1(-2) + 1(1) + 1(4) = 7$. That is row $3$ of $A$.

Two triangular solves

Solve $A\mathbf{x} = \mathbf{b}$ with the same $A$ and $\mathbf{b} = (2, 8, 10)$.

Forward, using $L\mathbf{y} = \mathbf{b}$. The first row gives $y_1 = 2$. The second gives $2y_1 + y_2 = 8$, so $y_2 = 4$. The third gives $-y_1 + y_2 + y_3 = 10$, so $y_3 = 10 + 2 - 4 = 8$. Then $\mathbf{y} = (2, 4, 8)$.

Backward, using $U\mathbf{x} = \mathbf{y}$. The third row gives $4x_3 = 8$, so $x_3 = 2$. The second gives $x_2 + x_3 = 4$, so $x_2 = 2$. The first gives $2x_1 + 4x_2 - 2x_3 = 2$, so $2x_1 = 2 - 8 + 4 = -2$ and $x_1 = -1$.

Check in the original matrix. $2(-1) + 4(2) - 2(2) = 2$, $4(-1) + 9(2) - 3(2) = 8$, and $-2(-1) - 3(2) + 7(2) = 10$. All three match $\mathbf{b}$.

A second right-hand side, at no extra setup cost

Keep $L$ and $U$ and take $\mathbf{b} = (2, 3, 1)$. Forward: $y_1 = 2$, then $2(2) + y_2 = 3$ gives $y_2 = -1$, then $-2 + (-1) + y_3 = 1$ gives $y_3 = 4$. Backward: $4x_3 = 4$ gives $x_3 = 1$, then $x_2 + 1 = -1$ gives $x_2 = -2$, then $2x_1 + 4(-2) - 2(1) = 2$ gives $x_1 = 6$.

Check: $2(6) + 4(-2) - 2(1) = 12 - 8 - 2 = 2$, $4(6) + 9(-2) - 3(1) = 24 - 18 - 3 = 3$, and $-2(6) - 3(-2) + 7(1) = -12 + 6 + 7 = 1$. Correct, and the elimination was never repeated.

A matrix that needs a row swap

Let $A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$. There is no multiplier that clears the $(2,1)$ entry using row $1$, because row $1$ starts with $0$. No $LU$ factorization of this $A$ exists: a unit lower triangular $L$ times an upper triangular $U$ always has $(1,1)$ entry equal to the $(1,1)$ entry of $U$, and then the $(2,1)$ entry is a multiple of it, so a zero in the corner would force a zero below it as well. Swap the rows first. With $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ you get $PA = I$, which is already triangular, so $PA = LU$ with $L = U = I$.

Practice

Row reduce accurately, since every multiplier you record becomes an entry of $L$.

Invert small matrices, and compare the effort against factoring and substituting.

Videos

Watch for the moment where the elimination steps are collected into one lower triangular matrix and the multipliers appear in it unchanged. The discussion of why no extra arithmetic is needed to build $L$, and of what row exchanges cost, is the part worth rewinding.

Quiz

Five items on producing $L$ and $U$ and on solving with them.