38
$\begingroup$

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.

$\endgroup$
9

2 Answers 2

35
$\begingroup$

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.

$\endgroup$
3
  • 6
    $\begingroup$ 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$. $\endgroup$
    – egreg
    Commented Feb 26, 2014 at 22:06
  • $\begingroup$ Wouldn't the proof need to change if the matrices are complex? Then $(Xv)^T(Xv)=0$ does not imply $Xv =0$. $\endgroup$ Commented Jul 26, 2022 at 7:58
  • 1
    $\begingroup$ Yes, properly one needs to use the adjoint and not the transpose. But usually a question that is only tagged "linear algebra" and doesn't clarify it, is considering the real case. $\endgroup$ Commented Jul 26, 2022 at 13:05
6
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ why do we need to show u = 0? I am a little confused on your notation for $0 = (XTXu, u) = (Xu , Xu)$ $\endgroup$ Commented Feb 27, 2014 at 2:05
  • $\begingroup$ It is really $0=(X^T X u, u) = (Xu, Xu)$. Just a typo $\endgroup$ Commented Jul 19, 2019 at 1:56
  • $\begingroup$ Correct. I fixed it. $\endgroup$ Commented Jul 19, 2019 at 5:11
  • $\begingroup$ Wouldn't the proof need to change if the matrices are complex? Then $(Xv)^T(Xv)=0$ does not imply $Xv =0$. $\endgroup$ Commented Jul 26, 2022 at 7:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .