Worked examples — LU decomposition — algorithm, applications

---

The scenario matrix

Every $A$ you can be asked to factor falls into one of these cells. We will hit all of them.

#	Cell (the scenario)	What makes it special	Example
C1	Generic $2\times 2$, all pivots nonzero	The "textbook happy path"	Ex 1
C2	Generic $3\times 3$, then solve $A\mathbf{x}=\mathbf{b}$	Combine factor + two solves	Ex 2
C3	Zero pivot in the top-left — needs a row swap $\Rightarrow PA=LU$	Naive $A=LU$ fails	Ex 3
C4	Tiny pivot — mathematically fine but numerically dangerous	Why we pivot for stability	Ex 4
C5	Singular matrix ($\det =0$) — a pivot dies to zero after elimination	LU still exists, $U$ has a zero on the diagonal	Ex 5
C6	Use LU to get $\det A$ and $A^{-1}$	Reuse the same $L,U$	Ex 6
C7	Many right-hand sides at once (real-world word problem)	The 80/20 payoff	Ex 7
C8	Negative & fractional entries — sign bookkeeping in multipliers	Signs of $m_{ik}$	Ex 8
C9	Non-square (rectangular) matrix	LU still works column-by-column; $L$ square, $U$ rectangular	Ex 9

Each example below is tagged with its cell.

---

Notation we will actually use (built from zero)

Before any arithmetic, let us name every symbol so nothing appears unearned.

Figure s01 (in words). A $2\times 2$ grid of cells labelled $a_{11},a_{12}$ (top row) and $a_{21},a_{22}$ (bottom row). The top-left cell $a_{11}$ is highlighted amber and labelled "PIVOT (divide by this)". The bottom-left cell $a_{21}$ is highlighted cyan and labelled "kill this to 0". To the right, the formula $m_{21}=a_{21}/a_{11}$ is written with the caption "how many pivot-rows to subtract." So: amber = the number you divide by, cyan = the number you're trying to zero out, and their ratio is the multiplier.

---

C1 — the happy path

Forecast: guess — will $L$ have a whole number or a fraction under its diagonal? (The pivot is $3$, the number below is $1$, so predict $m_{21}=\frac{1}{3}$.)

1. Pivot $=a_{11}=3$; multiplier $m_{21}=\frac{a_{21}}{a_{11}}=\frac{1}{3}$. Why this step? We must kill the $1$ under the pivot; $m_{21}$ is exactly how many pivot-rows to subtract.
2. Row${}_2\leftarrow$Row${}_2-\frac{1}{3}$Row${}_1$: $\left(1,5\right)-\frac{1}{3}(3,6)=(0,3)$. Why? Subtracting $\frac{1}{3}$ of $(3,6)=(1,2)$ leaves $(0,3)$ — the first entry becomes $0$ as designed.
3. Assemble: $U=\left(\begin{array}{cc}3& 6\\ 0& 3\end{array}\right)$, $L=\left(\begin{array}{cc}1& 0\\ \frac{1}{3}& 1\end{array}\right)$. Why? $U$ is what survived; $L$ stores the $+m_{21}=\frac{1}{3}$.

Verify: $LU=\left(\begin{array}{cc}1& 0\\ \frac{1}{3}& 1\end{array}\right)\left(\begin{array}{cc}3& 6\\ 0& 3\end{array}\right)=\left(\begin{array}{cc}3& 6\\ 1& 5\end{array}\right)=A.$ ✓

---

C2 — factor then solve

Forecast: the entries $2,4,8$ double each time — expect clean whole multipliers $m_{21}=2,m_{31}=4$.

1. Column 1. $m_{21}=\frac{4}{2}=2$, $m_{31}=\frac{8}{2}=4$. Row${}_2-2$Row${}_1=(0,1,1)$; Row${}_3-4$Row${}_1=(0,3,5)$. Why? Clear everything below the first pivot $2$ using ratios to it.
2. Column 2. New pivot $=1$ (position $(2,2)$). $m_{32}=\frac{3}{1}=3$. Row${}_3-3\cdot (0,1,1)=(0,0,2)$. Why? Now clear below the second pivot; we always use the current pivot row.
3. Assemble. $U=\left(\begin{array}{ccc}2& 1& 1\\ 0& 1& 1\\ 0& 0& 2\end{array}\right),L=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 4& 3& 1\end{array}\right).$
4. Forward solve $L\mathbf{y}=\mathbf{b}$: $y_1=4;2y_1+y_2=10\Rightarrow y_2=2;4y_1+3y_2+y_3=26\Rightarrow 16+6+y_3=26\Rightarrow y_3=4.$ Why forward? $L$ is lower triangular, so the top row is solved instantly and each new row uses only known values.
5. Back solve $U\mathbf{x}=\mathbf{y}$: $2x_3=4\Rightarrow x_3=2;x_2+x_3=2\Rightarrow x_2=0;2x_1+x_2+x_3=4\Rightarrow 2x_1=2\Rightarrow x_1=1.$ Why back? $U$ is upper triangular, so the bottom variable is isolated first.

