A square matrix is said to have a Cholesky decomposition if it can be written as the product of a lower triangular matrix and its transpose (conjugate transpose in the complex case); the lower triangular matrix is required to have strictly positive real entries on its main diagonal.
In this lecture we are going to prove that all positive definite matrices possess a Cholesky factorization. Moreover, the decomposition is unique.
We start with a definition.
Definition Let be a matrix. We say that possesses a Cholesky decomposition if and only if there exists a lower triangular matrix such that its diagonal entries are strictly positive real numbers andwhere denotes the conjugate transpose of .
When is real (its entries have zero complex parts), then the conjugate transpose coincides with the transpose and the Cholesky factorization is
Example Consider the lower triangular matrixand its conjugate transposeThen, the matrixhas the Cholesky decomposition
Remember that a complex matrix is said to be positive definite if and only if the quadratic form is real (i.e., it has zero complex part) for any vector andwhenever .
When we restrict our attention to real vectors and matrices, then we say that a real matrix is positive definite if and only if is symmetric and for any non-zero real vector .
Positive definiteness is a necessary and sufficient condition for the existence of a Cholesky factorization.
Proposition A square matrix possesses a Cholesky factorization if and only if it is positive definite.
Let us prove the "if" part, starting from the hypothesis that is positive definite. Since a positive definite matrix is Hermitian (i.e., ), it is also normal. Therefore, it can be diagonalized aswhere is a unitary matrix and is a diagonal matrix having the eigenvalues of on its main diagonal. Moreover, since is positive definite, its eigenvalues are strictly positive real numbers. Thus, we can writewhere is a diagonal matrix such that its -th entry satisfiesfor . Therefore, The matrix , being unitary, is full-rank. The matrix is diagonal (hence triangular) and its diagonal entries are strictly positive. Thus, by the properties of triangular matrices, is full-rank . The product of two full-rank matrices is full-rank. Therefore, is full-rank and, as a consequence, it has a QR decompositionwhere is a unitary matrix and not only is upper triangular, but it also has strictly positive real entries on its main diagonal (remember that all square matrices have a QR decomposition, and the latter strict positivity condition is satisfied if the matrix being decomposed is full-rank). Thus, we havewhere is a lower triangular matrix having strictly positive diagonal entries on its main diagonal. Hence, has the Cholesky decompositionLet us now prove the "only if" part, starting from the hypothesis that has a Cholesky decomposition, as in the previous equation. Since the diagonal entries of are strictly positive, is full-rank. Therefore, for any , we haveand quadratic forms satisfywhere the last inequality follows from the positive definiteness property of the norm. Moreover, the norm is guaranteed to be a real number. Therefore, is positive definite.
The Cholesky factorization is unique.
Proposition A positive definite matrix possesses a unique Cholesky factorization, in the sense that there exists a unique lower triangular matrix with strictly positive real entries on its main diagonal that satisfies
Suppose that there exists another decompositionThen, we haveandwhere the existence of the inverses and is guaranteed by the fact that and are triangular with strictly positive diagonal entries. Since and are lower triangular, is lower triangular. Since and are upper triangular, is upper triangular. The lower triangular matrix can be equal to the upper triangular matrix only if both matrices are diagonal. Therefore,where is a diagonal matrix. Note thatAs a consequence,Thus, any diagonal entry of (denote it by ) satisfiesIn other words, the diagonal entries of are all located on the unit circle. Moreover, they need to satisfy the constraintwhere the diagonal entries of both and are real and strictly positive. The only way to satisfy this constraint by remaining on the unit circle is to pickfor all . Therefore,and
The Cholesky factorization of a matrix can be computed by directly solving the equation
In particular, by the definition of matrix product, the latter equation implies thatfor any entry located at the intersection of the -th row and -th column (for and ).
Since is lower triangular, whenever . Therefore,
We derive the entries of from the latter equation, by following the rules:
we solve one column at a time, starting from the first column (), and then solving the other columns in order ();
in each column, we first derive the diagonal entry and then the other entries (only for because when ).
By solving equation (1), we find that the diagonal entries are
Since the entries on the main diagonal of need to be real and strictly positive, we always choose the positive root. Moreover, if the number under the square root is not strictly positive, then we stop the algorithm and we conclude that is not positive definite.
Again by solving equation (1), we find that the other entries (for ) arewhere we have used the fact that because the entries on the main diagonal are real.
Example Let us find the Cholesky factorization of We need to find a matrixsuch thatWe start from the first column and its diagonal entryThe next entry in the first column isWe now move to the second column and its diagonal entryTherefore, the lower triangular matrix used in the Cholesky decomposition is
Below you can find some exercises with explained solutions.
Compute the Cholesky decomposition of
We start from the first row. The diagonal entry isThe second entry isand the third one isWe now proceed to the second column, where we start with the entryThe entry below it isWe can now go to the third column and findThus, the triangular matrix used in the decomposition is
Please cite as:
Taboga, Marco (2017). "Cholesky decomposition", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/Cholesky-decomposition.
Most of the learning materials found on this website are now available in a traditional textbook format.