$\newcommand{\br}{\\}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\P}{\mathbb{P}}$ $\newcommand{\F}{\mathbb{F}}$ $\newcommand{\L}{\mathcal{L}}$ $\newcommand{\spa}[1]{\text{span}(#1)}$ $\newcommand{\dist}[1]{\text{dist}(#1)}$ $\newcommand{\max}[1]{\text{max}(#1)}$ $\newcommand{\min}[1]{\text{min}(#1)}$ $\newcommand{\supr}[1]{\text{sup}(#1)}$ $\newcommand{\infi}[1]{\text{inf}(#1)}$ $\newcommand{\set}[1]{\left\{#1\right\}}$ $\newcommand{\emptyset}{\varnothing}$ $\newcommand{\otherwise}{\text{ otherwise }}$ $\newcommand{\if}{\text{ if }}$ $\newcommand{\proj}{\text{proj}}$ $\newcommand{\union}{\cup}$ $\newcommand{\intercept}{\cap}$ $\newcommand{\abs}[1]{\left| #1 \right|}$ $\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$ $\newcommand{\pare}[1]{\left(#1\right)}$ $\newcommand{\t}[1]{\text{ #1 }}$ $\newcommand{\head}{\text H}$ $\newcommand{\tail}{\text T}$ $\newcommand{\d}{\text d}$ $\newcommand{\limu}[2]{\underset{#1 \to #2}\lim}$ $\newcommand{\der}[2]{\frac{\d #1}{\d #2}}$ $\newcommand{\derw}[2]{\frac{\d #1^2}{\d^2 #2}}$ $\newcommand{\pder}[2]{\frac{\partial #1}{\partial #2}}$ $\newcommand{\pderw}[2]{\frac{\partial^2 #1}{\partial #2^2}}$ $\newcommand{\pderws}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}}$ $\newcommand{\inv}[1]{{#1}^{-1}}$ $\newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $\newcommand{\nullity}[1]{\text{nullity}(#1)}$ $\newcommand{\rank}[1]{\text{rank }#1}$ $\newcommand{\var}[1]{\text{var}(#1)}$ $\newcommand{\tr}[1]{\text{tr}(#1)}$ $\newcommand{\oto}{\text{ one-to-one }}$ $\newcommand{\ot}{\text{ onto }}$ $\newcommand{\ceil}[1]{\lceil#1\rceil}$ $\newcommand{\floor}[1]{\lfloor#1\rfloor}$ $\newcommand{\Re}[1]{\text{Re}(#1)}$ $\newcommand{\Im}[1]{\text{Im}(#1)}$ $\newcommand{\dom}[1]{\text{dom}(#1)}$ $\newcommand{\fnext}[1]{\overset{\sim}{#1}}$ $\newcommand{\transpose}[1]{#1^{\text{T}}}$ $\newcommand{\b}[1]{\boldsymbol{#1}}$ $\newcommand{\None}[1]{}$ $\newcommand{\Vcw}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Vce}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Vcr}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Vct}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Vcy}[6]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{bmatrix}}$ $\newcommand{\Vcu}[7]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{bmatrix}}$ $\newcommand{\vcw}[2]{\begin{matrix} #1 \br #2 \end{matrix}}$ $\newcommand{\vce}[3]{\begin{matrix} #1 \br #2 \br #3 \end{matrix}}$ $\newcommand{\vcr}[4]{\begin{matrix} #1 \br #2 \br #3 \br #4 \end{matrix}}$ $\newcommand{\vct}[5]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \end{matrix}}$ $\newcommand{\vcy}[6]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{matrix}}$ $\newcommand{\vcu}[7]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{matrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Mqr}[4]{\begin{bmatrix} #1 & #2 & #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqt}[5]{\begin{bmatrix} #1 & #2 & #3 & #4 & #5 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mrq}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Mtq}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Mww}[4]{\begin{bmatrix} #1 & #2 \br #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mwe}[6]{\begin{bmatrix} #1 & #2 & #3\br #4 & #5 & #6 \end{bmatrix}}$ $\newcommand{\Mew}[6]{\begin{bmatrix} #1 & #2 \br #3 & #4 \br #5 & #6 \end{bmatrix}}$ $\newcommand{\Mee}[9]{\begin{bmatrix} #1 & #2 & #3 \br #4 & #5 & #6 \br #7 & #8 & #9 \end{bmatrix}}$
Definition: Inconsistent (Overdetermined)

Consider a system of linear equations

$$\b{Ax} = \b{b} $$

where $\b{A} \in \R^{m \times n}, \b{b} \in \R^m, m \geq n $, and $\rank{ \b{A}} = n $.

Note that the number of unknowns, $n $, is no larger than the number of equations, $m $.

If $b $ does not belong to the range of $\b{A} $, i.e. $\b{b} \not\in \mathcal{ R }(\b{A})$, then this system of equations is said to be inconsistant or overdetermined.

In this case, there is no solution to the above set of equations.

Definition: Least-Squares Solution

A vector $\b{ x }^* $ that minimizes $\norm{ \b{Ax} - \b{b}}^2$ is called a least-squares solution; that is, $\forall \b{x} \in \R^n $,

$$\norm{ \b{Ax} -\b{b}}^2 \geq \norm{ \b{A x^*} - \b{b}}^2 $$

Lemma 12.1

Let $\b{A} \in \R^{m \times n}, m \geq n. $ Then,

$$\rank{ \b{A}} = n \iff \rank{ \transpose{ \b{A}} \b{A}}= n\ \text{(the square matrix }\transpose{ \b{A}}\b{A}\text{ is non singular)}$$

Proof 
  </span>
</span>
<span class="proof__expand"><a>[expand]</a></span>

Suppose that $\rank{ \b{A}} = n $.

To show $\rank{ \transpose{ \b{A}} \b{A}}= n$, it is equivalent to show $\nullity{ \transpose{ \b{A}} \b{A}} = \set{ \b{0}} $.

Fix $\b{x} \in \mathcal{ N }(\transpose{ \b{A}}\b{A})$, then $\transpose{\b{A}} \b{A} \b{x} = \b{0}$.

That implies

$$\norm{ \b{Ax}}^2 = \transpose{ \b{x}} \transpose{ \b{A}} \b{A} \b{x} = \b{0} $$

Therefore,

$$\norm{ \b{Ax}}^2 = \b{0} $$

that is,

$$\b{Ax} = \b{0}$$

$\rank{ \b{A}} = n \implies \b{x} = \b{0} $.

Proof 
  </span>
</span>
<span class="proof__expand"><a>[expand]</a></span>

Suppose that rank $\transpose{ \b{A}} \b{A} = n $, that is, $\mathcal{ N } (\transpose{ \b{A}} \b{A}) = \set{ \b{0}}.$

To show $\rank{ \b{A}} = n$. It is equivalent to show that $\mathcal{ N } (\b{A}) = \set{ \b{0}}. $

Fix $\b{x} \in \mathcal{ N } (\b{A})$, then $\b{Ax} = \b{0} $.

Then, $\transpose{ \b{A}} \b{Ax} = \b{0}$. Hence, $\b{x} = \b{0} $.

Theorem

The unique vector $\b{x}^* $ that minimizes $\norm{ \b{Ax} - \b{b}}^2$ is given by the solution to the equation $\transpose{ \b{A}} \b{A} \b{x} = \transpose{ \b{A}} \b{b}$ i.e.

$$\b{x}^* = \inv{(\transpose{ \b{A}} \b{A})} \transpose{ \b{A}} \b{b} $$

Theorem

Let $\b{h} \in \mathcal{ R } (\b{A}) $ be such that $\b{h} - \b{b} $ is orthogonal to $\mathcal{ R }(\b{A}) $. Then $\b{h} = \b{A} \b{x}^* = \b{A} \inv{(\transpose{ \b{A}} \b{A})} \transpose{ \b{A}} \b{b}$.