Big Picture of Linear Algebra

The Importance of Strang's Big Picture

下圖是Strang給的Big Picture of Linear Algebra，既然敢叫Big Picture，必定是有它厲害的地方，不過Strang並沒有說得很清楚，本文說明這張圖為什麼很重要。

不過因為這張圖有稜有角不好畫，所以我都會快速畫兩個8，如下圖。

說明一下縮寫表示的意思
CS表示column space
RS表示row space
R表示range
N表示nullspace

注意到$CS(A)=R(A)$, $RS(A)=CS(A^t)$。

圖形中為了避免出現太多不同的符號，所以不寫CS跟RS，只用R跟N來表示這些空間。

證明垂直的時候，比較偏好使用CS跟RS。

證明維度的時候，比較偏好使用R。

1. Visualization: Perpendicular

$RS(A)\perp N(A)$
$CS(A)\perp N(A^t)$

Proof: Let $\mathbf{v}$ be a vector in $N(A)$ and $\mathbf{r}$ be a row of $A$. Then $\langle \mathbf{r}, \mathbf{v}\rangle=0$ by the definition of multiplication and $A\mathbf{v}=\mathbf{0}$. The second part follows immediately from considering the transpose of $A$ in the first part and the row space of $A^t$ is the same as the column space of $A$.

2. Visualization: Orthogonal Complement

$RS(A)^{\perp}=N(A)$
$CS(A)^{\perp}=N(A^t)$

3. Visualization: Dimension

Let $A$ be a $m\times n$ matrix. We can view $A$ as a linear transformation $A:F^n\to F^m$ defined by $A(\mathbf{v})=A\mathbf{v}$.

We can also view $A^t$ as a linear transformation $A^t:F^m\to F^n$ defined by $A^t(\mathbf{w})=A^t\mathbf{w}$.

By the dimension theorem,
$n=\text{nullity}(A)+\text{rank}(A)=\dim{N(A)}+\dim{R(A)}$
$m=\text{nullity}(A^t)+\text{rank}(A^t)=\dim{N(A^t)}+\dim{R(A^t)}$

Since $\text{rank}(A)=\text{rank}(A^t)$, the following identities follows immediately from the above ones. $n=\text{nullity}(A)+\text{rank}(A^t)=\dim{N(A)}+\dim{R(A^t)}$
$m=\text{nullity}(A^t)+\text{rank}(A)=\dim{N(A^t)}+\dim{R(A)}$

4. $N(A^t A)=N(A), R(A^t)=R(A^t A)$

$N(A^t A)=N(A)$

Proof: ($\supseteq$) is trivial. We show the other direction ($\subseteq$) $$\begin{array}{ll} & \mathbf{v}\in N(A^t A) \\ \Rightarrow & A^t A\mathbf{v}=\mathbf{0} \\ \Rightarrow & \mathbf{v}^t A^t A \mathbf{v}=\mathbf{0} \\ \Rightarrow & (A\mathbf{v})^t (A \mathbf{v})=\mathbf{0} \\ \Rightarrow & A\mathbf{v}=\mathbf{0} \\ \Rightarrow & A\mathbf{v}\in N(A) \end{array}$$

$R(A^t)=R(A^t A)$

Proof: ($\supseteq$) is trivial. We show the other direction ($\subseteq$) $$\begin{array}{lll} \dim{R(A^t A)} & = & n-\dim{N(A^t A)} \\ & = & n-\dim{N(A)} \\ & = & \dim{R(A)} \\ & = & \dim{R(A^t)} \end{array}$$ Since $R(A^t A)$ is a subspace of $R(A^t)$ and they have the same dimension, they are identical.

5. Columns of $A$ are linear independent $\Leftrightarrow$ $A^t A$ is invertible

Remark: This is a key step of finding the least square solution or orthogonal projection.

Proof: Let $A$ be a $m\times n$ matrix. $$\begin{array}{cl} & \text{columns of }A \text{ are linear independent} \\ \Rightarrow & \text{rank}(A)=n \\ \stackrel{R(A^t A)=R(A)}{\Rightarrow} & \text{rank}(A^t A)=\text{rank}(A)=n \\ \stackrel{A^t A\text{ is }n\times n}{\Rightarrow} & A^t A\text{ is invertible} \end{array}$$

6. $A^t A$

當我們考慮$A^t A$的時候，左右兩個圖會是相同的而併在一起。

7. Visualization: Least Square

8. Visualization: Pseudoinverse