LU decomposition — algorithm, applications: Visual walkthrough

Step 0 — What is a matrix and what does "triangular" mean?

Look at the shaded triangles below: the zeros are what make these matrices cheap to solve — a fact we cash in later.

Figure — LU decomposition — algorithm, applications

Our goal, stated visually: take a full square grid $A$ and split it into a lower-left triangle $L$ times an upper-right triangle $U$ .

$A = lower, 1’s on diagonal L upper, pivots on diagonal U$

$A$ — the original grid we are handed.
$L$ — the record of our moves (defined below).
$U$ — the leftover staircase after we clean up (defined below).

Step 1 — One elimination move, drawn as an arrow

WHAT we just did: subtracted a scaled copy of the pivot row from the row below it.

WHY this exact number $m_{ik}$ ? Because we want the entry $a_{ik}$ to become zero. Subtracting $m_{ik} \times a_{k k}$ from $a_{ik}$ gives $a_{ik} - \frac{a _{ik}}{a _{k k}} \cdot a_{k k} = 0$ . The ratio is designed to cancel. That is the whole reason we divide by the pivot — no other number kills that entry in one clean step.

$a_{ik}$ — the troublemaker we want gone (row $i$ , column $k$ ).
$a_{k k}$ — the pivot we are eliminating from.
$m_{ik}$ — "how many pivot-rows fit into the troublemaker."

PICTURE: think of each row as a vector. The move slides row $i$ along the direction of row $k$ until its $k$ -th slot hits zero.

Step 2 — A move is a matrix (the elementary matrix)

The move " $row_{i} \leftarrow row_{i} - m_{ik} row_{k}$ " is achieved by multiplying on the left by an elementary matrix $E$ : the identity matrix, but with $- m_{ik}$ placed in position $(i, k)$ .

$E = 100 01 - m_{31} 001 (example: kills entry (3, 1) ’s neighbour)$

The $1$ 's down the diagonal mean "keep every row as it is..."
...except the single $- m_{ik}$ , which says "...but from row $i$ also subtract $m_{ik}$ of row $k$ ."

WHY the minus sign? Because we subtract. Remember this sign — it flips in the next step, and that flip is the punchline.

PICTURE: the identity is a "do nothing" stamp; the lone off-diagonal number is the one instruction we injected.

Step 3 — Stack the moves: $E_{k} \dots E_{1} A = U$

WHAT: we chained the moves. Read right-to-left: $E_{1}$ acts first, then $E_{2}$ , and so on.

WHY the order matters: we clear column 1 top-to-bottom first, then column 2, etc. Each later move works on already-cleaned columns, so it never re-dirties an earlier one. This "no interference" is what keeps $L$ simple in Step 5.

$A$ — start.
$E_{1}, E_{2}, \dots$ — the moves in the order performed.
$U$ — the finished upper-triangular staircase; its diagonal entries are the pivots.

PICTURE: watch the lower-left triangle of $A$ fill up with zeros, column by column, until only the upper staircase survives.

Step 4 — Undo the moves to isolate $A$

Solving for $A$ : $A = call this L E_{1}^{- 1} E_{2}^{- 1} \dots E_{k}^{- 1} U .$

$E_{i}^{- 1}$ — the move that reverses $E_{i}$ .
The inverses come in reverse order (last move undone first) — same as taking off shoes then socks in reverse.
$L$ — we name this whole product $L$ . That is the definition; we still must check it is nice.

Here is the beautiful fact: the inverse of an elementary matrix is the same matrix with the sign flipped. If $E$ had $- m_{ik}$ , then $E^{- 1}$ has $+ m_{ik}$ .

WHY does the sign just flip? Because "subtract $m_{ik}$ of row $k$ " is undone by "add $m_{ik}$ of row $k$ " — the reverse move. No new numbers appear.

Step 5 — The multipliers drop straight into $L$

WHAT: we multiplied all the inverse moves together and — magically — got a matrix whose off-diagonal entries are literally the multipliers, with $+$ signs.

WHY no messy cross-terms? Because of the ordering in Step 3. Each $E_{i}^{- 1}$ has its single number in a different $(i, k)$ slot, and (since we go top-down, left-to-right) multiplying them never makes two of these numbers collide. So the product just deposits each $+ m_{ik}$ in its own home. This is exactly the parent note's "steel-man check."

