Why does multiplying by $\textbf{A}^T$ make a previously unsolvable linear system solvable

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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