12
$\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$
  • $\begingroup$ If $n=m$, it is enough to check that $\det(X) \not=0$ $\endgroup$ – naslundx Feb 26 '14 at 21:46
  • $\begingroup$ I am specifically interested when $n \neq m$ $\endgroup$ – Pinocchio Feb 26 '14 at 21:48
  • 1
    $\begingroup$ Hint: What happens if $X$ has full row rank? $\endgroup$ – Nitish Feb 26 '14 at 21:50
  • $\begingroup$ full row rank means when all the rows of X have a pivot? $\endgroup$ – Pinocchio Feb 26 '14 at 21:51
  • $\begingroup$ 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$. $\endgroup$ – Michael Feb 26 '14 at 21:56
14
$\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$
  • 4
    $\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 Feb 26 '14 at 22:06
4
$\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$
  • $\begingroup$ why do we need to show u = 0? I am a little confused on your notation for $0 = (XTXu, u) = (Xu , Xu)$ $\endgroup$ – Pinocchio Feb 27 '14 at 2:05
  • $\begingroup$ It is really $0=(X^T X u, u) = (Xu, Xu)$. Just a typo $\endgroup$ – Herman Jaramillo Jul 19 at 1:56
  • $\begingroup$ Correct. I fixed it. $\endgroup$ – Yiorgos S. Smyrlis Jul 19 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.