# Least squares and null space

I want to solve a least squares problem, $$\min_x ||y - A x ||^2$$ with $$A \in \mathbb{R}^{m\times n}$$. Suppose I were to find two distinct solutions $$x_1,x_2$$, which solve the problem, so that $$||y - A x_1 ||^2 = || y - A x_2 ||^2$$ Does this imply that $$A$$ has a non-trivial null space?

Certainly, if $$x_2 = x_1 + z$$ and $$z \in Ker(A)$$, then the above condition would hold. But is it possible to have a non-singular $$A$$ which can have two distinct least squares solutions as above?

There is a unique vector in the span of $$A$$ (the columnspace of $$A$$) that is closest to $$y$$, namely the orthogonal projection of $$y$$ onto the columnspace. Since $$Ax_1$$ and $$Ax_2$$ are both “closest” to $$y$$, then $$Ax_1$$ and $$Ax_2$$ are both the orthogonal projection of $$y$$ onto the columnspace, and therefore $$Ax_1=Ax_2$$; in particular, $$x_1-x_2$$ lies in the nullspace of $$A$$.
An interesting question in this situation is to find the vector $$\mathbf{x}_0$$ among all vectors for which $$\lVert A\mathbf{x}-\mathbf{y}\rVert^2$$ is minimal that has least norm. This can be done in two steps using the problem of “minimal solutions”, or in a single step by using the pseudoinverse of $$A$$.
If $$\text{the columns of A are linearly independent},$$ then $$A^\top A$$ is invertible and the solution is uniquely given by $$(A^\top A)^{-1} A^\top y.$$
The above condition is equivalent to $$\text{A has a trivial nullspace}.$$
(Note that the above conditions include the case where $$A$$ is non-singular, but are more general since they handle cases where $$A$$ is not square.)