Why is "$Ax=b$ is solvable $\iff AA^\mathsf{T}y=b$ is solvable" true?

Question

We have a random matrix A ($m\times n$), a vector $x$ from $\mathbb{R^{n}}$ and vectors $y$ and $b$ from $\mathbb{R^{m}}$.

Why is it true that $Ax=b$ has a unique solution $\iff$ $ A A^\mathsf{T} y=b$ has a unique solution?

Is it reasonable to approach this from a column space point of view? If $Ax=b$ has a unique solution then $b$ is in the column space of $A$, $b\in C(A)$. How can it be proved that the column spaces of $A$ and $AA^\top x$ are the same?

Answer 1

Indeed, this is not true as stated. Take $m = 2$, $n=1$, $A = b = \begin{pmatrix}1 \\ 0 \end{pmatrix}$.

Then $$Ax = b$$ is the same as $$\begin{pmatrix}1 \\ 0 \end{pmatrix} x = \begin{pmatrix}1 \\ 0 \end{pmatrix}$$ which has the unique solution $x=1$.

On the other hand, $AA^T y = b$ is the same as $$\begin{pmatrix}1 & 0 \\ 0 & 0 \\ \end{pmatrix} y = \begin{pmatrix}1 \\ 0 \end{pmatrix}$$ which has multiple solutions, e.g. $y = \begin{pmatrix}1 \\ 0\end{pmatrix}$ or $y = \begin{pmatrix}1 \\ 1\end{pmatrix}$.

Answer 2

$\det(AA^T)=\det(A)\det(A^T)=(det(A))^2\ne0$