Is a least squares solution to $Ax=b$ necessarily unique

Question

Let $A$ be an $m$ x $n$ matrix, and suppose that $b\in\mathbb{R}^n$ is a vector that lies in the column space of $A$. Is a least squares solution to $Ax=b$ necessarily unique? If so, give a detailed proof. If not, find a counter example.

I understand that a least-squares solution to $Ax=b$ is a vector $\hat{x}\in\mathbb{R}^n$ such that $\|b-A\hat{x}\|\le\|b-Ax\|$ for any vector $x\in\mathbb{R}^n$ which gives me the impression that the least squares solution to $Ax=b$ is not necessarily unique. However, I'm at a loss as to how to prove this.

Answer 1

The statement needs a crisp definition. Consider the matrix $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$ ($m$ rows, $n$ columns, rank $\rho$).

Uniqueness

If the data vector $b$ is not in the null space $\mathcal{N}(\mathbf{A}^{*})$ the least squares solution exists. If the number of columns is greater or equal to the rank of $\mathbf{A}$, $n\ge \rho$, the solution is unique.

Demonstration

The linear system $\mathbf{A}x=b$, $$ \begin{bmatrix}1 & 0\end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}b\end{bmatrix}, $$ offers the least squares solution $$ x_{LS} = \color{blue}{x_{particular}} + \color{red}{x_{homogeneous}} = \color{blue}{\begin{bmatrix}b \\ 0\end{bmatrix}} + \alpha \color{red}{\begin{bmatrix}0 \\ 1\end{bmatrix}} $$ where the arbitrary constant $\alpha \in \mathbb{C}$

The particular solution lives in the range space $\color{blue}{\mathcal{R}(\mathbf{A})}$. The homogeneous solution inhabits the null space $\color{red}{\mathcal{N}(\mathbf{A}^{*})}$. When this null space is trivial (when $n\ge \rho$), the is no homogeneous contribution and the least squares solution is unique.

Unique least square solutions

Answer 2

If $b$ is in the column space of $A$ then a true solution exists, which is unique if and only if the columns of $A$ are linearly independent.

If $b$ is not in the column space of $A$ then the least-squares solution is the orthogonal projection of $b$ to the column space of $A$, which is of course unique.