Cholesky Decomposition - Proof For Positive Semi-definite Matrices

Proof For Positive Semi-definite Matrices

The above algorithms show that every positive definite matrix A has a Cholesky decomposition. This result can be extended to the positive semi-definite case by a limiting argument. The argument is not fully constructive, i.e., it gives no explicit numerical algorithms for computing Cholesky factors.

If A is an n-by-n positive semi-definite matrix, then the sequence {A_k} = {A + (1/k)I_n} consists of positive definite matrices. (This is an immediate consequence of, for example, the spectral mapping theorem for the polynomial functional calculus.) Also,

A_k → A

in operator norm. From the positive definite case, each A_k has Cholesky decomposition A_k = L_kL*_k. By property of the operator norm,

So {L_k} is a bounded set in the Banach space of operators, therefore relatively compact (because the underlying vector space is finite dimensional). Consequently it has a convergent subsequence, also denoted by {L_k}, with limit L. It can be easily checked that this L has the desired properties, i.e. A = LL* and L is lower triangular with non-negative diagonal entries: for all x and y,

Therefore A = LL*. Because the underlying vector space is finite dimensional, all topologies on the space of operators are equivalent. So L_k tends to L in norm means L_k tends to L entrywise. This in turn implies that, since each L_k is lower triangular with non-negative diagonal entries, L is also.