I'm trying to solve the next problems:
Given a matrix $A\in \mathbb{R}^{m\times n}$ and a vector $b\in \mathbb{R}^m$, it can be proved that there exists $\tilde{x}\in \mathbb{R}^n$ such that $\left\|b-A\tilde{x}\right\|=\min_{x\in \mathbb{R}^n}\left\|b-Ax\right\|$. This $\tilde{x}$ is called a least squares solution of $Ax=b$. I have to prove these items
a) if $m\geq n$ and $\hat{x}\in \mathbb{R}^n$, prove that $\left\|b-A\hat{x}\right\|=\min_{x\in \mathbb{R}^n}\left\|b-Ax\right\|$ if, and only if, $(b-A\hat{x})\in R(A)^\bot$.
b) Prove that $\hat{x}\in \mathbb{R}^n$ is a least squares solution of $Ax=b$ if, and only if, $A^tA\hat{x}=A^tb$.
I've proved the implications $\Leftarrow$ in both cases.
a) $\Leftarrow)$ Sppose that $(b-A\hat{x})\in R(A)^\bot$. Then, for each $x\in \mathbb{R}^n$, $\langle b-A\hat{x},Ax\rangle=0$. Therefore, using the pythagoras theorem for the inner product ($u\bot v \implies \left\|u+v\right\|^2=\left\|u\right\|^2+\left\|v\right\|^2$) we have that for every $x\in \mathbb{R}^n$
\begin{eqnarray*} \left\|b-Ax\right\|^2 & = & \left\|b-Ax-A\hat{x}+A\hat{x}\right\|^2 \\ & = & \left\|(b-A\hat{x})+A(\hat{x}-x)\right\|^2 \\ & = & \left\|b-A\hat{x}\right\|^2+ \left\|A(\hat{x}-x)\right\|^2 \\ & \geq & \left\|b-A\hat{x}\right\|^2. \end{eqnarray*} Hence, $\left\|b-A\hat{x}\right\|\leq \left\|b-Ax\right\|$ for every $x\in \mathbb{R}^n$; that is, $\left\|b-A\hat{x}\right\|=\min_{x\in \mathbb{R}^n}\left\|b-Ax\right\|$.
For the other part I don´t know how can I use the fact that $m\geq n$. Could you please give some suggestion?
b) $\Leftarrow)$ Using the implication $\Leftarrow)$ in the item $a)$, if we prove that $(b-A\hat{x})\in R(A)^\bot$, then we can conclude that $\hat{x}$ is a least squares solution for $Ax=b$. Now, using the fact that $A^tA\hat{x}=A^tb$, we have that $A^t(b-A\hat{x})=0$ and therefore, for every $x\in \mathbb{R}^n$, $$\langle A^t(b-A\hat{x}),x\rangle=0.$$
Since for every matrix is true that $\langle Ax,y\rangle=\langle x,A^ty\rangle$ and in the real case the inner product is symmetric, it implies that for every $x\in \mathbb{R}^n$
$$0=\langle A^t(b-A\hat{x}),x\rangle=\langle b-A\hat{x},Ax\rangle.$$
That is, $b-A\hat{x}\in R(A)^\bot$ anf with this we can conclude that $\hat{x}$ is a least squares solution of $Ax=b$.
Also I couldn't prove the other implication. Could you please give me some suggestions to prove the implication $\Rightarrow$ in the items a) and b)? Thanks.