Vector $x$ Solves Least Squares Problem $\iff$ $b - Ax \in \text{Null}(A^*)$ I am preparing for a graduate exam in Numerical Linear Algebra and I have to solve the following question (without calculus, and without any other theorems about Least Squares):

Let $A \in \mathbb{C}^{m \times n}$ with $n < m$ (not necessarily of full rank). For any $x \in \mathbb{C}^n$ let $r(x) = b - Ax$. Show that $x$ solves the least squares problem $\min_{x \in \mathbb{R}^n}||b - Ax||_2$ if and only if $r(x) \in \text{Null}(A^*).$

Below, I wrote down my attempt. Not only is it incomplete (it purports to prove just one direction of the equivalence), but later I realized that it contains a major flaw. I would immensely appreciate your help  in either fixing this solution, or finding a new one.
I have very little time on the exam, so as a bonus, I would be very thankful if you could tell me if you see bad habits in my mathematical writing which make the solution too long.
P.S. I have an inkling that a correct solution might involve a QR decomposition, but I'm not sure.

Flawed Solution:
Lemma: The equation $A^*Ap = A^*b$ has a solution.
Proof: We are trying to show that $A^*b \in \text{Col}(A^*A) = \text{Null}(A^*A)^{\perp}$. Take any $y \in \text{Null}(A^*A).$ We will show that $A^*b \perp y$.
But first, we will show $Ay = 0$. Indeed, $$y \in \text{Null}(A^*A) \implies A^*Ay = 0 \implies y^*A^*Ay = 0 \implies ||Ay|| = 0 \implies Ay = 0.$$
Now, we show perpendicularity. We have
$$(A^*b)^*y = b^*(Ay) = b^*0 = 0.$$
So $A^*b \in \text{Col}(A^*A)$.
Q.E.D.

We proceed to the main proof. Let $p$ be a solution of $A^*Ap = A^*b$. Then $A^*b - A^*Ap = 0$.
We claim $r(p) \perp \text{Col(A)}.$ Indeed, for any $Az \in \text{Col}(A)$, we have
$$(Az)^*(b - Ap) = z^*(A^*b - A^*Ap ) = 0.$$
Now, by the Pythagorean Theorem,
$$||b - Ay||^2 = ||b - Ap + Ap - Ay||^2 = ||b - Ap||^2 + ||Ap - Ay||^2 \ge ||b - Ap||^2$$
with equality $\iff Ay = Ap$.
$\color{red}{\text{The flaw is here. I need to bound the function } ||b - Ax||}$
$\color{red}{\text{ by a constant, not by a function of p.}}$
Now suppose $x$ is a vector that solves the L.S. problem. Then $Ax = Ay$, so $r(x) = b - Ax = b - Ap = r(p)$
and $r(p) \in \text{Null}(A^*)$ because $A^*Ap = A^*b \implies A^*(b - Ap) = 0$.
Now for the converse, suppose that $A^*Ax = A^*b$. I don't yet know how to show that $Ax = Ap$.
 A: I'll use the fact that $N(A^*)$ is the orthogonal complement of $R(A)$. (I like to call this fact the "four subspaces theorem" because it shows how the four subspaces $R(A), N(A), R(A^*)$, and $N(A^*)$ are related.)
There is a unique way to decompose $b$ as
$$
\tag{1}b = b_1 + b_2
$$
with $b_1 \in R(A)$ and $b_2 \in N(A^*)$. Notice that if $x \in \mathbb C^n$ then $b_1 - Ax \in R(A)$, and so $b_1 - Ax \perp b_2$. It follows that
\begin{align}
\|b - Ax \|_2^2 &= \|b_2 + b_1 - Ax \|_2^2 \\
&= \| b_2 \|^2 + \| b_1 - Ax \|_2^2.
\end{align}
This expression is minimized when $Ax = b_1$, or equivalently when $b - Ax = b_2$.
So, if $x$ minimizes $\| r(x) \|_2$, then $r(x) \in N(A^*)$. On the other hand, suppose that $r(x) \in N(A^*)$. Comparing the equation
$$
b = Ax + r(x)
$$
with the unique decomposition (1) reveals that $r(x) = b_2$, which means that $\| r(x) \|_2$ is minimal.
A: Note that $at^2+bt+c$ has a minimum  for $t=0$ iff $b=0$ and $a\geq 0$.
You may then consider minimizing $\|r(x)\|^2=(Ax-b,Ax-b)$. Replacing $x$ by $x+ty$ with $t$ real and $y$ a vector yields:
$$ \|r(x+ty)\|^2 =
            \|r(x)\|^2 + 2t (y,A^* r(x)) + t^2(Ay,Ay)$$
By the above, $\|r(x)\|^2$ is the minimum value iff for every $y$ the linear term vanishes, or equivalently, iff $A^* r(x)=0$.
A: I remember solving this exactly same problem for a course on Numerical Linear Algebra about four years ago.
Suppose $x$ solves the linear square problem. Then $x$ is a critic point of the function $f(z) = \|Az-b \|^2$, that is $0 = \nabla f(z) = 2 A^* A x - 2 A^* b$ (I will not discuss how I computed this to go straight to the point, unless you need it). Hence, $A^T(Ax - b) = 0$. That is, $r(x) = b-Ax \in \operatorname{Null}(A^*)$.
For the converse, suppose $r(x) = b-Ax \in \operatorname{Null}(A^*)$. We make use of the Fundamental Theorem of Linear Algebra $\operatorname{Null}(A^*) = \operatorname{Im}(A)^\perp $ and the orthogonal projector and the fact that is the best approximator.
\begin{align}
b-Ax \in \operatorname{Null}(A^*) & \Leftrightarrow b-Ax \in \operatorname{Im(A)}^\perp\\
& \Leftrightarrow Ax-b \perp Ay \quad \forall y \in \mathbb{C}^n\\
& \Leftrightarrow Ax = \operatorname{Proj}_{\operatorname{Im}(A)}(b)\\
& \Leftrightarrow Ax - b= \operatorname{Proj}_{\operatorname{Im}(A)}(b) - b\\
& \Rightarrow \|Ax-b\| = \|\operatorname{Proj}_{\operatorname{Im}(A)}(b) - b\| = \min_{z \in \operatorname{Im}(A)}\|z-b\| = \min_{x \in \mathbb{C}^n}\|Ax-b\|.
\end{align}
That is, $x$ the least squares problem.
A: You're not using "WLOG" correctly. It's when you're making an assumption that might technically not be true but obviously doesn't affect the logic of the proof. It should be pretty obvious how the proof would work without that assumption. See wikipedia for an example. You assuming that $A$ is full rank is a big assumption, on the other hand, so it doesn't make sense to tag "WLOG" at the start because it drastically changes the problem.
