Definition of Cholesky decomposition

Definition: The Cholesky decomposition of a symmetric (Hermitian) positive-definite matrix $A$ is a factorization:

$$A = LL^*$$

where $L$ is a lower triangular matrix with positive diagonal entries.

For real symmetric positive-definite matrices: $A = LL^T$.

Example:
$$\begin{pmatrix} 4 & 2 \\ 2 & 5 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$$

Properties:

• Exists and is unique for every symmetric positive-definite matrix
• Computationally about twice as fast as LU decomposition
• Used in Monte Carlo simulation, Kalman filters, and optimization
• Can be used to solve $Ax = b$ via forward and backward substitution

Algorithm: Entries of $L$ are computed column by column:
$l_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} l_{jk}^2}$ and $l_{ij} = (a_{ij} - \sum_{k=1}^{j-1} l_{ik}l_{jk})/l_{jj}$ for $i > j$.