Phase 5 - Lesson 5.4
Cholesky Factorization and Positive-Definite Systems
The symmetric, twice-as-fast factorization - and the engine that turns independent normals into a correlated portfolio.
Builds on: LU specializes to symmetric positive-definite matrices here.
Leads to: Correlated-normal simulation feeds Monte Carlo (Phase 13) and risk (Phase 14).
Leads to: Correlated-normal simulation feeds Monte Carlo (Phase 13) and risk (Phase 14).
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- State positive-definiteness and derive the Cholesky factorization \(A=LL^\top\).
- Explain why Cholesky needs no pivoting and costs half of LU.
- Implement Cholesky and verify \(LL^\top=A\) on a covariance matrix.
- Use Cholesky to simulate correlated normal random vectors with a target covariance.
- Diagnose non-positive-definite covariance matrices via a failed factorization.
Key Vocabulary
- Positive definite
- Symmetric \(A\) with \(x^\top A x\gt 0\) for all \(x\ne0\); equivalently all eigenvalues positive.
- Cholesky factor
- Lower-triangular \(L\) with positive diagonal such that \(A=LL^\top\).
- Covariance matrix
- Symmetric positive-semidefinite \(\Sigma\) with \(\Sigma_{ij}=\Cov(X_i,X_j)\).
- Correlated normals
- A vector \(X=\mu+LZ\) built from i.i.d. standard normals \(Z\) so that \(\Cov(X)=LL^\top=\Sigma\).
- Positive semidefinite
- \(x^\top A x\ge0\) for all \(x\); allows zero eigenvalues (a singular covariance).
- Nearest-PD repair
- Projecting an indefinite estimated covariance to the closest positive-definite matrix so Cholesky succeeds.
Intuition & Motivation
Intuition
A covariance matrix \(\Sigma\) is the ‘shape’ of a cloud of correlated risks. Cholesky finds a lower-triangular \(L\) that is the matrix square root of that shape: \(\Sigma=LL^\top\). Multiply independent unit-variance shocks \(Z\) by \(L\) and you stretch and rotate the round cloud into exactly the correlated ellipse you want - because \(\Cov(LZ)=L\,\Cov(Z)\,L^\top=LL^\top=\Sigma\). This one identity is how every Monte-Carlo engine turns a random-number generator into correlated asset returns.
The factorization
Theorem - Cholesky existence & uniqueness
A symmetric matrix \(A\) is positive definite iff it has a unique factorization \(A=LL^\top\) with \(L\) lower-triangular and strictly positive diagonal. The algorithm requires no pivoting and uses about \(n^3/3\) flops - half of LU.
Entrywise, comparing both sides of \(A=LL^\top\) gives the recursion:
\[L_{jj}=\sqrt{A_{jj}-\sum_{k\lt j}L_{jk}^2},\qquad L_{ij}=\frac{1}{L_{jj}}\Big(A_{ij}-\sum_{k\lt j}L_{ik}L_{jk}\Big)\ (i\gt j).\] (5.5)
If any diagonal radicand is \(\le 0\), the matrix is not positive definite - a failed Cholesky is the cheapest positive-definiteness test there is.
Worked Example - Cholesky of a 2×2 covariance
1
Let \(\Sigma=\begin{psmallmatrix}4&2\\2&3\end{psmallmatrix}\) (variances 4 and 3, covariance 2).
2
\(L_{11}=\sqrt{4}=2\), then \(L_{21}=\Sigma_{21}/L_{11}=2/2=1\).
3
\(L_{22}=\sqrt{\Sigma_{22}-L_{21}^2}=\sqrt{3-1}=\sqrt{2}\approx1.4142\).
4
Check: \(LL^\top=\begin{psmallmatrix}4&2\\2&3\end{psmallmatrix}=\Sigma\). The correlation implied is \(2/\sqrt{4\cdot3}\approx0.577\).
Application: simulate correlated normals
To draw \(X\sim\Normal(\mu,\Sigma)\), factor \(\Sigma=LL^\top\), draw \(Z\sim\Normal(0,I)\), and set \(X=\mu+LZ\). The empirical covariance of many such draws converges to \(\Sigma\).
Common Mistakes to Avoid
- Feeding a non-symmetric or indefinite matrix to Cholesky and ignoring the failure - it is telling you \(\Sigma\) is invalid.
- Using \(X=\mu+L^\top Z\) (upper factor) instead of \(X=\mu+LZ\); the covariance then is \(L^\top L\ne\Sigma\) in general.
- Estimating a covariance from too few samples so it is only positive semidefinite, then wondering why Cholesky throws.
- Adding a huge jitter to force positive-definiteness; use the smallest ridge or a nearest-PD projection.
Quant Practitioner Tips
- A failed Cholesky is the standard, cheap check that an estimated covariance is valid.
- Cache \(L\) once per risk matrix and reuse it for every Monte-Carlo path.
- For a nearly-PSD estimate, add \(\lambda I\) with the smallest \(\lambda\) that restores positivity, or clip negative eigenvalues.
- In finance, \(L\) gives an interpretable factor decomposition: each variable is a triangular combination of orthogonal shocks.
Knowledge Check
Q1 Medium
Cholesky needs no pivoting because:
Q2 Medium
To draw \(X\sim\Normal(0,\Sigma)\) from standard normals \(Z\) with \(\Sigma=LL^\top\), set:
Q3 Easy
A failed Cholesky (a non-positive radicand) on an estimated covariance most likely means:
Practical Exercise
Given target correlation \(\rho\) and unit variances, write the \(2\times2\) Cholesky factor of \(\Sigma=\begin{psmallmatrix}1&\rho\\\rho&1\end{psmallmatrix}\) and use it to express two correlated standard normals in terms of independent \(Z_1,Z_2\).
▶ Show full solution
Here \(L_{11}=1\), \(L_{21}=\rho\), \(L_{22}=\sqrt{1-\rho^2}\).
\[X_1=Z_1,\qquad X_2=\rho Z_1+\sqrt{1-\rho^2}\,Z_2.\]
Then \(\Var(X_2)=\rho^2+(1-\rho^2)=1\) and \(\Cov(X_1,X_2)=\rho\) - the standard two-factor recipe used throughout derivatives pricing.
After the reveal, answer for yourself: What goes wrong at \(|\rho|=1\), and how does that show up in the Cholesky factor?
Lesson Summary
Cholesky factors a symmetric positive-definite \(A=LL^\top\) with no pivoting and half the cost of LU; a non-positive radicand signals loss of positive-definiteness. Its headline application is correlated simulation: \(X=\mu+LZ\) turns independent normals into a target-covariance vector, the backbone of Monte-Carlo risk engines.
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
▶ Show retrieval prompts & answers
Q: How do you simulate \(X\sim\Normal(\mu,\Sigma)\) from standard normals?
A: Factor \(\Sigma=LL^\top\) (Cholesky), draw \(Z\sim\Normal(0,I)\), and set \(X=\mu+LZ\); then \(\Cov(X)=\Sigma\).
A: Factor \(\Sigma=LL^\top\) (Cholesky), draw \(Z\sim\Normal(0,I)\), and set \(X=\mu+LZ\); then \(\Cov(X)=\Sigma\).
Q: What does a failed Cholesky tell you?
A: The matrix is not positive definite - typically an invalid or under-sampled covariance; it is the cheapest PD test.
A: The matrix is not positive definite - typically an invalid or under-sampled covariance; it is the cheapest PD test.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Confidence / mastery rating
Personal notes