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

課程主要說明矩陣的相乘
### Matrix Multiplication

高中所學的矩陣相乘概念，假設有兩個Matrix-$A, B$，相乘得到新的Matrix-$C$，其中$A$為mxn，而$B$為nxp，相乘之後得到的$C$為mxp。

$C_{ij}$的值，就是將$A$第$i$個row與$B$第$j$個column取出做inner prodoction，也就是將兩個元素兩兩相乘之後加總。

### Matrix Multiplication

上面是一個矩陣計算的範例。

### Matrix Multiplication

不過相信畢業之後很多人都忘了高中職所教的矩陣相乘的概念，因此實務上可以如上圖所示的作法。

$AB$相乘，那就將$A$放置$B$放上面，$A$的row與$B$的column延伸出去所交集的點就以該row與該column做inner product就可以得到該位置的值。
### Matrix Multiplication - 4 ways

上面是一個矩陣計算的範例。
### Matrix Multiplication

我們可以從Linear Combination的觀點來看待矩陣相乘這件事，即$AB=A\left[b_1 \space b_2 \space ... \space b_p \right]=\left[Ab_1 \space Ab_2 \space ... \space Ab_p \right]$

Matrix與Vector相乘就是將Matrix內的column做linear combination。

因此，矩陣相乘之後的第一個column，就是$A$這個matrix的所有column做linear combination，這個coefficient就是$B$第一個column。相乘之後的第二個column依然是$A$的column做linear combination，只是coefficient是$B$的第二個column。

因此，矩陣相乘就是用不同的coefficient($B$)對同一組vector set($A$)做linear combination。

### Matrix Multiplication - 4 ways

這邊是一個以linear combination計算的範例。

### Matrix Multiplication - Meaning

$C=AB$，這可以看成一個system-$A$，然後輸入$B$的column-$b_1$就可以得到$C$的$c_1$，反覆的計算，最終得到$c_p=A b_p$，然後將$c_1 \sim c_p$結合起來，就是$C$也就是$AB$。
### Matrix Multiplication - Meaning

另一種說法，相乘可以視為是兩個線性系統的Composition。

所謂的Composition，假設有兩個function，$f, g$，以這兩個function組成一個新的function，即$g(f(.))$，這就是將兩個function做composition，即$g \circ f$，input先通過$f$再通過$g$。
### Matrix Multiplication - Meaning

將相同的概念套到目前所提到的$C=AB$，也將是將$AB$這兩個system給composition起來得到一個新的function，其coefficient就是$C$。

舉例來說，假設$A$為mxn，$B$為nxp，也就是輸入一個$R^p$的vector經過$B$會得到一個$R^n$的vector，再通過$A$產生一個$R^m$的vector。

但如果是將兩個system給composition起來的話，就直接是輸入一個$R^p$，經過$C$得到$R^m$
### Matrix Multiplication - Meaning

要證明這件事不難。之前課程提過，在不知道linear system參數的情況下，可以利用standard vector，來得到該Matrix columns。

我們要證明的就是，將standard vector分別丟到原始$AB$與composition之後的$C$是否相同，即input-$e^1$經過$B$得到的$b_1$再經過$A$得到的$AB_1$會等於$c_1$。相同的道理，$e^2...e^p$的輸入得到的也是一樣。
### Matrix Multiplication - Meaning

將結果列出來，就可以得到$C=\left[Ab_1 \space Ab_2 \space ... \space Ab_p \right]$，將$A$提出來，將$b_1 \space b_2 \space ... \space b_p$集合起來，就可以得到$C=AB$。

我們現在知道，原本兩個linear system，其coefficient為$A, B$，將兩個linear system compose起來得到一個新的system，其coefficient-$C$就是兩個linear system的兩個matrix相乘。

### Matrix Multiplication

剛才提的是將Matrix Multiplication視為對column做linear combination，這邊說明的是將它視為對row做linear combination。

$AB$相乘，將$A$的每一個row做為coefficient，去乘上$B$的每一個row(固定)，也就是相乘的第一個row就是$A$的第一個row去乘上$B$的每一個row。

### Matrix Multiplication - 4way

