8
$\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$
15
$\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.

| cite | improve this answer | |
$\endgroup$

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.