What are the requirements on a matrix $A$ for $A^TA$ to have an inverse?

Question

I know there's a theorem stating that if the columns of $A$ are independent, then the columns of $A^TA$ are also independent ($A$ is invertible $\Rightarrow A^TA$ is positive symmetric definite is the most common way to prove this. That $A^TA$ is invertible follows immediately from the fact that $0$ is not an eigenvalue)

But is that the minimum requirement for $A^TA$ to be invertible, or can $A^TA$ be invertible even in cases where $A$ is not? I have not been able to prove in general that "$A$ is not invertible $\Rightarrow A^TA$ is not invertible".

Answer 1

This can be shown without invoking determinants as follows: Note that $A^TAx=0$ iff either $Ax=0$ or $A^Tz=0$ for some $z\in\operatorname{Im}(A)$. Consequently:

$$ \ker(A^TA) = \ker(A) \oplus A^{-1}\Big(\ker(A^T)\cap \operatorname{Im}(A))\Big)$$

Here, $A^{-1}$ denotes the pre-image. However, $\ker(A^T) = \operatorname{Im}(A)^\perp$ (this is a fundamental Lemma in linear algebra, remember it/ try to prove it on your own!), hence $\ker(A^T)\cap \operatorname{Im}(A)=\{0\}$. So

$$\ker(A^TA) = \ker(A)\oplus A^{-1}\big(\{0\}\big) =\ker(A) \oplus \ker(A) = \ker(A)$$

In particular, if $A$ is square, then $A$ is invertible if and only if $A^T A$ is invertible.

Answer 2

If $A$ is not invertible, then$$\det(A^TA)=\det(A)^2=0,$$and therefore $A^TA$ is not invertible too.

Answer 3

If the matrix $A$ is square, then invertibility of $AA^T$ is the same as $A$ being invertible. Indeed, if $B$ is an inverse of $AA^T$, then $A(A^TB)$ is the identity, so this provides a right inverse for $A$. A single-sided inverse to a square matrix is sufficient to prove it is invertible.

The converse is obvious, because if $A$ is invertible then $(A^T)^{-1}=(A^{-1})^T$.

However, the argument for general matrices is much more interesting. The fact to use is that $A$ and $AA^T$ have the same rank. Once you know this, you see that $AA^T$ is invertible if and only if $A$ has full row rank (rank equals the number of rows).

Why do the matrices $A$ and $AA^T$ have the same rank? It's easier to prove this for $B$ and $B^TB$ and then use $B=A^T$.

We can prove that $B$ and $B^TB$ have the same null space. If $v\in N(B)$ (that is, $Bv=0$), then obviously $v\in N(B^TB)$. Conversely, from $v\in N(B^TB)$ we have $B^TBv=0$, so also $$ 0=v^TB^TBv=(Bv)^T(Bv) $$ implying $Bv=0$.

Now the rank-nullity theorem allows us to finish: \begin{align} n&=\operatorname{rk}B+\dim N(B) \\ &=\operatorname{rk}B^TB+\dim N(B^TB) \end{align} so we reach $\operatorname{rk}B=\operatorname{rk}B^TB$ as desired.