Why does multiplying by $\textbf{A}^T$ make a previously unsolvable linear system solvable Consider for instance the linear system:
$$\left(
\begin{array}{cc}
 1 & 2 \\
 3 & 4 \\
 5 & 6 \\
\end{array}
\right).\left(
\begin{array}{c}
 x \\
 y \\
\end{array}
\right)=\left(
\begin{array}{c}
 1 \\
 2 \\
 4 \\
\end{array}
\right)$$
This is over determined and thus has no solution. Yet, by simply multiplying both sides by $\textbf{A}^T$:
$$\left(
\begin{array}{ccc}
 1 & 3 & 5 \\
 2 & 4 & 6 \\
\end{array}
\right).\left(
\begin{array}{cc}
 1 & 2 \\
 3 & 4 \\
 5 & 6 \\
\end{array}
\right).\left(
\begin{array}{c}
 x \\
 y \\
\end{array}
\right)=\left(
\begin{array}{ccc}
 1 & 3 & 5 \\
 2 & 4 & 6 \\
\end{array}
\right).\left(
\begin{array}{c}
 1 \\
 2 \\
 4 \\
\end{array}
\right)$$
We find that the system now has a unique solution, which is the (x,y) that minimizes the squared error.
Now I understand the derivation of why multiplying by the transpose helps to find the pseudoinverse which then helps to perform OLS regression, but my question is perhaps a bit more fundamental. 
How can multiplying both sides of an equation by a matrix change a system which previously had no solutions into one that has a unique solution? This seems to against what I assumed that the solutions to $\textbf{A}x = \textbf{B}$ were the same as the solutions to $\textbf{P}\textbf{A}x = \textbf{P}\textbf{B}$.

The solutions to $Ax=b$ are the same as those of $PAx=Pb$ if $P$ is one-to-one, i.e. $\ker(P) = \{0\}$.  If $P$ is not one-to-one, so that $P y = 0$ for some $y \ne 0$, then any $x$ such that $Ax = b + y$ is a solution of $PAx = Pb$ but not a solution of $Ax = b$. 
