# Linear Algebra for Machine Learning and Data Science(Week4: Eigenvalues and Eigenvectors)
###### tags: `coursera` `Linear Algebra` `math`
[week4](https://www.coursera.org/learn/machine-learning-linear-algebra/home/week/4)
## Bases in Linear Algebra
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/Np8AS/bases-in-linear-algebra)

課程說明basis
### Bases in Linear Algebra

課程中說過很多次的basis，像是將一個正方形的basis經過線性轉換變成平行四邊行，這兩個都是basis。
### Bases in Linear Algebra

這裡面最重要的不是這兩個形態，而是定義它們的兩個從原點指出的向量，這就是basis。
### Bases

它的特性就是，空間中的每個點都可以表示為basis元素中的線性組合。為什麼它們叫basis？假設，空間中有一個點，那我們有沒有辦法單純的用這basis所指向的方向到達這個點？答案是可以的，而且基本上是有無限多種可能的。

### Bases

basis不一定會是直角的，也可以斜斜的，這邊給出更多範例。

### What is not a basis?

這邊給出non-basis的範例，像兩個向量是在一條線上，因為它只有一個方向，所以只能往那個方向走，因此對於左上的點它是無法到達的，也就是說，它是無法覆蓋整個平面空間的。
## Span in Linear Algebra
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/wweH5/span-in-linear-algebra)

課程說明span
### Span

簡單說，basis能到達的任一個空間上的點的集合就是span，即使是non-basis也有span，以剛剛我們看到的範例來說，它的span就是那條線。
### Span

即使是兩個不同方向的向量也是一樣，它的span是包含兩個向線的所有線上的點的集合。
### Span

兩個相同的向量所擁有的span也是一樣，過線的所有點的集合就是它的span。
### Is this a basis?

現在有個問題，這兩個向量是不是形成這條直線的basis？

答案是否定的，因為basis必需是最小的生成集合(miniman spanning set)，所以這兩個向量要各別是basis的長度，但它們並不是。它們是spanning set，但並不是basis。
### Is this a basis for something?

上面的範例來看，它就是那條線的basis。任何過原點的向量，在相同方向的情況下都是這個線的basis。
### A basis is a minimal spanning set

總的來看，basis就是最小生成集合，上圖左來看，這個向量確實就是那條線的basis，但上圖右的這兩個向量就不是了，太多了。
### A basis is a minimal spanning set

相同的問題在高維度上也會發生，上圖左的兩個向量形成平面的basis，但你拿掉其中一個向量它就不再是basis，因為無法再到達平面空間的任意位置。

上圖右的三個向量也無法形成平面的basis，雖然它們也是可以形成空間中的任何位置，但太多了。這三個向量的任意兩個向量的子集都是basis，多出來的就冗餘了。

### Number of elements in the basis is the dimension

這邊有一個有趣的關聯，那就是basis的長度會是平面空間的維度。上圖左來看，一個向量形成basis，因此其空間維度為1，上圖右的話則是兩個向量形成basis，其空間維度為2。
## Eigenbases
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/gRt9N/eigenbases)
### Basis

Eigenbases是所有basis的大哥，這邊給出一個範例。有一個線性轉換矩陣，$\begin{matrix}2 & 1 \\ 0 & 3 \end{matrix}$，左邊是原始的座標，右邊是轉換後的座標。

給出兩個向量，$(0, 1), (1, 0)$之後，經過點積計算可以得到$(1, 3), (2, 0)$。可以清楚看到左邊的正方形經過轉換變成右邊的平行四邊形，空間其餘的區域也都是相對應的轉換。這樣的轉換又稱為座標的轉換，或basis的改變。這也正是我們想利用轉換矩陣做的事情。
### Eigenbasis

現在我們來點不一樣的，不再選擇正方形的basis，而是選擇平行四邊形的basis(1, 0)(1, 1)，可以發現到，轉換過後也是一個平行四邊形，當然空間中的其它區域也是相對應的轉換。

特別的地方在於，這些位置是平形的，左右兩邊是一個比例而以，我們對空間做的事情就是以水平方向展延2倍，然後對角線展延3倍。這個basis很特別，單純的由兩次的展延所組成，又稱為eigenbasis。

### Eigenbasis

這種eigenbasis有什麼用途呢？這邊給出一個範例，假設你想知道空間中$(3, 2)$轉換之後的結果，乘上矩陣當然就可以直接得到$(8, 6)$，但有另一種方式，以線性轉換來看就是我們的水平展延2倍，對角展延3倍，看起來似乎簡單多了，單純的經過兩次的展延就能得到轉換後的結果。

