## Unit5.4.4Proof of the Cholesky Factorizaton Theorem

Partition, once again,

\begin{equation*} A \rightarrow \FlaTwoByTwoSingleLine{ \alpha_{11} }{ a_{21}^H }{ a_{21} }{ A_{22} }. \end{equation*}

The following lemmas are key to the proof of the Cholesky Factorization Theorem:

Since $A$ is Hermitian so are $A_{22}$ and $A_{22} - l_{21} l_{21}^H \text{.}$

Let $x_2 \in \C^{n-1}$ be an arbitrary nonzero vector. Define $x = \FlaTwoByOneSingleLine{ \chi_1 }{ x_2 }$ where $\chi_1 = - a_{21}^H x_2 / \alpha_{11} \text{.}$ Then, since clearly $x \neq 0 \text{,}$

\begin{equation*} \begin{array}{l} 0 \\ ~~~\lt~~~~ \lt A \mbox{ is HPD } \gt \\ x^H A x \\ ~~~=~~~~ \lt \mbox{ partition } \gt \\ \FlaTwoByOneSingleLine{ \chi_1 }{ x_2 }^H \FlaTwoByTwoSingleLine{ \alpha_{11}}{ a_{21}^H }{ a_{21} }{ A_{22} } \FlaTwoByOneSingleLine{ \chi_1 }{ x_2 } \\ ~~~=~~~~ \lt \mbox{ partitioned multiplication } \gt \\ \FlaTwoByOneSingleLine{ \chi_1 }{ x_2 }^H \FlaTwoByOneSingleLine{ \alpha_{11} \chi_1 + a_{21}^H x_2 } { a_{21} \chi_1 + A_{22} x_2 } \\ ~~~=~~~~ \lt \mbox{ partitioned multiplication } \gt \\ \alpha_{11} \overline \chi_1 \chi_1 + \bar \chi_1 a_{21}^H x_2 + x_2^H a_{21} \chi_1 + x_2^H A_{22} x_2 \\ ~~~=~~~~ \lt \mbox{ linear algebra } \gt \\ \alpha_{11} \frac{a_{21}^H x_2}{\alpha_{11}} \frac{x_{2}^H a_{21}}{\alpha_{11}} {\color{black} {- \frac{x_{2}^H a_{21}}{\alpha_{11}}}} a_{21}^H x_2 - x_2^H a_{21} {\color{black} {\frac{a_{21}^H x_2}{\alpha_{11}} + x_2^H A_{22} x_2 }}\\ ~~~=~~~~ \lt ~~~\mbox{ since } x_2^H a_{21}, a_{21}^H x_2 \mbox{ are scalars and hence can move around; } \alpha_{11} / \alpha_{11} = 1 \gt \\ x_2^H a_{21} \frac{ a_{21}^H x_2 }{\alpha_{11}} - x_2^H a_{21} \frac{ a_{21}^H x_2 }{\alpha_{11}} - x_2^H a_{21} \frac{ a_{21}^H x_2 }{\alpha_{11}} + x_2^H A_{22} x_2 \\ ~~~=~~~~ \lt \mbox{ cancel terms; factor out } x_2^H \mbox{ and } x_2 \gt \\ x_2^H ( A_{22} - \frac{a_{21} a_{21}^H}{\alpha_{11}} ) x_2 \\ ~~~~=~~~~ \lt \mbox{ simplify } \gt \\ x_2^H ( A_{22} - l_{21} l_{21}^H ) x_2. \end{array} \end{equation*}

We conclude that $A_{22} - l_{21} l_{21}^H$ is HPD.

Proof by induction.

1. Base case: $n = 1 \text{:}$

Clearly the result is true for a $1 \times 1$ matrix $A = \alpha_{11} \text{:}$ In this case, the fact that $A$ is HPD means that $\alpha_{11}$ is real and positive and a Cholesky factor is then given by $\lambda_{11} = \sqrt{\alpha_{11}} \text{,}$ with uniqueness if we insist that $\lambda_{11}$ is positive.

2. Inductive step: Assume the result is true for $n = k \text{.}$ We will show that it holds for $n = k+1 \text{.}$

Let $A \in \C^{(k+1) \times (k+1)}$ be HPD. Partition

\begin{equation*} A = \left( \begin{array}{c c} \alpha_{11} \amp a_{21}^H \\ a_{21} \amp A_{22} \end{array} \right) \mbox{ and } L = \left( \begin{array}{c c} \lambda_{11} \amp 0 \\ l_{21} \amp L_{22} \end{array} \right) . \end{equation*}

Let

• $\lambda_{11} = \sqrt{\alpha_{11}}$ (which is well-defined by Lemma 5.4.4.1,

• $l_{21} = a_{21} / \lambda_{11} \text{,}$

• $A_{22} - l_{21} l_{21}^H = L_{22} L_{22}^H$ (which exists as a consequence of the Inductive Hypothesis and Lemma 5.4.4.2.)

Then $L$ is the desired Cholesky factor of $A \text{.}$

3. By the Principal of Mathematical Induction, the theorem holds.