---
tags: Linear Algebra - HungYiLee
---

Linear Algebra - Lec 08~13: Solving System of Linear Equations
===

[TOC]

# [課程網站](http://speech.ee.ntu.edu.tw/~tlkagk/courses_LA18.html)

# [Lecture 8: Solving System of Linear Equations (part 1)](https://www.youtube.com/watch?v=zuTH1WdREkY&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=8)

## Equivalent

兩個 equation 有相同的 solution set，就是 equivalent

### Elementary Row Operation

以下三個操作會得到 equivalent 的 linear equation
1. **Interchange**: interchange any two rows of the matrix
2. **Scaling**: multiply every entry of some row by the same nonzero scalar
3. **Row Addition**

這三個操作其實就是 **elementary row operations**


### Augmented Matrix

$\begin{bmatrix}A|b\end{bmatrix}$

## Reduced Row Echelon Form (RREF)

利用 elementary row operations 的那三個操作把 augmented matrix 簡化成最好求解的形式，這個形式就是 RREF，以下開始說明。

### 先介紹 Row Echelon Form

定義：
1. 所有 non-zero rows 都在所有 zero rows 的上方
2. 每個 row 的 leading entry 都在上一個 row 的 leading entry 的右方

### Reduced Row Echelon FOrm

除了以上兩點須滿足以外，另外需滿足：
3. 每個 leading entry 所在的 column 必須是 **standard vector** (即只有一維是 1，其他為 0)

- RREF is unique
- REF may be not unique

### Pivot Position & Pivot Columns
- leading entry 所在的 position 和 columns 就稱為 pivot position 和 pivot columns
- leading entry 應該是每列的第一個非零項

## 利用 RREF 來解 linear equation

### Unique Solution(恰有一組解)

RREF 看起來是 $\begin{bmatrix}I&b'\end{bmatrix}$
- 眼睛閉著都解得出來

### Infinite Solution (Parametric Representation, Basic Variables, Free Variables)
對於所有 equation，把 leading entry 以外的所有 variable 都丟到等號右邊，可以得到一組 **parametric representation**，此時
1. 被丟到右邊的 variable，稱為 **free variable**
2. leading entry 所在的 variable，稱為 **basic variable**
3. 解空間可以被表示為：幾組 vector 的 linear combination 加上一個 constant vector

**Example**

### No Solution
- 當 augmented matrix 的某個 row 只有最後一個 element 不為 0，則該 linear system 無解
- ex: $\begin{bmatrix}1&0&-3&0\\0&1&2&0\\0&0&0&3\\0&0&0&0\end{bmatrix}$

# [Lecture 9: Solving System of Linear Equations (part 2)](https://www.youtube.com/watch?v=YzAg9l9FO7Y&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=9)

## Gaussian Elimination 高斯消去法
略

## 得到了 RREF 之後
- 其實和上一節的過程一樣

## 終於可以用手 check linear independent or not 了
給定 **vector set** $\{a_1, a_2, ..., a_n\}$

- 若它們是 linear **dependent**，則
- 存在 $a_i$ 為其他 vector 的 linear combination。也就是
- 存在 scalar $x_1,...,x_n$ **不全為 0**，使得 $x_1a_1+x_2a_2+...+x_na_n=0$。即
- $Ax=0$ 有 non-zero solution (無窮多解)
- $A=\begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix}$

# [Lecture 10: What can we know from RREF? (part 1)](https://www.youtube.com/watch?v=ObibwhRY8xc&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=10)

## RREF v.s. Linear Combination

### Column Correspondence Theorem

假設 $A=\begin{bmatrix}a_1&a_2&...&a_n\end{bmatrix}$，$a_i$ 是 $A$ 的第 $i$ 個 column vector，且 $A$ 的 RREF 為 $R=\begin{bmatrix}r_1&r_2&...&r_n\end{bmatrix}$，則
- 若 $a_i$ 是 $A$ 其他 columns 的 linear combination $\implies$ $r_i$ 也是 $R$ 其他 columns 的 linear combination，且和 $a_i$ 的 linear combination 是**相同的 coefficient**
- 若 $r_i$ 是 $R$ 其他 columns 的 linear combination $\implies$ $a_i$ 也是 $A$ 其他 columns 的 linear combination，且和 $r_i$ 的 linear combination 是**相同的 coefficient**

**Example**


#### Intuitive Idea
- elementary row operation 不會改變 column 之間的關係

#### 證明



因此，**column correspondence theorem** 的另外一個陳述就是
- **若 $A$ 的 RREF 是 $R$，則 $Ax=0$ 和 $Rx=0$ 會有相同的 solution set $x$**

#### example
上面的結論其實就**等同於 column correspondence theorem**，若不能接受，來看看例子
1. 若 $A$ 中存在一個 column vector 是其他 column vectors 的 linear combination，則這樣的 linear combination 就對應著一組解
2. 而由上面的證明可以知道，$Rx=0$ 也會有相同的一組解，利用此解代回 $Rx=0$ 可以得到相同的 linear combination，完畢