Verify: $A\mathbf{x}=\left(\begin{array}{ccc}2& 1& 1\\ 4& 3& 3\\ 8& 7& 9\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 2\end{array}\right)=\left(\begin{array}{c}4\\ 10\\ 26\end{array}\right)=\mathbf{b}.$ ✓

---

C3 — zero pivot, must permute ($PA=LU$)

Forecast: the top-left entry is $0$. Can you compute $m_{21}=\frac{3}{0}$? No — dividing by zero is undefined. So naive $A=LU$ cannot start. We must swap rows first.

Figure s02 (in words). Two matrices side by side. On the left, the matrix $A=\left(\begin{array}{cc}0& 2\\ 3& 4\end{array}\right)$ with its top-left entry ($0$) highlighted amber and labelled "cannot divide by 0" — this is the fatal zero pivot. A cyan arrow labelled "swap rows, $P=[[0,1],[1,0]]$" points to the right, where the swapped matrix $PA=\left(\begin{array}{cc}3& 4\\ 0& 2\end{array}\right)$ appears with its top-left entry ($3$) highlighted green and labelled "pivot = 3 (good)". Message: swapping rows turns a dead zero pivot into a live nonzero one.

1. Diagnose the failure. Pivot $a_{11}=0$; $m_{21}=\frac{3}{0}$ is impossible. Why? Elimination requires dividing by the pivot. A zero pivot has no valid multiplier. (This is the amber cell in the figure.)
2. Swap rows 1 and 2. Record the swap in a permutation matrix $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, giving $PA=\left(\begin{array}{cc}3& 4\\ 0& 2\end{array}\right).$ Why? $P$ just re-orders rows; multiplying $A$ on the left by $P$ physically performs the swap and keeps a permanent receipt. (This is the cyan arrow in the figure.)
3. Now factor $PA$. It is already upper triangular. The only entry below a pivot is the $(2,1)$ entry, which is already $0$, so $m_{21}=\frac{0}{3}=0$ — no elimination is required at all. $L=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),U=\left(\begin{array}{cc}3& 4\\ 0& 2\end{array}\right).$ Why does $L$ become the identity? $L$ stores the multipliers, and here every multiplier is $0$ because there was nothing to subtract — the entries below each pivot were already zero. A grid of $1$'s on the diagonal and $0$'s below it is the identity, so $L=I$.

Verify: $PA=\left(\begin{array}{cc}3& 4\\ 0& 2\end{array}\right)=LU.$ And unwinding: $A=P^{-1}LU=P^{\top }LU$ recovers the original. ✓ (Check: $P^{\top }LU=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}3& 4\\ 0& 2\end{array}\right)=\left(\begin{array}{cc}0& 2\\ 3& 4\end{array}\right)$.)

---

C4 — tiny pivot, stability twist

Forecast: the pivot $0.001$ is not zero, so naive LU works mathematically. But $m_{21}=1/0.001=1000$ is huge — guess that this large number is where rounding error would hide.

1. Naive (no swap). $m_{21}=\frac{1}{0.001}=1000$. Row${}_2-1000\cdot$Row${}_1$: $(1,1)-1000(0.001,1)=(0,1-1000)=(0,-999)$. $L=\left(\begin{array}{cc}1& 0\\ 1000& 1\end{array}\right),U=\left(\begin{array}{cc}0.001& 1\\ 0& -999\end{array}\right).$ Why note the size? On a computer that rounds, $1-1000\approx -1000$ could swallow the true $-999$; the $1000$ multiplier amplifies any error. Mathematically exact, numerically fragile.
2. With partial pivoting. Swap so the entry of largest absolute value in the column ($|1|>|0.001|$) becomes the pivot: $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, $PA=\left(\begin{array}{cc}1& 1\\ 0.001& 1\end{array}\right),m_{21}=\frac{0.001}{1}=\mathrm{0.001.}$ Row${}_2-0.001$Row${}_1=(0,1-0.001)=(0,0.999)$. $L=\left(\begin{array}{cc}1& 0\\ 0.001& 1\end{array}\right),U=\left(\begin{array}{cc}1& 1\\ 0& 0.999\end{array}\right).$ Why better? Now every multiplier has magnitude $\le 1$, so no error gets amplified.

