# 線性獨立觀察

回顧上次的[線性獨立觀察](https://hackmd.io/mdFxn5DWQImMX_0MvmIddA?view#%E7%B7%9A%E6%80%A7%E7%8D%A8%E7%AB%8B%E8%A7%80%E5%AF%9F)，在某個向量空間 $W$ 中，對於一個「有限/無限」的子集 $S$，我們可以透過「一個一個拔/選擇公理」分別證明一定存在一個子集 $R\subseteq S$，$span(R)=span(S)$ 且 $R$ 是線性獨立的。

但是我們也有提到，$R$ 並不唯一；因此我們想知道這些 $R$ 「大小」會不會一樣。

# 向量空間基本定理 / 取代定理 Replacement Theorem

$$
\displaylines{
\text{If }S\text{ is a subset of a vector space and }\\Q\text{ is a linearly independent subset of span(S) with}\ min(|Q|,|S|)<\infty
}
$$

$$
\begin{align}
\text{then there is an }R&\subseteq S \text{ with:}
\\
Q \cap R &= \varnothing
\\
|Q|+|R|&=|S|
\\
span(Q\cup R)&=span(S)
\end{align}
$$

上面的定理說明了，兩個任意的子集合，只要有一個叫做 $Q$，他只要滿足下面兩個條件

- 線性獨立
- $Q\subseteq span(S)$

就會滿足那三個神奇的性質；也因此可以知道 $|Q|\le|S|$

大多數的證法 $S$ 跟 $Q$ 都要是「有限的」，然後同樣是以歸納法推導出來。

但是CS大學長江宗儒推導出了一個更強的版本，只要 $S$ 跟 $Q$ **其中一個是**「有限的」就好，然後一樣以歸納法得證。

# 證明

在這裡都是在某個向量空間底下。為了方便討論：

- $Q$ 是任意的固定大小的子集，並且是線性獨立的。
- $S$ 是「所有的」 $S$，只要滿足 $Q\subseteq span(S)$ 和 $min(|S|,|Q|)<\infty$

這裡的歸納法有點特別，是以「交集的個數」作為歸納的骨牌。

# Base Case

歸納法的 Base Case 是：

$$
交集大小=|Q\cap S|=min(|S|,|Q|)
$$

也就是交集最大的可能數量是其中一個人的全部。因為我們不知道 $S$ 是不是「無限的」，所以有可能 $Q\subseteq S$ 或 $S\subseteq Q$。

- Case 1：如果 $Q\subseteq S$
- 那麼只要令 $R=S\ \setminus Q$，就可以輕易發現三個條件都滿足了
- 可以發現 $Q$ 是不是線性獨立**並不影響結果**
- Case 2：如果 $S\subseteq Q$
- 根據敘述可以知道 $S\subseteq Q \subseteq span(S)$
- 根據生成空間觀察可以知道：
- $Q \subseteq span(S)\Rightarrow span(Q)\subseteq span(S)$
- $S\subseteq Q \subseteq span(Q)\Rightarrow span(S) \subseteq span(Q)$
- $\Rightarrow span(S)=span(Q)$
- 這個放在下面討論

延續 Case 2，接著我們需要找到一個 $R \subseteq S$，並且：

- $Q \cap R = \varnothing$
- $|Q|+|R|=|S|$
- $span(Q\cup R)=span(S)$

雖然 $S$ 並沒有給任何條件，但是因為 $Q$ 是「線性獨立」的，並且 $S\subseteq Q$，所以可以知道如果 $S$ 是 $Q$ 的 proper set，那麼理論上：

$$
span(S)\subset span(Q)
$$

但是這會跟我們的結論 $span(S)=span(Q)$ 矛盾，因此可以知道 $S$ 不是 $Q$ 的 proper set，或者說 $S=Q$，然後就可以知道 $R=\varnothing$，也就發現那三個條件都滿足了。

:::info
上面兩種 Case 都可以寫成 $R=S\setminus Q$ 的形式。
:::

# 歸納步驟

:::warning
這裡的歸納方式是一種比較少見(?的歸納方式。

通常的歸納方式是假設 n=k 成立，則去嘗試推導出 n=k+1 的時候也成立。

但這裡所使用的歸納方式是「倒過來」的歸納方式，也就是說假設 n=k 成立，則可以推導出 n=k-1 成立。
:::

我們是以「交集的數量」作為歸納的 index，所以倒著來就是指，我們假設交集數量等於 n 的時候成立，則交集數量等於 n-1 的時候也會成立。

證明開始。

---

因為現在不是 Base Case 了，也就是說：

$$
|Q\cap S|<min(|S|,|Q|)
$$

並且有說 $Q$ 是固定大小的，所以可以知道：

$$
min(Q,S)\le |Q|\\
\Rightarrow |Q\cap S| < |Q|
$$

這個大小關係很重要，要先記住。

接著我們假設有一個成員 $q$：

$$
q\in Q\ \setminus S \subseteq span(S)
$$

從之前線性獨立的推導可以知道 $q$ 一定不是 $0$，因為任何包含 $0$ 的子集必定不是線性獨立的。

然後因為 $q$ 在 $span(S)$ 裡面，也就是說 $q$ 可以由 $S$ 的成員的線性組合所表示：

$$
q=a_{1}s_{1}+...+a_{n}s_{n}
$$

其中 $a_{1}...a_{n}$ 是非零的純量，$s_{1}...s_{n}$ 是非零且相異的向量，且 $n\ge1$：

- $s_{1}...s_{n}$ 是非零且相異的目的是為了避免 $a_{1}s_{1}+...+a_{n}s_{n}$ 加起來跑出 0
- $a_{1}...a_{n}$ 是非零的用意也一樣。

而眼尖的我們可以發現，$s_{1}...s_{n}$ 當中必定要有一個 $s_{i}$ 不在 $Q\cap S$ 裡面，不然如果全部的 $s_{i}$ 都在 $Q\cap S$ 裡面，也就代表他們都在 $Q$ 裡面，換個表示法就會變成：

$$
q=a_{1}q_{1}+...+a_{n}q_{n}
$$

這樣會讓 $Q$ 變成線性不獨立，跟前提造成矛盾。

所以為了方便討論(不失一般性)，我們將那個不在 $Q\cap S$ 裡面的令為 $s_{1}$。

$$
s_{1}\in S\ \setminus Q
$$

---

接著就是**通靈時刻**，我們構造出一個神奇的 $S'$：

$$
S'=(S\ \setminus \{s_{1}\}) \cup \{q\}
$$

這個神奇的 $S'$ 具有很多神奇的特質：

- 因為 $s_{1}$ 原本只在 $S$ 裡面，$q$ 原本只在 $Q$ 裡面，所以可以知道：
- $|S'|=|S|$
- 也就是從 $S$ 中拔一個出來，再塞一個進去
- 並且因為 $s_{1}$ 原本就不在 $Q$ 裡面，然後我們又塞了 $q$ 到 $S'$ 裡面去：
- $|Q\cap S'|>|Q\cap S|$
- 或者說 $|Q\cap S'|=|Q\cap S|+1$，因為 $|Q\cap S| = |Q\cap (S\ \setminus \{s_{1}\})|$

>有沒有逐漸看出我們的 n+1 跟 n 了呢

首先，從上面的等式我們可以知道：

$$
\displaylines{
q=a_{1}s_{1}+...+a_{n}s_{n}\\
\Rightarrow s_{1}=a_{1}^{-1}(q+(-a_{2})s_{2}+...+(-a_{n})s_{n})\in span(S')\\
\Rightarrow \{s_{1}\}\subseteq span(S')
}
$$

然後根據基本的集合推論：

$$
S\ \setminus \{s_{1}\}=S'\ \setminus \{q\}\subseteq S' \subseteq span(S')
$$

所以把兩者結合起來可以得到：

$$
S\ \setminus \{s_{1}\}\cup\{s_{1}\}\subseteq span(S')\\
\Rightarrow S \subseteq span(S')
$$

並且我們知道 $S'=(S\ \setminus \{s_{1}\}) \cup \{q\}$，這兩個人又在 $span(S)$ 裡面，所以又可以根據生成空間觀察：

$$
S'\subseteq span(S)\\
\Rightarrow span(S')\subseteq span(S)
$$

結合下來就變成：

$$
S \subseteq span(S') \subseteq span(S)
$$

這個東西在上面看過類似的結構，也就是兩次生成空間觀察弄下去，就會發現：

$$
span(S)=span(S')
$$

# 收尾

接著就是精彩的收尾時刻了。

假設 $S'$ 當中，存在 $R\subseteq S'$：

- $Q \cap R = \varnothing$
- $|Q|+|R|=|S'|$
- $span(Q\cup R)=span(S')$

這個假設就是我們的「令 n=k+1 時成立」的「假設部分」，只不過這裡是令「交集大小等於$|Q\cap S'|=|Q\cap S|+1$」成立。

接著是推論出「交集大小等於 $|Q\cap S|$」成立：

- 因為 $Q \cap R = \varnothing$，所以可以知道 $R\subseteq S'\ \setminus Q$
- 而 $S'\ \setminus Q \subseteq S$，所以可以知道 $R\subseteq S$

所以我們的 $R$ 有了，那麼接著一樣是看有沒有滿足三個性質：

- $Q \cap R = \varnothing$
- 有，畢竟就是同一個 $R$，他剛好同時在 $S'$ 跟 $S$ 裡面
- $|Q|+|R|=|S|$
- 有，因為上面我們有證明 $|S'|=|S|$
- 所以可知 $|Q|+|R|=|S'|=|S|$
- $span(Q\cup R)=span(S)$
- 有，因為上面我們有證明 $span(S)=span(S')$
- 所以可知 $span(Q\cup R)=span(S')=span(S)$

所以可以發現，當我假設「交集大小等於$|Q\cap S'|$」的時候成立，則「交集大小等於$|Q\cap S|=|Q\cap S'|-1$」的時候也成立。

因此根據數學歸納法，當交集大小等於 $|Q\cap S|$ 的時候，對於一個固定大小的 $Q$，以及任意大小的 $S$，只要 $Q$ 是線性獨立，並且 $Q\subseteq span(S)$，則存在 $R\subseteq S$ 滿足：

- $Q \cap R = \varnothing$
- $|Q|+|R|=|S|$
- $span(Q\cup R)=span(S)$

:::success
因為我們是假設 n=k+1 的時候成立，然後推導出 n=k 的時候成立，所以這時候骨牌不可以再從 n=1 開始推，而是要從 n=max 開始反向推。

這也是為甚麼一開始的 Base Case 是 $|Q\cap S|=min(|Q|,|S|)$ 的緣故，因為要從最大值推回來。
:::

# Comment

再看一次取代定理：

$$
\displaylines{
\text{If }S\text{ is a subset of a vector space and }Q\\\text{ is a linearly independent subset of span(S) with}
min(|Q|,|S|)<\infty
}
$$

$$
\begin{align}
\text{then there is an }R&\subseteq S \text{ with:}
\\
Q \cap R &= \varnothing
\\
|Q|+|R|&=|S|
\\
span(Q\cup R)&=span(S)
\end{align}
$$

:::warning
「取代定理」是說可以從 $S\ \setminus Q$ 找出個子集 $R$ 使得 $Q\cup R$「取代」$S$：大小與地盤都相同。
或者說把原本 $S$ 的其中一部份替換成 $Q$。

這個「替換」的性質在之後會很常用到，因為常常會令 $S$ 是某個子空間的 $basis$。
:::

---

# 定理證明

上面推導的版本中，條件是 $min(|Q|,|S|)<\infty$，我們以這個版本推導出 $max(|Q|,|S|)\le |\mathbb{N}|$

也就是說對於兩個無線可數的子集 $Q$ 跟 $S$，其中 $Q$ 是線性獨立的，並且 $Q \subseteq span(S)$，這裡令 $R = S\ \setminus Q$，可知 $R \subseteq S$：

- $Q \cap R = \varnothing$
- 滿足，因為 $R = S\ \setminus Q$
- $|Q|+|R|=|S|$
- 滿足，還是因為 $R = S\ \setminus Q$
- 並且因為左右邊都是「無限可數個」，大小都是 $|\mathbb{N}|$
- $span(Q\cup R)=span(S)$
- 因為 $S\subseteq Q\cup R \subseteq span(S)$，所以套用兩次生成空間觀察即可得到
- $S\subseteq Q\cup R$ 就是集合的性質
- $Q\cup R \subseteq span(S)$ 是原本的條件 + 集合的性質

總之我們證明了無限可數的版本。

---

# 推論 Corollary

從基本定理的第二條可以知道：

$$
\displaylines{
|Q|+|R|=|S|\\
|Q|\le |S|
}
$$

有了這個推論後

- 讓我們令 $S=R_{1}$，$R_{1}$ 是一個可以張出子空間 $V$ 的線性獨立集
- 讓我們令 $S=R_{2}$，$R_{2}$ 是另一個可以張出子空間 $V$ 的線性獨立集

此時有趣的事情發生了，因為兩者都是線性獨立，並且又包含於對方的伸張集，也就是 $V$ 裡面。

所以使用基本定理的推論可以知道：

$$
\displaylines{
|R_{1}|\le R_{2}\\
|R_{2}|\le R_{1}\\
\Rightarrow |R_{1}| = |R_{2}|
}
$$

---

# 基底與維度 / Basis & Dimension

既然每個可以張出相同向量空間的線性獨立集合有相同的大小，那麼我們就把這些線性獨立集合叫做「基底 Basis」，並且把該大小叫做「維度」

$$
\text{Let V be a subspace of vectors space W. A subset S of V is a basis of V if}
$$

- $span(S) = V$
- $\text{S is linearly independent}$

:::warning
$\{0_{W}\}$ 不會是 ($\{0_{W}\}$,$F$,$\cdot$ ) 的基底，因為 $\{0_{W}\}$ 線性不獨立；$\varnothing$ 才是基底。
:::

# 標準基底

之前就有推導過，不論是有限或無限的子集 $S$，一定存在一個 $R\subseteq S$ 是線性獨立的，但是 $R$ 不一定唯一；換句話說就是基底可能有很多種人選。

下面介紹的是所謂的「標準基底」，就是...長得比較標準的基底。

## 多元組空間

$$
\displaylines{
\text{The standard basis of }F_{n}\text{ for any field F is}\\
S=\{e_{1},e_{2},...,e_{n}\}\\
\text{where each }e_{i}\text{ with }i\in\{1,2,...,n\}\text{ is the n-tuple}：\\
(0_{F},0_{F},...,0_{F},1_{F},0_{F},0_{F},...,0_{F})\\
\text{such that i-th component of }e_{i}\text{ is }1_{F}\text{ and the other n − 1 components of }e_{i}\text{ are all }0_{F}
}
$$

講白話一點就是第 i 個位子是 1 其他是 0 所組成的向量集合。

## 多項式空間

字太多，所以省略如下：

$\mathbb{P}_{n}(F)$ 的基底是：

$$
S=\{1_{F},x^{1},x^{2},...,,x^{n}\}
$$

$\mathbb{P}(F)$ 的基底是：

$$
S=\{1_{F},x^{1},x^{2},...,,x^{n},...\}
$$

別忘記，多項式有定義不可以是無限多項，除非當中只有有限項是非零。

:::info
可以發現對 $\mathbb{P}(F)$ 來說，雖然 $|S|=\infty$，但是仍舊沒有冗員。

當初定義線性組合的時候有說 $n\ne \infty$，除非有限項為非零，剛好這裡就是一個例子；也就是說我們只能從 $S$ 中挑有限個出來做線性組合。
而這也跟多項式所需要的定義相符合。
:::

---

# 維度觀察

接下來是各種和維度有關的性質，或者說觀察 Obversation。

## 維度觀察一

$$
\displaylines{
\text{For any finite subset S of a vector space}\\
dim(span(S))\le |S|
}
$$

讓 $Q$ 代 $span(S)$ 的基底，根據基本定理第二點就可以證明了。

:::warning
上面的觀察告訴我們，$k$ 個向量最多只能生成 $k$ 維空間。
:::
:::info
因為「$Q$ 代 $span(S)$ 的基底」，而當初 $Q$ 是有限的，因此這裡才要求 $S$ 是有限的。
:::

## 維度觀察二

$$
\displaylines{
\text{If S is a finite subset of vector space V with}\\
|S|=dim(V)\\
\text{then S is }\color{yellow}{\text{linearly independent}}\text{ if and only if }\color{red}{\text{S spans V}}
}
$$

這句話翻成中文是：「如果一個子空間 $V$ 的有限子集 $S$ 的大小跟維度一樣，則 $S$ 是線性獨立跟 $S$ 張出 $V$ 是等價的」

而我們可以回想當初定義基底的時候，我們是說：

- $span(S) = V$
- $\text{S is linearly independent}$

則 $S$ 是基底，並且他的大小就是維度 $|S|=dim(V)$

### 證明 -- 左到右

「如果 $S$ 大小跟維度一樣，則如果 $S$ 線性獨立，則 $S$ 張出 $V$。」

這個跟觀察一一樣用基本定理，並且也一樣：

- $S$ 代 $V$ 的基底，這裡叫他做 $B$
- $Q$ 代 $S$

然後最終得到的三個性質中，$|S| + |R|=|B|$ 但是 $S$ 跟 $B$ 兩個人大小一樣，所以可以知道 $R$ 是空集合，因此就可以知道：

$$
span(S\cup R)=span(S)=span(B)=V
$$

:::info
可以再次注意到，因為 $S$ 是基本定理中的 $Q$，所以條件中需要是「有限的」，有限才能說明 $|S|=|B|$
:::

### 證明 -- 右到左

「如果 $S$ 大小跟維度一樣，則如果 $S$ 張出 $V$，則 $S$ 線性獨立。」

由於這裡已知 $S$ 張出 $V$，所以就將 $V$ 替換成 $span(S)$。

$$
|S|=dim(span(S))
$$

由於 $S$ 大小是有限的，所以可以根據線性獨立觀察，得知存在一個子集 $R\subseteq S$，$R$ 是線性獨立的，並且 $span(R)=span(S)$。

但是因為 $span(R)=span(S)$，且 $R$ 又是線性獨立，代表 $R$ 是 $span(S)$ 的一個基底，也就代表他的大小要是 $dim(span(S))$，因此就會發現：

$$
\displaylines{
|R|=dim(span(S))=|S|\\
|R|=|S|\wedge R\subseteq S\\
\Rightarrow R = S
}
$$

最後一個等於可以成立，還有一個要素是 $S$ 是「有限的」。

:::info
可以再次發現「$S$ 是有限的」這個前提很重要，如果沒有這個前提，雖然線性獨立觀察依舊可用，但我們就不能說明 $R=S$。
:::

## 維度觀察三

$$
\displaylines{
\text{If V is a subspace of a finite-dimensional vector space W, then the following statements hold}\\
dim(V)\le dim(W)\\
if\ dim(V) = dim(W),then\ V=W
}
$$

首先 $dim(V)\le dim(W)$ 就是基本定理告訴我們的事情，除了可以以「代入的角度」去思考：

- 讓 $S$ 是 $W$ 的基底
- 讓 $Q$ 是 $V$ 的基底
- 根據基本定理可以知道存在一個 $R\subseteq S\ \setminus Q,|Q|+|R|=|S|$
- 也就是說我們可以從 $S$ 這個基底中，把一部分替換成 $Q$
- 因此可知 $dim(V)\le dim(W)$

也可以說「我們可以把子空間的基底，擴充成母空間的基底」。

:::warning
但是要注意，這些擴充阿甚麼的前提是「**維度是有限的**」。
:::

:::info
如果維度是無限的，那麼第一個雖然會成立，但是第二點不一定成立。
舉例來說，$\mathbb{P}(F)$ 是原本那個有無限多維度的多項式空間。
如果我們只挑 2 的次方項出來，叫做 $\mathbb{P}_{2^{n}}(F)$：

$$
S=\{x^{2},x^{4},...,x^{2^{n}}\}
$$

那麼 $\mathbb{P}_{2^{n}}(F) \subseteq \mathbb{P}(F)$，並且 $dim(\mathbb{P}_{2^{n}}(F))=dim(\mathbb{P}(F))$，但是 $\mathbb{P}_{2^{n}}(F) \ne \mathbb{P}(F)$
:::

---

# 座標定理

在這之前，我們引入有序集合，並且用角括弧作區別：

$$
\displaylines{
\{1,2\}=\{2,1\}\\
\langle 1,2 \rangle \ne \langle 2,1 \rangle
}
$$

下面會用小寫希臘字母代表有序基底。

$$
\displaylines{
\text{Let V be a vector space over F with}\\
1\le dim(V) = n \color{red}{< \infty}\\
\text{If }\beta = \langle β_{1},...,β_{n} \rangle \text{ is an ordered subset of V, then $\beta$ is an ordered basis of V}\\
\text{if and
only if for each vector x ∈ V, there is a unique n-tuple }(a_{1},..., a_{n}) ∈ F^{n}\text{ with}\\
x=a_{1}\beta_{1}+...+a_{n}\beta_{n}
}
$$

這裡可以注意到，$V$ 的維度是「**有限的**」

白話來說，$\beta$ 是一組有序基底，跟 $V$ 的成員可以被 $\beta$ 唯一的表示是等價的。

## 座標

從座標定理可以知道表示法是唯一的，所以對每個 $V$ 中的向量 $x$，那組唯一的係數 $(a_{1},..., a_{n})$ 就是「**座標**」，數學上記為：

$$
[x]_{\beta}=(a_{1},..., a_{n})
$$

# 證明

## 左到右

如果 $\beta$ 是一組有序基底，則 $V$ 的成員可以被 $\beta$ 唯一的表示。

因為 $\beta$ 是一組基底，代表他可以張出 $V$。假設對於 $x\in V$，有兩組座標可以描述 $x$：

$$
\displaylines{
x = a_{1}\beta_{1}+...+a_{n}\beta_{n} = b_{1}\beta_{1}+...+b_{n}\beta_{n}\\
\Rightarrow 0 = (-a_{1}+b_{1})\beta_{1}+...+(-a_{n}+b_{n})\beta_{n}
}
$$

因為 $\beta$ 是一組基底，根據零線組觀察，$(-a_{i}+b_{i}),\forall i$ 必須要是 0：

$$
(-a_{i}+b_{i})=0 \Rightarrow a_{i}=b_{i}
$$

## 右到左

如果 $V$ 的成員可以被 $\beta$ 唯一的表示，則 $\beta$ 是一組有序基底。

我們嘗試找出 $0_{V}$ 的唯一表示：

$$
a_{1}\beta_{1}+...+a_{n}\beta_{n}=0
$$

因為只有唯一的一組 $(a_{1},..., a_{n})$ 可以表示出 $0_{V}$，而這一組必須是全部的 $a_{i}$ 都是 $0_{F}$，所以可以根據零線組觀察，$\beta$ 是線性獨立的。

所以 $\beta$ 可以表示出 $V$，並且又是線性獨立的，因此 $\beta$ 是一組基底。