Four fundamental subspaces
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\newcommand{\trans}{^\top} \newcommand{\adj}{^{\rm adj}} \newcommand{\cof}{^{\rm cof}} \newcommand{\inp}[2]{\left\langle#1,#2\right\rangle} \newcommand{\dunion}{\mathbin{\dot\cup}} \newcommand{\bzero}{\mathbf{0}} \newcommand{\bone}{\mathbf{1}} \newcommand{\ba}{\mathbf{a}} \newcommand{\bb}{\mathbf{b}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bd}{\mathbf{d}} \newcommand{\be}{\mathbf{e}} \newcommand{\bh}{\mathbf{h}} \newcommand{\bp}{\mathbf{p}} \newcommand{\bq}{\mathbf{q}} \newcommand{\br}{\mathbf{r}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\bu}{\mathbf{u}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bw}{\mathbf{w}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\nul}{\operatorname{null}} \newcommand{\rank}{\operatorname{rank}} %\newcommand{\ker}{\operatorname{ker}} \newcommand{\range}{\operatorname{range}} \newcommand{\Col}{\operatorname{Col}} \newcommand{\Row}{\operatorname{Row}} \newcommand{\spec}{\operatorname{spec}} \newcommand{\vspan}{\operatorname{span}} \newcommand{\Vol}{\operatorname{Vol}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\idmap}{\operatorname{id}} \newcommand{\am}{\operatorname{am}} \newcommand{\gm}{\operatorname{gm}} \newcommand{\mult}{\operatorname{mult}} \newcommand{\iner}{\operatorname{iner}}$
from lingeo import random_good_matrix, random_int_list
Recall that if $V$ is a subspace in $\mathbb{R}^n$, then its orthogonal complement is
$$V^\perp = \{\bw\in\mathbb{R}^n : \inp{\bw}{\bv} = 0 \text{ for all }\bv\in V\}.$$
Suppose $V = \vspan(S)$ for some finite set $S$.
(We will show in the next chapter that in fact every subspace in $\mathbb{R}^n$ can be generated by a finite set.)
Then every matrix $\bb$ can be written as a unique representation
$$\bb = \bw + \bh$$
such that $\bw\in V$ and $\bh\in V^\perp$.
Also, $(V^\perp)^\perp = V$.
Let $A$ be an $m\times n$ matrix.
Let $R$ be the reduced echelon form of $A$ and $r$ the number of its pivots.
Consider the augmented matrix $\left[\begin{array}{c|c} A & I_m \end{array}\right]$.
Let $\left[\begin{array}{c|c} R & B \end{array}\right]$ be its reduced echelon form.
Then $\Row(A)$ and $\ker(A)$ are subspaces in $\mathbb{R}^n$ and they are the orthogonal complement of each other.
Let $\beta_R = \{\br_1,\ldots,\br_r\}$ be the set of nonzero rows in $R$.
Then $\Row(A) = \vspan(\beta_R)$.
Let $\beta_K = \{\bh_1, \ldots, \bh_{n-r}\}$ be the set of homogeneous solutions solved by setting one free variable as $1$ and others as $0$.
Then $\ker(A) = \vspan(\beta_K)$.
On the other hand, $\Col(A)$ and $\ker(A\trans)$ are subspaces in $\mathbb{R}^m$ and they are the orthogonal complement of each other.
The subspace $\ker(A\trans)$ is called the left kernel of $A$.
Let $\beta_C = \{ \bu_1,\ldots, \bu_r \}$ be the set of columns of $A$ corresponding to the pivots of $R$.
Then $\Col(A) = \vspan(\beta_C)$.
Let $\beta_L = \{ \bb_1,\ldots,\bb_{m-r} \}$ be the last $m-r$ rows in $B$.
Then $\ker(A\trans) = \vspan(\beta_L)$.
We call each of $\beta_R$, $\beta_K$, $\beta_C$, $\beta_L$ the standard basis of the corresponding subspace.
(We have not yet mentioned what is a basis, so you may view them as standard generating sets of the corresponding subspaces.
But we will prove they are really a basis in the future.)
執行下方程式碼。
矩陣 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 的最簡階梯形式矩陣。
Run the code below. Let $\left[\begin{array}{c|c} R & B \end{array}\right]$ be the reduced echelon form of $\left[\begin{array}{c|c} A & I \end{array}\right]$.
### code
set_random_seed(0)
print_ans = False
m,n,r = 3,5,2
A, R, pivots = random_good_matrix(m,n,r, return_answer=True)
AI = A.augment(identity_matrix(3), subdivide=True)
RB = AI.rref()
B = RB[:,n:]
print("[ A | I ] =")
show(AI)
print("[ R | B ] =")
show(RB)
if print_ans:
Rp = R[:r,:] ### r x n
H = zero_matrix(Rp.base_ring(), n, n-r) ### n x (n-r)
free = [i for i in range(n) if i not in pivots]
H[pivots] = -Rp[:, free]
H[free] = identity_matrix(n-r)
C = A[:, pivots] ### m x r
Bp = B[r:,:] ### (m-r) x m
print("beta R = rows of")
show(Rp)
print("beta K = columns of")
show(H)
print("beta C = columns of")
show(C)
print("beta L = rows of")
show(Bp)
執行以下程式碼。
令 $S = \{ \br_1, \br_2, \br_3 \}$ 為矩陣 $A$ 的各列向量
且 $V = \vspan(S)$。
求 $T$ 使得 $V^\perp = \vspan(T)$。
Run the code below. Let $S = \{ \br_1, \br_2, \br_3 \}$ be the columns of $A$ and $V = \vspan(S)$. Find $T$ such that $V^\perp = \vspan(T)$.
### code
set_random_seed(0)
print_ans = False
m,n,r = 3,5,2
A, R, pivots = random_good_matrix(m,n,r, return_answer=True)
print("A =")
show(A)
if print_ans:
H = zero_matrix(R.base_ring(), n, n-r)
free = [i for i in range(n) if i not in pivots]
H[pivots,:] = R[:r,free]
H[free,:] = identity_matrix(n-r)
print("T = the set of columns of")
show(H)
執行以下程式碼。
令 $S = \{ \bu_1, \bu_2 \}$ 為矩陣 $A$ 的各行向量
且 $V = \vspan(S)$。
求 $\bb$ 在 $V$ 上的投影。
Run the code below. Let $S = \{ \bu_1, \bu_2 \}$ be the columns of $A$ and $V = \vspan(S)$. Find the projection of $\bb$ onto $V$.
### code
set_random_seed(0)
print_ans = False
A = random_good_matrix(5,2,2)
print("A =")
show(A)
b = vector(random_int_list(5))
print("b =", b)
if print_ans:
ATAinv = (A.transpose() * A).inverse()
w = A * ATAinv * A.transpose() * b
print("projection =", w)
執行以下程式碼。
令 $S = \{ \bu_1, \bu_2, \bu_3 \}$ 為矩陣 $A$ 的各行向量
且 $V = \vspan(S)$。
求 $\bb$ 在 $V$ 上的投影。
(如果你發覺 $A\trans A$ 不可逆的話﹐
記得把一些不重要的向量拿掉。
只要生成出來是 $V$,
不一定要把全部向量放進去。)
Run the code below. Let $S = \{ \bu_1, \bu_2, \bu_3 \}$ be the columns of $A$ and $V = \vspan(S)$. Find the projection of $\bb$ onto $V$. (If you found that $A\trans A$ is not invertible, then you might consider removing some redundant columns. After all, all we care about is $V$ but not the vectors.
### code
set_random_seed(0)
print_ans = False
A = random_good_matrix(5,3,2)
print("A =")
show(A)
b = vector(random_int_list(5))
print("b =", b)
if print_ans:
Ap = A[:,pivots]
ATAinv = (Ap.transpose() * Ap).inverse()
w = Ap * ATAinv * Ap.transpose() * b
print("projection =", w)
令 $A$ 為一 $m\times n$ 矩陣。
我們知道高斯消去法不會影響列空間,
因此自然地 $\Row(A) = \vspan(\beta_R)$。
以下我們說明為什麼 $\ker(A) = \vspan(\beta_K)$。
Let $A$ be an $m\times n$ matrix. We know that row operations does not change the row space, so $\Row(A) = \vspan(\beta_R)$.
Here we study why $\ker(A) = \vspan(\beta_K)$.
令 $R$ 為 $A$ 的最簡階梯形式矩陣。
我們把領導變數拉到左邊、自由變數拉到右邊
(最後求完解以後再把變數順序拉回來就好),
因此我們可以假設 $R$ 的非零列長得像 $R' = \begin{bmatrix} I_r & Y \end{bmatrix}$。
我們把每個 $\mathbb{R}^n$ 的向量都寫成 $(\bv_1, \bv_2)$ 使得 $\bv_1\in\mathbb{R}^r$ 而 $\bv_2\in\mathbb{R}^{n-r}$。
說明
Let $R$ be the reduced echelon form of $A$. For convenience, we assume all leading variables are on the left while all the free variables are on the right. (We may change the order of the variables again once we have solved the system.) Therefore, we may assume the nonzero rows of $R$ has the form $R' = \begin{bmatrix} I_r & Y \end{bmatrix}$. Let us consider every vector in $\mathbb{R}^n$ as $(\bv_1, \bv_2)$, where $\bv_1\in\mathbb{R}^r$ and $\bv_2\in\mathbb{R}^{n-r}$. Show that
$$ \ker(A) = \ker(R') = \{(-Y\bv_2, \bv_2): \bv_2\in\mathbb{R}^{n-r}\}. $$令 $H$ 為一 $n\times (n-r)$ 的矩陣﹐
其各行向量是由 $\beta_K$ 中的向量組成。
觀察到 $H = \begin{bmatrix} -Y \\ I_{n-r} \end{bmatrix}$。
說明 $H\bv_2 = (-Y\bv_2, \bv_2)$、
因此 $\ker(A) = \Col(H) = \vspan(\beta_K)$。
Let $H$ be the $n\times (n-r)$ matrix whose columns are vectors in $\beta_K$. Observe that $H = \begin{bmatrix} -Y \\ I_{n-r} \end{bmatrix}$.
Show that $H\bv_2 = (-Y\bv_2, \bv_2)$. Therefore, $\ker(A) = \Col(H) = \vspan(\beta_K)$。
藉由 $H\trans$ 和 $R'$ 的形式的相似性,
說明 $\ker(H\trans) = \Col(R'\trans)$。
Based on the similarity of the structures of $H\trans$ and $R'$, show that $\ker(H\trans) = \Col(R'\trans)$.
若 $S\subseteq\mathbb{R}^n$ 是一群有限個數的向量而 $V = \vspan(S)$。
證明 $(V^\perp)^\perp = V$。
Suppose $S\subseteq\mathbb{R}^n$ is a finite set of vectors and $V = \vspan(S)$. Show that $(V^\perp)^\perp = V$.
令 $A$ 為一 $m\times n$ 矩陣。
令 $\bu_1,\ldots,\bu_n$ 為 $A$ 的各行向量。
接下來我們說明 $\Col(A) = \vspan(\beta_C)$ 及 $\ker(A\trans) = \vspan(\beta_L)$。
令 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 為 $\left[\begin{array}{c|c} A & I_m \end{array}\right]$ 的最簡階梯形式矩陣。
Let $A$ be an $m\times n$ matrix. Let $\bu_1,\ldots,\bu_n$ be the columns of $A$. We will show that $\Col(A) = \vspan(\beta_C)$ and $\ker(A\trans) = \vspan(\beta_L)$. Let $\left[\begin{array}{c|c} R & B \end{array}\right]$ be the reduced echelon form of $\left[\begin{array}{c|c} A & I_m \end{array}\right]$.
令 $\beta_K = \{\bh_1,\ldots,\bh_{n-r}\}$。
令 $j$ 為 $R$ 的第 $i$ 個軸。
藉由 $A\bh_i = \bzero$ 來說明 $\bu_j\in\vspan(\beta_C)$、
並證明 $\Col(A) = \vspan(\beta_C)$。
Let $\beta_K = \{\bh_1,\ldots,\bh_{n-r}\}$. Let $j$ be the $i$-th pivot of $R$. Use the fact that $A\bh_i = \bzero$ to show that $\bu_j\in\vspan(\beta_C)$ and $\Col(A) = \vspan(\beta_C)$.
令 $\hat{R}$ 為 $R$ 中對應到軸的那幾個行向量所組成的 $m\times r$ 矩陣。
令 $\hat{A}$ 為 $A$ 中對應到 $R$ 的軸的那幾個行向量所組成的 $m\times r$ 矩陣。
藉由 $\ker(\hat{R}) = \{\bzero\}$ 來說明 $\ker(\hat{A}) = \{\bzero\}$。
Let $\hat{R}$ be the $m\times r$ submatrix of $R$ induced on the columns corresponding to the pivots. Let $\hat{A}$ be the $m\times r$ submatrix of $A$ induced on the columns corresponding to the pivots of $R$. Use the fact that $\ker(\hat{R}) = \{\bzero\}$ to show that $\ker(\hat{A}) = \{\bzero\}$.
接著我們說明 $\beta_C$ 和 $\beta_L$ 中的向量互相垂直。
令 $\be_1,\ldots,\be_n$ 為 $I_n$ 中的行向量。
觀察到
利用這個性質推得 $R\be_i = B\bu_i$ 並說明 $\bu_i$ 和 $\beta_L$ 中的各向量垂直。
Now we show that any vector in $\beta_C$ is orthogonal to any vector in $\beta_L$.
Let $\be_1,\ldots,\be_n$ be the columns of $I_n$. Observe that
$$ \left[\begin{array}{c|c} A & I_m \end{array}\right] \begin{bmatrix} \be_i \\ -\bu_i \end{bmatrix} = \bzero. $$Use this fact to show that $R\be_i = B\bu_i$ and that $\bu_i$ is orthogonal to any vector in $\beta_L$.
由前一題我們已知 $\Col(A)^\perp \supseteq \vspan(\beta_L)$。
接著我們證明 $\Col(A)^\perp \subseteq \vspan(\beta_L)$。
令 $\bb\in\Col(A)^\perp$ 則 $\bb\trans A = \bzero$。
考慮 $\bv\trans = \bb\trans \left[\begin{array}{c|c} A & I_m \end{array}\right] =
\left[\begin{array}{c|c} \bzero\trans & \bb\trans\end{array}\right]$。
說明 $\bv\trans$ 也落在 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 的列空間中﹐進而說明 $\bb\in\vspan(\beta_L)$。
因為 $\Col(A)^\perp = \ker(A\trans)$﹐
所以 $\ker(A\trans) = \vspan(\beta_L)$。
By the previous problem, we know that $\Col(A)^\perp \supseteq \vspan(\beta_L)$. Now we show that $\Col(A)^\perp \subseteq \vspan(\beta_L)$. Let $\bb\in\Col(A)^\perp$ 則 $\bb\trans A = \bzero$. Consider $\bv\trans = \bb\trans \left[\begin{array}{c|c} A & I_m \end{array}\right] = \left[\begin{array}{c|c} \bzero\trans & \bb\trans\end{array}\right]$. Show that $\bv\trans$ is in the row space of $\left[\begin{array}{c|c} R & B \end{array}\right]$. Therefore, $\bb\in\vspan(\beta_L)$.
Since $\Col(A)^\perp = \ker(A\trans)$, we know $\ker(A\trans) = \vspan(\beta_L)$.
其實我們也可以證明 $\ker(A\trans)^\perp = \Col(A)$。
如此一來可以再次說明 $(V^\perp)^\perp = V$。
因為我已知 $\ker(A\trans)^\perp \supseteq \Col(A)$。
接著我們證明 $\ker(A\trans)^\perp \subseteq \Col(A)$。
令 $\bb\in\ker(A\trans)^\perp$ 因此 $B\bb$ 的最後 $m-r$ 項都是 $0$。
說明存在 $\bv\in\mathbb{R}^n$ 使得
$$
\left[\begin{array}{c|c} R & B \end{array}\right] \begin{bmatrix} \bv \\ \bb \end{bmatrix} = \bzero.
$$
因此 $A\bv + I_m\bb = \bzero$﹐得到 $\bb\in\Col(A)$。
In fact, we may prove that $\ker(A\trans)^\perp = \Col(A)$. This provides an alternative proof to $(V^\perp)^\perp = V$.
Since we already know that $\ker(A\trans)^\perp \supseteq \Col(A)$, it is enough to show that $\ker(A\trans)^\perp \subseteq \Col(A)$. Let $\bb\in\ker(A\trans)^\perp$. Thus, the last $m-r$ entries of $B\bb$ are zero. Show that there is a vector $\bv\in\mathbb{R}^n$ such that
$$ \left[\begin{array}{c|c} R & B \end{array}\right] \begin{bmatrix} \bv \\ \bb \end{bmatrix} = \bzero. $$Therefore, $A\bv + I_m\bb = \bzero$﹐得到 $\bb\in\Col(A)$.
若 $S\subseteq\mathbb{R}^n$ 是一群有限個數的向量而 $V = \vspan(S)$。
依照以下步驟證明:
任何向量 $\bb\in\mathbb{R}^n$ 都可以寫成 $\bb = \bw + \bh$
使得 $\bw\in V$ 且 $\bh\in V^\perp$。
Suppose $S\subseteq\mathbb{R}^n$ is a finite set of vectors and $V = \vspan(S)$. Use the given instructions to show that: Any vector $\bb\in\mathbb{R}^n$ can be written as $\bb = \bw + \bh$ such that $\bw\in V$ and $\bh\in V^\perp$.
令 $A_S$ 為一矩陣其各行向量由 $S$ 的各向量組成﹐
並算出其 $\beta_C$。
令 $A$ 為 $A_S$ 中只留 $\beta_C$ 中向量的子矩陣。
由前一題我們知道 $\Col(A_S) = \Col(A) = V$
且 $\ker(A) = \{\bzero\}$。
Let $A_S$ be the matrix whose columns are vectors in $S$. Find the $\beta_C$ of $A_S$. Let $A$ be the submatrix of $A_S$ composed of vectors in $\beta_C$. By the previous problem, we know $\Col(A_S) = \Col(A) = V$ and $\ker(A) = \{\bzero\}$.
說明 $A\trans A$ 可逆。
同時驗證
符合我們要的條件。
Explain why $A\trans A$ is invertible. Also, verify that
$$ \begin{aligned} \bw &= A(A\trans A)^{-1}A\trans \bb, \\ \bh &= \bb - \bw \end{aligned} $$satisfy the desired properties.
證明 $\bb$ 寫成 $\bw + \bh$ 的方法唯一。
也就是說﹐如果 $\bb = \bw_1 + \bh_1 = \bw_2 + \bh_2$
使得 $\bh_1,\bh_2\in V$ 且 $\bw_1,\bw_2\in V^\perp$﹐
則 $\bh_1 = \bh_2$ 且 $\bw_1 = \bw_2$。
Show that the decomposition $\bb = \bw + \bh$ is unique. That is, if $\bb = \bw_1 + \bh_1 = \bw_2 + \bh_2$ such that $\bh_1,\bh_2\in V$ and $\bw_1,\bw_2\in V^\perp$, then $\bh_1 = \bh_2$ 且 $\bw_1 = \bw_2$.