Verify: naive $LU=\left(\begin{array}{cc}0.001& 1\\ 1& 1\end{array}\right)=A$ ✓; pivoted $LU=\left(\begin{array}{cc}1& 1\\ 0.001& 1\end{array}\right)=PA$ ✓.

---

C5 — singular matrix, $\det =0$

Forecast: rows $1$ and $3$ look proportional-ish; ${\text{col}}_2=2{\text{col}}_1$. Predict a zero pivot appears and $\det A=0$.

1. Column 1. $m_{21}=2,m_{31}=3$. Row${}_2-2$Row${}_1=(0,0,1)$; Row${}_3-3$Row${}_1=(0,0,1)$. Why? Standard clearing under the first pivot $1$.
2. Column 2. The candidate pivot $(2,2)$ is now $0$, and every entry below it is also $0$. There is nothing to eliminate. Formally $m_{32}=\frac{a_{32}}{a_{22}}=\frac{0}{0}$ — undefined, but since $a_{32}$ is already $0$ no elimination is needed, so we set $m_{32}=0$ and move on. Why $m_{32}=0$? A multiplier tells us how many pivot-rows to subtract to zero out the entry below; that entry is already zero, so we subtract nothing, i.e. the multiplier is $0$. No swap can help because the whole subcolumn is zero — the mark of a singular matrix.
3. Assemble. $U=\left(\begin{array}{ccc}1& 2& 3\\ 0& 0& 1\\ 0& 0& 1\end{array}\right),L=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 3& 0& 1\end{array}\right).$ Note the pivot pattern is broken: a zero sits on the diagonal at $(2,2)$.
4. Determinant. $\det A=\prod u_{ii}=1\cdot 0\cdot 1=0.$ Why? A single zero pivot on the diagonal of $U$ makes the product zero — the matrix is singular, no inverse.

Verify: $LU=\left(\begin{array}{ccc}1& 2& 3\\ 2& 4& 7\\ 3& 6& 10\end{array}\right)=A$ ✓ and $\det A=0$ ✓ (rows are linearly dependent: Row${}_3$-Row${}_2$ = Row${}_1$).

---

C6 — determinant AND inverse from one factorisation

Forecast: pivots were $2,1,2$; predict $\det A=2\cdot 1\cdot 2=4$.

