# 李宏毅_Linear Algebra Lecture 31: Gram-Schmidt Process
###### tags: `Hung-yi Lee` `NTU` `Linear Algebra Lecture`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW)
## Linear Algebra Lecture 31: Gram-Schmidt Process
[課程連結](https://www.youtube.com/watch?v=PzqVLldlHTE&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=32)

### Orthogonal Basis

這邊說明的是將一個不是orthogonal basis的basis利用演算法轉為一個orthogonal basis，這整個過程稱為Gram-Schmidt Process。

相關可以見上一堂課程筆記說明。

### Visualization

[影片](https://www.youtube.com/watch?v=Ys28-Yq21B8)很清楚的說明整個計算的說明，非常直觀。
### Proof

這邊說明，為什麼剛才簡報提到的Span $\left\{v_1, v_2, \cdots, v_i \right\} =$ Span $\left\{u_1, u_2, \cdots, u_i \right\}$，其中$\left\{u_1, u_2, \cdots, u_k \right\}$ 因為是basis，因此為independent。

首先說明$\left\{v_1, v_2, \cdots, v_k \right\}$會是orthogonal vector set：
* 在$k=1$情況下，因為只有一個vector，因此它就直接是一個orthogonal vector
* 假設，$k=n$是成立的，那$n+1$，也就是$v_{n+1} \cdot v_i = 0$，其中$i < n + 1$，意思就是：
* 當$n=2$，那$v_2 \cdot v_1 = 0$
* 當$n=3$，那$v_3 \cdot v_1, v_3 \cdot v_2$都會是0
* 證明如下：
* 將$v_k$與$v_i$做dot product，假設$\left\{v_1, v_2, \cdots, v_{k-1} \right\}$都是orthogonal vector set(我們要證明再加入$v_k$它還是orthogonal)，那$v_k$與$v_i$做dot product的情況下，每個項目都會是0，最後會只剩下$u_k \cdot v_i - \dfrac{u_k \cdot v_i}{\Vert v_i \Vert^2}v_i \cdot v_i$，而$v_i \cdot v_i = \Vert v_i \Vert^2$，因此消掉，剩下$u_k \cdot v_i - u_k \cdot v_i = 0 = v_k$，因此我們知道$v_k \cdot v_i = 0$，也因此，利用Gram-Schmidt找出來的vector set一定是orthogonal，但目前並不能保證原始的vector set的subspace與orthogonal vector set的subspace是一樣的

以先前課程所提過的，只要能夠在dimension = k的vector set，找出k個independent vector，那它就是basis。

我們要證明，$v_1 \cdots v_k$是$u_1 \cdots u_k$的basis-$V$：
* $V$的dimension=k，$v_1 \cdots v_k$也是k
* $v_1 \cdots v_k$都是$u$的linear combination，因此$v_1 \cdots v_k \in V$
* $v_1 \cdots v_k$已經證明是orthogonal，但它必須是non zero的vector才是independent，而$v_1 = u_1$，其中$u_1$是某一個basis的成員，而basis的成員一定是independent而且為non-zero vector，因此$v_1$也一定是non-zero。而$v_2$的部份，如果$v_2=0$，那就代表$u_2$是$v_1$的linear combination，而$v_1 = u_1$，這就意味著它們($\left\{u_1, u_2, \cdots, u_i \right\}$)是dependent，但這並不成立，因此$v_2$不可能為zero vector，以此類推
* 證明$\left\{v_1, v_2, \cdots, v_k \right\}$既為orthogonal也是non-zero，因此為independent
### Example

有一個basis-$S = \left\{u_1, u_2, u_3 \right\}$，很明顯的這三個vector是linear independent，我們希望找出orthogonal basis。這可以直接帶入Gram-Schmidt的公式。