Chapter 10 Quiz — LU and PLU Decomposition
Twelve quick checks on factorization, solving, pivoting, and cost. Try each before opening the answer. Reach for a pencil only on the short computational ones.
Q1. In one phrase, what is the LU decomposition?
Answer
**Gaussian elimination, remembered.** $U$ is the upper-triangular echelon form elimination produces; $L$ is the unit lower-triangular matrix recording the multipliers used along the way. Together $A=LU$, so the elimination is saved rather than discarded.Q2. Why does $L$ have $1$'s on its diagonal, and what sits below the diagonal?
Answer
The unit diagonal encodes "start from the original rows" (each row begins as itself before any subtraction). Below the diagonal sit the **elimination multipliers**: $\ell_{ij}$ is how many copies of pivot-row $j$ were subtracted from row $i$. The unit-diagonal convention also makes the factorization **unique**.Q3. You have $A=LU$. Describe the two steps that solve $A\mathbf{x}=\mathbf{b}$, and which kind of substitution each uses.
Answer
Write $LU\mathbf{x}=\mathbf{b}$ and set $\mathbf{y}=U\mathbf{x}$. First solve $L\mathbf{y}=\mathbf{b}$ by **forward substitution** (top-down, since $L$ is lower-triangular). Then solve $U\mathbf{x}=\mathbf{y}$ by **back substitution** (bottom-up, since $U$ is upper-triangular). Two cheap triangular solves replace one expensive elimination.Q4. A fixed $A$ must be solved against $1000$ different right-hand sides. Why is LU the right tool, and roughly what is the cost of each approach?
Answer
Re-eliminating from scratch costs $\sim\tfrac23 n^3$ *per* right-hand side, so $\sim 1000\cdot\tfrac23 n^3$ total. LU factors **once** ($\sim\tfrac23 n^3$) and then each solve is just two triangular substitutions ($\sim 2n^2$), so the total is $\sim\tfrac23 n^3 + 1000\cdot2n^2$. Because $n^2\ll n^3$, the one-time factorization dominates and the savings are enormous. **Factor once, reuse many.**Q5. True or false: every square matrix has an $A=LU$ factorization with $L$ unit lower-triangular. If false, give the correct universal statement.
Answer
**False.** Plain $A=LU$ (no pivoting) exists only when every pivot encountered is nonzero — equivalently, when every leading principal minor is nonzero. The matrix $\begin{bsmallmatrix}0&1\\1&0\end{bsmallmatrix}$ has no such factorization (zero first pivot) yet is invertible. The correct universal statement: **every square matrix has a $PA=LU$ factorization** with a permutation $P$.Q6. When is pivoting required (not just advisable)?
Answer
When a pivot position holds a **zero** and a nonzero entry sits below it in that column. Without a swap you would divide by zero forming the multiplier, and the algorithm fails. (Pivoting is additionally *advisable* — though not strictly required — whenever a pivot is nonzero but small relative to entries below it, because dividing by a small pivot amplifies rounding error. The first is about existence; the second about accuracy.)Q7. What does the permutation matrix $P$ do, and what is its inverse?
Answer
$P$ is an identity matrix with reordered rows; multiplying $PA$ **reorders the rows of $A$** in that pattern (bundling all the elimination swaps into one step). Its inverse is its transpose, $P^{-1}=P^{\mathsf{T}}$ (undoing a shuffle is shuffling back) — $P$ is an orthogonal matrix.Q8. Solve $L\mathbf{y}=\mathbf{b}$ for $L=\begin{bsmallmatrix}1&0\\4&1\end{bsmallmatrix}$, $\mathbf{b}=(3,14)$.
Answer
Forward substitution: $y_1=3$; then $4y_1+y_2=14\Rightarrow y_2=14-12=2$. So $\mathbf{y}=(3,2)$.Q9. Why should you not solve $A\mathbf{x}=\mathbf{b}$ by computing $A^{-1}$ and forming $A^{-1}\mathbf{b}$?
Answer
Two reasons. **Cost:** computing $A^{-1}$ takes about $2n^3$ operations — roughly $3\times$ a single LU factorization — and then a matrix–vector multiply, so it does strictly more work. **Accuracy:** forming and applying the explicit inverse introduces more rounding error and is numerically less stable than solving the triangular systems directly. The rule: *never invert a matrix to solve a system; factor and substitute.*Q10. scipy's lu(A) returns factors $P,L,U$ that don't match your hand-computed $A=LU$. Are you wrong?
Answer
Not necessarily. scipy **always pivots** (partial pivoting for stability), so it computes a *PLU* factorization $A=PLU$, which generally differs from the no-pivot $A=LU$ you did by hand. The LU factorization is unique only **once the pivoting strategy is fixed**. Both are correct: check the invariant ($P^{\mathsf{T}}A=LU$, or that both solve $A\mathbf{x}=\mathbf{b}$ to the same $\mathbf{x}$), not the raw factors.Q11. Roughly how many operations does the LU factorization of an $n\times n$ matrix cost, and where does that cost come from?
Answer
About $\tfrac13 n^3$ multiply–add pairs (often quoted as $\tfrac23 n^3$ floating-point operations). It comes from the nested elimination loops: clearing column $k$ touches roughly $(n-k)^2$ entries, and summing over all columns gives $\sum (n-k)^2\approx n^3/3$. The cubic cost is why doubling $n$ makes factoring about $8\times$ slower.Q12. What is the recurring big idea that LU introduces, and name one later factorization that continues it.