In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for efficient numerical solutions, e.g., Monte Carlo simulations. It was discovered by André-Louis Cholesky for real matrices, and posthumously published in 1924. When it is applicable, the Cholesky decomposition is roughly twice as efficient as the LU decomposition for solving systems of linear equations.
Statement
The Cholesky decomposition of a Hermitian positive-definite matrix A, is a decomposition of the form
where L is a lower triangular matrix with real and positive diagonal entries, and L* denotes the conjugate transpose of L. Every Hermitian positive-definite matrix (and thus also every real-valued symmetric positive-definite matrix) has a unique Cholesky decomposition.
The converse holds trivially: if A can be written as LL* for some invertible L, lower triangular or otherwise, then A is Hermitian and positive definite.
When A is a real matrix (hence symmetric positive-definite), the factorization may be written
where L is a real lower triangular matrix with positive diagonal entries.
Positive semidefinite matrices
If a Hermitian matrix A is only positive semidefinite, instead of positive definite, then it still has a decomposition of the form where the diagonal entries of L are allowed to be zero. The decomposition need not be unique, for example:
However, if the rank of A is r, then there is a unique lower triangular L with exactly r positive diagonal elements and n−r columns containing all zeroes.
Alternatively, the decomposition can be made unique when a pivoting choice is fixed. Formally, if A is an positive semidefinite matrix of rank r, then there is at least one permutation matrix P such that has a unique decomposition of the form with , where L1 is an lower triangular matrix with positive diagonal.
LDL decomposition
A closely related variant of the classical Cholesky decomposition is the LDL decomposition,
where L is a lower unit triangular (unitriangular) matrix, and D is a diagonal matrix. That is, the diagonal elements of L are required to be 1 at the cost of introducing an additional diagonal matrix D in the decomposition. The main advantage is that the LDL decomposition can be computed and used with essentially the same algorithms, but avoids extracting square roots.
For this reason, the LDL decomposition is often called the square-root-free Cholesky decomposition. For real matrices, the factorization has the form and is often referred to as LDLT decomposition (or LDLT decomposition, or LDL′). It is reminiscent of the eigendecomposition of real symmetric matrices, , but is quite different in practice because Λ and D are not similar matrices.
The LDL decomposition is related to the classical Cholesky decomposition of the form LL* as follows:
Conversely, given the classical Cholesky decomposition of a positive definite matrix, if S is a diagonal matrix that contains the main diagonal of , then A can be decomposed as where (this rescales each column to make diagonal elements 1),
If A is positive definite then the diagonal elements of D are all positive. For positive semidefinite A, an decomposition exists where the number of non-zero elements on the diagonal D is exactly the rank of A. Some indefinite matrices for which no Cholesky decomposition exists have an LDL decomposition with negative entries in D: it suffices that the first n−1 leading principal minors of A are non-singular.
Example
Here is the Cholesky decomposition of a symmetric real matrix:
And here is its LDLT decomposition:
Geometric interpretation
The Cholesky decomposition is equivalent to a particular choice of conjugate axes of an ellipsoid. In detail, let the ellipsoid be defined as , then by definition, a set of vectors are conjugate axes of the ellipsoid iff . Then, the ellipsoid is preciselywhere maps the basis vector , and is the unit sphere in n dimensions. That is, the ellipsoid is a linear image of the unit sphere.
Define the matrix , then is equivalent to . Different choices of the conjugate axes correspond to different decompositions.
The Cholesky decomposition corresponds to choosing to be parallel to the first axis, to be within the plane spanned by the first two axes, and so on. This makes an upper-triangular matrix. Then, there is , where is lower-triangular.