LU decomposition — algorithm, applications: Exercises

This page is your self-test for LU decomposition — algorithm, applications. Every problem states cleanly what to do, then hides a complete worked solution. Try first, then open the callout. Levels climb from "just recognise the pieces" up to "put everything together."

Before we start, one word does all the heavy lifting on this page, so let's pin it down in plain language.

Everything here uses only tools from the parent note: elimination multipliers $m_{ik} = a_{ik} / a_{k k}$ , unit-lower-triangular $L$ , upper-triangular $U$ , forward/back substitution, permutations $P$ , and the product-of-pivots rule.

Figure — LU decomposition — algorithm, applications

This figure is your map for every solution below: whenever a solution says "pivot" look at the magenta diagonal cell; whenever it computes a multiplier $m_{ik}$ and stores it in $L$ , that number lives in an orange lower-left cell at position $(i, k)$ ; the violet upper cells are the entries that survive into $U$ . Keep this picture open as you work Exercises 2.3, 4.1 and 4.2 — each row operation there is literally "orange cell $\to$ becomes $0$ , its multiplier recorded in $L$ ."

Level 1 — Recognition

Exercise 1.1

Which of these are valid $L$ (unit lower triangular) and which are valid $U$ (upper triangular)?

M_{1} = (1301), M_{2} = (2051), M_{3} = (1021), M_{4} = (1302) .

Recall Solution

Recall two rules from the parent note:

