# 李宏毅_Linear Algebra Lecture 8: Solving System of Linear Equations (part 1)
###### tags: `Hung-yi Lee` `NTU` `Linear Algebra Lecture`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW)
## Linear Algebra Lecture 8: Solving System of Linear Equations (part 1)
[課程連結](https://www.youtube.com/watch?v=zuTH1WdREkY&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=8)
### 九章算術

九章算術是漢朝的書，這邊實際操作的是高斯消去法。
### 算法統宗

明代以歌來解，二元一次方程式就以二色方程歌來解!
### Equivalent

先前的課程談的是定義、專有名詞的說明，本課程談的是如何解。

如果兩個systems of linear equations有相同解，那就可以稱為equivalent。
### Equivalent

可以透過三種方法來操作system of linear equations讓它們變換之後依然是equivalent(等價)的system of linear equations：
1. Interchange：交換，什麼事都沒有發生，依然等價
2. Scaling：縮放，可能乘上某一個數值，依然等價，要注意的是，乘上的應該是一個non-zero的值
3. Row Addition：將某一個equation乘上n倍之後加給另一個equation，依然等價

### Solving system of linear equation

求解的方式就是用上面三種方式來讓複雜的equation變為簡單的equation，以此快速求解。

### Augmented Matrix

剛才的範例是二元聯立，如果是多元的話通常會有很多未知數，coefficient的部份以matrix-$A$來表示，維度為mxn，未知數則以向量$x$來表示，最終的常數項也是以向量$b$來表示，即$Ax=b$

### Augmented Matrix

你也可以用一種稱為Augmented Matrix的方式來表示，很單純的將$A$與$b$放在一起，即$[A | b]$，其維度為mx(n+1)

### Solving system of linear equation

實際求解過程中，我們並不會將一堆的符號寫出來，而是單純的在Augmented Matrix內操作。
### Solving system of linear equation

對於複雜的方程式我們一樣採相同的方式做計算，而對於先前所提的三種變換方式，其名稱為elementary row operations。而對我們簡化到最後讓我們可以一眼看出答案的那個Matrix，其名稱為reduced row echelon form(RREF)。

### Reduced Row Echelon Form

Echelon：階級

談Reduced Row Echelon Form之前先談Row Echelon Form：
1. 所有的non-zero的row都在zero row的上方
2. 所有row的leading entries拿出來(即由左至右第一個不為零的元素)排成echelon form
* 換句話說，下一個row的leading entry應該是在上一個row的右下方

### Reduced Row Echelon Form

像上圖這個Matrix就不是Echelon Form，因為它的leading entries並沒有依階排序

### Reduced Row Echelon Form

Reduced Row Echelon Form必需先滿足Row Echelon Form的兩個條件之外再滿足一個條件：
3. leading entry所在的column必須為standard vectors(leading entry以外的值為0)

### Reduced Row Echelon Form

檢查是否為Reduced Row Echelon Form之前，要先確認它是否為Row Echelon Form。

### RREF is unique

Reduced Row Echelon Form有一個性質，也就是每一個Matrix只會有一個Reduced Row Echelon Form，但它可以有多個Row Echelon Form。

### Reduced Row Echelon Form

pivot：中樞、樞杻

原始的Matrix-$A$的Reduced Row Echelon Form-$R$的leading entry的位置稱為pivot positions，而pivot positions所在的column就稱為pivot column。

### Reduced Row Echelon Form

在給定Reduced Row Echelon Form的時候該如何求解?解有三種，唯一解、無窮解、無解。

唯一解：
如果Reduced Row Echelon Form在去掉最後一個column之後，它是identity matrix(即左上右下對角線為1其餘為0)

### Reduced Row Echelon Form

無窮多解：
對於不知道的解稱為free variable，有限制的部份稱為basic variable，只要存在著free variable就意味著擁有無窮多解。可以以Parameteric Representation的方式來表示。

### Reduced Row Echelon Form

無解：
直觀來看，只要某一個row，其最後一維為non-zero，其餘為zero，那它就是inconsistent

### Reduced Row Echelon Form

高斯消去的大原則是，利用一連串的elementary row operations讓它變為Row Echelon Form，再經過一連串的elementary row operations讓它再變為Reduced Row Echelon Form