Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Cholesky decomposition

by , PhD

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.

Table of Contents

Definition

We start with a definition.

Definition Let A be a $K imes K$ matrix. We say that A possesses a Cholesky decomposition if and only if there exists a lower triangular $K imes K$ matrix $L$ such that its diagonal entries are strictly positive real numbers and[eq1]where $L^{st }$ denotes the conjugate transpose of $L$.

When $L$ is real (its entries have zero complex parts), then the conjugate transpose $L^{st }$ coincides with the transpose $L^{ op }$ and the Cholesky factorization is[eq2]

Example Consider the lower triangular matrix[eq3]and its conjugate transpose[eq4]Then, the matrix[eq5]has the Cholesky decomposition[eq6]

Existence

Remember that a complex matrix A is said to be positive definite if and only if the quadratic form $x^{st }Ax$ is real (i.e., it has zero complex part) for any vector x and[eq7]whenever $x eq 0$. We have proved that if a complex matrix is positive definite, then it is also Hermitian.

When we restrict our attention to real vectors and matrices, then we say that a real matrix A is positive definite if and only if A is symmetric and [eq8]for any non-zero real vector x. Note that, in the real case, symmetry is an explicit requirement and not a consequence of positive definiteness.

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.

Proof

Let us prove the "if" part, starting from the hypothesis that A is positive definite. Since a positive definite matrix A is Hermitian (i.e., $A=A^{st }$), it is also normal. Therefore, it can be diagonalized as[eq9]where $P$ is a unitary matrix and $D$ is a diagonal matrix having the eigenvalues of A on its main diagonal. Moreover, since A is positive definite, its eigenvalues are strictly positive real numbers. Thus, we can write[eq10]where $D^{1/2}$ is a diagonal matrix such that its $left( k,k ight) $-th entry satisfies[eq11]for $k=1,ldots ,K$. Therefore, [eq12]The matrix $P$, being unitary, is full-rank. The matrix $D^{1/2}$ is diagonal (hence triangular) and its diagonal entries are strictly positive. Thus, by the properties of triangular matrices, $D^{1/2}$ is full-rank . The product of two full-rank matrices is full-rank. Therefore, $D^{1/2}P$ is full-rank and, as a consequence, it has a QR decomposition[eq13]where $Q$ is a unitary matrix and not only $R$ 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 have[eq14]where $L=R^{st }$ is a lower triangular matrix having strictly positive diagonal entries on its main diagonal. Hence, A has the Cholesky decomposition[eq6]Let us now prove the "only if" part, starting from the hypothesis that A has a Cholesky decomposition, as in the previous equation. Since the diagonal entries of $L$ are strictly positive, $L$ and $L^{st }$ are full-rank. Therefore, for any $x eq 0$, we have[eq16]and quadratic forms satisfy[eq17]where the last inequality follows from the positive definiteness property of the norm. Moreover, the norm [eq18] is guaranteed to be a real number. Therefore, A is positive definite.

Uniqueness

The Cholesky factorization is unique.

Proposition A $K imes K$ positive definite matrix A possesses a unique Cholesky factorization, in the sense that there exists a unique lower triangular matrix $L$ with strictly positive real entries on its main diagonal that satisfies[eq6]

Proof

Suppose that there exists another decomposition[eq20]Then, we have[eq21]and[eq22]where the existence of the inverses [eq23] and $M^{-1}$ is guaranteed by the fact that $L$ and $M$ are triangular with strictly positive diagonal entries. Since $M$ and $L$ are lower triangular, $M^{-1}L$ is lower triangular. Since $M^{st }$ and $L^{st }$ are upper triangular, [eq24] is upper triangular. The lower triangular matrix $M^{-1}L$ can be equal to the upper triangular matrix [eq25] only if both matrices are diagonal. Therefore,[eq26]where $D$ is a diagonal matrix. Note that[eq27]As a consequence,[eq28]Thus, any diagonal entry of $D$ (denote it by $D_{kk}$) satisfies[eq29]In other words, the diagonal entries of $D$ are all located on the unit circle. Moreover, they need to satisfy the constraint[eq30]where the diagonal entries of both $M$ and $L$ are real and strictly positive. The only way to satisfy this constraint by remaining on the unit circle is to pick[eq31]for all k. Therefore,[eq32]and[eq33]

How to compute the Cholesky decomposition

The Cholesky factorization of a $K imes K$ matrix A can be computed by directly solving the equation[eq6]

In particular, by the definition of matrix product, the latter equation implies that[eq35]for any entry $A_{tv}$ located at the intersection of the $t$-th row and $v$-th column (for $t=1,ldots ,K$ and $v=1,ldots ,K$).

Since $L$ is lower triangular, $L_{vu}=0$ whenever $u>v$. Therefore,[eq36]

We derive the entries of $L$ from the latter equation, by following the rules:

By solving equation (1), we find that the diagonal entries are[eq37]

Since the entries on the main diagonal of $L$ 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 A is not positive definite.

Again by solving equation (1), we find that the other entries $L_{tv}$ (for $t>v$) are[eq38]where we have used the fact that [eq39] because the entries on the main diagonal are real.

Example Let us find the Cholesky factorization of [eq40]We need to find a matrix[eq41]such that[eq6]We start from the first column and its diagonal entry[eq43]The next entry in the first column is[eq44]We now move to the second column and its diagonal entry[eq45]Therefore, the lower triangular matrix used in the Cholesky decomposition is[eq46]

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Compute the Cholesky decomposition of[eq47]

Solution

We start from the first row. The diagonal entry is[eq48]The second entry is[eq49]and the third one is[eq50]We now proceed to the second column, where we start with the entry[eq51]The entry below it is[eq52]We can now go to the third column and find[eq53]Thus, the triangular matrix used in the decomposition is[eq54]

How to cite

Please cite as:

Taboga, Marco (2021). "Cholesky decomposition", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/Cholesky-decomposition.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.