Cholesky Decomposition

The Cholesky decomposition of a symmetric positive definite matrix is a factorization into a unique upper triangular such that

This factorization has a number of uses, one of which is that, because it is a triangular factorization, it can be used to solve systems of equations involving symmetric positive definite matrices. (The way that a triangular factorization can be used to solve a matrix equation is shown above in the section on LU Decomposition.) If a matrix is known to be of this form it is preferred over the LU factorization because the Cholesky factorization is faster to compute. If you want to solve a matrix equation using the Cholesky factorization you can do this directly from LinearSolve using the Cholesky method, this is described in a previous section.

The Cholesky factorization can be computed in Mathematica with the function CholeskyDecomposition.

In[1]:=

Out[3]//MatrixForm=

This reconstructs the original matrix.

In[4]:=

Out[4]=

If the matrix is not positive definite then the Cholesky decomposition does not exist.

In[5]:=

Out[6]=

There are a number of equivalent definitions of positive definite, such as the eigenvalues being all positive.

In[7]:=

Out[8]=

One way to test if a matrix is positive definite is to see if the Cholesky decomposition exists.

Note that if the matrix is complex, the factorization is defined by the conjugate transpose. The following computes the Cholesky decomposition of a complex matrix.

In[9]:=

Out[10]=

This demonstrates that the factorization is correct.

In[11]:=

Out[11]//MatrixForm=

Cholesky and LU Factorizations

The Cholesky factorization is related to the LU factorization as

where is the diagonal matrix of pivots. This can be demonstrated as follows.

In[1]:=

Out[4]//MatrixForm=

Now you can compute the matrix.

In[5]:=

Out[9]//MatrixForm=

This step computes the matrix of pivots.

In[10]:=

Out[12]//MatrixForm=

Finally, this computes ; its transpose is equal to the Cholesky decomposition.

In[13]:=

Out[13]//MatrixForm=