Does $\operatorname{rank}(A^TA)=\operatorname{rank}(AA^T)$ hold for all $n \times m$ matrices $A$? My intuition tells me this should not be true, but I honestly don't know how to show whether it is true or false. I'm having a very hard time understanding what role the transpose matrix plays in calculations like these.
 A: There are a few relevant equations for the $n\times m$ matrix $A$:
$$
                     \mbox{Rank}(A)=\mbox{RowRank}(A)=\mbox{ColumnRank}(A)\\
                     \mbox{ColumnRank}(A)+\mbox{dim}[\mathcal{N}(A)]=m\\
                     \mathcal{N}(A^{T}A)=\mathcal{N}(A)
$$
The last one holds because $A^{T}Ax$ implies $x^{T}A^{T}Ax=(Ax)^{T}(Ax)=0$ and, hence, also $Ax=0$ (the opposite inclusion that $Ax = 0$ implies $A^{T}Ax=0$ is trivial.) Therefore,
$$
\begin{align}
    \mbox{Rank}(A^{T}A) & =\mbox{ColumnRank}(A^{T}A) \\
        & = m-\mbox{dim}(\mathcal{N}(A^{T}A)) \\
        & = m-\mbox{dim}(\mathcal{N}(A)) \\
        & = \mbox{ColumnRank}(A)
         = \mbox{Rank}(A)
\end{align}
$$
Finally,
$$
      \mbox{Rank}(A^{T}A)=\mbox{Rank}(A)=\mbox{Rank}(A^{T})=\mbox{Rank}(AA^{T}).
$$
A: Let $v$ be a vector such that $A^TAv=0$. Then, we have that $v^TA^TAv=0$, and so $\langle Av, Av\rangle=0$, which means that $Av=0$. So anything in the null space of $A^TA$ is also in the null space of $A$, and the other direction is obvious, so the null spaces of $A$ and $A^TA$ are equal. Similarly, the null spaces of $A^T$ and $AA^T$ are equal. Since the ranks of $A$ and $A^T$ are the same, say $k$, we have that $A^TA$ has a nullity of $m-k$ and $AA^T$ has a nullity of $n-k$, so the ranks of these products are $m-(m-k)=k$ and $n-(n-k)=k$, respectively, so the ranks are equal.
