Editing Cholesky decomposition (section)

== Proof for positive semi-definite matrices ==

=== Proof by limiting argument ===
The above algorithms show that every positive definite matrix <math display=inline> \mathbf{A} </math> 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 <math display=inline> \mathbf{A} </math> is an <math display=inline> n \times n </math> [[Positive-definite matrix|positive semi-definite matrix]], then the sequence <math display="inline"> \left(\mathbf{A}_k\right)_k := \left(\mathbf{A} + \frac{1}{k} \mathbf{I}_n\right)_k </math> consists of [[Positive-definite matrix|positive definite matrices]]. (This is an immediate consequence of, for example, the spectral mapping theorem for the polynomial functional calculus.) Also,
<math display=block> 
\mathbf{A}_k \rightarrow \mathbf{A}
\quad \text{for} \quad
k \rightarrow \infty
</math> 
in [[operator norm]]. From the positive definite case, each <math display=inline> \mathbf{A}_k </math> has Cholesky decomposition <math display=inline> \mathbf{A}_k = \mathbf{L}_k\mathbf{L}_k^* </math>. By property of the operator norm,

<math display=block>\| \mathbf{L}_k \|^2 \leq \| \mathbf{L}_k \mathbf{L}_k^* \| = \| \mathbf{A}_k \| \,.</math>

The <math display=inline>\leq</math> holds because <math display=inline>M_n(\mathbb{C})</math> equipped with the operator norm is a C* algebra. So <math display=inline> \left(\mathbf{L}_k \right)_k</math> 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 <math display=inline> \left( \mathbf{L}_k \right)_k</math>, with limit <math display=inline> \mathbf{L}</math>. 
It can be easily checked that this <math display=inline> \mathbf{L}</math> has the desired properties, i.e. <math display=inline> \mathbf{A} = \mathbf{L}\mathbf{L}^* </math>, and <math display=inline> \mathbf{L}</math> is lower triangular with non-negative diagonal entries: for all <math display=inline> x</math> and <math display=inline> y</math>,

<math display=block> 
\langle \mathbf{A} x, y \rangle 
= \left\langle \lim \mathbf{A}_k x, y \right\rangle 
= \langle \lim \mathbf{L}_k \mathbf{L}_k^* x, y \rangle 
= \langle \mathbf{L} \mathbf{L}^*x, y \rangle \,. 
</math>

Therefore, <math display=inline> \mathbf{A} = \mathbf{L}\mathbf{L}^* </math>. 
Because the underlying vector space is finite-dimensional, all topologies on the space of operators are equivalent. 
So <math display=inline> \left( \mathbf{L}_k \right)_k</math> tends to <math display=inline> \mathbf{L}</math> in norm means <math display=inline> \left( \mathbf{L}_k \right)_k</math> tends to <math display=inline> \mathbf{L}</math> entrywise. 
This in turn implies that, since each <math display=inline> \mathbf{L}_k</math> is lower triangular with non-negative diagonal entries, <math display=inline> \mathbf{L}</math> is also.

=== Proof by QR decomposition ===

Let <math display=inline>\mathbf{A}</math> be a [[Positive-definite matrix|positive semi-definite]] Hermitian matrix. Then it can be written as a product of its [[Square root of a matrix|square root matrix]], <math display=inline>\mathbf{A} = \mathbf{B} \mathbf{B}^*</math>. Now [[QR decomposition]] can be applied to <math display=inline>\mathbf{B}^*</math>, resulting in <math display=inline>\mathbf{B}^* = \mathbf{Q}\mathbf{R}</math>
, where <math display=inline>\mathbf{Q}</math> is unitary and <math display=inline>\mathbf{R}</math> is upper triangular. Inserting the decomposition into the original equality yields <math display=inline>A = \mathbf{B} \mathbf{B}^* = (\mathbf{QR})^*\mathbf{QR} = \mathbf{R}^*\mathbf{Q}^*\mathbf{QR} = \mathbf{R}^*\mathbf{R}</math>. Setting <math display=inline>\mathbf{L} = \mathbf{R}^*</math> completes the proof.