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.

⏱ 55 min● Intermediate🔗 Prereqs: 5.2

Builds on: LU specializes to symmetric positive-definite matrices here.
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

Let \(\Sigma=\begin{psmallmatrix}4&2\\2&3\end{psmallmatrix}\) (variances 4 and 3, covariance 2).

\(L_{11}=\sqrt{4}=2\), then \(L_{21}=\Sigma_{21}/L_{11}=2/2=1\).

\(L_{22}=\sqrt{\Sigma_{22}-L_{21}^2}=\sqrt{3-1}=\sqrt{2}\approx1.4142\).

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:

It only works on triangular matrices

Positive-definiteness keeps every pivot (diagonal radicand) strictly positive

It ignores rounding error

It uses complex arithmetic

Q2 Medium

To draw \(X\sim\Normal(0,\Sigma)\) from standard normals \(Z\) with \(\Sigma=LL^\top\), set:

\(X=\Sigma Z\)

\(X=LZ\)

\(X=L^{-1}Z\)

\(X=Z/L\)

Q3 Easy

A failed Cholesky (a non-positive radicand) on an estimated covariance most likely means:

The code has a bug for sure

The matrix is not positive definite - often too few samples or a bad estimate

The matrix is too large

You must switch to LU

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\).

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.

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

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lec 23 - Lecture 23: Cholesky factorization and its stability.
Monte Carlo Methods in Financial Engineering (Paul Glasserman, 2004) foundational - Ch. 2 - Ch. 2: generating correlated normals via \(X=\mu+LZ\) for Monte Carlo.
Linear Algebra Done Right (Sheldon Axler, 4th ed., 2024) current - Ch. 7 - Positive operators and their square roots.

← 5.3 Next: 5.5 →