Proof of a fact about symmetric pd matrices

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.

-
Do you mean $A=C'C$ ? –  adam W Jan 18 '13 at 13:16
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
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

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.)

-
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