11
$\begingroup$

Given a real Hermitian positive-definite matrix $A$ is a decomposition of the form $A=L L^T$ where L is a lower triangular matrix with positive diagonal entries. I read some proofs about the existence of Cholesky decomposition. Most of them start from LDU decomposition. Then the proof shows that $U^T=L$ and $A=LDU=LD^{\frac{1}{2}} D^{\frac{1}{2}}L^T=CC^T$ where $C=L D^\frac{1}{2}$.

How can I prove the existence of Cholesky decomposition without any preassumption like LDU decomposition exists? Or how can I prove LDU decomposition exists? I know it may be easy. But I just cannot figure it out.

For uniqueness, I think it's not hard to prove.

$\endgroup$
16
$\begingroup$

A classical way is to use the induction. Let $A\in\mathbb{R}^{n\times n}$ be positive definite. It is trivial for $n=1$, just take the square root. Assume that a Cholesky factorization exists for positive definite matrices of dimension $n-1$ and partition $A$ as $$ A = \begin{bmatrix} \tilde{A}&a\\a^T&\alpha \end{bmatrix}, $$ where $\tilde{A}\in\mathbb{R}^{(n-1)\times(n-1)}$. Since a principal submatrix of a positive definite matrix is positive definite, $\tilde{A}$ has a Cholesky factorization $\tilde{A}=\tilde{L}\tilde{L}^T$. Consider $$\tag{1} L_1^{-1}AL_1^{-T} := \begin{bmatrix} \tilde{L}^{-1}&0\\ 0&1 \end{bmatrix} \begin{bmatrix} \tilde{A}&a\\ a^T&\alpha \end{bmatrix} \begin{bmatrix} \tilde{L}^{-T}&0\\ 0&1 \end{bmatrix} = \begin{bmatrix} I&b\\ b^T&\alpha \end{bmatrix} =:B, \quad b:=\tilde{L}^{-1}a. $$ Next we eliminate $b$ by $$\tag{2} L_2^{-1}BL_2^{-T} := \begin{bmatrix} I&0\\-b^T&1 \end{bmatrix} \begin{bmatrix} I&b\\ b^T&\alpha \end{bmatrix} \begin{bmatrix} I&-b\\0&1 \end{bmatrix} = \begin{bmatrix} I&0\\0&\alpha-b^Tb \end{bmatrix} = \begin{bmatrix} I&0\\0&\alpha-a^TA^{-1}a \end{bmatrix}. $$ The diagonal matrix on the right-hand side of (2) is a result of congruence transformations applied to $A$, so the right-hand side of (2) is positive definite and $0<\alpha-a^TA^{-1}a=\lambda^2$ for some real $\lambda$. Set $$ L_3:=\begin{bmatrix}I&0\\0&\lambda\end{bmatrix} $$ so $L_2^{-1}BL_2^{-T}=L_3L_3^T$. From (1) we have $$ L_2^{-1}L_1^{-1}AL_1^{-T}L_2^{-T}=L_3L_3^T, $$ so $$ A=LL^T, \quad L:=L_1L_2L_3 = \begin{bmatrix} \tilde{L}&0\\ 0&1 \end{bmatrix} \begin{bmatrix} I&0\\b^T&1 \end{bmatrix} \begin{bmatrix} I&0\\ 0&\lambda \end{bmatrix} = \begin{bmatrix} \tilde{L}&0\\ b^T&\lambda \end{bmatrix} = \begin{bmatrix} \tilde{L}&0\\ a^T\tilde{L}^{-T}&\lambda \end{bmatrix} $$ is a Cholesky factorization of $A$.

There is a source of non-uniqueness of the factorization in the choice of the sign of $\lambda$. As soon as one requires the signs of the diagonal terms of the Cholesky factors to be fixed (e.g., positive), the factorization is unique.

A simple way to confirm this can be made as follows. Assume $$ A=LL^T=MM^T $$ are two Cholesky factors of $A$. This gives $$\tag{3} I=L^{-1}MM^TL^{-T}=(L^{-1}M)(L^{-1}M)^T $$ and $$\tag{4} (L^{-1}M)=(L^{-1}M)^{-T}. $$ The left-hand and right-hand sides of (4) are, respectively, lower and upper triangular matrices which means that $D:=L^{-1}M$ is both lower and upper triangular and hence a diagonal matrix. From (3) we have $I=D^2$ so $D$ is a diagonal matrix with $\pm 1$ diagonal entries and $M=LD$ meaning that two Cholesky factors of $A$ differ by the signs of their columns.

$\endgroup$
5
  • $\begingroup$ Firstly, this is super helpful, so thank you! I have a follow up question - must one additionally show $0<\alpha−a^TA^{−1}a=\lambda^2, \quad \lambda \in \mathbb{R}$ for this inductive proof to hold? Or is this inherent, in some way? $\endgroup$ – Pablo Jan 4 at 12:11
  • $\begingroup$ @Pablo Thanks, I'm glad it helps. It is already mentioned below (2). The diagonal matrix on the right-hand side is positive definite (and hence $\alpha-a^TA^{-1}a>0$) because it is the result of a congruence transformation applied to $A$ which is supposedly positive definite. This is because such transformations preserve positive definiteness (in fact, they preserve the matrix inertia but the preservation of positive definiteness is much easier to show and it does not need to involve eigenvalues). $\endgroup$ – Algebraic Pavel Jan 4 at 12:57
  • $\begingroup$ ah, okay, I understand now, thank you - I hadn't realised that transformations preserve positive definiteness. The implication here, then, is that showing a $2 \times 2$ matrix has a cholesky decomposition is sufficient to show an $N \times N$ matrix of the some composition also has one? $\endgroup$ – Pablo Jan 4 at 13:02
  • $\begingroup$ @Pablo I'm not sure what do you mean. The proof is based on induction. Assuming a matrix of size $(N-1)\times (N-1)$ has a Cholesky decomposition, it shows that $N\times N$ matrix has one as well. $\endgroup$ – Algebraic Pavel Jan 4 at 14:18
  • $\begingroup$ It was a poorly worded statement, my apologies. It was more a statement (as much for my own benefit) that if one can show (empirically) that the $2\times2$ case works, then thats all we need. $\endgroup$ – Pablo Jan 4 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.