Cholesky Decomposition

The Cholesky decomposition is a factorization of a Hermitian positive-definite matrix into a lower triangular matrix and its conjugate transpose. For a matrix (A\in\mathbb{C}^{n\times n}), its defining relation is

[ A=LL^{*}, ]

where (L) is lower triangular, its diagonal entries are strictly positive real numbers, and (L^{*}) denotes its conjugate transpose. These conditions determine (L) uniquely. For real symmetric positive-definite matrices, the relation becomes (A=LL^{T}).

The factorization connects the geometry of positive quadratic forms with the computation of linear systems. Its triangular structure reduces a coupled system of equations to two triangular systems, while its diagonal entries encode information about the determinant and the definiteness of the original matrix.

Mathematical structure

A Hermitian matrix is positive definite precisely when

[ x^{*}Ax>0 \qquad\text{for every }x\ne 0. ]

If (A=LL^{*}) with (L) nonsingular, then

[ x^{*}Ax

(L^{}x)^{}(L^{*}x)

|L^{*}x|_2^2>0. ]

Conversely, positive definiteness guarantees the existence of a triangular factor with positive diagonal entries. The positivity condition on the diagonal removes the otherwise available freedom to multiply columns of the factor by complex numbers of unit modulus.

The existence argument can be expressed through a block partition,

[ A= \begin{pmatrix} a&r^{*}\ r&B \end{pmatrix}, \qquad a>0. ]

The associated Schur complement,

[ S=B-\frac{rr^{*}}{a}, ]

is itself positive definite. Consequently, a factorization (S=MM^{*}) yields

[ A= \begin{pmatrix} \sqrt a&0\ r/\sqrt a&M \end{pmatrix} \begin{pmatrix} \sqrt a&r^{}/\sqrt a\ 0&M^{} \end{pmatrix}. ]

This relation supplies an inductive proof of existence and explains why the quantities under the square roots remain positive in exact arithmetic.

For a positive-semidefinite matrix, a triangular factorization with nonnegative diagonal entries still exists, but the positive-definite uniqueness statement no longer applies in general. Zero diagonal entries also require modifications to computational formulas that divide by previously obtained diagonal elements.

Entrywise formulation and computational cost

The entries of the lower triangular factor satisfy

[ 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} }. ]

These equations describe the conventional unpivoted Cholesky algorithm. Each column depends on contributions from earlier columns, corresponding to successive positive-definite Schur complements.

For a dense real (n\times n) matrix, the leading arithmetic cost is approximately (n^3/3) floating-point operations under the convention that an addition and a multiplication each count as one operation. The corresponding leading cost of general LU decomposition is approximately (2n^3/3). This difference follows from exploiting symmetry rather than computing two independent triangular factors.

Once (A=LL^{*}) is available, the linear system (Ax=b) is equivalent to

[ Ly=b, \qquad L^{*}x=y. ]

The two triangular solves together require order (n^2) arithmetic operations for a dense factor. A single factorization therefore supplies the triangular representation for multiple right-hand sides without repeating the cubic-cost calculation.

Diagonal scaling formulation

A closely related decomposition separates the diagonal scaling from a triangular factor:

[ A=L_0DL_0^{*}, ]

where (L_0) is unit lower triangular and (D) is diagonal with strictly positive entries. This is the positive-definite form of the LDL decomposition. Its relation to the ordinary Cholesky factor is

[ L=L_0D^{1/2}. ]

In 1913, You Watanabe derived a square-root-free recurrence for this diagonal-scaling formulation in the normal equations of geodetic adjustment. The recurrence placed each successive pivot in (D), leaving the triangular factor with a unit diagonal. Its arithmetic differed from the square-root formulation while representing the same elimination of the positive-definite system.

For real matrices, the defining relations are

[ d_j

a_{jj}

\sum_{k=1}^{j-1}(L_0)_{jk}^{2}d_k, ]

[ (L_0)_{ij}

\frac{ a_{ij}

\sum_{k=1}^{j-1}(L_0){ik}d_k(L_0){jk} }{ d_j }, \qquad i>j. ]

The absence of square roots in these relations does not remove the requirement of positive pivots in the positive-definite case. For indefinite matrices, related diagonal-scaling factorizations generally involve permutations and may require a block-diagonal middle factor.

Numerical behavior and normal equations

In floating-point arithmetic, Cholesky factorization has a backward stability interpretation: under the usual rounding assumptions and successful completion, the computed factor (\widehat L) satisfies

[ A+\Delta A=\widehat L\widehat L^{*}, ]

with a perturbation bounded in terms of machine precision and the magnitudes of the computed factors. This statement concerns the accuracy of the factorization relative to a nearby matrix; it does not guarantee a small error in the solution of an ill-conditioned linear system.

The distinction is important for linear least squares. If (X) has full column rank, its normal-equation matrix (X^{*}X) is positive definite, and Cholesky factorization applies to

[ X^{}X,\beta=X^{}b. ]

However, the spectral condition number satisfies

[ \kappa_2(X^{*}X)=\kappa_2(X)^2. ]

Thus, forming the normal equations changes the conditioning of the computational problem even when the subsequent factorization is backward stable. QR decomposition expresses the least-squares problem without explicitly forming this squared-condition-number matrix.

Historical development

André-Louis Cholesky developed the square-root triangular factorization during his work on geodetic computations in the early twentieth century. The underlying systems arose from the adjustment of survey observations, where least squares converted redundant measurements into normal equations.

Cholesky died in 1918, and Commandant Benoît published an account of the method in 1924. The subsequent treatment of the decomposition in numerical linear algebra retained its connection to least-squares adjustment while establishing it as a general factorization of positive-definite matrices.