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}$.
 A: 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$. 
A: 
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.
A: A general principle (some would say "tautology") connecting sets and their defining properties is as follows:
Let $E_1 := \{x | p_1(x)\} $ (with the meaning "$x$ has property $p_1$") and  $E_2 := \{x | p_2(x)\} $.
$$\text{If}  \  \forall x, (\ p_1(x) \implies p_2(x)), \ \  \text{then} \ \  E_1 \subset E_2$$
Here, as $AX=B \implies A^TAX=A^TB$, the set $E_1$ of solutions of equation $AX=B$ is included into the set $E_2$ of solutions of  $A^TAX=A^TB$.
Rather often (as in the case shown in your question), $E_1=\varnothing$ whereas $E_2 \neq \varnothing$. 
But what we have shown explains that this is not contradictory.
A: Consider an analogy with the 1D case: $1=0$ is false but $0(1)=0(0)$ is true. Multiplying both sides by zero turned a false equation into a true one.
In the case of an overdetermined system $Ax=b$, you are effectively multiplying certain components of the space by zero when you multiply by $A^T$. The reason is that if the rank of $A$ is less than its number of rows, then $A^T$ has a nontrivial null space. (In particular, if $A$ has more rows than columns then $A^T$ has a nontrivial null space; this is the usual situation.) Thus you are asking $Ax-b$ to be just in the null space of $A^T$, rather than actually being zero. This is a milder requirement, so new solutions can crop up.
A: One intuition for this is thinking about it geometrically. In your case, $A$ is a linearly independent $3\times 2$ matrix, so its column space is a plane in $\mathbb R^3$, and $A\vec x$ is a point in this plane. If we choose a new point $\vec b\in\mathbb R^3$, it generically won't be on the plane of $\text{col}\ A$.
Left multiplying by $A^T$ can be thought of as orthogonally projecting a vector in $\mathbb R^3$ into a 2-dimensional space, expressed in a new basis. In this new space, the column space of $A^TA$ is all of $\mathbb R^2$, so any choice of $\vec b\in \mathbb R^3$ will result in an $A^T\vec b\in\mathbb R^2$ than can be written as $A^TA\vec x$ for some $\vec x\in\mathbb R^2$.