The $1$ 's on the diagonal: every reverse-move keeps its own row, so the diagonal stays all ones. This is why $L$ is called unit lower triangular.
$m_{21}, m_{31}, m_{32}$ — the multipliers, sitting exactly where we eliminated.

PICTURE: each multiplier we computed during elimination falls, like a coin into a slot, into position $(i, k)$ of $L$ .

Recall Why exactly are the diagonals of

$L$ all $1$ ? Because each reverse elimination matrix is the identity plus one off-diagonal number — it never touches the diagonal — so multiplying them keeps every diagonal entry at $1$ . The 1's on $L$ 's diagonal come from where? ::: The identity part of every inverse elementary matrix (moves never rescale a row).

Step 6 — Watch a full $2 \times 2$ get factored

Take the parent's example $A = (2437)$ .

WHAT/WHY, step by step:

Pivot $a_{11} = 2$ . To kill the $4$ below it: $m_{21} = \frac{4}{2} = 2$ . (We divide by the pivot because that ratio cancels the $4$ .)
Apply $row_{2} \leftarrow row_{2} - 2 row_{1}$ : $(4, 7) - (4, 6) = (0, 1)$ . Column 1 below the pivot is now zero.
Read off: $U = (2031), L = (1201) .$ The $2$ in $L$ is exactly the multiplier from step 1.

$U$ 's diagonal $(2, 1)$ = the two pivots.
$L$ 's single off-diagonal $2$ = the single multiplier.

PICTURE: the entry that was $4$ turns to $0$ in the grid, and simultaneously a " $2$ " is written into $L$ 's slot — one leaves the working matrix, its record enters $L$ .

Step 7 — The degenerate case: a zero pivot

Example: $A = (0111)$ has pivot $a_{11} = 0$ . Plain $A = LU$ is impossible as written.

WHY it feels wrong: nothing about $A$ is broken — it is a perfectly good invertible matrix. The problem is purely that this order of elimination hit a zero.

THE FIX — permutation. Swap the two rows first. Swapping is itself a matrix, a permutation matrix $P$ : $P = (0110), P A = (1011),$ which is already upper triangular — now factorable. In general we get $P A = LU .$

$P$ — records which rows we swapped (pure bookkeeping, costs no arithmetic).
Choosing the swap that brings the largest entry to the pivot is called partial pivoting — it keeps multipliers $\leq 1$ in size and controls error.

PICTURE: two rows trade places; the $0$ that blocked us is escorted out of the pivot seat.

Recall Why does one row swap flip the sign of the determinant?

Each swap multiplies $det A$ by $- 1$ . So $det A = (- 1)^{# swaps} \prod_{i} u_{ii}$ — see Determinants.

The one-picture summary

Everything above compresses into a single flow: eliminate → zeros go into $U$ , multipliers go into $L$ , swaps go into $P$ .

Recall Feynman retelling — the whole walkthrough in plain words

You start with a messy grid of numbers. You clean it up one column at a time by subtracting scaled copies of the pivot row from the rows beneath — each "how much did I subtract?" number is a multiplier. As the lower-left of the grid empties out into zeros, an upper staircase $U$ is left standing (its diagonal is the pivots). Meanwhile, every multiplier you used gets written down into its matching slot in a second matrix $L$ , whose diagonal is all $1$ 's because you never rescaled a whole row. Multiply $L$ times $U$ and you get your original grid back — you've split it into "the record of my moves" times "the tidy leftover." If a pivot ever lands on zero, you can't divide, so you swap that row with a better one and remember the swap in a permutation matrix $P$ , giving $P A = LU$ . That's it: elimination that never forgets its homework.

Connections

Gaussian Elimination — this whole page is elimination, slowed to one picture per move.
Permutation Matrices — the $P$ in $P A = LU$ (Step 7).
Determinants — product of the pivots on $U$ 's diagonal.
Matrix Inverse — reuse the same $L, U$ against each identity column.
Triangular Systems & Substitution — why the $L$ and $U$ shapes are cheap to solve.
Cholesky Decomposition — the symmetric special case $A = L L^{⊤}$ .