從範例來看，一個3x2的矩陣乘上2x2的矩陣。

第一個row就是取左邊矩陣第一個row-$\left[1 \space 2 \right]$，乘上右邊的矩陣，第一個元素就乘上右邊矩陣的第一個row，第二個元素就乘上右邊矩陣的第二個row，以此類推。

### Matrix Multiplication

最後一個看待Matrix Multiplication的觀點，就是將它視為一堆matrices的summation。

假設有兩個matrix-$A, B$，$A$的column為$a$，$B$的row為$b$，接下來將$A$的第一個column-$a_1$乘上$B$的第一個row-$b_1^T$，以此類推。

$a_1b_1^T$可以將它視為是兩個矩陣的相乘，其中$a_1$的維度為nx1，而$b_1^T$則是1xp，兩者相乘就得到一個nxp的矩陣，你可以得到n個nxp的矩陣，最後再將它們相加，這就是將矩陣相乘視為一堆矩陣相加的概念。
### Matrix Multiplication

上面是一個概念上的範例，可以注意的是，以這種方法計算而得的多個矩陣，它們的rank也會是相同的，因此也可以視為是一堆rank=1的矩陣相加。

這種概念可以推廣到另一個概念，也就是Block Multiplication。

概念上就是，將左邊的matrix以column為單位來看待，右邊的matrix則是row為單位來看待，因此左邊的matrix可以視為一個1x2的矩陣，而右邊的matrix則可以視為一個2x1的矩陣，最終會得到一個1x1的矩陣。

### Augmentation and Partition

之前我們提過矩陣的Augmentation的概念，就是將兩個matrix併在一起得到一個新的matrix。

而矩陣的Partition就是可以用各種的方法來分割它。
### Block Multiplication

如果要做矩陣的相乘，就可以將兩個矩陣分割，然後將每一個分割後的block視為一個單位，再去分割後的單位做相乘。

上面範例，將矩陣分為四個block，這樣就可以將矩陣視為有四個元素的矩陣，只是每個元素裡面就都還是一個矩陣，這樣子就可以將它們視為scalar的計算，唯一要注意的是，雖然將它們視為scalar的計算，但本質上還是矩陣的相乘，因此不能調整順序。
### Block Multiplication

上面給出一個範例，不同的顏色代表不同的block之間的計算。分割的時候要注意到維度上的問題，避免造成無法計算。
### Block Multiplication

上面給出一個範例。
### Not Communicative

這邊開始說明矩陣相乘的性質。

1. $AB \neq BA$

### Not Communicative

從維度的角度來看就可以直觀的瞭解兩者交換的結果並不會相同，mxn與nxp相乘為mxp，而nxp與mxn相乘則因為維度問題而無法相乘。

### Properties

* 假設A、B、C、P、Q皆為矩陣，其維度為kxm，C為mxn而P、Q為nxp，矩陣相乘有以下性質：
1. 對任何的scalar-s而言，其s(AC)=(sA)C=A(sC)
2. (A + B)C = AC + BC
3. C(P + Q) = CP + CQ
4. I~k~A = A = AI~m~ (I為Identity matrix)
5. 任何矩陣乘上zero matrix其結果為zero matrix

* 如果有k個相同矩陣相乘，則可以寫為多項式，即A^k^ = AAAA.....A(k個A)
* A^1^ = A
* A^0^ = I~n~

### Properties

* 假設A為kxm，且C為mxn
1. $(AC)^T = C^TA^T$，兩者相乘的維度為kxn，如果都先各自transpose之後為nxm與mxk，相乘之後即為nxk
2.
### Special Matrix

1. Diagonal Matrix: 即對角線有值，非對角線的元素皆為0
2. Symmetric Matrix: 對稱矩陣，即$A^T = A$，而$AA^T$與$A^TA$都會是方形，且依然對稱
### Practical Issue

這邊說明的是，位置的差異會造成計算量的不同。

假設A、B、C、P、Q皆為矩陣，其維度為kxm，C為mxn而P、Q為nxp，其中A(CP) = (AC)P，雖然結果相同，但計算量是不同的。