# Proving positive (semi-)definiteness of a matrix equation for Cholseky decomposition.

I'm trying to prove, or disprove, that the following matrix is positive (semi-)definite and symmetric (so a covariance matrix); $$M = C_M^{-1} + G^T C_D^{-1} G.$$ Here, $C_M$ is a covariance matrix (which is positive semi-definite and symmetric, sometimes positive definite) of dimensions $n \times n$, which is not necessarily diagonal. The matrix $C_D$, of dimensions $m \times m$, is also a covariance matrix which in my application is always diagonal, but could be extended to any arbitrary covariance matrix (so always positive semi-definite, symmetric).

G is an arbitrary matrix of dimensions $m \times n$. It does not necessarily have full rank. I think this already excludes positive definiteness of the second term, since $x^T G^T G x = (G x)^T(G x) > 0$ only if G is full rank.

Can we extend this to $G^T C_D^{-1} G$ to prove that M is positive semi-definite symmetric? I'd suggest to use the property $x^T A x \geq 0$;

$$\begin{eqnarray} x^T G^T C_D^{-1} G x &=& (G x)^T C_D^{-1} (G x) \nonumber \\ & \overset{?}{\geq} & 0 \end{eqnarray}$$

I guess this boils down to proving that the inverse of $C_D$ (and $C_M$) is positive semi-definite, because afterwards we can again use the same definition on $(G x)^T C_D^{-1} (G x)$. And the sum of PSD matrices is also PSD (that proof is rather easy, see here).

And then a small follow up; if the second term is PSD, but the first term is PD, the resulting matrix M is also PD right?

For a little context, from the first equation matrix $M$ is used as the mass matrix in a Hamiltonian Monte Carlo sampler, and I need to Cholesky decompose it to propose momentum samples. Cholesky decomposition can (I think) only be done on a positive definite matrix. If a matrix is positive semi-definite, it is still possible to Cholesky decompose it if the diagonal entries of $L$ are allowed to be zero, but I don't know if my algorithm breaks down in this case.

If a matrix $A$ is symmetric positive definite, then $A^{-1}$ is symmetric positive definite.

Proof: Let the SVD of $A=UDU^T$, then $A^{-1}=UD^{-1}U^T$, we can see from the eigenvalues that $A^{-1}$ is positive definite.

If a matrix $A$ is positive definite and matrix $B$ is symmetric positive semidefinite, then $A+B$ is positive definite.

Proof:

$$x^T(A+B)x=x^TAx+x^TBx > 0$$

• Thanks, easy as 1, 2, 3, both proofs! The term $(G x)^T C_D^{-1} (G x)$ then also proves PD/PSD right? – Lars Gebraad Aug 9 '17 at 8:48
• If $C_D$ is positive definite then $(Gx)^TC_D^{-1}(Gx) \geq 0$, hence it is PSD. I don't think it is PD as $Gx$ can be zero even though $x$ is non-zero. – Siong Thye Goh Aug 9 '17 at 9:00
• So the requirement for $M$ to be PD if $C_M$ is PSD is that $G$ has full rank, and $C_D$ is PD. – Lars Gebraad Aug 9 '17 at 9:19