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

稍早課程提到，可以透過linear combination或是span來確認system of linear equation是否有解，現在要談的是，有解的前提之前應該會有多少解的存在。
### Today

本次課程討論的是，下面幾種假設，其中一個成立，為唯一解：
* 假設$A$是independent
* Rank A = n
* Nullity A = 0

下面幾種假設下，其中一個成立，為無窮多解：
* 假設$A$是dependent
* Rank A < n
* Nullity A > 0

一個system of linear equation所存在的解不是唯一解就是無窮多解，只要找的出第二組解，就一定找的出第三組解，也就找的出無窮多解。
### Definition

* Dependent
* 不獨立，依賴
* 假設有$n$個vector，$\left\{a_1, a_2,..., a_n \right\}$，並且存在一組scalars，$\left\{ x_1, x_2, ..., x_n \right\}$，不全為0的情況下其linear combination為0，則為dependent
* $x_1a_1 + x_2a_2 + ... + x_na_n = 0$
* 找到一組解的情況下，將coefficient皆除2，那就得到另一組解，皆除3，就可以再得到另一組解，因此只要找到一組就可以找到無窮多組解
* Independent
* 獨立，自主
* 假設有$n$個vector，$\left\{a_1, a_2,..., a_n \right\}$，並且僅於$\left\{ x_1, x_2, ..., x_n \right\}$皆為0情況才其linear combination為0，則為independent

### Dependent and Independent

Linear Dependent:
* 給定一個vector set，$\left\{a_1, a_2,..., a_n \right\}$，假如存某一個vector-$a_i$，為其它vector的linear combination，那這個vector set是dependent
* 範例(上)直觀來看，左邊向量是右邊向量乘上五分之二所得，因此左邊向量為右邊向量的linear combination(反之亦然)，為dependent
* 範例(下)，最右邊的向量為左邊兩個向量相加而得，因此為dependent

### Dependent and Independent

* 範例來看，雖然無法直觀的觀察是否互為linear combination的關係，但左右任一向量乘上零都可以是中間向量，因此依然為dependent
* 這並不違反先前所提的Independent，因為就算兩邊的coefficient皆為零，中間給定一個$\pi$，其所得結果依然為0，並不滿足coefficient皆為0其linear combination為0的狀況
* 這個案例所說明的是，如果vector set內有一個zero vector，那它就是dependent，但這並不包含只有一個vector的vector set

### Dependent and Independent

在vector set有一組以上的vector的時候，這兩件事所說明的就是同一件事。

舉例來說，$2a_i + a_j + 3a_k = 0$，假設有一個vector set為dependent，依定義它存在一組非全為0的系數做linear combination之後為0。

$2a_i + a_j + 3a_k = 0$，將$3a_k$移至等號右方，再除3，換句話說，$a_k$為$a_i, a_j$的linear combination，這意味著$a_k$是一個冗員。
### Intuition

假設一個system of linear equation的matrix-$A$為dependent，那一但有一組解就擁有無窮多組解。要注意到條件是，一但有一組解，因為並不保證dependent一定有解。

上面範例直觀說明：
左邊的matrix先確認是否為dependent，可以明顯的看的出來，其中一個vector為其它兩個vector相加所得，因此為linear dependent。

接下來，因為第三個vector為第一、二個vector相加而得，因此可以將第三個vector以第一、二個vector的linear combination來表示，就可以找到另一組解。

只要$A$是dependent並且找的到一組解，那就找的出無窮多組解。
### Proof

上面用比較直觀的方法來說明，這邊用正式的證明來證明，當Column of $A$為dependent，只要有一組解就擁有無窮多組解，以及相反的，只要有無窮多解，其Column of $A$即為dependent，這兩件事情是等價的。

### Proof

Homogeneous：如果有一個system of linear equation，其constant項為0，則為homogeneous，即$Ax=0$(原本為$Ax=b$，當$b=0$則為homogeneous)

Homogeneous linear equations一定有一組$x$皆為0的解，即便你根本不知道$A$的內容。

依據Dependent、Independent定義，我們在Homogeneous linear equations上可以先得到兩個結論：
* dependent：$Ax=0$存在一組非0解，$x \neq 0$，擁有無窮多解
* independent：$Ax=0$僅存在一組全0解
### Proof

上面是針對Homogeneous的狀況，這邊是針對一般的狀況說明。

* 由dependent證明無窮多解：
在$A$為dependent的情況下，我們已經知道Homogeneous情況下，$Au=0$，其中$u$可以找的出一組non-zero vector的解，而$Ax=b$是有解的，因此我們存在一組解，$v$，即$Av=b$，這種情況下就可以存在無限多組解，只要將兩個式子的左右半部互加，得到$A(u+v)=b+0$，$(u+v)$就是另一組解。
* 由無窮多解證明dependent：
在擁有無窮多解的情況下，隨便都能找出兩組解，$Au=b$、$Av=b$，其中$u \neq v$，將兩邊相減，即$A( u - v) = b - b = 0$，因為$u \neq v$，即可得到dependent的定義，不全為0的情況下其linear combination為0。

### Rank and Nullity

* Rank：指在矩陣的Column內，可以找到最多indpendent的column的數目
* Nullity：依據rank定義而來，即所有的column數量減去rank的數量即可

左邊範例：
因為沒有任一column可以被其餘column組成，因此皆為independent，其rank=3，nullity=0

老師說，如果範例的答案你回答4就太智障了，因為rank的定義來自column有的數量，只會小於等於column的數量

中間範例：
以三個vector來看，右邊的vector是左邊的vector\*10所得，因此rank不會等於3。以兩個vector來看，左邊\*3就會等於中間，中間$*\dfrac{10}{3}$為右邊，左邊\*10為右邊，因此ran也不為2。只看一個vector的話，按定義，它就是independent。因此rank=1，而nullity=2。

右邊範例：
如果是zero vector sets，那它就是dependent，因為任意值都可以滿足$Ax=b$，因此這個vector sets找不出滿足independent的column，rank=0，nullity=3。

### Rank and Nullity

一樣的範例，直接秒看即可。

### Rank and Nullity

假設matrix-$A$維度為mxn，如果rank=n，那意味著所有的column皆為independent，一但有解，那就只會有一組解。

### Conclusion

因此，當有解的時候可以根據是否為independent、rank是否為n，nullity是否為0來判斷是否只有唯一解。

### Conclusion

但反過來說，並不能因為它是independent、dependent是說它是不是有解，這並沒有直接相關，因為independent也存在沒有解的情況，但只要有解就是唯一解。而dependent則只要有解就是擁有無窮多解。