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