Chapter 10 — Key Takeaways

The big ideas

  • LU decomposition is Gaussian elimination, remembered. Eliminating $A$ produces an upper-triangular $U$ (the echelon form); LU keeps the multipliers you would otherwise discard and packs them into a unit lower-triangular $L$, so that $A = LU$. This is the chapter's threshold concept: an elimination need not be repeated for every right-hand side — record it once as two triangular factors and reuse it. (Theme: factoring a matrix reveals structure you can reuse.)
  • $L$ stores how, $U$ stores where. $U$ is where elimination ends; $L$ records how it got there — the entry $\ell_{ij}$ is the multiplier that cleared position $(i,j)$, and the unit diagonal says "start from the original rows." Multiplying $LU$ replays the elimination and rebuilds $A$, so no information is lost.
  • Triangular systems are cheap; that is the whole point. Forward substitution (down, through $L$) and back substitution (up, through $U$) each cost $\sim n^2$, versus $\sim n^3$ for a full elimination. LU trades one $n^3$ factorization for two $n^2$ solves per right-hand side.
  • Solve $A\mathbf{x}=\mathbf{b}$ as $L\mathbf{y}=\mathbf{b}$ then $U\mathbf{x}=\mathbf{y}$. Name the intermediate vector $\mathbf{y}=U\mathbf{x}$, forward-solve for $\mathbf{y}$, then back-solve for $\mathbf{x}$. Two staged triangular solves replace one tangled one.
  • Factor once, reuse for many right-hand sides. When the same $A$ is solved against $m$ different $\mathbf{b}$'s, factoring once ($\sim\tfrac23 n^3$) and reusing ($\sim 2n^2$ each) costs $\tfrac23 n^3 + 2mn^2$ — versus $m\cdot\tfrac23 n^3$ for re-eliminating each time. For large $m$ this is a hundred- or thousandfold saving. (Theme: computation validates theory — the operation counts make the choice unambiguous.)
  • Plain $A=LU$ does not always exist; $PA=LU$ always does. No-pivot LU works only when every pivot is nonzero (every leading principal minor nonzero). When a zero (or dangerously small) pivot appears, you must swap rows, recording the swaps in a permutation matrix $P$. Every square matrix has a $PA=LU$ factorization with partial pivoting — which is why production software computes PLU.
  • State when pivoting is required. Pivoting is mandatory when a pivot position is zero with a nonzero entry below it (else you divide by zero). It is advisable even for nonzero-but-small pivots, because dividing by a small pivot amplifies floating-point error. Existence vs. accuracy — two distinct reasons to swap.
  • Never invert a matrix to solve a system. Computing $A^{-1}$ costs about $2n^3$ (roughly $3\times$ an LU) and is numerically less stable; then $A^{-1}\mathbf{b}$ is an extra multiply. To solve, factor and substitute; compute $A^{-1}$ only when you genuinely need the inverse itself. np.linalg.solve honors this — it runs a PLU, not an inversion. (Failure mode avoided: treating the factorization, or the inverse, as the point.)
  • LU is a tool, not the destination. Its job is fast, repeatable solving — and it is your first instance of the recurring big idea that factoring a matrix exposes structure you can reuse, the same instinct behind eigendecomposition, QR, the spectral theorem, and the SVD.

Skills you gained

  • Recognizing triangular matrices and solving triangular systems by forward / back substitution.
  • Factoring a small matrix as $A=LU$ by hand, reading the multipliers straight into $L$, and verifying $LU=A$.
  • Solving $A\mathbf{x}=\mathbf{b}$ from a precomputed LU via $L\mathbf{y}=\mathbf{b}$ then $U\mathbf{x}=\mathbf{y}$.
  • Deciding when a row swap is required, building the permutation matrix $P$, and factoring $PA=LU$ (PLU) by hand and in scipy.
  • Reasoning about operation counts ($\sim\tfrac13 n^3$ factor, $\sim n^2$ solve) and justifying factor-once-reuse-many and "never invert to solve."
  • Reconciling a library's pivoted factorization with a hand no-pivot one by checking the invariant ($P^{\mathsf{T}}A=LU$) rather than the raw factors.
  • Implementing lu_decompose, plu, and solve_lu from scratch in pure Python and verifying against scipy.linalg.lu / np.linalg.solve, minding 1-indexed math vs. 0-indexed code.

Terms to know

LU decomposition / factorization · lower-triangular / upper-triangular · unit (lower-)triangular (unit diagonal) · multiplier $\ell_{ij}$ · forward substitution · back substitution · permutation matrix $P$ · PLU decomposition ($PA=LU$) · partial pivoting · pivot · leading principal minor · operation count ($\tfrac13 n^3$ / $n^2$) · in-place factorization · triangular solve · factorization (as reuse).

Notation reminders (locked for the whole book)

  • $A=LU$ with $L$ unit lower-triangular (1's on the diagonal, multipliers below) and $U$ upper-triangular (the echelon form).
  • $PA=LU$ for the pivoted (PLU) factorization; $P$ is a permutation matrix with $P^{-1}=P^{\mathsf{T}}$. (scipy's lu uses the convention $A=PLU$ — watch which form your library returns.)
  • The solve pipeline: $L\mathbf{y}=\mathbf{b}$ (forward), then $U\mathbf{x}=\mathbf{y}$ (back); with a permutation, $L\mathbf{y}=P\mathbf{b}$.
  • Math indexes from 1 ($\ell_{21}$ is row 2, column 1); numpy / scipy index from 0 (L[1,0]). Watch the shift in all code.

How this connects forward

  • Chapter 11 (Determinant) reads the determinant straight off the LU: $\det A = \pm\,(\text{product of the pivots on } U\text{'s diagonal})$, the sign being $(-1)^{\#\text{row swaps in }P}$. The visualizer's det annotation finally gets its full meaning, and LU is the fast way to compute it.
  • Chapter 9 (Inverse) is the contrast partner: computing $A^{-1}$ is itself a (more expensive) elimination, which is why we factor to solve rather than invert.
  • Chapter 20 (QR) and Chapter 25 (Diagonalization) continue the factor-once-reuse theme — precompute a QR for repeated least-squares fits, an eigendecomposition for repeated matrix powers.
  • Chapter 28 (Positive Definite) introduces the Cholesky factorization $A=R^{\mathsf{T}}R$, LU's specialized, roughly-twice-as-fast cousin for symmetric positive-definite matrices — the one circuit and finance solvers actually use.
  • Chapter 30 (SVD) is the grand culmination of "factoring reveals structure": $A=U\Sigma V^{\mathsf{T}}$ factors every matrix into rotate–stretch–rotate.
  • Chapter 38 (Numerical Linear Algebra) quantifies when even a careful PLU strains — ill-conditioning, the condition number, the floating-point reality behind the clean algorithm.

The recurring themes, here

This chapter is where "factoring a matrix reveals structure you can reuse" is born, and where "computation validates theory and theory guides computation" becomes a design decision: the operation counts (theory) dictate that you factor once and never invert (practice). Hold the framing the chapter opens and closes with — LU is a tool for solving efficiently, not the point of the subject. The point is what matrices do; LU is how you make a matrix's action cheap to apply, again and again. The next time you write a solve inside a loop, you will hear this chapter asking: did you factor outside the loop?