# I have to show that the matrix $M^TM$ is SPD if and only if the columns of the matrix M are linearly independent

I have been given M be an $m\times n$ matrix. I have to show that the matrix $M^TM$ is symmetric positive definite if and only if the columns of the matrix $M$ are linearly independent

My thoughts are as below $M^TM$ looks like a cholesky property and we know it is applicable as the matrix is SPD, still not able to connect how and which specific property to use to show if and only if columns of M are linearly independent...

Any hint as to how I should approach this...

-

## 2 Answers

It is obvious that $M^T M$ is symmetric.

Suppose the matrix $M^T M$ is SPD but $M$ does not have linearly independent columns. Then $M$ is not injective, and consequently $M^T M$ is not definite.

Suppose $M$ has linearly indepedent columns, then $M^T$ has linearly indepedent rows. For any $x$ let $y = Mx$, then $x^T M^T M x = y^T y$. This product is zero if and only if $y$ is zero. Then $x$ must have been zero. Whence $x^T M^T M x = 0$ if and only if $x$ is zero. Whence the matrix is symmetric positive-definite.

-
@Christian: I approved your edit because you fixed that glitch. But note that writing $M^t$ is a perfectly acceptable way of denoting the transpose of a matrix. –  t.b. Mar 13 '12 at 11:20
@t.b. I have never seen it anywhere before, but Ok, according to your link it seems apprpriate. –  Christian Rau Mar 13 '12 at 11:55

If and only if proofs go 2 ways: Since this is homework, I'll throw in some hints:

Given that columns are independent, prove $M^TM$ is symmetric positive definite.

For any matrix (Singular or not), $M^TM$ is always symmetric. (Try transposing it to see what you get).

Now, if columns are independent, what can be said about its eigenvalues?

So, $Ax=\lambda x$, premultiply both sides with $A^T$,

$A^TAx=A^T\lambda x = \lambda (A^Tx) = ??$.

Given that $M^TM$ is SPD, prove columns are independent.

If $M^TM$ is SPD, then again the symmetric part is fairly useless; the useful part is the PD. Let $x$ be a eigenvector of M.

$M^TMx = M^T\lambda x = \lambda M^Tx = \lambda^2x$

So now, if M was singular. There would be a $\lambda=0 \text{ but } x \neq 0 \text { s.t. } M^TMx=0$

How does this violate the our assumption of SPD ?

-
Since M is m x n I think eigenvalue analysis is not general enough. It only deals with linear operators from one linear space mapping to the same linear space. –  ldog Mar 13 '12 at 9:28
I seem to have missed the fact that it is rectangular.....Drat ! I'll fix it soon. –  Inquest Mar 13 '12 at 9:37