# 秩與核數

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

from lingeo import random_good_matrix

## Main idea

Recall that the number of of pivots of a matrix is the number of nonzero rows in its reduced echelon form.

Let $A$ be an $m\times n$ matrix with $r$ pivots.
Since we know bases of its four fundamental subspaces, we have
1. $\dim(\operatorname{Row}(A)) = \dim(\operatorname{Col}(A)) = r$.
2. $\dim(\operatorname{ker}(A)) = n - r$.
3. $\dim(\operatorname{ker}(A^\top)) = m - r$

The value $r$ is the **rank** of $A$, denoted as $\operatorname{rank}(A)$,
the value $n - r$ is the **nullity** of $A$, denoted as $\operatorname{null}(A) = n - r$,
while $m - r$ is usually referred to as the **left nullity** of $A$.

Note that $r$ is also the number of leading variables, and $n - r$ is also the number of free variables.

##### Dimension theorem (matrix form)

Let $A$ be an $m\times n$ matrix.
Then $\operatorname{rank}(A) + \operatorname{nullity}(A) = n$, the number of columns.

## Side stories
- low-rank matrix
- row rank and column rank

## Experiments

##### Exercise 1

執行下方程式碼。
試著看出 $A$ 的秩、核數、以及左核數。

### code
set_random_seed(0)
print_ans = False
r = choice([3,2,1,0])
m,n,r = 3,4,r
A = random_good_matrix(m,n,r)

print("A =")
show(A)

if print_ans:
    print("rank =", r)
    print("nullity =", n - r)
    print("left nullity =", m - r)

:::warning
- [x] 不用一直跳出數學模式，像是 $\rank(A) = r = 3$ 就好
:::

$Ans:$

藉由 `seed = 0`執行程式碼後得
$$
A = \begin{bmatrix}
1 & 5 & -5 & -5 \\
3 & 15 & -14 & -15 \\
6 & 30 & -27 & -29
\end{bmatrix}
$$
將 $A$ 進行列運算後得矩陣 $R$
$$R = \begin{bmatrix}
1 & 5 & 0 & 0 \\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
\end{bmatrix}
$$

所以由 $R$ 可得
$\operatorname{rank}(A) = r = 3$
$\operatorname{nullity}(A) = n - r = 1$
$\operatorname{left nullity}(A)= m - r = 0$
其中，令 $A$ 為一 $m\times n$ 矩陣，$r$ 為軸數。

## Exercises

##### Exercise 2

令 $A$ 為一矩陣且其秩為 $r$。
回顧 $r$ 同時是列空間和行空間的維度。
以下討論秩的一些基本性質。

##### Exercise 2(a)

說明 $\operatorname{rank} \begin{bmatrix} A & O \end{bmatrix} =
\operatorname{rank} \begin{bmatrix} A \\ O \end{bmatrix} = r$。
更一般來說 $\operatorname{rank} \begin{bmatrix} A & O \\ O & O \end{bmatrix} = r$。

:::info
原本想的是你們可以用行空間、列空間來解釋，但你們的說法也可以~
:::

$Ans:$

$A$ 的秩本來就為 $r$，且 $O$ 不會影響軸的個數，
所以 $\operatorname{rank} \begin{bmatrix} A & O \end{bmatrix} =
\operatorname{rank} \begin{bmatrix} A \\ O \end{bmatrix} =\operatorname{rank} \begin{bmatrix} A & O \\ O & O \end{bmatrix}=
r$。

##### Exercise 2(b)

說明對大小適當的矩陣 $B,C,D$ 來說﹐
$\operatorname{rank} \begin{bmatrix} A & B \end{bmatrix} \geq r$ 且
$\operatorname{rank} \begin{bmatrix} A \\ C \end{bmatrix} \geq r$。
更一般來說 $\operatorname{rank} \begin{bmatrix} A & B \\ C & D \end{bmatrix} \geq r$。

:::warning
題目有錯，應該都要換成 $\geq$。
這題我直接掛懸賞，不會扣分。
:::

$Ans:$

