Statement: $Ax=b$ has a solution if and only if $A^T A x = A^T b$ has a solution

Question

Is the following statement correct? How can I prove it?

$Ax=b$ has a solution if and only if $A^TAx=A^Tb$ has a solution.

I know that $Ax=b$ has a solution if and only if $A$ is invertible. In that case, the solution is $A^{-1}b$. Therefore, every solution of $Ax=b$, is also a solution of $A^TAx$. But this is not the other way around, right? Or is it?

Any help appreciated! Thank you!

(I know there are other similar questions about this, but these posts do not answer my specific question)

Answer 1

Hint: If the number of unknowns is equal to the number of equations: $$0\ne |A^TA|=|A^T|\cdot |A| \iff |A|\ne 0.$$

Answer 2

Your statement is not true, because $A^TAx=A^Tb$ always has solutions. Indeed, $\Bbb R^n=Im(A)+Im(A)^\bot$, so you can write $b=Ay+b'$ with $y\in \Bbb R^m$ and $b'\bot Im(A)$. Then $$(A^Tb'|A^Tb')=(AA^Tb'|b')=0,$$thus $A^Tb'=0$, and $A^TAy=A^T(Ay+b')=A^Tb$.

Answer 3

In general the linear system $Ax=b$ has exactly one solution for every vector $b\neq 0$, if the matrix $A$ is invertible. If this is true it is also true that the system $A^TAx=A^Tb$ has also one solution (the same as $Ax=b$).

When matrix $A$ is not invertible and the system has no solution then $x=(A^TA)^{-1}A^Tb$ is the vector that minimizes the sum square error $|Ax-b|^2$.

In the case when we have many solutions then $x=(A^TA)^{-1}A^Tb$ is the solution that minimizes $|x|^2$

So if the system $A^TAx=A^Tb$ then $Ax=b$ may have one, many or no solutions.