Cholesky factorization

We know that a positive definite matrix A has a unique symmetric square root F such that :

F ² = FF' = A

Now if we do not insist on symmetry, there is a very large set of (non symmetric) matrices G such that :

GG' = A

and which may also be regarded as "square roots" of A. The positive definite matrix A is then said to be factored into the "square" of its square root.

-----

One of these factorizations is of particular interest, both from theoretical and practical standpoints : the Cholesky factorization (or "Cholesky decomposition"), which is expressed as follows.

 * Let A be a positive definite matrix. * Then there exists a unique lower triangular matrix L with positive diagonal elements such that : A = LL'

If A is only positive semidefinite, the diagonal elements of L can only be said to be non negative.

The Cholesky factorization can be symbolically represented by :

-----

The Cholesky factorization is the prefered numerical method for calculating :

* The inverse,

* and the determinant

of a positive definite matrix (in particular of a covariance matrix), as well as for the simulation of a random multivariate normal variable.

_____________________________________________________

 Tutorial

In this Tutorial, we first identify a large set of non symmetric square roots of a positive definite matrix.

-----

We then describe two different ways of establishing the existence of the (unique) Cholesky factorization :

* The first one is very much in the spirit of Linear Algebra, and establishes the existence of the Cholesky factorization recursively :

- The factorization is assumed to exist and be unique for positive definite matrices of order (n - 1).

- It is then proved that this implies that the same is true for positive definite matrices of order n.

* The second way is more "pedestrian" and actually builds iteratively the matrix L column after column, and in each column, element after element.

Both demonstrations are constructive, and lead to actual numerical algorithms.

CHOLESKY FACTORIZATION

 A family of non symmetric "square roots" of a positive definite matrix Recursive Cholesky factorization Iterative Cholesky factorization TUTORIAL

______________________________________________________

 Positive definite matrix Covariance matrix