# Why does the Cholesky decomposition exist?

From wikipedia, given any matrix $A$, we can sometimes decompose $A = LU$ using Gaussian elimination. Other times, a permutation matrix is needed, giving $PA = LU$.

If $A$ is Hermitian positive-definite, I can show that IF no permutation matrix is needed, then Gaussian elimination gives $A=LU$ which I can eventually massage and get the Cholesky decomposition $A=LL^*$. However, it seems that Hermitian positive-definite matrices are special in that no permutaiton matrix is ever needed, and hence the Cholesky decomposition always exist. Why?

• It is in Fundamentals of Matrix Computations by David S. Watkins. It is a beautiful proof, but perhaps a little too much to write down here. Dec 29, 2013 at 5:33
• @Stephen: thanks for the reference. Perhaps a hint or a summary would help? I do not have access to any libraries that would have math books :( Dec 29, 2013 at 5:40
• It uses something called the Schur complement. I tried using google to find online proofs. Maybe this would work? cis.upenn.edu/~jean/schur-comp.pdf Dec 29, 2013 at 5:54
• Oh actually, I think I figured out a proof. Suppose that you are performing elimination and at some stage, the $k^{th}$ pivot came out as zero. Look at the elimination matrix $E$ thus far, and let $x$ be the $k^{th}$ row of $E$. Then $xAx^* = 0$, contradicting the positive-definiteness of $A$ Dec 29, 2013 at 6:04
• I don't remember it being that simple. Also I don't understand your proof. Dec 29, 2013 at 6:06

The diagonal entries of $U$ in $A=LU$ are quotients of successive main diagonal minors of the matrix $A$. If $A$ is positive definite, the main minors are all positive. Sometimes this is called the Hurwitz criterion.
Put the diagonal elements of $U$ into a diagonal matrix $D$, then $A=LU=LDL^*$. Which again shows that the Cholesky decomposition works, since the critical numbers of the algorithm are these diagonal entries.