Cholesky decomposition is a matrix factorization that expresses a real symmetric positive-definite matrix as (A=LL^T), where (L) is lower triangular with strictly positive diagonal entries. For a complex Hermitian matrix, the corresponding expression is (A=LL^), where (L^) denotes the conjugate transpose. It is a standard method in numerical linear algebra for exploiting positive definiteness when solving equations and performing related computations. (netlib.org)
Definition and mathematical properties
For an (n\times n) Hermitian matrix (A), positive definiteness means [ x^*Ax>0 \qquad\text{for every nonzero }x\in\mathbb C^n. ] Every such matrix has a unique Cholesky factor (L) when its diagonal entries are required to be positive real numbers. An equivalent upper-triangular convention writes (A=U^U), with (U=L^). For real matrices, conjugate transposition reduces to ordinary transposition. (nhigham.com)
The converse follows directly: if (A=LL^*) and (L) has positive diagonal entries, then (L) is invertible and [ x^*Ax=|L^*x|_2^2>0 ] for every nonzero (x). Thus the factorization converts a positive quadratic expression into a squared Euclidean norm. (statlect.com)
The triangular factor is not generally a matrix square root in the sense (L^2=A). Its defining property is the product with its transpose or conjugate transpose. Uniqueness depends on the positive-diagonal convention; without that normalization, signs or complex phases can be redistributed between corresponding factor columns. (statlect.com)
Construction and example
The elementary algorithm computes the factor column by column. In the complex case, [ l_{jj} =\sqrt{a_{jj}-\sum_{k=1}^{j-1}|l_{jk}|^2}, ] and, for (i>j), [ l_{ij} =\frac{a_{ij}-\sum_{k=1}^{j-1} l_{ik}\overline{l_{jk}}}{l_{jj}}. ] Entries above the diagonal are zero. In exact arithmetic, positive definiteness ensures that every square-root argument is strictly positive. (statlect.com)
For example, direct multiplication verifies [ \begin{pmatrix} 4&2\ 2&3 \end{pmatrix}
\begin{pmatrix} 2&0\ 1&\sqrt2 \end{pmatrix} \begin{pmatrix} 2&1\ 0&\sqrt2 \end{pmatrix}. ] The first column gives (l_{11}=2) and (l_{21}=1); the remaining diagonal entry is (\sqrt{3-1}=\sqrt2).
The construction is closely related to Gaussian elimination, specialized to preserve symmetry. At each stage, the remaining matrix is updated by subtracting contributions from previously computed columns. Positive definiteness is preserved in the relevant Schur complements, so ordinary positive-definite Cholesky factorization requires no pivoting. (nhigham.com)
Computational cost and implementation
For a dense real matrix, conventional Cholesky factorization requires approximately (n^3/3) floating-point operations, counting multiplication and addition separately. This is about half the leading operation count of general LU decomposition. Its computational complexity is therefore cubic, while storing the triangular factor requires (n(n+1)/2) entries. These counts follow from the scalar recurrences and their triangular summation ranges. (statlect.com)
High-performance implementations use blocked algorithms: they factor diagonal blocks, solve triangular matrix equations, and update trailing blocks using matrix–matrix operations. LAPACK supplies these routines through its POTRF family, using Level 3 Basic Linear Algebra Subprograms. Only the selected upper or lower triangle of the input is needed. (netlib.org)
Linear systems and determinants
To solve a linear system (Ax=b), first compute (A=LL^*), then solve [ Ly=b,\qquad L^*x=y ] by forward and backward substitution. Each additional right-hand side costs (O(n^2)) operations after factorization. The same factor can therefore be reused, without explicitly constructing an inverse matrix. (gaussianprocess.org)
The determinant is also immediately available: [ \det A=\prod_{i=1}^n l_{ii}^{,2}, \qquad \log\det A=2\sum_{i=1}^n\log l_{ii}. ] Evaluating the logarithmic form avoids directly multiplying potentially very large or very small diagonal factors. (gaussianprocess.org)
Numerical behavior and extensions
Cholesky factorization has strong numerical stability properties. Under standard assumptions for floating-point arithmetic, a successfully computed factor (\widehat L) satisfies [ A+\Delta A=\widehat L\widehat L^*, ] where the perturbation is small relative to (A), with bounds depending on dimension and machine precision. Nevertheless, a mathematically positive-definite matrix can suffer numerical breakdown when it is sufficiently close to singularity. A large condition number also limits the accuracy of subsequent solutions despite a small backward error. (nhigham.com)
For positive-semidefinite matrices, triangular factors may exist with zero diagonal entries, but strict-positive-diagonal uniqueness no longer applies. Pivoted Cholesky uses simultaneous row and column permutations; it can expose matrix rank and support truncated low-rank approximations. Indefinite symmetric matrices instead generally require an (LDL^*)-type factorization with suitable pivoting. (nhigham.com)
Statistical applications
For a positive-definite covariance matrix (\Sigma=LL^T), transforming a vector (z) of independent standard normal variables by (x=\mu+Lz) produces a multivariate normal distribution with mean (\mu) and covariance (\Sigma). This follows from the covariance transformation rule and underlies Gaussian sampling. (gaussianprocess.org)
In Gaussian process models, Cholesky factors support predictions and evaluation of the marginal likelihood, combining triangular solves with log-determinants. The dense factorization’s cubic cost motivates approximation methods for large datasets. (gaussianprocess.org)