Unit lower triangular $L$ : zeros above the diagonal, and 1's on the diagonal.
Upper triangular $U$ : zeros below the diagonal (diagonal can be anything).
$M_{1}$ : zeros above diagonal ✓, diagonal $= (1, 1)$ ✓ → valid $L$ .
$M_{2}$ : zero below diagonal ✓ → valid $U$ (diagonal $(2, 1)$ is fine for $U$ ).
$M_{3}$ : zero below diagonal ✓ → valid $U$ . (It also happens to have 1's on the diagonal, so it is also a valid $L$ ? No — $L$ needs zeros above, but $M_{3}$ has a $2$ above. So it is only a valid $U$ .)
$M_{4}$ : zeros above ✓ but diagonal $= (1, 2)$ , and $2 \neq = 1$ → NOT unit lower triangular. It is a valid lower triangular matrix, just not the unit kind LU uses.

Exercise 1.2

In the factorisation

(39620) = L (1301) U (3062),

name (a) the two pivots, (b) the single multiplier $m_{21}$ , and (c) $det A$ read straight off $U$ .

Recall Solution

(a) Pivots are the diagonal of $U$ (the magenta cells in the figure): $u_{11} = 3$ and $u_{22} = 2$ .
(b) The multiplier is the off-diagonal entry of $L$ (an orange cell): $m_{21} = 3$ . Sanity check: $m_{21} = a_{21} / a_{11} = 9/3 = 3$ ✓.
(c) $det A = \prod_{i} u_{ii} = 3 \cdot 2 = 6$ . (No row swaps, so no sign flip.)

Level 2 — Application

Exercise 2.1

Factor $A = (26415)$ into $LU$ .

Recall Solution

Step 1 (WHY): we stand on pivot $a_{11} = 2$ (the top-left magenta cell). To make the matrix upper-triangular we must turn the $6$ directly below it into $0$ . The multiplier is "how many copies of row 1 to subtract from row 2": $m_{21} = \frac{a _{21}}{a _{11}} = \frac{6}{2} = 3.$ Step 2 (WHAT + WHY): row $_{2} \leftarrow$ row $_{2} - 3 \cdot$ row $_{1}$ gives $(6, 15) - (6, 12) = (0, 3)$ . The leading $0$ is exactly the cleared entry; this is why the operation produces the upper-triangular shape of $U$ : $U = (2043) .$ Step 3 (WHY): $L$ must record how we reached $U$ so that $LU = A$ . The parent note shows each multiplier drops in with a $+$ sign, so store $+ m_{21} = 3$ in the orange $(2, 1)$ cell: $L = (1301) .$ Check: $LU = (1301) (2043) = (26415) = A$ ✓.

Exercise 2.2

Using the $A$ and factors from 2.1, solve $A x = b$ with $b = (830)$ by the two-solve method.

Recall Solution

Forward solve $L y = b$ (row by row, top-down): $y_{1} = 8, 3 y_{1} + y_{2} = 30 \Rightarrow y_{2} = 30 - 24 = 6.$ Back solve $U x = y$ (row by row, bottom-up): $3 x_{2} = 6 \Rightarrow x_{2} = 2, 2 x_{1} + 4 x_{2} = 8 \Rightarrow 2 x_{1} = 8 - 8 = 0 \Rightarrow x_{1} = 0.$ Answer: $x = (0, 2)^{⊤}$ . Verify $A x = (2 \cdot 0 + 4 \cdot 2 6 \cdot 0 + 15 \cdot 2) = (830)$ ✓.

Exercise 2.3

Factor the $3 \times 3$ matrix $A = 123258137 .$

Recall Solution

Column 1 (WHY): we stand on pivot $a_{11} = 1$ and must zero out both entries below it (the two orange cells in column 1). Each multiplier is that entry divided by the pivot: $m_{21} = \frac{2}{1} = 2, m_{31} = \frac{3}{1} = 3.$ Subtract those multiples of row 1 — this is why the whole first column below the pivot becomes zero:

row $_{2} - 2$ row $_{1} = (0, 1, 1)$
row $_{3} - 3$ row $_{1} = (0, 2, 4)$ $\to 100212114 .$ Column 2 (WHY): now we stand on the new pivot in position $(2, 2)$ , which is $1$ (read it off the matrix as it stands, not the original $5$ ). One entry, the $2$ at $(3, 2)$ , sits below it, so $m_{32} = \frac{2}{1} = 2, row_{3} - 2 row_{2} = (0, 0, 2) .$ That zeroes the last sub-diagonal entry, completing the upper-triangular shape:

L=\begin{pmatrix}1&0&0\\2&1&0\\3&2&1\end{pmatrix}.$$ **WHY $L$ looks like this:** each multiplier we used is stored (with a $+$ sign) in the orange cell whose position matches the entry it cleared — $m_{21}\to(2,1)$, $m_{31}\to(3,1)$, $m_{32}\to(3,2)$ — which is exactly *how we got to $U$*. **Full check** — multiply out **every** entry of $LU$, not just one row: $$LU=\begin{pmatrix}1&0&0\\2&1&0\\3&2&1\end{pmatrix}\begin{pmatrix}1&2&1\\0&1&1\\0&0&2\end{pmatrix} =\begin{pmatrix} 1 & 2 & 1\\ 2 & 2{+}1 & 2{+}1\\ 3 & 6{+}2 & 3{+}2{+}2 \end{pmatrix} =\begin{pmatrix}1&2&1\\2&5&3\\3&8&7\end{pmatrix}=A\ ✓.$$ (Row 2: $2\cdot(1,2,1)=(2,4,2)$ plus $1\cdot(0,1,1)$ gives $(2,5,3)$. Row 3: $3\cdot(1,2,1)+2\cdot(0,1,1)+1\cdot(0,0,2)=(3,8,7)$. Every entry matches.)

Level 3 — Analysis

Exercise 3.1

Attempt to factor $A = (0324)$ . If plain $LU$ fails, produce $P A = LU$ instead.

Recall Solution

Why plain $LU$ fails: the first pivot is $a_{11} = 0$ . The multiplier $m_{21} = a_{21} / a_{11} = 3/0$ is undefined — division by zero. No amount of algebra fixes this; we must move a nonzero entry into the pivot slot.

Partial pivoting: swap rows 1 and 2. The permutation matrix that swaps rows of a $2 \times 2$ is $P = (0110), P A = (3042) .$ Now pivot $= 3$ , and the entry below it is already $0$ , so $m_{21} = 0/3 = 0$ . Hence $L = (1001), U = (3042), P A = LU .$ Check: $LU = U = P A$ ✓.

Exercise 3.2

Read $det A$ off the factorisation of 3.1. Remember the sign rule.

Recall Solution

$det U = 3 \cdot 2 = 6$ , and $det L = 1$ . But we performed one row swap, so $det A = (- 1)^{# swaps} det U = (- 1)^{1} \cdot 6 = - 6.$ Direct check: $det (0324) = 0 \cdot 4 - 2 \cdot 3 = - 6$ ✓.

Exercise 3.3

For the $3 \times 3$ matrix $A$ of Exercise 2.3 (with $U$ diagonal $1, 1, 2$ ), compute $det A$ , and state how many flops the factorisation cost roughly for $n = 3$ using the $\frac{2}{3} n^{3}$ estimate.

Recall Solution

Determinant: no swaps were used, so $det A = \prod_{i} u_{ii} = 1 \cdot 1 \cdot 2 = 2.$ Flop estimate: $\frac{2}{3} n^{3} = \frac{2}{3} \cdot 27 = 18$ flops (an order-of-magnitude estimate, not exact). The point isn't the exact count — it's that cost grows like $n^{3}$ , so a $10 \times$ bigger matrix costs $\sim 1000 \times$ more to factor.

Level 4 — Synthesis

Exercise 4.1

You must solve $A x = b_{i}$ for the three right-hand sides

undefined