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?

  • $\begingroup$ 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. $\endgroup$ Commented Dec 29, 2013 at 5:33
  • 1
    $\begingroup$ @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 :( $\endgroup$
    – suncup224
    Commented Dec 29, 2013 at 5:40
  • $\begingroup$ 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 $\endgroup$ Commented Dec 29, 2013 at 5:54
  • $\begingroup$ 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$ $\endgroup$
    – suncup224
    Commented Dec 29, 2013 at 6:04
  • $\begingroup$ I don't remember it being that simple. Also I don't understand your proof. $\endgroup$ Commented Dec 29, 2013 at 6:06

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .