The Cholesky Factorisation of a matrix A is given by a matrix L such that LL^{T}=A, where L is lower triangular.

This factorisation is a special case of LU factorisation which is possible if and only if the original matrix was symmetric positive definite: that is, A=A^{T} (the symmetric part) and for any vector **x** other than the zero vector, **x**^{T}A**x** is strictly greater than zero (the positive definite part).

Once such a factorisation has been found, the original system A**x**=**b** can be solved as for LU factorisation, with L^{T} taking the place of U. Thus the only difference is making use of the symmetry to simplify the derivation.

**Deriving a Cholesky Factorisation**

As with LU factorisation, the matrix L is built up by a series of column vectors which are obtained by an iterative process using the matrix A and previously determined columns. There is no longer any need to track U, since this will simply be L^{T}; however, additional computation is introduced by the use of square roots.

So to start the process, define **L _{1}** as the first column of A divided through by sqrt(a

_{1,1}).

Construct a new matrix A

^{2}by A

^{2}= A -

**L**(again, this is not a scalar product, else the difference makes no sense). Obtain

_{1}L_{1}^{T}**L**from the second column of A

_{2}^{2}divided by sqrt(a

^{2}

_{2,2}).

Proceed iteratively, finding

**L**by

_{i}**A**/sqrt(a

^{i}_{i}^{i}

_{i,i}), until all N columns have been found. Then check LL

^{T}gives A.

**Possible problems**

If any of the diagonal entries of A is zero or negative, then dividing by the square root won't be possible (working in the reals). However, by the iff relation between being symmetric positive definite and having a Cholesky factorisation, this should not occur. In fact, this can be used as a test for A being SPD, rather than the potentially awkward **x**^{T}A**x** > 0: attempt to find the Cholesky factors and if the process ever fails, you didn't have an SPD matrix.

**A sample Cholesky factorisation**

Let A be the matrix

2 -1 0 -1 2 -1 0 -1 2Then

**L**is

_{1}**A**/sqrt(a

_{1}_{1,1})= [2, -1, 0]

^{T}/sqrt(2). It's easiest to carry the square root outside the vector, as it'll be squared back up again when we construct A

^{2}:

2 -1 0 2 -1 0 0 0 0 A -The second column of AL= -1 2 -1 - -1 0.5 0 = 0 1.5 -1 0 -1 2 0 0 0 0 -1 2_{1}L_{1}^{T}

^{2}divided by sqrt(a

^{2}

_{2,2})=sqrt(3/2) gives us

**L**= [0 3/2 -1]

_{2}^{T}/sqrt(3/2). Repeat again to get A

^{3}which is just

0 0 0 0 0 0 0 0 4/3Which makes

**L**=[0 0 4/3]

_{3}^{T}/sqrt(4/3)= [0 0 2/√3]

^{T}. Combining these columns we get for L:

2/√2 0 0 -1/√2 √(3/2) 0 0 -√(2/3) 2/√3