eigenbasis中的兩個vector即稱為eigtnvector，那兩個展延的因子，也就是2、3的話則稱為eigenvalues。

這是很重要的觀念，因為它們確實簡化了整個計算。

## Eigenvalues and eigenvectors
[課程連結](https://www.coursera.org/learn/machine-learning-linear-algebra/lecture/gakHB/eigenvalues-and-eigenvectors)

課程說明如何經過計算得到eigenvalues
### Finding eigenvalues

上圖左是課程中常用的矩陣$\begin{matrix}2 & 1 \\ 0 & 3 \end{matrix}$來做為說明，看看這對其週圍的點的影響。從上一堂課的說明我們知道，這個矩陣的轉換就是水平2倍，對角3倍的變化。

上圖右是做為比較的矩陣，$\begin{matrix}3 & 0 \\ 0 & 3 \end{matrix}$，這是一個任意方向都會展延3倍的轉換。

注意到一件事，那就是這兩個矩陣的轉換並非相同的，但它們在某些點上是重合的。換句話說，它們在兩圖上特別標起來的線上(也就是對角線)的行為是相同的。

### Finding eigenvalues

這意謂著它們有無限多個點是匹配的，這很怪啊，轉換之後應該只會在原點，也就是$(0,0)$的地方重疊而以。當它們有無限點匹配的時候就代表著有non-singular的味道在裡面，到底發生什麼事？

:::success
似乎指的是兩個矩陣乘上某一個向量之後的結果會是相同的，也就是：
:::

如果兩個轉換會在無限多點上重疊的話，那就代表在這個重疊區的這兩個轉換的差(相減)會是零，也就是在對角線上相減的結果會是零。這也意謂著你拿著任意一個向量去怎麼乘這個差都會是零，這也是singular transformation的特徵。

:::success
兩個重疊區域相減為零則意謂著：

:::

回想一下，non singular transformation對於矩陣乘向量會等於$(0,0)$就只有一個解，那就是向量等於$(0,0)$的情況。所以如果你有很多解可以滿足這情況的話，那就代表這個矩陣是singular，這可以很輕易的用行列式來驗證(行列式為零)。
### Finding eigenvalues

這是跟剛剛一樣的範例，不過對比的矩陣變成是$\begin{matrix}2 & 0 \\ 0 & 2\end{matrix}$。很明顯的，這兩個轉換不盡相同，但在水平的線上卻一樣是展延2倍。
### Finding eigenvalues

也就是說，左右兩個矩陣在乘上某個$x, y$的向量都會有無限多點在那條水平線上。也就是說，這兩個矩陣的差在乘上向量$x, y$之後會得到零。
### Finding eigenvalues

那這兩個eigenvalues，也就是2、3，有什麼特別的嗎？

如果$\lambda$是eigenvalue，那麼由我們的矩陣所給出的轉換與依著$\lambda$來縮放的平面對於無限多個向量$x, y$來說會是相同的。

也就是說，這兩個矩陣的差乘上向量$x, y$就會是零。當它有很多組解的時候，對於無限多的向量與方程式而言就是這樣(不是很明白這邊的意思)。所以這個相減之後的矩陣就會是singular，或者我們說它的行列式就會是零：

展開之後就會得到$(2-\lambda)(3-\lambda)-1\cdot 0 = 0$，這個式子我們稱之為characteristic polynomial，也就是特徵多項式。

基本上我們要找到eigenvalues $\lambda$就是從這個特徵多項式中去找到它的根，能夠讓這個特徵多項式為零的就是eigenvalues。以這個範例來看就是2跟3。

### Finding eigenvectors

有eigenvalues就可以來找eigenvectors，我們要解的方程式就是這樣：

把上面的式子展開之後可以得到：
* $yx+y=2x$
* $0x+3y=2y$

得到的解就會是$x=1, y=0$，這就是eigenvalues=2所對應的eigenvector。

同樣的方法再做一次，就可以得到eigenvalues=3所對應的eigenvector。
### Quiz

這邊再給出一個範例，$\begin{matrix}9 & 4 \\ 4 & 3\end{matrix}$，求出它的eigenvalues。

首先寫出它的characteristic polynomial，$\det\begin{matrix}9 - \lambda & 4 \\ 4 & 3 - \lambda \end{matrix}=(9-\lambda)(3-\lambda)-4\cdot 4=0$，展開之後求它的根，可以得到eigenvalues為11、1。

延伸閱讀：
* [Eigenvectors and Generalized Eigenspaces](https://www.youtube.com/watch?v=ajXb3N6QEqc)
* [Principal Component Analysis (PCA)](https://www.youtube.com/watch?v=g-Hb26agBFg)

---
## 延伸閱讀
### Eigenvectors and Generalized Eigenspaces
[Eigenvectors and Generalized Eigenspaces](https://www.youtube.com/watch?v=ajXb3N6QEqc)

#### Matrices

一樣的從課程中常見的範例矩陣$\begin{matrix}2&1\\0&3\end{matrix}$開始，矩陣乘上向量$(x, y)$做個點積計算得到它的結果。

課程就要從這邊開始說明：
1. eigenvalues, eigenvectors, eigenspaces
2. Generalized eigenvalues, Generalized eigenvectors, Generalized eigenspaces

#### Linear transformations

這是一種把矩陣視為是線性轉換的很好的幾何方法，也就是一種映射空間的方法，也就是把空間中的$x,y$經過與矩陣的計算轉至另一個空間表述，每個點都有它的轉換。

先嚐試將一個正方形轉換看看，上面範例很明顯看的出來，原點的部份始終轉至原點，剩下三個點一樣經過計算可以得到，最終一個小小的正方形變成一個平行四邊形。對於空間中任一個點都是一樣的，它會轉至相對應的地方。所以可以看的左圖黑箭頭綠色點轉換至右圖的時候也是在相對應的座標上。

正方形跟平行四邊形填滿整個空間，我們把它稱為basis，也因此矩陣做的就是將basis轉換成另一個basis。

#### Eigenvalues, eigenvectors and eigenspace

換個角度來看世界，這次不用正方形，這次用小的平行四邊形，後面會說明怎麼取得這個小小的平行四邊形。轉換之後從一個小小的平行四邊形變成大大的平行四邊形。重點來了，為什麼不用剛剛的正方形就好，要特別用這個平行四邊行呢？因為這兩個平行四邊形有著平形的邊。

把目光放往藍色箭頭處，點$(1,0)$變成$(2, 0)$，這相當於把自己延伸2倍。再把目光放往藍色箭頭處，點$(1,1)$變成$(3,3)$，這相當於把自己延伸3倍。這意謂著整個線性轉換是由這兩個方向以及延伸倍數所定義，這對線性代數來說是很重要的一個觀念。

這裡面有個重要的詞，eigen，這是德文，意思就是自己，形成basis的兩個向量稱為eigenvectors，那所形成的basis稱為eigenbasis，兩個延伸倍數，也就是我們說的2、3即為eigenvalues。

#### Eigenvalues, eigenvectors and eigenspace

藍色向量的部份經過轉換之後還是在同一條線上，另一個紅色向量也是同樣的，雖然都經過倍數的拉伸，但仍然是在同一條線性，這兩條線即稱為eigenspace，這也是唯一通過原點經過轉換還是自己本身兩條線。其它線想通過原點當然是可以的，不過經過線性轉換之後就不再是自己原本的那條線。當然，如果你的矩陣是identity matrix或是其它特殊矩陣的話就另當別論了。

#### Eigenvalues, eigenvectors and eigenspace

現在我們知道，當我們把矩陣乘上向量$(1,1)$的時候，我們會得到一個3倍的結果，乘上向量$(1,0)$的時候，我們會得到一個2倍的結果。

一般來說，矩陣會以$A$來表示，兩個eigenvectors會以$v_1, v_2$表示，eigenvalues則是$\lambda_1, \lambda_2$，我們會得到兩個方程式：
* $A v_1 = \lambda_1 v_1$
* $A v_2 = \lambda_2 v_2$

#### Eigenvalues, eigenvectors and eigenspace

eigenvectors與eigenvalues很好的定義了整個轉換。以上圖為例，那個綠色點所在的座標很好的形成一個平形四邊行，我們知道，藍線的部份會延伸2倍，紅線的部份會延伸3倍，延展出去就不難明白綠色點經過轉移之後的位置。這大大的簡化了整個線性轉移的過程。

#### Eigenvalues, eigenvectors and eigenspace

找出Eigenvalues, eigenvectors的過程涉及特徵多項式的行列式計算，這部份可以到https://www.wolframalpha.com 上去操作看看。

#### Some transformations are singular

並不是每一個矩陣都可以很好的轉換，有些可能就會變的亂七八糟，這種的就稱為singular transformation。

上圖左來看，每一個座標點經過轉換都會是0。上圖右轉換之後則是會變成線，而不是平面空間。

#### Transformations of the plane

上圖說明著空間中的各種可能的轉換。每一個non-singular transformation都是這三個轉換的某一個組合，也因此讓我們來喵喵看這三種轉換的eigenvectors。

#### Transformations of the plane

左圖，矩陣左上、右上的元素，左上是水平延伸，右下則是垂直延伸的倍數，變來變去都還是它自己，這意謂著它有兩個eigenvectors。

中圖，沒有向量的變化，而是座標系旋轉了，這並不代表它沒有eigenvectors，這邊不談。

右圖，注意到只有藍線的部份是本身的延伸，紅線的部份並不是，所以這只有一個eigenvector，以及一個稱為generalized eigenvector。

#### Generalized eigenvectors

回到剛剛介紹的網頁，給出一個矩陣$\begin{matrix}3&-1\\ 1& 1\end{matrix}$，結果來看得到得到一個eigenvector $(1, 1)$，然後它的eigenvalue $\lambda_1=2$，下面還有著一個generalized eigenvector $u$。

這個generalized eigenvector與generalized eigenvalue看起來也是往一個方向去延伸，但不完全是這樣的。

#### Generalized eigenvectors

我們用範例來說明，上圖左的平行四邊形經過矩陣轉換得到上圖右的結果。eigenvector $(1,1)$一如往常的發揮，變成了$(2, 2)$。但是eneralized eigenvector $(1, 0)$就不是到$(2, 0)$了，是在$(3, 1)$，有趣的話，$(2, 0)$再加上另一個eigenvector $(1, 1)$就是$(3, 1)$。也就是說，generalized eigenvector並不單純往自己的方向延伸，還會再加上另一個eigenvector，也就是往第一個eigenvector的方向上再做一點剪裁的概念，這樣的轉換就對應到拉伸、剪裁的行為。

第二張圖就是它的basis。
#### Generalized eigenvectors

數學上來看就是上圖這樣。把矩陣乘上紅色的eigenvector就是2倍的eigenvector，把矩陣乘上藍色的話就是2倍的之外再加上紅色的向量：
* $A_v1=\lambda v_1$，其中$v_1$為eigenvector
* $A_v2=\lambda v_2 + v_1$，其中$v_2$為generalized eigenvector

兩個轉換都是對應$\lambda$的拉伸，不過對於$v_2$來說還要再考慮$v_1$所造成的剪裁的影響。

值得注意的是，generalized eigenvector總是會與eigenvector有著相同的eigenvalues。如果它們有不同的eigenvalues，那就一定會有另一個真正的eigenvector。這部份就不在這個課程中證明了。

#### Generalized eigenspaces

現在來聊聊Generalized eigenspaces，我們知道，紅色的線是eigenvector，它會自我的延伸，所以它就是一個eigenspace，但藍色的generalized eigenvector並不會自我的延伸，它會被旋轉(延伸後剪裁掉)，我們可以來看看它到底給了自己什麼？如果能知道，那就能知道它的generalized eigenspaces。
#### Generalized eigenspaces

先讓我們畫出很多很多的平行線，第一個方程式讓我們知道它會從自己的方向拉伸2倍，這代表藍色的間隔會被拉開。

#### Generalized eigenspaces

第二個方程式則是跟我們說，藍色的方向會先被拉伸2倍，這代表紅色線也會被拉開，這時候的basis也有了變化。不過還沒有結束，我們還沒有考慮$v_1$的影響。


$v_1$給了我們一個方向，所以整個空間就被剪過去。現在，整個空間就是Generalized eigenspaces。

#### Generalized eigenspaces

有點難理解，回頭再來看一次。我們有個eigenvector，它本身就是一個eigenspace，其它平面的部份則是由藍色線所形成


我們知道藍色線的區域會被generalized eigenvector拉伸，


然後再往eigenvector的方向做剪裁。


這些藍色線在剪裁之後還是保持不變的狀態，所以我們可以說，eigenspace就是整個平面空間，這就是generalized eigenspace的觀念。把整個平面空間轉給自己。

#### Generalized eigenspaces

想像一下我們有一個三維空間，紅色的eigenvector把自己轉給自己，自成一個eigenspace，第二空間的部份就會是整個平面，也就是藍色區的generalized eigenspace。