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.
 A: 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)
$$
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:


*

*$A^TAx=0$,

*$(Ax)^T(Ax)=x^TA^TAx=0$,

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