Show that if $$\begin{bmatrix}A & I \\ O & A^T\end{bmatrix} \begin{bmatrix}\hat x \\ r\end{bmatrix} = \begin{bmatrix}b \\ 0\end{bmatrix}$$ then $\hat x$ is a least squares solution of the system $Ax = b$ and $r$ is the residual vector.
The wording of the problem is confusing to me, because I can usually find the least squares solution by finding the solution of $\hat x$ to $A^TA\hat x = A^Tb$. Except, this wants me to prove the least squares solution is $\hat x$, which doesn't make much sense to me.
Best Answer
So the matrix:
$\begin{bmatrix}A & I \\ O & A^T\end{bmatrix} \begin{bmatrix}\hat x \\ r\end{bmatrix} = \begin{bmatrix}b \\ 0\end{bmatrix}$
Allows us to generate the equations:
$A\hat{x} + r = b$ and $A^Tr = 0$
So, solving for $r$, we can show that this is the residual vector: $r = b - A\hat{x}$
And plug this into the second equation:
$$A^Tr = A^T(b - A\hat{x}) = A^Tb - A^TA\hat{x}$$
So if $\hat{x}$ is in fact the least squares solution to $Ax=b$, we have that:
$A^Tb - A^Tb$ which equals $0$.
So $\hat{x}$ is a solution to the normal equations and hence is the least squares solution to $Ax=b$.
Day is the best!