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

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.

• Rank conditions? Mar 29, 2016 at 3:29
• What is "Col A"? Mar 29, 2016 at 3:30
• @JohnHughes probably the column space of $A$ Mar 29, 2016 at 3:41
• Well, since $b$ is in the column space of $A$, $b=Ax$ for some $x$. Hence the residual norm of the LS problem can be made zero. What happens if we add to this $x$ some $y$ such that $Ay=0$? Mar 29, 2016 at 4:15
• Pavel's thinking along the same lines I am. How about $A = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, b = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, x_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, x_2 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$? Seems pretty non-unique. Simpler still is $A = \begin{bmatrix} 0 \end{bmatrix}, b = \begin{bmatrix} 0\end{bmatrix}, x_1 = \begin{bmatrix} 1\end{bmatrix}, x_2 = \begin{bmatrix} 2 \end{bmatrix}$. :) Mar 29, 2016 at 11:10

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

• No when $n$ is greater than $\rho$ the solution is not unique.
– Pew
Oct 2, 2021 at 2:26

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.