從 $R$ 推回 $A$ 亦然

### Span of Rows
$A$ 的 RREF 是 $R$，則
- 若把 $A$ 的 row vector 做 Span，則會和 $R$ 的 row vector 做 Span 有相同的 space

Span of Column 則沒有這樣的性質

### Conclusions
- Columns 的第一點即 **Column Correspondence Theorem**

# [Lecture 11: What can we know from RREF? (part 2)](https://www.youtube.com/watch?v=G-afSDZgEVI&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=11)

## RREF v.s. Independent

1. 從 Column Correspondence Theorem 可以推得，**pivot columns are linearly independent**
2. **non-pivot column 是該 column 左邊的 columns 的 linear combination**

### Pivot Column v.s. Independent
- All columns of $A$ are independent **iff**
- Every column is pivot column **iff**
- Every column in $RREF(A)$ is standard vector

### Column Vectors v.s. Independent

又

- 因此**矮胖型的 matrix 的 columns 不可能是 linear independent**
- 換句話說，**more than $m$ vectors in $\mathbb R^m$ must be dependent**.
- 記憶法：太胖的 matrix 自己走不動，所以是 dependent 的


### Intuition

- 矮胖型的 matrix，是一個 linear system，他的 input 維度比較大，output 維度比較小，例如 input 是三維，output 是二維
- 大的維度映射到小的維度，就會很擠，也就是說二維空間的一個點，還原回三維，會是一堆點
- 換句話說，這個 linear system $Ax=b$ 會有不只一組解 (也就是會有無窮多解)，或者沒有解
- 這就代表了 $A$ 的 column 不會是 linear independent 的。

# [Lecture 12: What can we know from RREF? (part 3)](https://www.youtube.com/watch?v=UaBRpTMX98c&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=12)

## RREF v.s. Rank

**$Rank(A)$：$A$ 的 maximum number of linear independent columns** (Review Lec 7)

若 $A$ 的 RREF 是 $R$ 則 $Rank(A)=Rank(R)$
1. 因此 $Rank(A)$ 等於 **number of pivot column**
2. 又 number of **pivot column** = number of **non-zero rows**
3. 因此 $Rank(A)$ 也等於 $R$ 的 **number of non-zero rows**


- 從 1. 可以得知 $Rank(A)$ 小於等於 $A$ 的 columns 數量
- 從 3. 可以得知 $Rank(A)$ 小於等於 $A$ 的 rows 數量
- 因此 **$Rank(A)$ 會小於等於 $\min(\text{# columns, # rows})$**


### Properties of Rank from RREF

從上個小節可知：Given $A\in\mathbb R^{m\times n}$，則 $Rank(A)\leq\min(m,n)$
- 則若 $m<n$，表示 $Rank(A)<n$
- 又 **"$A$ 的所有 $n$ 個 column vectors 是 independent 的" 等價於 "$Rank(A)=n$"** (review Lec 7)
- 因此我們又再次得到了相同的結論：**若 $m<n$ (即矮胖型的 matrix)，則 columns are dependent**

### Basic Variables, Free Variables v.s. Rank

- **rank = # non-zero row = # basic variables**
- **nullity = # columns - # non-zero row = # free variables**
- basic variables & free variables, review Lec 8

### Conclusion of Rank and Nullity

- 值得注意的是，由 Rank 的定義不能推得 Nullity 是 number of zero-rows of RREF，因為 Nullity 與 Rank 的關係只和 column 有關，和 row 無關。$Rank+Nullity=n\text{ , n is number of columns}$

# [Lecture 13: What can we know from RREF? (part 4)](https://www.youtube.com/watch?v=mSMh27SxKbM&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=13)

## RREF v.s. Span

### Consistent or not
definition of consistent, review Lec 6



剛剛得到的結論
- **$Ax=b$ is consistent for every $b$ iff $Rank(A)=m$**, $m$ 是 row 的數量

### Consistent v.s. Span
而 **$Ax=b$ is consistent for every $b$** 可以換句話說
- every $b$ is in the span of the columns of $A=[a_1\,a_2\,...\,a_n]$
- every $b$ belongs to $Span\{a_1,...,a_n\}$
- $Span\{a_1,...,a_n\}=\mathbb R^m$

又 **$Ax=b$ is consistent for every $b$ iff $Rank(A)=m$**
- 而我們知道 $Rank(A)$ 代表了 $A$ 中 independent columns 的最大數量
- 因此 $m$ 個 independent vectors 可以 span 出 $\mathbb R^m$
- 由上述又可以推論出，若有超過 $m$ 個 vector $v_i\in\mathbb R^m$，則這些 vector 是 dependent 的


- 

### Full Rank: Rank = n or Rank = m

#### $Rank(A)=n$
- 

#### $Rank(A)=m$
-