1. Determinant $=\prod u_{ii}=2\cdot 1\cdot 2=4.$ Why? $\det (LU)=\det L\det U=1\cdot \prod u_{ii}$; $L$ has all-$1$ diagonal so contributes $1$.
2. Set up the inverse by columns. Recall (definition above) ${\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3$ are the columns of $I$. The $j$-th column of $A^{-1}$ is the solution of $A\mathbf{x}={\mathbf{e}}_j$, solved with the same $L,U$ from Ex 2 (see Matrix Inverse). Why reuse? Factorisation was the expensive part; each column is just two cheap triangular solves, forward then back.
3. Column 1 — solve $A\mathbf{x}={\mathbf{e}}_1=(1,0,0{)}^{\top }$. Forward $L\mathbf{y}={\mathbf{e}}_1$: $y_1=1;2y_1+y_2=0\Rightarrow y_2=-2;4y_1+3y_2+y_3=0\Rightarrow 4-6+y_3=0\Rightarrow y_3=2.$ Back $U\mathbf{x}=\mathbf{y}$: $2x_3=2\Rightarrow x_3=1;x_2+x_3=-2\Rightarrow x_2=-3;2x_1+x_2+x_3=1\Rightarrow 2x_1-3+1=1\Rightarrow x_1=\frac{3}{2}.$ So column 1 of $A^{-1}$ is ${\left(\frac{3}{2},-3,1\right)}^{\top }$. Why? This single column shows the full recipe; columns 2 and 3 repeat it with ${\mathbf{e}}_2,{\mathbf{e}}_3$.
4. Column 2 — solve $A\mathbf{x}={\mathbf{e}}_2=(0,1,0{)}^{\top }$ the same way. Forward $L\mathbf{y}={\mathbf{e}}_2$: $y_1=0;2y_1+y_2=1\Rightarrow y_2=1;4y_1+3y_2+y_3=0\Rightarrow 0+3+y_3=0\Rightarrow y_3=-3.$ Back $U\mathbf{x}=\mathbf{y}$: $2x_3=-3\Rightarrow x_3=-\frac{3}{2};x_2+x_3=1\Rightarrow x_2=1-(-\frac{3}{2})=\frac{5}{2};2x_1+x_2+x_3=0\Rightarrow 2x_1+\frac{5}{2}-\frac{3}{2}=0\Rightarrow 2x_1=-1\Rightarrow x_1=-\frac{1}{2}.$ So column 2 is ${\left(-\frac{1}{2},\frac{5}{2},-\frac{3}{2}\right)}^{\top }$. Column 3 — solve $A\mathbf{x}={\mathbf{e}}_3=(0,0,1{)}^{\top }$. Forward $L\mathbf{y}={\mathbf{e}}_3$: $y_1=0;y_2=0;4y_1+3y_2+y_3=1\Rightarrow y_3=1.$ Back $U\mathbf{x}=\mathbf{y}$: $2x_3=1\Rightarrow x_3=\frac{1}{2};x_2+x_3=0\Rightarrow x_2=-\frac{1}{2};2x_1+x_2+x_3=0\Rightarrow 2x_1-\frac{1}{2}+\frac{1}{2}=0\Rightarrow x_1=0.$ So column 3 is ${\left(0,-\frac{1}{2},\frac{1}{2}\right)}^{\top }$. Why identical process? $L,U$ never change — only the right-hand side does, which is the whole point of LU.
5. Assemble the inverse by placing each solved column side by side: $A^{-1}=\left(\begin{array}{ccc}\frac{3}{2}& -\frac{1}{2}& 0\\ -3& \frac{5}{2}& -\frac{1}{2}\\ 1& -\frac{3}{2}& \frac{1}{2}\end{array}\right).$ Why trust it? $A{A}^{-1}=I$ is checked in VERIFY.

Verify: $\det A=4$ ✓, and $A{A}^{-1}=I_3$ ✓ (both machine-checked below).

---

C7 — real-world word problem, many right-hand sides

Forecast: $A$ is already upper triangular — guess $L=I$ and both solves are pure back-substitution.

1. Factor once. $A$ has all zeros below the diagonal, so no elimination is needed: $L=I_3$, $U=A$. Why once? Same $A$ both days — factor a single time, reuse for every $\mathbf{b}$.
2. Monday, forward solve $L\mathbf{y}={\mathbf{b}}_1$. Since $L=I$, we get $\mathbf{y}={\mathbf{b}}_1=(6,7,8{)}^{\top }$ immediately. Why trivial? The identity leaves any vector unchanged.
3. Monday, back solve $U\mathbf{x}=\mathbf{y}=(6,7,8{)}^{\top }$: $4x_3=8\Rightarrow x_3=2$; $2x_2+3x_3=7\Rightarrow 2x_2+6=7\Rightarrow x_2=\frac{1}{2}$; $x_1+x_2+x_3=6\Rightarrow x_1+\frac{1}{2}+2=6\Rightarrow x_1=\frac{7}{2}$. Why bottom-up? $U$ isolates the last variable first. Monday batches: $\mathbf{x}={\left(\frac{7}{2},\frac{1}{2},2\right)}^{\top }$.
4. Tuesday, forward solve $L\mathbf{y}={\mathbf{b}}_2$. Again $L=I$, so $\mathbf{y}={\mathbf{b}}_2=(3,4,4{)}^{\top }$. Why no re-factor? We reuse the exact same $L,U$ — only the right-hand side changed.
5. Tuesday, back solve $U\mathbf{x}=\mathbf{y}=(3,4,4{)}^{\top }$: $4x_3=4\Rightarrow x_3=1$; $2x_2+3x_3=4\Rightarrow 2x_2+3=4\Rightarrow x_2=\frac{1}{2}$; $x_1+x_2+x_3=3\Rightarrow x_1+\frac{1}{2}+1=3\Rightarrow x_1=\frac{3}{2}$. Tuesday batches: $\mathbf{x}={\left(\frac{3}{2},\frac{1}{2},1\right)}^{\top }$.

Verify (units: batches): Monday $A{\left(\frac{7}{2},\frac{1}{2},2\right)}^{\top }=(6,7,8{)}^{\top }$ ✓; Tuesday $A{\left(\frac{3}{2},\frac{1}{2},1\right)}^{\top }=(3,4,4{)}^{\top }$ ✓. Each new day cost only $\approx n^2$ work (one forward + one back solve), not a fresh $\frac{2}{3}{n}^3$ elimination.

---

C8 — negative & fractional entries (sign bookkeeping)

Forecast: pivot is negative. The multiplier $m_{21}=3/(-2)=-1.5$ is negative too — guess $L$ carries a negative number below its diagonal, and subtracting a negative multiple = adding.

1. Multiplier. $m_{21}=\frac{a_{21}}{a_{11}}=\frac{3}{-2}=-\mathrm{1.5.}$ Why the sign? The formula $a_{ik}/a_{kk}$ doesn't care about signs — it always answers "how many pivot rows to subtract." Here it's $-1.5$.
2. Eliminate. Row${}_2-(-1.5)$Row${}_1=$ Row${}_2+1.5$Row${}_1$: $(3,-5)+1.5(-2,4)=(3-3,-5+6)=(0,1).$ Why "+"? Subtracting a negative multiplier flips to addition — the algebra self-corrects.
3. Assemble. $U=\left(\begin{array}{cc}-2& 4\\ 0& 1\end{array}\right)$, $L=\left(\begin{array}{cc}1& 0\\ -1.5& 1\end{array}\right)$.

Verify: $LU=\left(\begin{array}{cc}1& 0\\ -1.5& 1\end{array}\right)\left(\begin{array}{cc}-2& 4\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}-2& 4\\ 3& -5\end{array}\right)=A$ ✓. Also $\det A=(-2)(1)=-2$, matching $(-2)(-5)-(4)(3)=10-12=-2$ ✓.

