LU decomposition (numerical)

WHAT is LU decomposition?

WHY two triangular matrices? Because triangular systems are trivial to solve:

• $L\mathbf{y}=\mathbf{b}$ → solve top-to-bottom (forward substitution).
• $U\mathbf{x}=\mathbf{y}$ → solve bottom-to-top (back substitution).

So $A\mathbf{x}=\mathbf{b}$ becomes $LU\mathbf{x}=\mathbf{b}$, set $U\mathbf{x}=\mathbf{y}$, solve the two easy pieces.

HOW do we derive it? (Doolittle, from scratch)

Take a general $3\times3$ to see the machinery. Write $L$ with unit diagonal and $U$ general:

Multiply $LU$ and match entries with $A$. The trick: go row by row of $U$, then column by column of $L$, because each new equation introduces exactly one new unknown.

Row 1 of $U$ (first row of $L$ is $(1,0,0)$): $u_{11}=a_{11},\quad u_{12}=a_{12},\quad u_{13}=a_{13}.$

Column 1 of $L$ (the second/third entries come from row·col): $a_{21}=\ell_{21}u_{11}\Rightarrow \ell_{21}=a_{21}/u_{11}$, and $\ell_{31}=a_{31}/u_{11}$.

Row 2 of $U$: $a_{22}=\ell_{21}u_{12}+u_{22}\Rightarrow u_{22}=a_{22}-\ell_{21}u_{12}$, $a_{23}=\ell_{21}u_{13}+u_{23}\Rightarrow u_{23}=a_{23}-\ell_{21}u_{13}$.

Column 2 of $L$: $a_{32}=\ell_{31}u_{12}+\ell_{32}u_{22}\Rightarrow \ell_{32}=\dfrac{a_{32}-\ell_{31}u_{12}}{u_{22}}$.

Row 3 of $U$: $a_{33}=\ell_{31}u_{13}+\ell_{32}u_{23}+u_{33}\Rightarrow u_{33}=a_{33}-\ell_{31}u_{13}-\ell_{32}u_{23}$.

Generalizing the pattern gives the Doolittle formulas:

WHY is this just Gaussian elimination in disguise?

Each elimination step "row$_i \leftarrow$ row$_i - m_{ik}\cdot$row$_k$" is multiplication by an elementary matrix $E_{ik}$. After full elimination $U = E_{n}\cdots E_1 A$, so $A=(E_n\cdots E_1)^{-1}U = LU$. The multipliers $m_{ik}$ that we discarded in plain elimination are precisely the entries $\ell_{ik}$ that LU keeps.

Worked Example 1 — factor and solve

Solve $A\mathbf{x}=\mathbf{b}$ with $A=\begin{pmatrix}2&3\\6&13\end{pmatrix},\quad \mathbf{b}=\begin{pmatrix}5\\35\end{pmatrix}.$

Step 1: $u_{11}=2,\ u_{12}=3$. Why? Row 1 of $L$ is $(1,0)$, so top row of $U$ = top row of $A$.

Step 2: $\ell_{21}=a_{21}/u_{11}=6/2=3$. Why? Multiplier to kill the $(2,1)$ entry.

Step 3: $u_{22}=a_{22}-\ell_{21}u_{12}=13-3\cdot3=4$. Why? Subtract what column-1 elimination contributed.

So $L=\begin{pmatrix}1&0\\3&1\end{pmatrix},\quad U=\begin{pmatrix}2&3\\0&4\end{pmatrix}.$ Check: $LU=\begin{pmatrix}2&3\\6&13\end{pmatrix}=A.$ ✓

Forward solve $L\mathbf{y}=\mathbf{b}$: $y_1=5$; $3y_1+y_2=35\Rightarrow y_2=35-15=20$. Why top-first? $L$ is lower triangular, first eq has one unknown.

Back solve $U\mathbf{x}=\mathbf{y}$: $4x_2=20\Rightarrow x_2=5$; $2x_1+3x_2=5\Rightarrow 2x_1=5-15=-10\Rightarrow x_1=-5$. Why bottom-first? $U$ is upper triangular.

$\boxed{\mathbf{x}=(-5,\ 5)^\top}$

Worked Example 2 — why pivoting is needed

Try to factor $A=\begin{pmatrix}0&1\\1&1\end{pmatrix}.$ $u_{11}=a_{11}=0$, then $\ell_{21}=a_{21}/u_{11}=1/0$ — blows up! Why? The pivot is zero even though $A$ is invertible.

Fix: partial pivoting. Swap rows so the largest-magnitude entry sits on the pivot. We record swaps in a permutation matrix $P$ and factor $PA=LU$. Here swap the two rows: $PA=\begin{pmatrix}1&1\\0&1\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}\begin{pmatrix}1&1\\0&1\end{pmatrix}.$ To solve $A\mathbf{x}=\mathbf{b}$ you solve $LU\mathbf{x}=P\mathbf{b}$ (permute $\mathbf{b}$ the same way).

A handy bonus: the determinant

Since $\det L=1$ (unit diagonal) and $\det U=\prod u_{ii}$, $\det A=\det(LU)=\prod_{i=1}^{n}u_{ii}\times(-1)^{\#\text{row swaps}}.$ Why? Determinant of a triangular matrix is the product of its diagonal; permutations flip sign once per swap.

Flashcards

Connections

• Gaussian Elimination — LU stores its multipliers.
• Forward and Back Substitution — the two solve phases.
• Partial Pivoting / Permutation Matrices — stability and $PA=LU$.
• Cholesky Decomposition — special LU for symmetric positive-definite $A$ ($A=LL^\top$).
• Crout Decomposition — sister convention (1's in $U$).
• Determinants — computed cheaply from $U$.
• Condition Number and Numerical Stability — why pivoting matters.

Concept Map

Hinglish (regional understanding)