Cholesky decomposition
Undergraduate
Consider a symmetric matrix $A$ whose eigenvalues are all positive (that is, $A$ is positive definite). The Cholesky decomposition of $A$ is the factorization
\[A = L L^{\top},\]where $L$ is lower triangular with positive diagonal entries.
Examples
Worked examples
-
The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\)
: None
Undergraduate
The matrix \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) has no Cholesky decomposition, because $A$ is not symmetric.
-
The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\)
: \[L = \begin{bmatrix} 2 & 0 \\ 1 & \sqrt{2} \end{bmatrix}\]
Undergraduate
The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric with positive eigenvalues $\frac{7 \pm \sqrt{17}}{2}$, so it has a Cholesky decomposition. Its factor $L$ is the LU factor $U$ with each row divided by the square root of its diagonal entry, transposed.
-
The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\)
: None
Undergraduate
The matrix \(A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) has no Cholesky decomposition, because $A$ is not symmetric.
-
The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\)
: None
Undergraduate
The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) has no Cholesky decomposition, because $A$ has the negative eigenvalue $-1$, so it is not positive definite. The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) is symmetric but has no Cholesky decomposition, because its eigenvalue $-1$ is negative, so it is not positive definite.
Properties
- A real square matrix $A$ has a Cholesky decomposition exactly when $A$ is symmetric positive definite, and then the decomposition is unique.
- Computing a Cholesky decomposition takes about half the work of an LU decomposition, and it needs no row exchanges.
- If $z$ is a vector of independent standard normal random variables and $\Sigma = L L^{\top}$, then $\mu + L z$ is normally distributed with mean $\mu$ and covariance $\Sigma$.
Notes
The related $L D L^{\top}$ decomposition, with $L$ lower triangular with ones on its diagonal and $D$ diagonal, avoids square roots and also applies to some symmetric matrices that are not positive definite.
For complex matrices, $A$ is Hermitian positive definite and $A = L L^*$.
Distinctions involving this term
- Types of matrix decompositions: A matrix decomposition writes a matrix in terms of simpler matrices. Most are products: LU, PLU, and Cholesky decompositions use triangular factors, QR and singular value decompositions use orthogonal factors, and eigendecompositions, Schur decompositions, and Jordan normal forms are similarities $A = P M P^{-1}$ to a simpler matrix $M$ (diagonal, triangular, or made of Jordan blocks). In contrast, the Jordan–Chevalley decomposition is a sum of commuting diagonalizable and nilpotent parts, and the Toeplitz decomposition is a sum $H + K$ of a symmetric matrix $H$ and a skew-symmetric matrix $K$.