Every definite positive matrix admits Cholesky decomposition: help with Demmel's proof

Question

I am studying Cholesky decomposition by using the book "Applied Numerical Linear Algebra" of Demmel. In particular, I am trying to understand why a positive definite matrix $A\in\mathbb{R}^{n\times n}$ admits a Cholesky decomposition.

In the book, the proof is made by induction on the dimension of matrix $n$. I am stuck at the second equality below.

If $n=1$, choose $ l_{11} = \sqrt{a_{11}}$ which exists since $a_{11} > 0$. As with Gaussian Elimination it suffices to understand the block 2-by-2 case. Write

$$ A = \begin{bmatrix} a_{11} & A_{12} \\ A_{21}^T & A_{22} \end{bmatrix} $$

$$ = \begin{bmatrix} \sqrt{a_{11}} & 0 \\ \frac{A_{21}^T}{a_{11}} & I \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & \tilde{A}_{22} \end{bmatrix} \begin{bmatrix} \sqrt{a_{11}} & \frac{A_{12}}{a_{11}} \\ 0 & I \end{bmatrix}$$

$$ = \begin{bmatrix} a_{11} & A_{12} \\ A_{21}^T & \tilde{A_{22}} + \frac{A_{12}^TA_{12}}{a_{11}} \end{bmatrix} $$

Why can the matrix be written as the product of those three matrices? What is the point?

Could anyone please help me?

Thank you in advance!

Answer 1

This decomposition tells us three things:

1. You can calculate $\widetilde{A}_{22}$ easily from $A$: we have $\widetilde{A}_{22}=A_{22}-\frac{A_{12}^TA_{12}}{a_{11}}$.
2. $\widetilde{A}_{22}$ is positive definite, because the positive definite matrix $A$ is congruent to the direct sum of $1$ and $A_{22}$. Therefore, by induction assumption, $\widetilde{A}_{22}$ admits a Cholesky decomposition $\widetilde{A}_{22}=\widetilde{L}\widetilde{L}^T$.
3. Now you get a Cholesky decomposition $LL^T$ of $A$ automatically, where $$ L=\pmatrix{\sqrt{a_{11}}&0\\ \frac{A_{12}^T}{\sqrt{a_{11}}}&I}\pmatrix{1&0\\ 0&\widetilde{L}} =\pmatrix{\sqrt{a_{11}}&0\\ \frac{A_{12}^T}{\sqrt{a_{11}}}&\widetilde{L}}. $$