---

C9 — non-square (rectangular) matrix

Forecast: $A$ has more rows than columns. Guess: $L$ stays square ($3\times 3$, one row per row of $A$) while $U$ inherits the rectangular shape ($3\times 2$). The idea is unchanged — clear each column below its pivot.

1. Column 1. Pivot $=a_{11}=2$; $m_{21}=\frac{1}{2}$, $m_{31}=\frac{3}{2}$. Row${}_2-\frac{1}{2}$Row${}_1=(0,5-2)=(0,3)$; Row${}_3-\frac{3}{2}$Row${}_1=(0,8-6)=(0,2)$. Why? Same rule: subtract $m_{i1}$ pivot-rows to zero the first column below the pivot.
2. Column 2. New pivot $=3$ at position $(2,2)$; $m_{32}=\frac{2}{3}$. Row${}_3-\frac{2}{3}$Row${}_2=(0,2-2)=(0,0)$. Why? We only have two columns, so this is the last pivot; clear what remains below it.
3. Assemble. $L$ is $3\times 3$ (stores the three multipliers), $U$ is $3\times 2$ (the surviving grid): $L=\left(\begin{array}{ccc}1& 0& 0\\ \frac{1}{2}& 1& 0\\ \frac{3}{2}& \frac{2}{3}& 1\end{array}\right),U=\left(\begin{array}{cc}2& 4\\ 0& 3\\ 0& 0\end{array}\right).$ Why the bottom-zero row of $U$? With only two columns, the third row has no pivot left — it becomes an all-zero row, which is normal for a "tall" matrix.

Verify: $LU=\left(\begin{array}{cc}2& 4\\ 1& 5\\ 3& 8\end{array}\right)=A$ ✓ (machine-checked below).

---

Recall Which cell would each stump you?

Zero top-left entry — which cell and what fix? ::: C3; swap rows, record in $P$, factor $PA=LU$. Pivot equals $10^{-9}$ but nonzero — is LU wrong? ::: C4; it's mathematically fine but numerically unstable, so pivot to the largest-magnitude entry. A whole subcolumn below the pivot is zero — swap? ::: C5; no valid nonzero entry to swap in — matrix is singular, $\det =0$. Two different $\mathbf{b}$'s, same $A$ — recompute $L,U$? ::: C7; no — factor once, reuse for each right-hand side at $O(n^2)$. A $3\times 2$ matrix — what shapes are $L,U$? ::: C9; $L$ stays square ($3\times 3$), $U$ inherits the rectangular shape ($3\times 2$).

Decision map

Connections

• LU decomposition — algorithm, applications — the parent this page drills into.
• Gaussian Elimination — every example is elimination with the steps saved.
• Permutation Matrices — the row-swap receipts in C3, C4.
• Determinants — read off pivots in C5, C6, C8.
• Matrix Inverse — column-by-column reuse in C6.
• Triangular Systems & Substitution — the cheap forward/back solves everywhere.
• Cholesky Decomposition — the symmetric positive-definite cousin.