$\operatorname{rank} \begin{bmatrix} A & B \end{bmatrix} \leq r$ 且
$\operatorname{rank} \begin{bmatrix} A \\ C \end{bmatrix} \leq r$。

$\operatorname{rank} \begin{bmatrix} A & B \\ C & D \end{bmatrix} =\operatorname{rank} \begin{bmatrix} A & B \end{bmatrix} =\operatorname{rank} \begin{bmatrix} A \\ C \end{bmatrix} \leq r$ 。

##### Exercise 3

證明所有秩為 $1$ 的 $m\times n$ 矩陣 $A$ 都可寫成 $A = {\bf u}{\bf v}^\top$﹐
其中 ${\bf u}\in\mathbb{R}^m$ 而 ${\bf v}\in\mathbb{R}^n$ 被視為是行向量。

:::warning
差很多喔，再想想。
如果秩為 $1$ 的話，行空間維度和列空間維度都是 $1$。
因為裡面的所有向量都平行。
:::

$Ans:$

如果秩為 $1$ 的話，行空間維度和列空間維度都是 $1$。
因為裡面的所有向量都平行。

$\bu = \begin{bmatrix} u_1\\ \vdots \\ u_m \end{bmatrix}$, $\bv=\begin{bmatrix}v_1&\ldots&v_m\end{bmatrix}$
$\bf u\bf v^\top=\begin{bmatrix}u_1v_1&\ldots&u_1v_m\\\ldots& &\ldots\\u_nv_1&\ldots&u_mv_n\end{bmatrix}$

所以，$A = {\bf u}{\bf v}^\top$。

##### Exercise 4

如果沒有先前的理論證明﹐很難想像列空間和行空間的維度永遠是一樣的。
（而且它們還一個在 $\mathbb{R}^m$ 中、另一個在 $\mathbb{R}^n$ 裡！）
依照以下的方式再次看出這兩個空間的維度相同。

##### Exercise 4(a)

令 $A$ 為一 $m\times n$ 矩陣、
$QA$ 為一 $m\times m$ 可逆矩陣、
$AP$ 為一 $n\times n$ 可逆矩陣。
回顧為什麼 $QA$ 和 $A$ 的列空間相同。
同理 $AP$ 和 $A$ 的行空間相同。

:::warning
重點是那個 "故" 都沒解釋
:::

$Ans:$

