Why do $A$ and $A^TA$ have the same row space?

Theorem: Let $A$ be an $m \times n$ real matrix. Then $A$ and $A^T A$ have the same row space.

I am trying to derive and intuitively understand why this theorem holds. Would appreciate any help. Thanks.

• Viewing the row space of a matrix as the image of multiplication with row vectors from the left, it's pretty easy to see that the row space of $A^TA$ is contained in the row space of $A$. The real meat of the problem is to show inclusion the other way. Sep 8, 2017 at 9:11
• You can prove this directly, by writing explicitly the matrix $A^{T}A$ and expressing its rows using the rows of $A$. But that doesn't give much intuition. The theorem is quite easy (and intuitive) if you know some stuff about inner product spaces, but you probably want a proof that doesn't use concepts that are not mentioned at all in the theorem. To this end, I don't think you can do better than Kevin's and user1551's answers (which are pretty much equivalent).
– Mark
Sep 8, 2017 at 15:05

Since $A^TA$ and $AA^T$ are clearly symmetric, then $$\operatorname{row}(A^TA) = \operatorname{col}(A^TA) \\ \operatorname{row}(AA^T) = \operatorname{col}(AA^T)$$

Now, each column of $A^TA$ is in $\operatorname{row}(A)$, thus $\operatorname{row}(A^TA) = \operatorname{col}(A^TA) \subseteq \operatorname{row}(A)$. Since $\operatorname{rank}(A^TA) = \operatorname{rank}(A)$, thus in fact $$\operatorname{row}(A^TA) = \operatorname{col}(A^TA) = \operatorname{row}(A)$$

Similarly one can show that $$\operatorname{row}(AA^T) = \operatorname{col}(AA^T) = \operatorname{col}(A)$$

The row space of $A^TA$ is a subspace of the row space of $A$ (because $x^T(A^TA)=(x^TA^T)A$), so it suffices to show that the two row spaces have equal dimensions, i.e. $A^TA$ and $A$ have the same row ranks.

In turn, it suffices to show that $A^TA$ and $A$ have the same column ranks (because row rank is equal to column rank). Since the ground field is real, the following condition is satisfied: $$\text{for every vector } v,\ v^Tv=0\Rightarrow v=0.\tag{\ast}$$ (This is true over $\mathbb R$ because $v^Tv=\|v\|^2$, the squared Euclidean norm of $v$). Therefore we have $(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(1)$ below:

1. $A^TAx=0$,
2. $(Ax)^T(Ax)=x^TA^TAx=0$,
3. $Ax=0$.

This means $A^TA$ and $A$ have identical null spaces. Now the rank-nullity theorem implies that they have the same ranks and our proof is completed.

Note that the problem statement is false if $\mathbb R$ is replaced by another field over which $(\ast)$ is not satisfied. In fact, if $v^Tv=0$ for some nonzero vector $v$, then $A^TA=0$ when every column of $A$ is equal to $v$. This happens, for instances, when $v$ is the complex vector $\pmatrix{1\\ i}$ or when $v=\pmatrix{1\\ 1}$ over the field $GF(2)$ (where $1+1=0$).

• As best as I can tell, this extends trivially to complex matrices by replacing the transpose with the conjugate transpose. Sep 8, 2017 at 15:21