If rank$(A)=r$, show that rank$(A^\top A)=r$ Let $A$ be $m\times n$ matrix with rank $r=\min(m,n)$. How do we show that rank$(A^T A)$ is $r$.
 A: Hint: show that $A$ and $A^TA$ have the same nullspace.  That is,
$$
Ax = 0 \iff A^TAx = 0
$$
It is helpful to note that $x^T(A^TAx) = \|Ax\|^2$
A: Firstly, we proof than $\mathsf{Null} A=\mathsf{Null} (A^TA)$ ($A$ is an $m\times n$ matrix):
a) $\mathsf{Null} A\subset \mathsf{Null} (A^TA)$, because $\mathsf{Null} A$ is always a subset of $\mathsf{Null}(BA)$.
b) If $x\in\mathsf{Null} (A^TA)$, then $A^T(Ax)=0$ and, so,  $Ax\in\mathsf{Null}(A^T)$. In the other hand, $Ax$ is in the column space of $A$, $\mathsf{Col}A$. 
Then, 
$$
    Ax\in\mathsf{Null}(A^T)\cap \mathsf{Col}A
$$
But we know
$\mathsf{nul}(A^T)=(\mathsf{Col}A)^\perp$, and, so, $\mathsf{Null}(A^T)\cap \mathsf{Col}A=\emptyset$. Consequently,
$Ax=0$, and $x\in\mathsf{Null}A$.
Now, 
$$
   \mathsf{rank} (A^TA)=n-\mathsf{dim} \mathsf{Null} (A^TA)=
    n-\mathsf{dim} \mathsf{Null} A=\mathsf{rank} A
$$
A: What you need is to use the Singular Value Decomposition. Then, just have a look what happens with singular values. Here is a link: http://en.wikipedia.org/wiki/Singular_value_decomposition
