Least square when $\ A^T A$ is not invertible?

Question

$\ A^TA\boldsymbol x =\ A^T \boldsymbol b$

$$\ A= \begin{bmatrix}1&-3&-3\\1&5&1\\1&7&2\end{bmatrix} and \boldsymbol\ b = \begin{bmatrix}5\\-3\\-5\end{bmatrix}$$

So I'm trying to solve it by: $\boldsymbol x = \ (A^TA)^{-1}A^T\boldsymbol b$, but $A$ nor $A^TA$ is invertible.

A solution is supposed to be $$\boldsymbol x = \begin{bmatrix}2\\-1\\0\end{bmatrix}$$

How is this possible?

Answer 1

Invertible means

"is every vector $v_1$ mapped uniquely to another vector $v_2$ so that there exists another linear operator which takes us back?"

In other words which maps $v_2$ to $v_1$. If such an operator exists then it is called the inverse to the first one.

For our matrix, we can verify that all vectors parallel to $(3,-1,2)^T$ are mapped to the $0$ vector.

This ruins the uniqueness that is required for the linear operator to be invertible.

In general a non-invertible matrix can give whole subspaces of solutions to matrix-vector equations due to the lack of unique mapping property.

For example in this case it is probably a whole line full of solutions to the equation. Maybe you can find the line if you are curious.

Answer 2

The normal equations $A^TAx=A^Tb$ are always consistent, even if $A^TA$ isn't invertible. That being said, to find a solution of $A^TAx=A^Tb$, I suggest you set up and solve the augmented system $\big[A^TA|A^Tb\big]$.

Answer 3

The general solution of the linear system $Ax=b\;$ is $$x = A^+b + (I-A^+A)y$$ where $A^+$ denotes the Moore-Penrose inverse, and $y$ is an arbitrary vector.
This solution is valid for any $A-$ rectangular or square or invertible or singular.

The supposed solution uses $$y = \pmatrix{7/4\\7/4\\7/4}$$