Visual walkthrough — LU decomposition (numerical)

Before we start, three words we will use constantly, defined in plain language and anchored to the pictures:

The diagonal itself is the set of positions $a_{11},a_{22},a_{33},\dots$ — where row number equals column number.

---

Step 1 — What "solving by elimination" actually does to a grid

WHAT. We start with a $3\times 3$ system. Elimination means: use the top-left number to wipe out the numbers directly below it, turning the left column into $\left(\begin{array}{c}\bullet \\ 0\\ 0\end{array}\right)$.

WHY. A grid whose bottom-left is all zeros (upper triangular) can be solved by back substitution — read the bottom equation, which has only one unknown, then climb up. So the entire goal of elimination is to manufacture that zero-filled corner.

PICTURE. Look at the grid below. The amber cell $a_{11}$ is the pivot — the number we divide by. The two cyan cells beneath it, $a_{21}$ and $a_{31}$, are the ones we want to turn into $0$.

To kill $a_{21}$ we subtract a copy of row 1 from row 2. How many copies? Exactly enough so the $a_{21}$ slot lands on zero. That number of copies is:

${\ell }_{21}=\underset{\text{number to erase}}{\underbrace{a_{21}}}/\underset{\text{pivot underneath row 1}}{\underbrace{a_{11}}}$

${\ell }_{21}$ is called a multiplier: the amount of row 1 we mixed into row 2.

---

Step 2 — The multiplier is worth keeping

WHAT. In ordinary elimination we compute ${\ell }_{21}=a_{21}/a_{11}$, do the subtraction, and then throw ${\ell }_{21}$ away. LU decomposition's one insight: don't throw it away — write it into the empty slot it just cleared.

WHY. The slot $(2,1)$ is now $0$ and will stay $0$ — it is spare storage. If we park ${\ell }_{21}$ there, the grid remembers how it was eliminated. Later that memory reconstructs the original $A$.

PICTURE. The amber arrow shows ${\ell }_{21}$ flowing from the "work we did" into the freshly-zeroed cell. That zeroed cell (now holding ${\ell }_{21}$) becomes an entry of $L$; the surviving top part becomes an entry of $U$.

${\text{new row}}_2=\underset{\text{old}}{\underbrace{{\text{row}}_2}}-\underset{\text{how much}}{\underbrace{{\ell }_{21}}}\cdot \underset{\text{the pivot row}}{\underbrace{{\text{row}}_1}}$

Every symbol here is doing a job: ${\ell }_{21}$ says how much, row${}_1$ says of what, the minus sign says remove it.

---

Step 3 — One elimination step = multiply by an elementary matrix

WHAT. The single operation "row${}_2\leftarrow$ row${}_2-{\ell }_{21}$row${}_1$" is itself a matrix. Call it $E_{21}$. It looks like the identity with $-{\ell }_{21}$ tucked into position $(2,1)$.

WHY. If a step is a matrix, then a whole elimination is a product of such matrices. Products are easy to invert and re-order — that is what lets us collect all the multipliers into one clean $L$.

PICTURE. The identity matrix (a "do nothing" grid, 1's on the diagonal) with one amber intruder $-{\ell }_{21}$ is the machine that performs Step 2.

$E_{21}=\left(\begin{array}{ccc}1& 0& 0\\ -{\ell }_{21}& 1& 0\\ 0& 0& 1\end{array}\right),E_{21}A=\text{(A with row 2 cleaned)}$

Term-by-term: the $1$'s copy every other row unchanged; the $-{\ell }_{21}$ in row 2 injects "$-{\ell }_{21}\times$ row 1" into row 2 — precisely Step 2.

---

Step 4 — Stack all steps: $U=(\text{all }E)A$

WHAT. Do every elimination in order — clear column 1, then column 2. Each is an elementary matrix. Multiply them all onto $A$ from the left. The result is upper triangular; call it $U$.

WHY. Once the grid is upper triangular, elimination is done. We have factored out all the "downward mixing" into the product of $E$'s sitting on the left of $A$.

PICTURE. Read left to right: $A$ enters, each $E$ shaves off one more sub-diagonal cell, and $U$ (clean upper-triangular staircase) emerges. See Gaussian Elimination for the same story without the matrix bookkeeping.

$\underset{\text{all elimination steps}}{\underbrace{E_{32}{E}_{31}{E}_{21}}}A=U$

The order matters: $E_{21}$ acts first (it is closest to $A$), then $E_{31}$, then $E_{32}$ — right-to-left, like functions.

---

Step 5 — Undo the steps to reveal $L$

WHAT. Move all the $E$'s to the other side. The inverse of the whole product is $L$: $A=(E_{32}{E}_{31}{E}_{21}{)}^{-1}U=LU.$

WHY. Inverting each $E$ just flips its one off-diagonal sign ($-\ell \to +\ell$), and — here is the small miracle — multiplying the inverses together simply drops each $+{\ell }_{ij}$ into its own slot with no cross-contamination. So $L$ is literally the table of multipliers, with $1$'s on the diagonal.

PICTURE. The amber $-\ell$ entries flip to $+\ell$ and assemble into the lower-triangular $L$. No arithmetic between them — each multiplier lands untouched.

$L=\left(\begin{array}{ccc}1& 0& 0\\ {\ell }_{21}& 1& 0\\ {\ell }_{31}& {\ell }_{32}& 1\end{array}\right)$

Reading it: diagonal $1$'s mean "each row keeps itself in full"; ${\ell }_{21}$ below records how much of row 1 went into row 2; ${\ell }_{32}$ how much of (cleaned) row 2 went into row 3. This is exactly the Doolittle form. (Swap the 1's onto $U$ instead and you get Crout Decomposition.)

