Cholesky decomposition ($A=L{L}^{\ast }$)

Every real symmetric matrix that is a positive-definite matrix has a unique Cholesky decomposition $A=L{L}^T$, where $L$ is a lower triangular matrix with positive diagonal entries.^[ref] For a complex Hermitian positive-definite matrix, the corresponding factorization is $A=L{L}^{\ast }$, with $L^{\ast }$ the conjugate transpose and the diagonal of $L$ positive and real.^[ref] The factorization turns a linear system into two triangular systems.

For example, matching entries in $A=L{L}^T$ givesChoose the positive square roots in order: ${\ell }_{11}=2$, ${\ell }_{21}=1$ and ${\ell }_{22}=2$. ThereforeThe 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.

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^{T}x=y$: $2x_2=4$ and $2x_1+x_2=4$, giving $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.

For any real vector $u$, a Cholesky decomposition gives the quadratic form identitySince $L$ is an invertible matrix, this squared Euclidean norm is positive whenever $u\ne 0$. The factorization thus certifies positive definiteness and gives coordinates in which the quadratic form is a sum of ordinary squares. For the matrix above,The level set $u^{T}Au=1$ is an ellipse; the linear map $z=L^{T}u$ sends it to the unit circle. The points $u=(1/2,0{)}^T$ and $u=(-1/4,1/2{)}^T$ go to $(1,0{)}^T$ and $(0,1{)}^T$, respectively.

The same factor works in the reverse direction for Gaussian random vectors. If $Z$ has independent unit-variance, zero-mean Gaussian random variables as coordinates, $X=LZ$ has covariance matrix $L{L}^T=A$. In this example $X_1=2Z_1$ and $X_2=Z_1+2Z_2$: their variances are $4$ and $5$, while their covariance is $2$. This is a concrete way to generate specified correlations from independent draws.

A triangular factor is not generally a square root of a matrix in the sense $B^2=A$. Here $L^2=\left(\begin{array}{cc}4& 0\\ 4& 4\end{array}\right)\ne A$. The Cholesky decomposition uses the product with the transpose, which is also what makes the quadratic form a squared Euclidean norm.

André-Louis Cholesky developed his calculation in the setting of geodetic adjustment: measured angles and lengths must satisfy geometric relations, while corrections should be small. The manuscript reproduced in Claude Brezinski's study is titled Sur la résolution numérique des systèmes d’équations linéaires and ends with the date 2 December 1910 at Vincennes. The manuscript reports a 56-equation calculation adjusting altitudes in an Algerian triangulation network. Its date establishes when this written account existed, rather than an exact invention date.^[ref]

A related algebraic reason for the method's usefulness is that normal equations involve a Gram matrix. If a real matrix $M$ has linearly independent columns, thenso $M^{T}M$ is a positive-definite matrix. That gives the structure needed by a Cholesky decomposition. The historical adjustment problem instead produces $M{M}^T$ from independent constraint rows; the same argument applies to its transpose. In numerical least squares, explicitly forming normal equations squares the condition number of a full-column-rank design matrix; a QR decomposition can therefore be preferable for accuracy. Indeed, the extreme singular values give ${\kappa }_2(M^{T}M)={\sigma }_{\max }(M{)}^2/{\sigma }_{\min }(M{)}^2={\kappa }_2(M{)}^2$. The factorization remains useful when a positive-definite matrix is already the natural input.

Given a Cholesky decomposition $A=L{L}^T$, a rank-one Cholesky update computes a triangular factor of $A+x{x}^T$ in $O(n^2)$ operations without refactorizing the matrix from scratch.