參考 [204-6(a)](https://hackmd.io/NaN1zN15R_WyWQg8M7TjlA#Exercise-6a)。

<!--
$A$為一$m\times n$矩陣，
且 $QA$ 為一$m\times n$矩陣，
$AP$ 為一$m\times n$矩陣，
故 $QA$ 和 $A$ 的列空間相同，都為 $n$，
$AP$ 和 $A$ 的行空間相同，都為 $m$。
-->

##### Exercise 4(b)

令 $Q$ 為一可逆矩陣且
$S = \{{\bf u}_1,\ldots,{\bf u}_k\}$ 是線性獨立的向量集合。
證明 $\{ Q{\bf u}_1,\ldots,Q{\bf u}_k \}$ 也線性獨立。

令 $A$ 為一 $m\times n$ 矩陣、
$Q$ 為一 $m\times m$ 可逆矩陣、
$P$ 為一 $n\times n$ 可逆矩陣。
藉此證明 $AP$ 和 $A$ 的列空間維度相同。
同理 $QA$ 和 $A$ 的行空間維度相同。

**[由汪駿佑同學提供]**
$Ans:$

假設 $S = \{{\bf u}_1,\ldots,{\bf u}_k\}$ 線性獨立。
考慮 $\{ Q{\bf u}_1,\ldots,Q{\bf u}_k \}$ 是否線性獨立。
若
$$
c_1Q\bu_1 + \cdots + c_kQ\bu_k = \bzero.
$$
則將 $Q$ 提出可得
$$Q(c_1\bu_1 + \cdots + c_k\bu_k) = \bzero.
$$
因為 $Q$ 可逆，所以
$$
c_1\bu_1 + \cdots + c_k\bu_k = Q^{-1}\bzero = \bzero.
$$
再加上 ${\{\bu_1,\ldots,\bu_k}\}$ 為線性獨立，我們知道
$$
c_1Q\bu_1 + \cdots + c_kQ\bu_k = \bzero
$$
的解僅有 $c_1= \cdots = c_k = 0$，符合線性獨立的條件，故 $\{ Q{\bf u}_1,\ldots,Q{\bf u}_k \}$ 線性獨立。

接著我們證明 $QA$ 和 $A$ 的行空間維度相同。
在 $A$ 的行向量中取出一些向量 $\beta_C$ 使得其為 $\Col(A)$ 的基底。
則
$$
Q\beta_C = \{Q\bu : \bu\in\beta_C\}
$$
為 $QA$ 中的一些行向量。
由於 $Q$ 可逆、且 $\beta_C$ 獨立，我們知道
$$\dim(\Col(QA)) \geq |Q\beta_C| = |\beta_C| = \dim(\Col(A)).
$$
同理，令 $B = QA$，則 $A = Q^{-1}B$。
依照上述同樣的論證，我們知道
所以
$$\dim(\Col(Q^{-1}B)) \geq \dim(\Col(B)),
$$
也就是
$$\dim(\Col(A)) \geq \dim(\Col(QA)),
$$
因此得到 $QA$ 與 $A$ 的行空間維度相同。

最後，由於 $A$ 的列空間即為 $A\trans$ 的行空間。
所以可以用一樣的方法得到 $AP$ 與 $A$ 的列空間維度相同。

##### Exercise 4(c)

說明任一個 $m\times n$ 矩陣 $A$ 都可以利用列運算及行運算變成
$$R = \begin{bmatrix}
I_r & O_{r, n-r} \\
O_{m-r, r} & O_{m-r, n-r} \\
\end{bmatrix}.
$$
藉由基本矩陣的幫忙﹐可以找到
$m\times m$ 的可逆矩陣 $E$ 和
$n\times n$ 的可逆矩陣 $F$
使得 $R = E A F$。

:::warning
寫人話
:::

$Ans:$

矩陣 $A$ 可以經過列運算得到最簡階梯形式。
而這個形式再經過行運算可以得到 $R$。

令 $E_1E_2E_3......E_s =E$ 為紀錄列運算的基本矩陣。
同理，
令 $F_1F_2F_3......F_t = F$ 為紀錄行運算的基本矩陣。
則 $(E_S.......E_2E_1)A(F_1F_2......F_S)=EAF=R$，
所以 $R = E A F$。

##### Exercise 4(d)

可以看出 $R$ 的行空間和列空間維度相同。
證明 $A$ 的行空間和列空間維度也相同。

**[由汪駿佑同學提供]**
$Ans:$
($A: m \times n$ 矩陣 、$Q$ 為一 $m\times m$ 可逆矩陣、$P$ 為一 $n\times n$ 可逆矩陣。)
<!--在此前我們已經知道 $R =EAF$，
其中$E$ 為一 $m\times m$ 可逆矩陣、$F$ 為一 $n\times n$ 可逆矩陣。
另外我們也知道 $EA$ 的行向量維度等於 $A$，與 $AF$ 的列向量維度等於 $A$。那我們可以把將 $EA$ 再右乘一個 $F$，得到 $EAF$，此時 $EAF$ -->

（由 4(a) 的敘述我們可以知道 $QA$ 和 $A$ 的列空間相同，所以 $QA$ 的列空間維度等於 $A$ 的列空間維度。
同理，$AP$ 的行空間維度等於 $A$ 的行空間維度。
再由 4(b) 的敘述得到 $QA$ 與 $A$ 的行空間維度相同，$AP$ 與 $A$ 的列空間維度相同。
最後，由 4(c) 的敘述中得到 $R$ 的行列空間維度相同，而 $R = EAF$，其中 $E$ 為一 $m\times m$ 可逆矩陣、$F$ 為一 $n\times n$ 可逆矩陣。）

結合 4(a)~4(c) 的敘述，我們可以從 $EAF = R$ 這個式子中得知 $R = EAF$ 的列空間等於 $AF$ 的列空間；而 $AF$ 的列空間維度等於 $A$ 的列空間維度，又 $R = EAF$ 的行向量維度與列向量維度相同。

故得證 $A$ 的行空間維度與列空間維度相同。

##### Exercise 5

證明以下關於秩的不等式。

##### Exercise 5(a)

證明 $\operatorname{rank}(A + B) \leq \operatorname{rank}(A) + \operatorname{rank}(B)$。
:::warning
- [x] 你們應該不知道線性變換是什麼吧？

令 $\{\ba_1, \ldots, \ba_n\}$ 及 $\{\bb_1,\ldots,\bb_n\}$ 分別為 $A$ 和 $B$ 的行向量。則 $A + B$ 的行向量為 ...。
因為 $??? \in\vspan\{\ba_1,\ldots,\ba_n,\bb_1,\ldots,\bb_n\}$，
所以 ...。
:::

$Ans:$

令 $\{\ba_1, \ldots, \ba_n\}$ 及 $\{\bb_1,\ldots,\bb_n\}$ 分別為 $A$ 和 $B$ 的行向量。
同時令 $\beta_C(A)$ 和 $\beta_C(B)$ 為 $\Col(A)$ 及 $\Col(B)$ 的基底。
則 $A + B$ 的行向量為 $\ba_i+\bb_i$。
因為 $\ba_i+\bb_i \in\vspan\{\ba_1,\ldots,\ba_n,\bb_1,\ldots,\bb_n\}$，
所以 $\Col(A + B) \subseteq\vspan\{\ba_1,\ldots,\ba_n,\bb_1,\ldots,\bb_n\}\subseteq\vspan(\beta_C(A)\cup\beta_C(B))$，
這表示 $\operatorname{rank}(A + B) \leq \operatorname{rank}(A) + \operatorname{rank}(B)$。。

<!--
因為子空間的維數等於基底向量的總數
所以 $\operatorname{rank}(A + B)$
= $\dim$(\( $C$ ($A$)) $+$ $C$ ($B$))
$\leq \dim$ $C$ ($A$) $+$ $\dim$ $C$($B$)
= $\rank$($A$) $+$ $\rank$($B$)
其中，以 $C$($A$) 表示矩陣 $A$ 的行空間。
-->

##### Exercise 5(b)

證明 $\operatorname{rank}(AB) \leq \min \{\operatorname{rank}(A), \operatorname{rank}(B)\}$。

:::warning

- [x] 矩陣不用粗體。
- [x] 行 --> 列
- [x] $r$ --> $\rank$
:::

$Ans:$

將 $A$ 設為一 $m$ x $n$ 的矩陣，
將 $B$ 設為一 $n$ x $s$ 的矩陣，
再將 $B$ , $AB$ 按列分為

$$B = \begin{bmatrix} \beta_1 \\ \vdots \\ \beta_n \end{bmatrix}
$$
$$AB=C = \begin{bmatrix} \gamma_1 \\ \vdots \\ \gamma_n \end{bmatrix}
$$
於是

$$AB= \begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & ~ & \vdots \\
a_{m1} & \cdots & a_{mn} \\
\end{bmatrix}\times
\begin{bmatrix} \beta_1 \\ \vdots \\ \beta_n \end{bmatrix} =
\begin{bmatrix}
a_{11}\beta_1 & + & \cdots & + & a_{1n}\beta_n \\
\vdots & ~ & ~ & ~ & \vdots & \\
a_{m1}\beta_1 & + & \cdots & + & a_{mn}\beta_n \\
\end{bmatrix} = \begin{bmatrix} \gamma_1 \\ \vdots \\ \gamma_n\end{bmatrix}.
$$

所以 $AB$ 的列向量 $\gamma_i$ ($i$ $=$ 1,2,3,....) 均可由 $B$ 的列向量線性表示出，故 $\rank$($AB$)$\leq$ $\rank$($B$)。
同理可證 $\rank$($AB$)$\leq$ $\rank$($A$)，故有 $\operatorname{rank}(AB) \leq \min \{\operatorname{rank}(A), \operatorname{rank}(B)\}$。

:::info
目前分數 4.5/5
:::