# 李宏毅_Linear Algebra Lecture 19: Basis
###### tags: `Hung-yi Lee` `NTU` `Linear Algebra Lecture`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW)
## Linear Algebra Lecture 19: Basis
[課程連結](https://www.youtube.com/watch?v=GB48DyvC14o&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=19)

### Outline

課程主要說明：
1. 什麼是subspace的basis
2. 如何檢查是否為subspace的basis

### Basis

假設有一個vector set-V，是一個nonezero subspace。另外有一個vector set-B 是V的basis，那這個vector set會滿足下面兩個條件：
* linear independent
* 是V的generation set，比方說V = Span B，Span之後可以產生subspace

舉例：
* $R^n$：所有n維向量所組成，是一個subspace，它有一個basis，由n個standard vector所組成，即$\left\{e_1, e_2, \cdots, e_n \right\}$，這可以利用上面兩個定義來檢查
* 首先，$\left\{e_1, e_2, \cdots, e_n \right\}$是independent
* 其次，$\left\{e_1, e_2, \cdots, e_n \right\}$是可以generate出$R^n$，因為你可以將這n個的stardard vector做各種不同的linear combination來產生所有的$R^n$內的所有的vectors

對$R^2$而言，只要有兩個independent vectors，那它們都是$R^2$的basis
### Basis

舉例來說，假設有一個Matrix-A，其column space為Col A，而Col A有一個basis，也就是其pivot columns：
* 首先，做為basis的條件之一就是其vector set為linear independent，而pivot columns是linear independent，之前課程提過，做完RREF之後，其column之間的關係是不變的，而那些pivot columns都是linear independent
* pivot columns做span之後，是可以成為column space的(我們知道，非pivot column的那些column都是pivot column的linear combination)
* 此例來說，第2個column是第1個column的linear combination，第5、6個column是第1、3、4個column的linear combination
### Property

繼續說明basis之前先說幾個直觀的觀念：
* vector set S一定包含在Span S裡面
* basis做span之後會等於其subspace，因此subspace的basis一定落在subspace裡面
* 如果有一個vector set S'包含在Span S裡面，那將S'做Span也必定包含在Span S裡面
* 如果有一個vector z，其包含於Span S裡面，把z加到S再做Span，所以大小與Span S一樣，也就是加上z之後並沒有什麼影響
* 反過來說，如果有一個vector z加入S之後做Span並沒有影響S單獨做Span，這意味著z原本就包含在Span S裡面
* 再換句話說，如果vector z並不包含在Span S裡面，那把z加到S再做Span所得的結果就會不一樣
### Theorem

basis幾個重要定理：
* basis是**最小**的generatorion set，一個subspace可以有很多不同的generation set，但裡面最小的那個，就是basis
* basis是**最大**的independent vector set，一個subspace可以用不同的vector組成不同的independent set，但裡面最大的那個，就是basis
* 一個subspace可以擁有無窮多個basis，但這些basis裡面的vector數量是一樣多的，而這個vector的數量就稱之為dimension
* 如果有一個subspace的dimension為3，這就代表這個subspace的basis都有3個vector
### Theorem 3

首先說明第三個定理，也就是同一個subspace內的所有basis的vector的數量都是一樣的。

假設有一個subspace-$V$的兩個basis，$\left\{u_1, u_2, \cdots , u_k \right\}$與$\left\{w_1, w_2, \cdots, w_p \right\}$，目前我們並不知道$k$是否等於$p$，但它們符合兩個條件，都是independent的vector set，而且將兩個vector做span都可以得到$V$。

現在開始證明$k=p$，將兩個vector set組成兩個matrix，即$A=\left[u_1 \space u_2 \space \cdots \space u_k \right]$、$B=\left[w_1 \space w_2 \space \cdots \space w_p \right]$。

這兩個matrix的column之間是有某種關係的，(1)$\left\{u_1, u_2, \cdots , u_k \right\}$做span會得到$V$，因為它是$V$的basis，(2)而$B$也是$V$的basis，因此$w_i$一定是屬於$V$，即$w_i \in V$，因為一個basis裡面的成員一定是落在它所generator出來的subspace裡面。

根據這兩項我們可以知道，$u_1, u_2, \cdots , u_k$做linear combination一定可以產生$w_i$，即$Ac_i = w_i$，對所有的$w_i$而言，$u_1, u_2, \cdots , u_k$乘上某一個vector-$c_i$會等於$w_i$，而$i$可以是$1, 2, ... , p$，因此得到$A\left[c_1 \space c_2 \space \cdots \space c_p \right] = \left[w_1 \space w_2 \space \cdots \space w_p \right]$，也就是$AC=B$.

假設，有某些$x$與$C$相乘為0，即$Cx=0$，而這個假設永遠成立，最糟的情況就是$x$是zero vector就可以，因此$ACx=Bx=0$。這說明了，如果某一個$x$是位於$C$的null space內，那它一定也位於$B$的null space內，而$B$是basis所構成的matrix，因此它的column都是independent，這意味著它的null space只有一個成員，就是zero vector。因此可以看到，右上圖的藍色區域Null B是一個zero vector，而$C$的null space包含在zero vector所構成的集合裡面，因此它也是zero vector。

現在我們知道，$C$的null space也是一個只有zero vector的集合，這也代表$C$的column也是independent。$C$是一個kxp的matrix，如果要它是independent，那它的維度就必需是$p \leq k$，接下來只要把剛才的推論反過來推，將角色對換，就可以得到$k \leq p$，就可以證明$k=p$。因此，一個vector space裡面如果有兩個basis，其成員一定是一樣多的。而成員的數目就可以描述subspace的特性，有幾個成員，其subspace的dimension就是多少。

### Theorem 3

講basis的時候並不會討論zero subspace，因為它的dimension會強制定義為0，而$n$維空間的dimension就會是$n$，其basis都會包含n個vector。
### Example

假設有一個subspace-$V$在一個四維空間中，其式為$x_1 - 3x_2 + 5x_3 - 6x_4 = 0$，計算其dimension為何：
* 如果這個subspace是由system of linear equation所組成，那只要求出它的解就可以得到它的basis
* 調整數學式$x_1 = 3x_2 - 5x_3 + 6x_4$，只有$x_1$是basis的variable，其餘皆為free variable
* 寫下該system of linear equation的parameter representation
* 得到的三個vector拿去做span會得到$V$
* 檢查所得的三個vector是否為independent，很明顯的確實為independent，因為你沒有辦法用任意兩個vector做linear combination得到另一個vector
* 經過上面計算得到$V$的其中一個basis，因此$V$的dimension為3
### Theorem 1

Basis是最小的generation set。假設在某一個subspace V中找出一個generation set S，其subspace V的basis一定會小於或等於這個S。這意味著，如果S有三個元素，那這個V的basis一定會小於或等於三個元素。

根據Reduction Theorem，所有的generation set裡面都會包含一個basis，又或者可以說，如果你有一個generation set，你可以將這個generation set去掉幾個元素之後變成一個basis。
### Theorem 1 - Reduction Theorem

這邊要說明如何證明『所有的generation set裡面都會包含一個basis』。

假設有一個generation set $S={u_1, u_2, \cdots, u_k}$，做span之後得到subspace V：
* Subspace V = Span S
* 假設Matrix $A = [u_1 \space u_2 \space \cdots \space u_k]$，就是將S的每一個元素做為A的column
* Subspace V = Col A
* 先前提過Matrix A的column space的basis就是A的pivot column，而pivot column就是column的subset
* 你找到一組basis，也就證明『所有的generation set裡面都會包含一個basis』

### Theorem 1 - Reduction Theorem

上面是一個範例說明。
### Theorem 2

這邊說明的是『basis是subspace裡面最大的independent set』。假設我們知道basis的大小為k~(成員數)~，在這個subspace裡面你絕對找不出多於k個independent vectors出來組成independent set，因為basis是最大的independent set。

Extension Theorem：
* 假設給定一個independent vector set S，它落在某一個subspace裡面，那你一定可以把這個S加上額外的vector將之變成basis
### Theorem 2 - Extension Theorem

也就是說，每一個independent set它不是basis就是正在成為一個basis。也就是說每一個independent set要嘛它是basis，不要嘛就是加入新的vectors之後它會成為basis。也就是independent set的大小是小於等於basis。

假設一個subspace V，在V裡面我們找到independent set S~(三個黑色點)~，把這個S做Span~(深藍色圈圈)~：
* 如果做完Span之後與V一樣大，那S就是basis
* 如果S做完Span之後不等於V，那我們一定可以在這個Span之外的空間中找到一個vector $v_1$，然後把這個$v_1$加到S，這時候它們依然會是independent
* 因為$v_1$不會是其它三個vector的linear combination，如果它是，那應該會落在Span之後的範圍內
* 以這四個vector再做一次Span，如果做完Span之後，其範圍與V一樣，那它就是一個basis，如果依然小於V，那就一定可以再找出一個vector，再做一次Span
* 反覆這個步驟，直到整個Span等於V
### More from Theorems

現在我們知道，basis是最小的generation set。假設，有一個subspace，m維的空間，$R^m$。這個m維空間的generation set至少需要m個vector。因為m維空間有無窮多個basis，但其中一個basis，就是所有m個standard vector所成的集合，它是m維空間中的一個basis，其dimension為m。而generation set一定是大於等於basis，因此所有可以generator m維空間的vector set，其成員數目至少一定要m個。

另一方面，subspace裡面，最大的independent set就是basis。而m維空間的basis是m個elements，dimension為m，因此在m維空間中找不出超過m個independent vector，只要你拿出超過m個vector出來，那就一定是dependent。因此三維空間中找出四個東西，其中一個一定是冗員。
### Summary

結論，如果將basis想成一個雕塑，那你要嘛用刪去的，要嘛疊加，也就是，雕像是大衛，那generation set就是一個大理石，將generation set進行雕塑就可以得到basis，或者independent vector set是一堆石頭，將它們堆疊起來就會變成basis。
### Intuitive Way

如果問你某一個vector set-$C$是否某一個subspace的basis，該如何用定義來確定?對於確認vector set-$C$是否為independent並不難，難的是不確定它是否能夠generator出$V$。

### Another way

有一種方法，可以快速瞭解。

假設有一個subspace-$V$，其dimention=$k$，怎麼知道這個$k$，只要找出它的basis就可以。

如果有一個vector set-$S$，它有$k$個vector，與subspace的dim是一樣的，那它只要滿足下面其中一個條件，那它就會是basis：
* S為independent
* S為subspace的generation set

再回頭剛才的問題，給定一個subspace-$V$，那$C$是否為$V$的basis?
* 首先，以parameteric representation可以確定，V的dim=2
* dim=2，而$C$的vector也是2，再加上$C$也是independent，因此$C$為$V$的basis
### Another way

現在要證明，假設有一個subspace-V，其dim=k，另外有一個vector sets-S，其成員數也是k，那滿足下面兩個條件下，S為basis：
* S為independent
* 根據extension theorem，我們知道，每一個independent的vector set，要嘛是basis，要嘛增加額外的vector之後變成basis。我們現在知道dim V=k，且S也有k個成員(k個vector)，而在一個dim=k的subspace中，是找不出超過k個independent vector，最多最多，就是k，而S已經有k個element，那已經是最大，既然已經無法再擴大，那就直接證明它就是basis
* S為subspace的generation set
* 根據reduction theorem，如果S是一個generation set，那S一定是basis。我們現在知道，basis是最小的generation set，如果我們要generate的是dim=k的subspace，那最少需要k個element，而S正好是k個element，沒有辦法再少了，因此直接證明它就是basis

### Example

這邊以範例說明，給定一個subspace-V，再給一個vector set-B，確認B是否為V的basis：
* 首先確定B是否為independent
* 接著找出V的dim，這可以看V有多少free variable
* 確定B的element
* 得證

### Example

這邊的範例，有一個vector set V，為S的Span，確認B是否為V的basis：
* 將Span S的vector做為Matrix A的column
* 找出Matrix A的pivot column數量，這可以利用RREF找出
* pivot column Span之後就是A的column space，也就是S的Span，也就是V
* 得到dimension
* 確定B的element
* 得證