# Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Linear Systems > Cholesky decomposition

## Cholesky decomposition

We will study a direct method for solving linear systems: the Cholelsky decomposition. Given a symmetric positive definite matrix A, the aim is to build a lower triangular matrix L which has the following property: the product of L and its transpose is equal to A.

Given a symmetric positive definite matrix , the Cholesky decomposition constructs a lower triangular matrix L which has the following property: . A symmetric matrix is positive definite if, for any vector , the product is positive.

The matrix is sometimes called the Â« square root Â» of . The Cholesky decomposition is often used to calculate the inverse matrix and the determinant of (equal to the square of the product of the diagonal elements of ).

### Example

The symmetric matrix

is equal to the product of the triangular matrix and of its transposed :

with

### Theorem

Cholesky Factorization:

If is a symmetric positive definite matrix, there is at least a lower triangular real matrix such as :

We can also impose that the diagonal elements of the matrix are all positive, and corresponding factorization is then unique.

### Algorithm

The Cholesky matrix is given by:

Equality gives :

since if

The matrix being symmetric, it is enough that the relations above are checked for , i.e. the elements of the matrix must satisfy:

For j=1, we determine the first column of :
(i=1) so
(i=2) so
...
(i=n) so

After having calculated the (j-1) first columns, we determine the j-th column of :
(i=j) so
(i=j+1) so
...
(i=n) so

### Solution of linear system

For the resolution of linear system : , the system becomes

We solve the system (1) to find the vector , then the system (2) to find the vector . The resolution is facilitated by the triangular shape of the matrices.

### Calculating Matrix Determinant

The Cholesky decomposition also makes it possible to calculate the determinant of , which is equal to the square of the product of the diagonal elements of the matrix , since