Uniqueness of a solution of a matrix

Question

Given $A \in C^{m\times n}$ of rank $n$ and $b \in C^{m}$, now consider the below system of equation $$\begin{equation} r + Ax = b \\ A^*r = 0 \end{equation}$$ where $I$ is $m \times m$ identity matrix. How can I show that $(r,x)^T$ is the unique solution where $r$ and $x$ are the residual and solution of below problem? $$minimize \: ||Ax-b||_2 $$ This is a question from Numerical Algebra book by Lloyd.

Answer 1

Denote by $\mathcal C$ the column space of $A$. Then $\mathcal C^\perp=\left\{w: A^\ast w=0\right\}$. Let $b=Au+v$ where $v\in\mathcal C^\perp$. Then $\|Ax-b\|^2 = \|A(x-u)\|^2 + \|v\|^2$. Hence $\|Ax-b\|$ is minimised if and only if $\|A(x-u)\|$ is minimised, and your problem boils down to showing that the equation $$ A(x-u) + (r-v) = 0,\quad r\in\mathcal C^\perp $$ has a unique solution $(x,r)$ and this $x$ is also the unique global minimiser of $\|A(x-u)\|$. The rest should be straightforward.