# 線性代數 Linear Algebra (U1014) - Homework 1
## Elimination Matrix, Back-substitution, and LU Decomposition
###### tags: `Linear Algebra (U1014, Spring, 2020)`
通訊系 江振宇 副教授
Assigned: 2020/3/31
Due: 2020/4/9

> 20200429: 訂一次修訂
>
---

### 學習目標
1. 熟悉row operation
2. 了解elimination matrix的意義
3. 練習back-substitution的方法
4. 了解matrix以及對應inverse matrix的關係
5. 了解第一個常用的解inverse matrix以及解linear equation的方法 -- LU decomposition
~~6. 練習使用Markdown撰寫數學式~~ (left for next HW)
~~7. 學習使用python工具計算~~ (left for next HW)

---

### 作業繳交內容
1. 將以下Steps 1-11手寫計算過程掃描成一個pdf檔上傳數位學苑，檔名為 "U1014-HW1-xxxxxxxx.pdf"，其中xxxxxxxx為同學的學號。
~~2. 將重要手寫數學式過程以Markdown網頁寫下，繳交網頁link~~(left for next HW)

---

### 寫完這份作業你將會：
1. 知道如何使用back-substitution以及LU decompostion解linear equation
~~2. 會使用Markdown language編輯工整的數學式~~
~~3. 使用簡單的python~~

---

### 請依以下步驟解$(1)$-$(4)$的四元一次聯立方程式(system of linear equations in four unknowns)
$a+2b+3c+4d = 2 \tag1$
$d+2a+3b+4c = 3 \tag2$
$c+2d+3a+4b = 4 \tag3$
$b+2c+3d+4a = 5 \tag4$

---

### Step 1: Construct Matrix Form
將以上問題寫成矩陣形式：

**\begin{gather*}Ax=y\tag5\end{gather*}**
其中
$$
A=\left[
\begin{matrix}
? & ? & ? & ?\\
? & ? & ? & ?\\
? & ? & ? & ?\\
? & ? & ? & ?
\end{matrix}
\right]\tag6
$$
$$
x=\left[
\begin{matrix}
a\\
b\\
c\\
d
\end{matrix}
\right]\tag7
$$
$$
y=\left[
\begin{matrix}
?\\
?\\
?\\
?
\end{matrix}
\right]\tag8
$$

---

### Step 2: Multiply a Elimination Matrix $E_1$ for Eliminating Coefficients of $a$ in $(2)$-$(4)$
找到三個Elimination Matrices $E_{21}$、$E_{31}$、$E_{41}$使得:

$$
E_{21}A=\left[
\begin{matrix}
1 & 0 & 0 & 0\\
l_{21} & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{matrix}
\right]A=\left[
\begin{matrix}
? & ? & ? & ?\\
0 & ? & ? & ?\\
? & ? & ? & ?\\
? & ? & ? & ?
\end{matrix}
\right]\tag9
$$

