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

Linear Algebra - Lec 14~17: Matrix Multiplication and Inverse
===

[TOC]

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

# [Lecture 14: Matrix Multiplication](https://www.youtube.com/watch?v=yO8lDzf4jMs&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=14)

## 高中的定義

- $A\in\mathbb R^{m\times n}$
- $B\in\mathbb R^{n\times p}$
- $C = AB\in\mathbb R^{m\times p}$

the $(i,j)$ entry of $AB$ is $c_{ij}$
- $c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{in}b_{nj}$
- the **inner product** of row $i$ of $A$ and column $j$ of $B$

## 圖形化的記法

- 把 $A$ 放到 $C$ 左邊，$B$ 放到 $C$ 上面，就可以直接對齊做內積

## 從 Linear Combination 的觀點看待

### Columns 的 Linear Combination

- $A=\begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix},\,a_i\in\mathbb R^m$
- $B=\begin{bmatrix}b_1&b_2&\cdots&b_p\end{bmatrix},\, b_i\in\mathbb R^n$

則 $AB=A\begin{bmatrix}b_1&b_2&\cdots&b_p\end{bmatrix}=\begin{bmatrix}Ab_1&Ab_2&\cdots&Ab_p\end{bmatrix}$

也就是說 $AB$ 的第 $i$ 個 column 就是 $Ab_i$。回想**矩陣與向量的相乘**，可以得知，$Ab_i$ 其實也就是 **$A$ 的 column vector 的 linear combination**。
因此 $AB$ 的第 $i$ 個 column，就是 $A$ 的 column vector 的 linear combination；
換句話說，$AB$ 的每個 column，都是 $A$ 的 column vector 的 linear combination，只是 coefficient 由 $b_i$ 決定。如下圖
- 

- Example

#### Meaning - Multiple Inputs

matrix multiplication $AB$ 可以看成有一個 linear system $A$，input 了 $p$ 個 vector $\begin{bmatrix}b_1&\cdots&b_p\end{bmatrix}$ 得到的 $p$ 個結果，如下圖
- 

#### Meaning - Composition

可以視為兩個 function $f$ 和 $g$ 的 composition $g(f(\cdot))$ (即 $g^\circ f$)，$f$ 和 $g$ 就是兩個 linear function。

證明省略
- (利用 standard vector 當 input)

### Rows 的 Linear Combination

- $AB$ 可以視為 $B$ 的 rows 的 linear combination

#### ***先跳過***

### 可視為 Summation of Matrices
假設
- $a_i$ 是 columns
- $b_i^T$ 是 rows

則矩陣乘積可以視為各個矩陣的加總
- $AB=\sum_i a_ib_i^T$
- 這些矩陣 $a_ib_i^T$ 的 **rank 都是 1**

#### Block Multiplication
照上圖來看，
- $A$ 可以看作只有一個 row，但有 $n$ 個 element $a_i$
- $B$ 可以看作只有一個 column，但有 $n$ 個 element $b_i^T$
- $A$、$B$ 相乘，就照本來矩陣相乘的做法，因此就得到了上面那個公式

#### Augmentation and Partition

上面只是 partition 的 special case，其實可以有各種切法，把切好的每一小塊當成一個 element，再做矩陣相乘(注意切割的時候 size 要對應能夠相乘)。如下圖：
- 

## Properties
- $AB\neq BA$
- 要讓 $AB$ 和 $BA$ 都有定義，他們**不一定**要是方陣


- $(AC)^T=C^TA^T$

## Special Matrix

## Practical Issue - 計算量
- $A\in\mathbb R^{m\times n}$
- $B\in\mathbb R^{n\times p}$

計算 $AB$ 所需計算量 $m\times n\times p$
- 計算 $ACP$ 相乘，優先順序不同，計算量就不同
- $(AC)P$ 和 $A(CP)$ 計算量不同

# [Lecture 15: Inverse of Matrix](https://www.youtube.com/watch?v=fOK-bLERPUM&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=15)

- **singular** = non-invertible
- **non-singular** = invertible

## 為何 不是方陣就一定不是 invertible

- ex: 對於所有 vector $v$ 要從3維降到2維，再還原回 3 維，不可能

## 為何 Inverse 一定是 Unique 的

假設 $A$ 有兩個 inverse $B, C$，即 $AB=BA=AC=CA=I$，則

$B=BI=B(AC)=(BA)C=IC=C$

## Inverse of Matrix Product
若 $A,B$ 都是 invertible，則 $AB$ 也 invertible，且 $(AB)^{-1}=B^{-1}A^{-1}$

另外 $(A_1A_2...A_k)^{-1}=A_k^{-1}A_{k-1}^{-1}...A_1^{-1}$

## Inverse of Matrix Transpose
- $(A^T)^{-1}=(A^{-1})^T$

### *Proof*
$A^{-1}A=I\implies (A^{-1}A)^T=I\implies A^T(A^{-1})^T=I$
$AA^{-1}=I\implies (AA^{-1})^T=I\implies (A^{-1})^TA^T=I$

得證

## Solving Linear Equations

利用 $x=A^{-1}b$ 可以直接解 $Ax=b$，但是很耗費計算資源

## Input-Output Model

- 

- 

- 

- 

Given
- cost matrix $C$
- demand vector $d$

想要多生產一單位的 element $i$，就需要多消耗 $(I-C)^{-1}$ 的第 $i$ 個 column 資源量

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

## Summary (WAAT?)

- 只要其中一個陳述成立就是 invertible

## Review: One-to-one

## Review: Onto

## Invertible implies One-to-one & Onto

## One-to-one and Onto

- **Square 前提下， One-to-one *iff* Onto**

## 以下略

# [Lecture 17: How to find the Inverse of a Matrix](https://www.youtube.com/watch?v=vV2ff0xFPbw&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=17)

## Elementary Matrix & Elementary Row Operation

- 希望對 matrix 做什麼樣的 elementary row operation，就直接**對 identity matrix 做相同的操作**，就得到了該 elementary matrix
- ex: 

### Inverse of Elementary Matrix

### RREF v.s. Elementary Matrix

- 把矩陣 $A$ **做 RREF 這件事情，可以看作是 $A$ 乘上一連串的 Elementary Matrix** $E_i$
- $E_k...E_2E_1A=R$，令 $P=E_k...E_2E_1$，則 $PA=R$
- 且 $P$ 必定是 invertible，$P^{-1}=E_1^{-1}E_2^{-1}...E_k^{-1}$

### 若某矩陣 Invertible 則代表該矩陣為 Elementary Matrices 的乘積

## Inverse of General Matrices

### Algorithm for Matrix Inversion



### 找 $A^{-1}C$ 也可以用類似的 approach
- 把 $[A\,\,C]$ 作 RREF 變成 $[I\,\,C']$
- $C'$ 就是 $A^{-1}C$