最小ノルム解の導出と図による理解

$AA^{\top}$ が正則であることを証明する。具体的には，行列が正則であることの意味と5つの条件の条件4「$AA^{\top}\overrightarrow{x}=\overrightarrow{0}$ なら $\overrightarrow{x}=\overrightarrow{0}$」を証明する。

$AA^{\top}\overrightarrow{x}=\overrightarrow{0}$ なら $\overrightarrow{x}^{\top}AA^{\top}\overrightarrow{x}=0$，つまり $(A^{\top}\overrightarrow{x})^{\top}(A^{\top}\overrightarrow{x})=0$

$\|A^{\top}\overrightarrow{x}\|_2^2=0$

長さが $0$ であるベクトルは $\overrightarrow{0}$ のみなので

$A^{\top}\overrightarrow{x}=\overrightarrow{0}$

ここで，定理の仮定より $A$ の行ベクトルが線形独立なので，$A^{\top}$ の列ベクトルが線形独立。つまり $\overrightarrow{x}=\overrightarrow{0}$ がわかる。

$A\overrightarrow{x_*}=(AA^{\top})(AA^{\top})^{-1}\overrightarrow{b}=\overrightarrow{b}$

$\|\overrightarrow{x}\|^2_2\\ =\|\overrightarrow{x}-\overrightarrow{x}_*+\overrightarrow{x}_*\|_2^2\\ =\|\overrightarrow{x}-\overrightarrow{x_*}\|_2^2+\|\overrightarrow{x}_*\|_2^2+2(\overrightarrow{x}-\overrightarrow{x_*})^{\top}\overrightarrow{x_*}$

ここで「$A\overrightarrow{x}=\overrightarrow{b}$ のとき第三項が $0$」なら $\|\overrightarrow{x}\|_2\geqq \|\overrightarrow{x_*}\|_2$ がわかる。以下では「$A\overrightarrow{x}=\overrightarrow{b}$ のとき第三項が $0$」を示す：

$(\overrightarrow{x}-\overrightarrow{x_*})^{\top} \overrightarrow{x_*}\\ =(\overrightarrow{x}-\overrightarrow{x_*})^{\top} A^{\top}(AA^{\top})^{-1}\overrightarrow{b}\\ =(A\overrightarrow{x}-A\overrightarrow{x_*})^{\top}(AA^{\top})^{-1}\overrightarrow{b}\\ =(\overrightarrow{b}-\overrightarrow{b})(AA^{\top})^{-1}\overrightarrow{b}\\ =0$

$\mathrm{Im}(A^{\top})=(\mathrm{Ker}\:A)^{\perp}$ である（有名な公式）。

よって，$\mathrm{Im}(A^{\top})$ への射影を考える。これは射影行列のイメージと楽しい公式より，$P=A^{\top}(AA^{\top})^{-1}A$ をかけることに対応する。

つまり，$P\overrightarrow{x_0}=\overrightarrow{x_*}$ を示せばよい。

これは $\overrightarrow{x_*}=A^{\top}(AA^{\top})^{-1}\overrightarrow{b}$ と $A\overrightarrow{x_0}=\overrightarrow{b}$ から分かる。