# 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=(XTXu,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