Skip to main content

Subsection 5.4.4 Proof 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.

login