# How to prove Cholesky decomposition for positive-semidefinite matrices?

According to Cholesky decomposition $A$ is a Hermitian positive-definite matrix if and only if $A=T^*T$ for some upper triangular matrix $T$. When $A$ is positive-semidefinite we have such decomposition too although in this case $T$ is not unique. Anyway, I know how to prove this in first case but my question is that how can we prove it for positive-semidefinite matrices?

• How does your proof happen to go in the positive definite case? – Omnomnomnom Jun 19 '15 at 15:52
• Actually, we can just prove the result using limits. Does the proof given here suit your needs, or did you want further explanation? – Omnomnomnom Jun 19 '15 at 15:55
• OK. I have tried some methods in limiting. For example I have supposed that $A$ be a positive-semidefinite matrix and ε be an arbitrary positive number then $A+εI$ surly is positive-definite matrix and we have Cholesky decomposition for it. But the problem arises when you want to tend ε to zero. It is not as simple as what seems at the first look! – morapi Jun 19 '15 at 22:14

That follows is a particular constructible solution in $T$, an upper triangular matrix with non-negative diagonal.

There is a unique hermitian $\geq 0$ $H$ s.t. $A=H^2$; let $rank(H)=rank(A)=r$. We consider the standard (Maple) $QR$ decomposition of $H$: $H=QR$ where $Q\in M_{n,r},R\in M_{r,n}$, the diagonal of $R$ being positive; moreover $Q^*Q=I_r$. The matrix $T=\begin{pmatrix}R\\0_{n-r,n}\end{pmatrix}$ is upper triangular with non-negative diagonal. Clearly $T^*T=R^*R$ and $A=H^2=R^*Q^*QR=R^*R$ and we are done.

EDIT. Answer to epsilone. This is the QR decomposition for singular real matrices (cf. Horn-Johnson, Matrix analysis, p.112 or Robbin, Matrix algebra using MINImal MATlab p.362). Assume for instance $r=3$; then the method gives the real decomposition $H=[Q_1,Q_2,Q_3][R_1^T,R_2^T,R_3^T]^T=[Q_1R_1+Q_2R_2+Q_3R_3]$ where the $Q_i$ are orthogonal vectors and $R$ is "triangular" with every $i,R_i[i]\not= 0$. If $R_i[i]<0$, then change $Q_i,R_i$ with $-Q_i,-R_i$ and we are done.

Maple 18 gives the result $Q',R'$ that is not exactly in the above form; to obtain $Q,R$, it suffices to keep the first $r$ columns of $-Q'$ and the first $r$ rows of $-R'$ (curiously, note the signum "-"). The method uses Gram Schmidt process and Householder transformations.

Example: Let $A=B^TB$ with the unknown matrix $B=\begin{pmatrix}5&1&3&-2\\4&-3&-4&3\end{pmatrix}$; we find $R\approx -\begin{pmatrix}-6.4&1.09&0.156&-0.312\\0&-2.97&-5&3.59\end{pmatrix}$.

I forget: when the matrices are complex, then replace the eventual factors $-1$ with factors $e^{\pm i\theta}$.

• Nice answer (+1). But is it always possible to have an $R$ matrix with positive diagonal in the reduced rank QR decomposition? A link or explanation would be much appreciated. – epsilone Nov 30 '15 at 19:22