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

Linear Algebra - Lec 25~28: Eigenvalue & Eigenvector, Diagonalization, PageRank
===

[TOC]

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

# [Lecture 25: Eigenvalues and Eigenvectors](https://www.youtube.com/watch?v=1RyHRIP8QGg&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=25)

- learn how to find a "good" coordinate system (to make the function easier)

## Outline

- What is Eigenvalue and Eigenvector?
- Eigen (German word): "**unique to**" or "belonging to"
- How to find eigenvectors (given eigenvalues)?
- Check whether a scalar is an eigenvalue
- How to find all eigenvalues?

## Definition of Eigenvalues & Eigenvectors

注意
- $A$ 必須是 square matrix
- zero-vector **不是一個 eigenvector**

### Example: Shear Transform

$\begin{bmatrix}x'\\y'\end{bmatrix}=T(\begin{bmatrix}x\\y\end{bmatrix})=\begin{bmatrix}x+my\\y\end{bmatrix}$
- x 軸的方向，就是這個 transform $T$ 的 eigenvector，而 eigenvalue 就是 1

### Example: Reflection

- $b_1$ 的方向是 $T(\cdot)$ 的 eigenvector，他的 eigenvalue 是 $1$
- $b_2$ 的方向也是 $T(\cdot)$ 的 eigenvector，他的 eigevalue 是 $-1$

### Example: Expansion & Compression

- 任何 vector 都是 eigenvector，而 eigenvalue 是縮放的比例

### Some matrices don't have eigenvector

- 例如 rotation，因為沒有一個 vector 在旋轉後會變成自己的 k 倍 (zero-vector 不算)
- 其實在 complex (複數) domain 有 eigenvector，影片 51:14

## How to find eigenvectors (given eigenvalues)

- An eigenvector of $A$ corresponds to a **unique eigenvalue**.
- An eigenvalue of $A$ has **infinitely many eigenvectors**.
- Do the eigenvectors correspond to the same eigenvalue form a subspace?
- No, 但是只要把 **zero-vector** 加進去這個集合，就是 subspace 了

## Eigenspace

- 同一個 eigenvalue $\lambda$ 對應的 eigenvector 所形成的集合，就是 **$(A-\lambda I_n)v=0$ 的 non-zero solution set**
- 而 **eigenspace** 是上面那個集合**再加上 zero vector** = = 囧
- 所以 ***eigenspace 就是 subspace 了吧?***


## Check whether a scalar is an eigenvalue

- 若 $\dim(Null(A-\lambda I_n))=0$，則不是 eigenvalue

### Example

- ***好像只要 $A-\lambda I_n$ 是 non-invertible，$\lambda$ 就是 eigenvalue??***

## Looking for Eigenvalues (找出所有 Eigenvalues)

- 解出 $\det(A-\lambda I_n)=0$ 所有可能的 $\lambda$ 即可
- 補充：
- 解出的所有 eigenvalue 乘起來會是 $\det(A)$
- 解出的所有 eigenvalue 加起來會是 $trace(A)$
- $trace(A)$ 就是 $A$ 對角線所有值的和


### Example 1


### Example 2


### Example 3

- 解 $t^2+1=0$
- 本題較特別，沒有實數 eigenvalue；**但有複數/虛數 eigenvalue**

## Characteristic Polynomial & Characteristic Equation


### Properties

- 在本章幾乎沒提到 RREF，因為 $A$ 和 $RREF(A)$ 並沒有相同的 characteristic polynomial，因此 eigenvalue 或 eigenvector 也不同
- similar 的兩個 matrix 有相同的 characteristic polynomials => 有同樣的 **eigenvalue** (不是 eigenvector!!)
- 這其實很直觀，因為兩個 matrix 只是從不同 viewpoint 看同一個 transform
- proof: assume $B=P^{-1}AP$
- $\det(B-tI)\\=\det(P^{-1}AP-P^{-1}(tI)P)\\=\det(P^{-1}(A-tI)P)\\=\det(P^{-1})\det(A-tI)\det(P)\\=\dfrac{1}{\det(P)}\det(A-tI)\det(P)\\=\det(A-tI)$
- 故得證

#### Q&A

- 解 $\det(A-tI_n)=0$ 其實就是在解 $t$ 的 $n$ 次多項式
- 因此 $A$ 的 eigenvalue 會小於等於 $n$ 個

## Characteristic Polynomial v.s. Eigenspace

