8
$\begingroup$

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?

$\endgroup$
10
  • $\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$
    – Stephen Montgomery-Smith
    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
    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$
    – Stephen Montgomery-Smith
    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
    Dec 29, 2013 at 6:04
  • $\begingroup$ I don't remember it being that simple. Also I don't understand your proof. $\endgroup$
    – Stephen Montgomery-Smith
    Dec 29, 2013 at 6:06

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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