$$
E_{31}A=\left[
\begin{matrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
l_{31} & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{matrix}
\right]A=\left[
\begin{matrix}
? & ? & ? & ?\\
? & ? & ? & ?\\
0 & ? & ? & ?\\
? & ? & ? & ?
\end{matrix}
\right]\tag{10}
$$

$$
E_{41}A=\left[
\begin{matrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
l_{41} & 0 & 0 & 1
\end{matrix}
\right]A=\left[
\begin{matrix}
? & ? & ? & ?\\
? & ? & ? & ?\\
? & ? & ? & ?\\
0 & ? & ? & ?
\end{matrix}
\right]\tag{11}
$$

注意！其實$E_{21}$、$E_{31}$、$E_{41}$分別把$(2)$、$(3)$、$(4)$的linear equations的pivot以$(1)$消去。請把$E_{21}$、$E_{31}$、$E_{41}$相乘，以得到$E_1$，說明$E_1$和$E_{21}$、$E_{31}$、以及$E_{41}$的關係：
$$
E_{1}=E_{21}E_{31}E_{41}=\left[
\begin{matrix}
1 & 0 & 0 & 0\\
l_{21} & 1 & 0 & 0\\
l_{31} & 0 & 1 & 0\\
l_{41} & 0 & 0 & 1
\end{matrix}
\right]\tag{12}
$$

$$
E_{1}Ax=\left[
\begin{matrix}
1 & 0 & 0 & 0\\
l_{21} & 1 & 0 & 0\\
l_{31} & 0 & 1 & 0\\
l_{41} & 0 & 0 & 1
\end{matrix}
\right]\left[
\begin{matrix}
A_{11} & A_{12} & A_{13} & A_{14}\\
A_{21} & A_{22} & A_{23} & A_{24}\\
A_{31} & A_{32} & A_{33} & A_{34}\\
A_{41} & A_{42} & A_{43} & A_{44}
\end{matrix}
\right]\left[
\begin{matrix}
a\\
b\\
c\\
d
\end{matrix}
\right]\\
=B_1
\left[
\begin{matrix}
a\\
b\\
c\\
d
\end{matrix}
\right]
\\=E_{1}y＝y_1\tag{13}
$$

求得其中的$B_1$為以下的形式，代表$(2)$-$(4)$的變數$a$的係數皆被消除：

$$
B_1=\left[
\begin{matrix}
? & ? & ? & ?\\
0 & ? & ? & ?\\
0 & ? & ? & ?\\
0 & ? & ? & ?
\end{matrix}
\right]\tag{14}
$$

由$(13)$可以知道，因為$E_{1}$對於$(5)$的左手和右手皆相乘，便可以得到新的linear equations:

$$B_1x＝y_1\tag{15}$$

---

### Step 3: Multiply a Elimination Matrix $E_2$ for Eliminating Coefficients of $b$ in $(3)$-$(4)$

找到一個Elimination Matrix $E_2$使得:

$$E_2B_1x＝E_2y_1\tag{16}$$

其中$$B_2=E_2B_1=\left[
\begin{matrix}
? & ? & ? & ?\\
0 & ? & ? & ?\\
0 & 0 & ? & ?\\
0 & 0 & ? & ?
\end{matrix}
\right]\tag{17}$$

所以我們可以將$(16)$整理成：

$$B_2x＝y_2\tag{18}$$

其中
$$y_2=E_2y_1\tag{19}$$

---

### Step 4: Multiply a Elimination Matrix $E_3$ for Eliminating Coefficients of $c$ in $(4)$

找到一個Elimination Matrix $E_3$使得:

$$E_3B_2x＝E_3y_2\tag{20}$$

其中

$$B_3=E_3B_2=\left[
\begin{matrix}
? & ? & ? & ?\\
0 & ? & ? & ?\\
0 & 0 & ? & ?\\
0 & 0 & 0 & ?
\end{matrix}
\right]\tag{21}$$

所以我們可以將$(20)$整理成：

$$B_3x＝y_3\tag{22}$$

其中
$$y_3=E_3y_2\tag{23}$$

---

### Step 5: Back-substitute to find $x=(a,b,c,d)$

$$B_3x=\left[
\begin{matrix}
B_3(1,1) & B_3(1,2) & B_3(1,3) & B_3(1,4)\\
0 & B_3(2,1) & B_3(2,2) & B_3(2,3)\\
0 & 0 & B_3(3,3) & B_3(3,4)\\
0 & 0 & 0 & B_3(4,4)
\end{matrix}
\right]\left[
\begin{matrix}
a\\
b\\
c\\
d
\end{matrix}
\right]=\left[
\begin{matrix}
y_3(1,1)\\
y_3(2,1)\\
y_3(3,1)\\
y_3(4,1)
\end{matrix}
\right]\tag{24}$$

由$(24)$可知：

$d=y_3(4,1)/B_3(4,4)\tag{25}$

而$c$、$b$、以及$a$可相繼使用$(24)$的其他rows的linear equations以back-substitution得到！

---

### Step 6: Rearrange Matrix

將Steps 1-5所使用的elimination matrices連續對$(5)$的左右手邊都進行處理，也就是：

**\begin{gather*}E_3E_2E_1Ax=E_3E_2E_1y\tag{26}\end{gather*}**

其中

**\begin{gather*}B_3=E_3E_2E_1A\tag{27}\end{gather*}**

為一個upper matrix。重寫$(26)$：

**\begin{gather*}B_3x=E_3E_2E_1y\tag{28}\end{gather*}**

---

### Step 7: Find Upper Matrices $U_1$ for $B_3$

找到一個Matrix $U_1$使得：

**\begin{gather*}U_1B_3=\left[
\begin{matrix}
? & ? & ? & 0\\
0 & ? & ? & 0\\
0 & 0 & ? & 0\\
0 & 0 & 0 & ?
\end{matrix}
\right]\tag{29}\end{gather*}**

此$U_1$必是一個如以下的upper matrix:

**\begin{gather*}U_1=\left[
\begin{matrix}
1 & 0 & 0 & u_{14}\\
0 & 1 & 0 & u_{24}\\
0 & 0 & 1 & u_{34}\\
0 & 0 & 0 & 1
\end{matrix}
\right]\tag{30}\end{gather*}**

可以讓以下的linear equation的左手邊的$U_1B_3$有更多的0:

**\begin{gather*}U_1B_3x=U_1E_3E_2E_1y\tag{31}\end{gather*}**

代表$(31)$比$(28)$更好解變數。

---

### Step 8: Find Upper Matrices $U_2$ for $U_1B_3$

我們可以繼續找一個Matrix $U_2$使得：

**\begin{gather*}U_2U_1B_3=\left[
\begin{matrix}
? & ? & 0 & 0\\
0 & ? & 0 & 0\\
0 & 0 & ? & 0\\
0 & 0 & 0 & ?
\end{matrix}
\right]\tag{32}\end{gather*}**

可以讓以下的linear equation的左手邊的$U_2U_1B_3$有更多的0:

**\begin{gather*}U_2U_1B_3x=U_2U_1E_3E_2E_1y\tag{33}\end{gather*}**

代表$(33)$比$(31)$更好解變數。

此$U_2$必是一個如以下的upper matrix:

**\begin{gather*}U_2=\left[
\begin{matrix}
1 & 0 & u_{13} & 0\\
0 & 1 & u_{23} & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{matrix}
\right]\tag{34}\end{gather*}**

---

### Step 9: Find Upper Matrices $U_3$ for $U_2U_1B_3$

我們可以繼續找一個Matrix $U_3$使得：

**\begin{gather*}U_3U_2U_1B_3=\left[
\begin{matrix}
? & 0 & 0 & 0\\
0 & ? & 0 & 0\\
0 & 0 & ? & 0\\
0 & 0 & 0 & ?
\end{matrix}
\right]\tag{35}\end{gather*}**

可以讓以下的linear equation的左手邊的$U_3U_2U_1B_3$有更多的0:

**\begin{gather*}U_3U_2U_1B_3x=U_3U_2U_1E_3E_2E_1y\tag{36}\end{gather*}**

代表$(36)$比$(33)$更好解變數。

此$U_3$必是一個如以下的upper matrix:

**\begin{gather*}U_3=\left[
\begin{matrix}
1 & u_{12} & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{matrix}
\right]\tag{37}\end{gather*}**

注意$(36)$的 $U_3U_2U_1B_3$為一個diagonal的matrix，只剩對角線的element有值，其他皆為0，因此我們可以令：

**\begin{gather*}D=U_3U_2U_1B_3=\left[
\begin{matrix}
D(1,1) & 0 & 0 & 0\\
0 & D(2,2) & 0 & 0\\
0 & 0 & D(3,3) & 0\\
0 & 0 & 0 & D(4,4)
\end{matrix}
\right]\tag{38}\end{gather*}**

重新整理 $(36)$ 我們得：

**\begin{gather*}Dx=U_3U_2U_1E_3E_2E_1y\tag{39}\end{gather*}**

如此我們也可以得到解：
**\begin{gather*}x=D^{-1}U_3U_2U_1E_3E_2E_1y\tag{40}\end{gather*}**

其中$D^{-1}$為$D$的inverse matrix:

**\begin{gather*}D^{-1}=\left[
\begin{matrix}
1/D(1,1) & 0 & 0 & 0\\
0 & 1/D(2,2) & 0 & 0\\
0 & 0 & 1/D(3,3) & 0\\
0 & 0 & 0 & 1/D(4,4)
\end{matrix}
\right]\tag{41}\end{gather*}**

---

### Step 10: Find Properties of Matrices $E_i$ and $U_i$ for $i=1,2,3$

請找$E_i$ and $U_i$的inverse matrices，也就是$E_i^{-1}$ and $U_i^{-1}$，並觀察和說明$E_i$ and $U_i$和$E_i^{-1}$ and $U_i^{-1}$之間的element關係，你應該會發現到一個對稱的關係，此對稱關係可以呼應一個square matrix和它的inverse matrix的關係！

---

### Step 11: Represent $A$ as a Product of a Lower Matrix, a Diagonal Matrix, and an Upper Matrix

請利用$(40)$以及Step 10所得到的特性，將$(5)$改寫成：

**\begin{gather*}Ax=LUx=y\tag{42}\end{gather*}**

也就是
**\begin{gather*}A=LU\tag{43}\end{gather*}**

其中

**\begin{gather*}L＝E_1^{-1}E_2^{-1}E_3^{-1} \tag{44}\end{gather*}**

**\begin{gather*}U＝U_1^{-1}U_2^{-1}U_3^{-1}D \tag{45}\end{gather*}**

將以上$L$以及$U$矩陣求出。$(43)$即為著名的LU decomposition，也就是將$A$拆解的方法，方便用於解linear equations以及做inverse matrix。