Let's assume that $A$ is a $m \times n$ matrix with linearly independent columns. Why are the columns of $A(A^T)$ also linearly independent? Is this new matrix invertible? What about $(A^T)A$?
The columns of $AA^T$ cannot be linearly independent unless $m=n$. If the columns of $A$ are linearly independent, then necessarily $m\ge n$.
If $m>n$, then $AA^T$ has $m$ columns, each of which is a linear combination of the columns of $A$, and there are only $n$ of those, so you have more than $n$ vectors in a space of dimension $n$, so they're not linearly independent.
Maybe I'll post the other cases here tomorrow . . . . . . .
(Bottom line: the columns in those other cases are linearly independent.)