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:
- when $n > m$ then $X$ must have...
- when $n < m$ then $X$ must have...
- 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.
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.
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$.