Existence of the Cholesky factorization

• We prove that the algorithm completes and that the Cholesky factorization exists.
• This decomposition is also unique.

To prove existence, we use a proof by induction. Let’s start with $k=1$. We have

$$a_{11}=e_1^{T}A{e}_1>0$$

This holds because $A$ is SPD. So we can write:

$$A=[\sqrt{a_{11}}][\sqrt{a_{11}}]=L{L}^T$$

Now, let’s consider a matrix of size $n$ and let’s assume that the Cholesky factorization exists for SPD matrices of size $n-1$.

Let’s perform one step of the factorization starting from $A$. We will end up with a matrix of size $n-1$ and will be able to use the induction hypothesis.

The first step of Cholesky can be written in this equivalent form:

$$A=\left(\begin{array}{cc}{a}_{11}& c^T\\ c& B\end{array}\right)=\left(\begin{array}{cc}1& 0\\ \frac{1}{a_{11}}c& I\end{array}\right)\left(\begin{array}{cc}{a}_{11}& 0\\ 0& B-\frac{1}{a_{11}}c{c}^T\end{array}\right)\left(\begin{array}{cc}1& \frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)$$

See the section Matrix block operations for details on this type of block operations.

Note that the first column of $L$ is equal to:

$$l_{,1}=\frac{a_{,1}}{\sqrt{a_{11}}}=\sqrt{a_{11}}\left(\begin{array}{c}1\\ \frac{1}{a_{11}}c\end{array}\right)$$

We are using the first column of $L$ with a scaling. This is the first step in the Cholesky factorization.

We prove that $B-(1/a_{11})c{c}^T$ is SPD.

1. That matrix is symmetric.
2. We now prove that $y^T(B-(1/a_{11})c{c}^T)y>0$ for any $y\ne 0.$

Check that for any row vector $z$ (see the section Matrix block operations for relevant information):

$$\left(\begin{array}{cc}1& z\\ 0& I\end{array}\right)\left(\begin{array}{cc}1& -z\\ 0& I\end{array}\right)=I$$

Use the equation above:

$$\left(\begin{array}{cc}1& \frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)\left(\begin{array}{cc}1& -\frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)=I$$

Define

$$X=\left(\begin{array}{cc}1& -\frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)$$

Recall that:

$$A=\left(\begin{array}{cc}1& 0\\ \frac{1}{a_{11}}c& I\end{array}\right)\left(\begin{array}{cc}{a}_{11}& 0\\ 0& B-\frac{1}{a_{11}}c{c}^T\end{array}\right)\left(\begin{array}{cc}1& \frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)$$

Using the results above:

$$X^{T}AX=\left(\begin{array}{cc}{a}_{11}& 0\\ 0& B-\frac{1}{a_{11}}c{c}^T\end{array}\right)$$

Take any

$$x=\left(\begin{array}{c}0\\ y\end{array}\right)\ne 0$$

Then:

$$x^T{X}^{T}AXx=(Xx{)}^{T}A(Xx)>0$$

because $A$ is SPD. But also:

$$x^T{X}^{T}AXx=y^T(B-(1/a_{11})c{c}^T)y$$

So from the results above

$$y^T(B-(1/a_{11})c{c}^T)y>0$$

for any $y\ne 0$. So $B-(1/a_{11})c{c}^T$ is SPD.

By the induction hypothesis, $B-(1/a_{11})c{c}^T$ has a Cholesky factorization since its size is $n-1$:

$$B-(1/a_{11})c{c}^T=L_1{L}_1^T$$

We get for $A$ (using block notations):

$$\begin{array}{rl}A& =\left(\begin{array}{cc}1& 0\\ \frac{1}{a_{11}}c& I\end{array}\right)\left(\begin{array}{cc}{a}_{11}& 0\\ 0& B-\frac{1}{a_{11}}c{c}^T\end{array}\right)\left(\begin{array}{cc}1& \frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)\\ & \\ & =\left(\begin{array}{cc}1& 0\\ \frac{1}{a_{11}}c& I\end{array}\right)\left(\begin{array}{cc}{a}_{11}& 0\\ 0& L_1{L}_1^T\end{array}\right)\left(\begin{array}{cc}1& \frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)\\ & \\ & =\left(\begin{array}{cc}1& 0\\ \frac{1}{a_{11}}c& I\end{array}\right)\left(\begin{array}{cc}\sqrt{a_{11}}& 0\\ 0& L_1\end{array}\right)\left(\begin{array}{cc}\sqrt{a_{11}}& 0\\ 0& L_1^T\end{array}\right)\left(\begin{array}{cc}1& \frac{1}{a_{11}}{c}^T\\ 0& I\end{array}\right)\\ & =L{L}^T\end{array}$$

with

$$L=\left(\begin{array}{cc}1& 0\\ \frac{1}{a_{11}}c& I\end{array}\right)\left(\begin{array}{cc}\sqrt{a_{11}}& 0\\ 0& L_1\end{array}\right)=\left(\begin{array}{cc}\sqrt{a_{11}}& 0\\ \frac{1}{\sqrt{a_{11}}}c& L_1\end{array}\right)$$

Matrix $L$ is lower triangular as expected. This concludes the proof. $\square$

To prove uniqueness, let’s assume that we have two such factorizations:

$$L_1{L}_1^T=L_2{L}_2^T$$

This implies that

$$L_2^{-1}{L}_1=L_2^T{L}_1^{-T}$$

where ${}^{-T}$ denotes the transpose of the inverse. The left-hand side is a lower-triangular matrix while the right-hand side is an upper-triangular matrix. Therefore both matrices are diagonal. If we match the diagonal terms on the left and right-hand sides we find that:

$$(\frac{[L_1{]}_{ii}}{[L_2{]}_{ii}}{)}^2=1$$

This implies that $|[L_1{]}_{ii}|=|[L_2{]}_{ii}|.$ But both terms are positive, so they are equal. So

$$L_2^{-1}{L}_1=I$$

and the matrices are equal. $\square$

Symmetric Positive Definite Matrices, Cholesky factorization