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}$.


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 direct implication $\textbf{A}x = \textbf{B} \implies \textbf{P}\textbf{A}x = \textbf{P}\textbf{B}$ holds for any $\textbf{P}$. However, the reverse implication $\textbf{P}\textbf{A}x = \textbf{P}\textbf{B} \implies \textbf{A}x = \textbf{B}$ only holds if $\textbf{P}$ has a left inverse $\textbf{P}^{-1}$ (because you can then multiply with $\textbf{P}^{-1}$ on the left to derive $\textbf{A}x = \textbf{B}$). But in this case, $\textbf{P}$ is a rectangular matrix with more columns than rows which has no left inverse.
