= Cholesky decomposition
{c}
{title2=$A=LL^*$}
{wiki}
= Cholesky factorization
{c}
{synonym}
Every real <symmetric matrix> that is a <positive-definite matrix> has a unique <Cholesky decomposition> $A=LL^T$, where $L$ is a <lower triangular matrix> with positive <diagonal entries>.<DPOTRF (LAPACK 3.12.1) by LAPACK project>[DPOTRF, LAPACK 3.12.1: Purpose, lower-triangular factorization; UPLO and INFO argument documentation]{ref} For a complex <Hermitian positive-definite matrix>, the corresponding factorization is $A=LL^*$, with $L^*$ the <conjugate transpose> and the diagonal of $L$ positive and real.<ZPOTRF (LAPACK 3.12.1) by LAPACK project>[ZPOTRF, LAPACK 3.12.1: Purpose, Hermitian factorization with conjugate transpose]{ref} The factorization turns a <linear system> into two <triangular systems>.
For example, matching entries in $A=LL^T$ gives
$$
A=\begin{pmatrix}4&2\\2&5\end{pmatrix},\qquad
L=\begin{pmatrix}\ell_{11}&0\\\ell_{21}&\ell_{22}\end{pmatrix},
\qquad
\ell_{11}^2=4,\quad\ell_{11}\ell_{21}=2,\quad
\ell_{21}^2+\ell_{22}^2=5.
$$
Choose the positive <square roots> in order: $\ell_{11}=2$, $\ell_{21}=1$ and $\ell_{22}=2$. Therefore
$$
\boxed{A=\begin{pmatrix}2&0\\1&2\end{pmatrix}
\begin{pmatrix}2&1\\0&2\end{pmatrix}.}
$$
The second radicand, $5-1^2=4$, is the scalar <Schur complement> remaining after eliminating the first variable. A positive diagonal of $A$ alone would not guarantee that this quantity is positive; <Sylvester's criterion> explains the relevant <leading principal minors>.
\Image[/cholesky-two-triangular-solves.png]
{title=<Cholesky decomposition> replaces one coupled <linear system> by two <triangular systems>}
{description=Original exact two-by-two example. Multiplying the displayed <lower triangular matrix> by its <transpose> recovers $A$; <forward substitution> and <backward substitution in a triangular system> give $x=(1,2)^T$ for $b=(8,12)^T$.}
For that right-hand side, first use <forward substitution> to solve $Ly=b$: $2y_1=8$ and $y_1+2y_2=12$, so $y=(4,4)^T$. Then use <backward substitution in a triangular system> to solve $L^Tx=y$: $2x_2=4$ and $2x_1+x_2=4$, giving \b[$x=(1,2)^T$]. No <matrix inverse> is required. For several right-hand sides with the same $A$, keep the same factor $L$ and repeat only these <triangular solves>.
Back to article page
