Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 62 · Eigenvalues and Decompositions

Cholesky Decomposition

Learn the Cholesky factorization A = L L^T for positive definite matrices: the algorithm, a worked example, solving systems, and sampling correlated data.

Some matrices are so well behaved that they can be factored in half the usual work. If a matrix is symmetric and positive definite, it can be written as A = L L^T, where L is lower triangular with positive diagonal entries. This is the Cholesky decomposition, named after the French officer André-Louis Cholesky who invented it for surveying calculations. It is like a square root for matrices.

It is the method of choice whenever the matrix is a covariance matrix, a Gram matrix X^T X from least squares, or the Hessian of a well-behaved optimization problem. It costs about half as much as LU decomposition, needs no pivoting, is numerically stable, and breaks down when the matrix is not positive definite (an error or NaNs, depending on the library), which makes it a handy test.

Positive definite matrices

A symmetric matrix A is positive definite if x^T A x > 0 for every nonzero vector x. Think of it as the matrix analogue of a positive number: the "energy" x^T A x is positive in every direction. Several equivalent descriptions are worth knowing (see the spectral theorem):

  • all eigenvalues of A are positive;
  • all pivots in Gaussian elimination are positive;
  • all leading principal minors (the determinants of the top-left k × k corners) are positive;
  • A = B^T B for some matrix B with independent columns.

If the inequality is only ≥ 0, the matrix is positive semi-definite, and a Cholesky factor may fail or be rank deficient.

What the factorization looks like

For A = L L^T with

TEXT
L = [ l11   0    0  ]
    [ l21  l22   0  ]
    [ l31  l32  l33 ]

matching entries of L L^T with A gives equations you solve in order, one column at a time:

TEXT
l_jj = sqrt( a_jj - Σ_{k<j} l_jk² )
l_ij = ( a_ij - Σ_{k<j} l_ik · l_jk ) / l_jj        for i > j

The square root is where positive definiteness matters: the quantity under the root is positive precisely when A is positive definite. If it is zero or negative, the algorithm stops.

A hand example. Take A = [[4, 12, -16], [12, 37, -43], [-16, -43, 98]].

  • l11 = sqrt(4) = 2, then l21 = 12/2 = 6 and l31 = -16/2 = -8.
  • l22 = sqrt(37 - 6²) = sqrt(1) = 1, then l32 = (-43 - (-8)(6))/1 = 5.
  • l33 = sqrt(98 - (-8)² - 5²) = sqrt(9) = 3.

So L = [[2, 0, 0], [6, 1, 0], [-8, 5, 3]], and you can check L L^T = A.

Python Cholesky from scratch, compared with NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The determinant line shows a free bonus: det(A) = (l11 · l22 · l33)², so log det A = 2 Σ log l_ii is cheap and safe from overflow. That is how Gaussian probability code evaluates log-likelihoods.

Solving systems with Cholesky

To solve A x = b, factor once and then solve two triangular systems, both fast:

  1. Forward substitution: L y = b (top to bottom).
  2. Back substitution: L^T x = y (bottom to top).

Because the expensive factorization is reusable, solving for many right-hand sides costs only the triangular steps. Cholesky takes about n³/3 multiplications compared with 2n³/3 for LU.

Sampling correlated random numbers

Suppose you can generate independent standard normal values z (mean 0, identity covariance) and want data with covariance matrix Σ. Factor Σ = L L^T and take x = L z. Then Cov(x) = L I L^T = Σ. This is how correlated simulations are produced for finance, physics and machine learning.

Python Solving a system and generating correlated data

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sample covariance comes out close to [[1, 0.8], [0.8, 1]]: multiplying uncorrelated numbers by L introduced exactly the correlation we asked for.

A practical warning

Floating-point errors can make a matrix that is mathematically positive semi-definite (for example, a covariance matrix from nearly collinear data) fail the factorization. The usual fixes are adding a tiny multiple of the identity (A + 1e-8 * I, called jitter) or using an eigenvalue-based method. Depending on the NumPy build, a failure shows up as a LinAlgError or as an array of NaNs, so check for both. Also remember that Cholesky only applies to symmetric matrices; NumPy reads only one triangle and silently ignores the other, so check symmetry yourself.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which matrices have a Cholesky factorization A = L L^T with L lower triangular?

    Cholesky requires the matrix to be symmetric and positive definite, so every pivot under the square root is positive.
  2. 2. Which is a reliable way to test whether a symmetric matrix is positive definite?

    Positive definite means all eigenvalues are positive. A nonzero determinant or positive entries or trace do not guarantee it (the matrix [[1, 2], [2, 1]] has all of them but an eigenvalue of -1).
  3. 3. For A = L L^T, how can you compute det(A) cheaply?

    det(A) = det(L) det(L^T) = (l11 * l22 * ... * lnn)^2.
  4. 4. You want random vectors with covariance matrix Sigma starting from independent standard normals z. What do you compute?

    Cov(Lz) = L I L^T = Sigma.
  5. 5. Compared with LU decomposition, Cholesky needs roughly...

    It exploits symmetry: about n^3/3 operations instead of 2n^3/3.

Summary

  • A symmetric positive definite matrix factors as A = L L^T with L lower triangular and a positive diagonal.
  • Column by column: l_jj = sqrt(a_jj - Σ l_jk²) and l_ij = (a_ij - Σ l_ik l_jk) / l_jj. A non-positive value under the root means the matrix is not positive definite.
  • Solve A x = b with one forward and one backward substitution; log det A = 2 Σ log l_ii.
  • x = L z turns independent noise into data with covariance L L^T.

Next: The Covariance Matrix, the most common positive semi-definite matrix in data science.