可以對 $\det(A-\lambda I_n)$ 做 factorization (因式分解)
- **eigenspace 的 dimension 一定小於等於 multiplicity**
- 補充：後面會提到，eigenspace 的 dimension 要等於 multiplicity，才可以被 diagonalize (對角化)


### Eigenvalues of upper triangular matrix

- upper triangular matrix 的 eigenvalues 就是它的對角線
- review: upper-triangular matrix 或 lower-triangular matrix 的 determinant 就是對角線相乘


## Summary


# [Lecture 26: Diagonalization](https://www.youtube.com/watch?v=TsB5_BiMFoo&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=26)

- 可對角化，也代表 $A$ 和 diagonal matrix $D$ 是 similar 的
- review: similar 代表兩個 matrix 是從不同的 coordinate system 看待同一個 transform

## Diagonalizable

- $A$ is called **diagonalizable** if $A=PDP^{-1}$
- $A\in\mathbb R^{n\times n}$
- $D\in\mathbb R^{n\times n}$ **diagonal** matrix
- $P\in\mathbb R^{n\times n}$ **invertible** matrix
- 要證明某個 matrix $A$ 不能被對角化，就先假設他可以被對角化，然後用反證法找出矛盾。

### Diagonalizable v.s. Eigenvalue & Eigenvector

$A,P,D$ 之間的關係
- $d_i$ 是 $A$ 的 eigenvalue，而 $d_i$ 對應的 eigenvector 是 $p_i$
- $P=[p_1\,p_2\,...\,p_n]$
- $D=[d_1e_1\,d_2e_2\,...\,d_ne_n]$


### Diagonalizable v.s. Basis

- **若 $A$ 是 diagonalizable，則 $A$ 的 eigenvectors 可以形成 $\mathbb R^n$ 的 basis**

### How to diagonalize a matrix?

根據上述：
1. 找到這個 matrix $A$ 的 $n$ 個 independent 的 eigenvectors
2. 那就找到了 $P$
3. 找到 $P$ 就可以找到 $D$

### How to find independent eigenvectors?

- **只要 eigenvector 對應的 eigenvalue 是不同的，那他們就 independent**
- 注意：**即使 eigenvalue 的數量小於 $n$，也有可能找到 $n$ 個 linear independent 的 eigenvector**


#### Proof: 不同的 eigenvalue 對應到的 eigenvector 一定是 independent 的
- 先假設他們是 dependent 的，但會造成矛盾，反證結案


- 只要找得到 $n$ 個 independent 的 eigenvector，那 $A$ 就是 diagonalizable 的；反之則否
- 你沒辦法找到大於 $n$ 個 independent 的 eigenvector

### Example


## Application of Diagonalization - Markov Chain

- **Markov Chain** 需要把 (transition) matrix 連乘 m 次，非常麻煩，因此需要 diagonalization 來幫助我們做計算



1. 先把 $A$ 做 diagonalization (對角化)

2. 再把 $A$ 連乘 m 次
- 會發現無論 initial condition 是在做什麼，最後的機率都會一樣

# [Lecture 27: Diagonalization for Linear Transformation](https://www.youtube.com/watch?v=L7Y8wB3xzEc&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=27)

## Review?: Test for a Diagonalizable Matrix

$A$ 是 diagonalizable iff
1. characteristic equation $\det(A-tI_n)=0$ 有 $n$ 個實根
2. 且每個 eigenvalue $\lambda$ 對應的 multiplicity 必須等於 eigenspace 的 dimension


## Review: Diagonalization of Linear Operator

就先把 linear operator 轉換成 matrix $A$，再做 diagonalize 即可

### 不能被對角化的 example

1. characteristic polynomial is $-t^2(t+2)$
2. eigenvalues: 0, -2
3. $RREF(A-0I_3)=\begin{bmatrix}1&-1&0\\0&0&1\\0&0&0\end{bmatrix}$
4. eigenvalue 0 的 eigenspace 的 dimension 是 1，小於 multiplicity，因此不能 diagonalize

## Eigenvectors form the good Coordinate System

- review Lec 21~22

### Example


# [Lecture 28: PageRank](https://www.youtube.com/watch?v=pSg9TG_U_fY&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=28)

## 有空再回來看 ˊ ˋ

- 1999, we present **Google**.

- PageRank 的分數就是去解 $Ax=x$，也就是 $(A-\lambda I)x=0$ 對應到 $\lambda=1$ 的 eigenvector