# Proof of when is $A=X^TX$ invertible?

Say we have an $n\times m$ matrix $X$. What are the specific properties that $X$ must have so that $A=X^TX$ invertible?

I know that when the rows and columns are independent, then matrix $A$ (which is square) would be invertible and would have a non-zero determinant. However, what confuses me is, what sort of conditions must we have on each row of $X$ such that $A$ would be invertible.

It would be very nice to have a solution of the form:

1. when $n > m$ then $X$ must have...
2. when $n < m$ then $X$ must have...
3. when $n = m$ then $X$ must have...

I think in the 3rd case we just need $X$ to be invertible but I was unsure of the other two cases.

• If $n=m$, it is enough to check that $\det(X) \not=0$ – naslundx Feb 26 '14 at 21:46
• I am specifically interested when $n \neq m$ – Pinocchio Feb 26 '14 at 21:48
• Hint: What happens if $X$ has full row rank? – Nitish Feb 26 '14 at 21:50
• full row rank means when all the rows of X have a pivot? – Pinocchio Feb 26 '14 at 21:51
• Consider $X$ as a linear operator and look what happens to the rank of the basis $(v_1,...,v_n)$ when $X$ maps it to $R^m$ and then $X^T$ maps it back to $R^n$. – Michael Feb 26 '14 at 21:56

Precisely when the rank of $X$ is $m$ (which forces $n\geq m$).

The key observation is that for $v\in\mathbb R^m$, $Xv=0$ if and only if $X^TXv=0$. For the non-trivial implication, if $X^TXv=0$, then $v^TX^TXv=0$, that is $(Xv)^TXv=0$, which implies that $Xv=0$.

If the rank of $X$ is $m$, this means that $X$ is one-to-one when acting on $\mathbb R^m$. So by the observation, $X^TX$ is one-to-one, which makes it invertible (as it is square).

Conversely, if the rank of $X$ is less than $m$, there exists $v\in\mathbb R^m$ with $Xv=0$. Then $X^TXv=0$, and $X^TX$ cannot be invertible.

• Which is a different way of saying that $X$ has a left inverse. Actually, if $X^TX$ is invertible, then $(X^TX)^{-1}X^T$ is a left inverse of $X$ and is exactly the Moore-Penrose pseudoinverse of $X$. – egreg Feb 26 '14 at 22:06

It is true if and only if:

$$m\le n$$ and Rank$$\,(X)=m$$.

Assume that $$m\le n$$ and Rank$$\,(X)=m$$, and let $$X^TXu=0$$, for some $$u\in\mathbb R^m$$. We need to show that $$u=0$$. We have also that $$0=(X^TXu,u)=(Xu,Xu),$$ and thus $$Xu=0$$. But as Rank$$\,(X)=m$$, this implies that $$u=0$$. (Otherwise, the columns of $$X$$ would be linearly dependent, and hence its rank less than $$m$$.)

Assume that $$X^TX\in\mathbb R^{m\times m}$$ is invertible. Then $$m=$$Rank$$\,(X^TX)\le$$Rank$$\,(X)\le \min\{m,n\}$$. Thus $$\min\{m,n\}=m$$, Rank$$\,(X)=m$$, and $$m\le n$$.

• why do we need to show u = 0? I am a little confused on your notation for $0 = (XTXu, u) = (Xu , Xu)$ – Pinocchio Feb 27 '14 at 2:05
• It is really $0=(X^T X u, u) = (Xu, Xu)$. Just a typo – Herman Jaramillo Jul 19 at 1:56
• Correct. I fixed it. – Yiorgos S. Smyrlis Jul 19 at 5:11