For every *non-square* matrix prove that $AA^t$ or/and $A^tA$ is singular

For every non-square matrix prove that $AA^t$ or/and $A^tA$ is singular.

Like the title, I want to prove this and I tried to think of ways to prove it but I couldn't think of some..

I know by this answer that $AA^t$ is symmetric but I cant make the connection.

If someone has at least a hint to that It'll be great if you could write it in the comment section so I could give it a shot!

Thanks in advance.

To elaborate on my hint, suppose $A$ is an $n \times m$ matrix and $n \neq m$. It must be that $rank(A^t) = rank(A) \leq \min(n,m) < \max(n,m)$.

Using the fact that $rank(AB) \leq rank(A)$ for any $A,B$ for which the product is defined, we have that:

$$rank(AA^t) \leq rank(A) < \max(n,m)$$ $$rank(A^tA) \leq rank(A^t) < \max(n,m).$$

But it must be the case that the dimensions of $AA^t$ or $A^tA$ is $\max(n,m)$. Therefore at least one of them does not have full rank. For square matrices, not having full rank is equivalent to being singular.