---
# System prepended metadata

title: 'Linear Algebra for Machine Learning and Data Science(Week2: Solving system of linear equations: Row echelon form and rank)'
tags: [math, coursera, Linear Algebra]

---

# Linear Algebra for Machine Learning and Data Science(Week2: Solving system of linear equations: Row echelon form and rank)
###### tags: `coursera` `Linear Algebra` `math`
[week2](https://www.coursera.org/learn/machine-learning-linear-algebra/home/week/2)
## The rank of a matrix
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/QPQ9l/the-rank-of-a-matrix)

課程中會說明如何計算矩陣的rank(秩)。
### Compressing Images - Reducing rank
![](https://hackmd.io/_uploads/S1URLmGzn.png)

左上角的原始照片，其rank=200，我們可以利用一些手法(SVD)來降低其rank做為壓縮使用，從上圖可以看的到，從rank=1一直到rank=50的照片呈現，基本來看rank=50已經可以看的出跟原始照片非常相似。

這麼做最大的好處就在於我們只需要更少的空間就可以保存一間照片。

### Systems of information
![](https://hackmd.io/_uploads/rk5admffh.png)

回想我們課程中提過的一個概念，也就是一個system所擁有的信息有多少。上圖的範例是最一開始提過的，三個system各自所帶有的信息：
* system1：兩個句子帶有兩段信息
* system2：兩個句子帶有一段信息
* system3：兩個句子沒有任何信息

這邊要說的重點就是，一個system所帶有的信息量就定義為rank。所以，上面的範例來看的話：
* system1：rank=2
* system2：rank=1
* system3：rank=0
### Systems of equations
![](https://hackmd.io/_uploads/Bky8t7zGh.png)

這是以矩陣來呈現剛剛的範例的結果。
### Rank and solutions to system
![](https://hackmd.io/_uploads/B1j39QGz3.png)

每個system的解空間(solution space)跟rank都有著特殊的關係，延續剛剛的範例：
* system1：解為一個點，一個點的維度(dimension)為0
* system2：解為一條線，一條線的維度(dimension)為1
* system3：解為一個平面，平面的維度(dimension)為2

### Rank of a matrix
![](https://hackmd.io/_uploads/H1i1p7zfh.png)


我們可以發現一個微妙的關聯，也就是矩陣的row的數量去減掉解空間的維度就會是rank：
* system1：non-singular，範例中可以看的出來，只有在rank=矩陣row的數量的時候，它才會是non-singular

## The rank of a matrix in general
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/hJnsk/the-rank-of-a-matrix-in-general)

課程說明$n \times n$矩陣的rank
### Rank of matrices
![](https://hackmd.io/_uploads/B10xI_mMh.png)

這是課程中見過的幾個聯立方程式，我們用這幾個來說明$n \times n$矩陣的rank：
* system1：3個方程式，任一個方程式無法由其它方程式演變而來，因此它帶有3段信息資訊，其rank=3
* system2：中間的方程式是另外上下兩個方程式相加之後除二的結果，所以3個方程式只帶有2段信息，其rank=2
* system3：第二、第三個方程式都可以由第一個方程式演變而來，因此3個方程式只帶有1段信息，其rank=1
* system4：什麼都沒有，因此3個方程式沒有帶來任何信息，其rank=0

有沒有簡單一點的方式可以讓我們快速得到rank？答案是有的，也就是row echelon form。

## Row echelon form of a matrix
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/fSZUz/row-echelon-form)


### Row echelon form
![](https://hackmd.io/_uploads/Hk6Bw_Qzh.png)

執行row echelon form就掌握幾個步驟：
1. 讓第一個column為1，這可以利用row operation來各自處理每個row
2. 相減，讓左下的元素變零
3. 整理，讓對角線的元素變一
### Row echelon form for singular matrices
![](https://hackmd.io/_uploads/Hko3wOQz3.png)

這邊範例說明的是在singular的矩陣上執行row echelon form的結果，可以看到最終我們並沒有辦法很好的讓對角線皆為1，這是有意函的，後面會說明。

### Row echelon form for singular matrices
![](https://hackmd.io/_uploads/B1L0vuXMn.png)

這個範例就只能這樣，我們就說，這就是它的row echelon form。
### Row echelon form, singularity and rank
![](https://hackmd.io/_uploads/HJMKudQG2.png)


剛剛我們說到，對角線的1是有意函的，上圖來看我們可以發現到，對角線有幾個1，那它的rank就會是多少，也就是說，當我們把一個矩陣經處理變成row echelon form之後，對角線的1有幾個就代表它的rank是多少，並且當rank的值為矩陣的row的數目的時候，它就是non-singular matrix。


## Row echelon form in general
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/6Rxh8/row-echelon-form-in-general)

課程說明在$n \times n$矩陣上計算其row echelon form
### Row echelon form
![](https://hackmd.io/_uploads/rydTYumG3.png)

在$n \times n$矩陣上計算其row echelon form的作法是一樣的：
1. 先把第一個row乘上三去減第二個row
2. 再把第一個row乘上二去減第三個row
3. 再拿第二個row去處理第三個row

這樣就可以得到一個圖右那般的對角線下為0的row echelon form。
### Row echelon form
![](https://hackmd.io/_uploads/H13C9OQz2.png)

row echelon form有幾個注意的點：
1. 全零的row不是不行，要放在最下面
2. 每一個row都會有一個pivot，也就是該row最左邊非零的那個元素(圈起來的數字)
3. 每個row的pivot都會在上面那個row的pivot的右邊
4. 矩陣的rank就是pivot的數量，你有幾個pivot，這個矩陣的rank就是多少
### Important note
![](https://hackmd.io/_uploads/ByEuoOQz3.png)

多數的書本上對於row echelon form之後的pivot不會特別處理讓它變成是1，基本上是允許的，不過這個課程就是會讓它是1。我猜測這是單純的男人的堅持。
### Another example
![](https://hackmd.io/_uploads/HkzRjdXGn.png)

這邊給出另一個範例，把第一個row拿來跟第二、第三個row相減就可以得到它的row echelon form。
### What if the matrix is singular?
![](https://hackmd.io/_uploads/HyQHnOQG2.png)
![](https://hackmd.io/_uploads/Bygwn_XMh.png)


這邊給出兩個singular matrix的範例

### Rank of matrices
![](https://hackmd.io/_uploads/S1nu3OQfh.png)

簡單的幾個範例。
## Reduced row echelon form
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/gJm6U/reduced-row-echelon-form)

### Systems of equations of matrices
![](https://hackmd.io/_uploads/r1E0daEMh.png)

上面範例中的上部是我們平常在解聯立方程式會做的事，想辦法處理掉$a$就可以得到$b$再回頭計算$a$。

下部是用row echelon form的概念來處理，中間很明顯的就是row echelon form，對角線下為0，對角線為1，最後我們只要讓對角線上也為0，那就變成是reduced row echelon form，這是對應上面解聯立方程式的結果。

### Reduced row echelon form
![](https://hackmd.io/_uploads/SyQjKaEM3.png)

這邊給出一個從row echelon form變成reduced row echelon form的範例。

我們的目標是消滅右上的0.2，這只要把第二個row乘上0.2去減掉就可以滿足得到reduced row echelon form。
### Reduced row echelon form
![](https://hackmd.io/_uploads/BkfQ56NG3.png)

Reduced row echelon form的幾個特點：
1. 以row echelon form的形式呈現
2. 每個pivot為1
3. pivot以外的值為0
4. 有幾個pivot就代表它的rank是多少
### Reduced row echelon form
![](https://hackmd.io/_uploads/B1H1jpNM2.png)

這邊說明大致的流程，簡單說就是消滅消滅再消滅，用pivot去消滅pivot上面的所有值：
* 第二個row乘上2去減掉第一個row，消滅第一個row的2
* 第三個row乘上5去加第一個row，消滅-5
* 第三個row乘上4去減第二個row，消滅4
* 得到reduced row echelon form

