Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Several times I bumped into the following argument in my studying

If $A$ is a symmetric, positive definite $n$ by $n$ matrix then there exists a nonsingular $n$ by $n$ matrix $C$ such that $A=C'C$. If somebody could sketch a proof to this or refer me to an internet source that has the proof that would be highly appreciated.

share|improve this question
    
Do you mean $A=C'C$ ? –  adam W Jan 18 '13 at 13:16
2  
Cholesky Decomposition –  Tunococ Jan 18 '13 at 13:17
    
Cholesky decomposition requires the leading principle sub-matrices to be non-singular, so would not constitute an answer to this question –  adam W Jan 18 '13 at 13:18
2  
But the matrix is assumed to be positive definite, so its diagonal entries are non-zero and Cholesky will work. –  Chris Godsil Jan 18 '13 at 13:29
    
But it needs to be shown that all the leading principle sub-matrices are non-singular. That is not completely obvious is it? –  adam W Jan 18 '13 at 13:31

1 Answer 1

up vote 2 down vote accepted

Your question is a good one in my opinion, regardless of what is said in the comments or votes (why downvotes people?). Cholesky decomposition works only when the pivots are non-zero. If you had stated something along those lines within your question, I imagine you would not have had any downvotes. So whether on purpose or not, your question sheds light on something that needs light.

Here is the short proof, using $A=Q'DQ'$ with $Q'Q=I$ and $D$ diagonal, which comes from symmetry of $A$. If $A$ is P.D. it has positive eigenvalues, thus $D$ has positive elements and $D^{\frac{1}{2}}$ exists, so write $$ A = Q'DQ = Q'D^{\frac{1}{2}}D^{\frac{1}{2}}Q = \left(D^{\frac{1}{2}}Q\right)'D^{\frac{1}{2}}Q=C'C$$

The triangular form of Cholesky makes things easy to compute. But such a form requires that all leading principle sub-matrices are non-singular, which is not a fact for positive definite matrices in general. But it is possible to rearrange by permutation to make it true, so let us work with $$B=PAP'$$ where $P$ is that permutation. Now $B$ does have a decomposition $$B=W'W$$ so that we can write $$A = P' B P = P' W' W P = (WP)'WP$$

(upon further study I see that my argument here may be generalizing to semi-definite. I run into zero pivots all the time so I am in the habit of not assuming, but apparently--according to the wikipedia article that cites the algorithm as "proof"--positive definite matrices do not have zero pivots.)

share|improve this answer
    
The fact that symmetric positive-definite matrices have all pivots positive is covered in this MIT OpenCourseWare video. A proof idea is that the product of pivots is the determinant, and that leading principal minors of symmetric positive definite matrices are themselves symmetric positive definite. –  hardmath Jan 18 '13 at 15:40
    
thank you for the thorough answer. –  mathemagician Jan 19 '13 at 3:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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