---

Step 6 — The degenerate case: a zero pivot

WHAT. Suppose the amber pivot $a_{11}=0$. Then ${\ell }_{21}=a_{21}/0$ — undefined. Elimination stalls even when $A$ is perfectly invertible.

WHY. Dividing by the pivot is baked into every multiplier. A zero pivot is a divide-by-zero, and a tiny pivot is nearly as bad — it magnifies rounding error (this is the link to Condition Number and Numerical Stability).

PICTURE. The left grid shows the stall: a red $0$ in the pivot seat. The right grid shows the cure — swap two rows so a big number sits on the pivot. That swap is a permutation matrix $P$, giving $PA=LU$. This is Partial Pivoting.

$PA=LU,\text{solve }L\mathbf{y}=P\mathbf{b},U\mathbf{x}=\mathbf{y}$

Term-by-term: $P$ reorders the rows of $A$ (and the same reorder must hit $\mathbf{b}$); after the swap the pivot is nonzero and Steps 1–5 run normally.

---

Step 7 — Two triangular solves finish the job

WHAT. With $A=LU$ in hand, $A\mathbf{x}=\mathbf{b}$ becomes $LU\mathbf{x}=\mathbf{b}$. Name the middle vector $\mathbf{y}=U\mathbf{x}$. Solve $L\mathbf{y}=\mathbf{b}$ downward, then $U\mathbf{x}=\mathbf{y}$ upward.

WHY. A triangular system has a "one new unknown per line" structure: the first row of $L\mathbf{y}=\mathbf{b}$ involves only $y_1$, the second only $y_1,y_2$, and so on — no algebra, just substitution. See Forward and Back Substitution.

PICTURE. Green flows down the staircase of $L$ (forward), then flows up the staircase of $U$ (back). The two directions are the two triangles' shapes made physical.

$\underset{\text{top}\to \text{bottom}}{\underbrace{L\mathbf{y}=\mathbf{b}}}\text{then}\underset{\text{bottom}\to \text{top}}{\underbrace{U\mathbf{x}=\mathbf{y}}}$

And the free bonus (from Step 5's diagonal): since $\det L=1$, the determinant is $\det A=(-1{)}^{\#\text{swaps}}{\prod }_i{u}_{ii}$ — just multiply the diagonal of $U$.

---

The one-picture summary

The whole journey in one frame: $A$ enters on the left; elimination (the $E$'s) shaves it into upper-triangular $U$ while quietly filing every multiplier into lower-triangular $L$; the reunion $L\cdot U$ reproduces $A$ exactly; and any right-hand side $\mathbf{b}$ then rides two cheap staircases (down, then up) to the answer $\mathbf{x}$.

Recall Feynman retelling — say it to a friend

You want to un-mix a system of equations. So you clean it up column by column: for each number under a pivot, figure out how many copies of the pivot's row you must subtract to zero it out, and subtract them. That "how many copies" number is a multiplier. Normally you'd forget it — but the cell you just zeroed is now empty, so you store the multiplier there instead. When you're done, the top-right of your grid is the cleaned-up upper matrix $U$, and the bottom-left holds all your stored multipliers, which (with 1's down the diagonal) form $L$. Multiply $L$ by $U$ and, magically, you get your original $A$ back — because $L$ literally remembers every move you made. If a pivot ever turns out to be zero, you can't divide by it, so you just swap that row with a lower one that has a big number there, remember the swap in $P$, and continue. After all this, solving for any new right-hand side is trivial: slide down $L$ (forward substitution), then climb up $U$ (back substitution). Factor once, solve forever.

---

Connections

• 4.8.19 LU decomposition (numerical) (Hinglish) — the parent topic (Hinglish).
• Gaussian Elimination — the elimination that Steps 1–4 photograph.
• Forward and Back Substitution — the two staircase solves of Step 7.
• Partial Pivoting / Permutation Matrices — the cure in Step 6.
• Crout Decomposition / Cholesky Decomposition — sibling factorizations (1's on $U$; symmetric case).
• Determinants — the bonus at the end of Step 7.
• Condition Number and Numerical Stability — why a tiny pivot is dangerous.