# [線性代數] 線性方程組 (System of Linear Equations)

在國中的時候學過的二元一次聯立方程式，其實就是一種線性方程組。解二元一次聯立方程式對我們來說跟吃飯一樣簡單，那下面這個三元一次聯立方程式樣怎麼解呢？
$$
\left\{
\begin{array}{l}
2x_1 + 2x_2 + 2x_3 = 4 \\
-2x_1 + 5x_2 + 2x_3 = 1 \\
8x_1 + 2x_2 + 5x_3 = 7 \\
\end{array}
\right.
$$
<!--
## 線性方程式 (Linear Equations)
$$
\left\{
\begin{array}{c}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\
\vdots\\
a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m
\end{array}
\right.
$$ -->
<!-- ## 係數矩陣 (Coefficeint matrix) -->

# 目錄
[TOC]

# 增廣矩陣 (Augmented matrix)

一個線性方程組轉可以換成由等號左側的係數組成的**係數矩陣 (Coefficeint matrix)** 和右側的常數組成的**可變向量 (Variable vector)**，兩個合在一起就變成**增廣矩陣 (Augmented matrix)**
$$
\overbrace{
\left[
\begin{array}{c:c}
\underbrace{
\begin{matrix}
2 & 2 & 2 \\
-2 & 5 & 2 \\
8 & 2 & 5 \\
\end{matrix}}_\text{Coefficeint matrix}&
\underbrace{
\begin{matrix}
4 \\
1 \\
7 \\
\end{matrix}}_\text{Variable vector}
\end{array}
\right]}^\text{Augmented matrix}
$$
中間那條虛線通常可以省略不寫
$$
\begin{bmatrix}
2 & 2 & 2 & 4 \\
-2 & 5 & 2 & 1 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}
$$

# 等價 (Equivalent)
比較兩個線性方程組 **是否擁有相同的解** ，若陣列 $A$ 等價於 $B$，那麼 $A$ 和 $B$ 必定存在某種定義明確的關係，而且經由某種運算程序可以將 $A$ 變換為 $B$，也可以將 $B$ 變換回 $A$。

# 基本列運算 (Elementary row opreation)
透過等價的性質，我們可以用下面三個基本列運算來化簡線性方程組，進而得到方程組的解。
## Interchange
把矩陣中的其中一列和另一列**互換**。將第一行和第二行互換後兩矩陣仍等價。
$$
\begin{bmatrix}
2 & 2 & 2 & 4 \\
-2 & 5 & 2 & 1 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}=
\begin{bmatrix}
-2 & 5 & 2 & 1 \\
2 & 2 & 2 & 4 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}
$$

## Scaling
把矩陣中的其中一列**乘上一個非零的常數**。將第一行乘上 $\frac{1}{2}$ 後兩矩陣仍等價。
$$
\begin{bmatrix}
2 & 2 & 2 & 4 \\
-2 & 5 & 2 & 1 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}=
\begin{bmatrix}
1 & 1 & 1 & 2 \\
-2 & 5 & 2 & 1 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}
$$

## Row addotion
把矩陣中的其中一列乘上一個非零的常數後**加到另一列**。將第二行乘上 $4$ 後加到第三行後兩矩陣仍等價。
$$
\begin{bmatrix}
2 & 2 & 2 & 4 \\
-2 & 5 & 2 & 1 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}=
\begin{bmatrix}
2 & 2 & 2 & 4 \\
-2 & 5 & 2 & 1 \\
0 & 22 & 13 & 11 \\
\end{bmatrix}
$$

# 階梯型矩陣 & 簡化列階梯形矩陣
## 階梯型矩陣 (row echelon form)
如果滿足以下三個條件，則稱矩陣為階梯型矩陣：
* 每個 zero row 都位於最下方。
* leading entry 越在左方的 row 必須在陣列的越上方。
* leading entry 的下方必須是 0。

$$
\begin{bmatrix}
1 & * & * & * \\
0 & 1 & * & * \\
0 & 0 & 1 & * \\
\end{bmatrix}\text{$or$}
\begin{bmatrix}
1 & * & * & * \\
0 & 1 & * & * \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}\text{$or$}
\begin{bmatrix}
0 & 1 & * & * & * & * & *\\
0 & 0 & 1 & * & * & * & *\\
0 & 0 & 0 & 0 & 1 & * & *\\
0 & 0 & 0 & 0 & 0 & 1 & *\\
0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix}
$$

## 簡化列階梯形矩陣 (reduced row echelon form)
如果滿足條件，則稱矩陣為簡化的行梯形形式
* 矩陣為階梯型形式。
* 每個 row 的 leading entry 必須是 1。
* leading entry 的上下必須是 0。

$$
\begin{bmatrix}
1 & 0 & 0 & * \\
0 & 1 & 0 & * \\
0 & 0 & 1 & * \\
\end{bmatrix}\text{$or$}
\begin{bmatrix}
1 & 0 & 0 & * \\
0 & 1 & 0 & * \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}\text{$or$}
\begin{bmatrix}
0 & 1 & 0 & * & 0 & 0 & *\\
0 & 0 & 1 & * & 0 & 0 & *\\
0 & 0 & 0 & 0 & 1 & 0 & *\\
0 & 0 & 0 & 0 & 0 & 1 & *\\
0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix}
$$
<!--
| 階梯型矩陣 | 簡化列階梯形矩陣 |
|:----------:|:----------------:|
| Text | Text |
| Text | Text |
| Text | Text |
-->

:::info
:nerd_face: **小幫手**：上面的條件是用我自己的話解釋的，如果看不懂我寫什麼，請看這裡：
:::spoiler 文言文版
### 階梯型矩陣
* 每個非零行都位於每個零行上方。
* 非零行的前導條目位於該列右側的一列中，其中包含任何先前行的前導條目。
* 如果一列包含某行的開頭條目，則該開頭條目之下的該列的所有條目均為0。

### 簡化列階梯形矩陣
* 矩陣為行梯形形式。
* 如果某列包含某個行的開頭條目，則該列的所有其他條目均為0。
* 每個非零行的開頭條目為1。
:::

# 高斯消去法 & 高斯-約當消去法
其實高斯消去法就是利用**基本列運算**將增廣矩陣化簡成**階梯型矩陣**，高斯-約當消去法則是化簡成**簡化列階梯形矩陣**。
## 高斯消去法
#### 1. 找出非零列
#### 2. 使 povit pos 為非零 (or 1)
#### 3. 使 povit pos 下方為零
#### 4. 忽略完成 1-3 步的 row 直到所有 row 都被忽略

## 高斯-約當消去法
延續剛才高斯消去法的步驟，繼續完成矩陣的運算：
#### 5. 讓 leading entry 變成 1
#### 6. 忽略完成第5步的 row 直到所有 row 都被忽略

<!--
### 運算流程圖

start=>start: 增廣矩陣
end=>end: 簡化列階梯形矩陣
st1=>operation: 找出非零列
st2=>operation: povit pos 為非零 (or 1)
st3=>operation: povit pos 下方為零
cond4=>condition: 忽略完成1-3步的row 
				  直到所有row都被忽略
st5=>operation: 讓 leading entry 變成 1
cond6=>condition: 忽略完成第5步的row 
				  直到所有row都被忽略

start->st1->st2->st3->cond4
cond4(yes)->st5
cond4(no,right)->st1
st5->cond6
cond6(yes)->end
cond6(no)->st5

## 範例
就拿上面的方程組作範例，
$$
\begin{bmatrix}
2 & 2 & 2 & 4 \\
-2 & 5 & 2 & 1 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}
$$

* 第一個 row $\times\frac{1}{2}$

$$
\begin{bmatrix}
1 & 1 & 1 & 2 \\
-2 & 5 & 2 & 1 \\
8 & 2 & 5 & 7 \\
\end{bmatrix}
$$

使 povit pos 下方為零
* 第1個 row $\times 2$ 加到第2個 row
* 第1個 row $\times -8$ 加到第3個 row

$$
\begin{bmatrix}
1 & 1 & 1 & 2 \\
0 & 7 & 4 & 5 \\
0 & -6 & -3 & -9 \\
\end{bmatrix}
$$

因為第一個 row 的 povit pos 下方皆為零，所以可以忽略該 row。接著重複 2、3 步驟。

* 第3個 row 加到第2個 row

$$
\begin{bmatrix}
1 & 1 & 1 & 2 \\
0 & 1 & 1 & -4 \\
0 & -6 & -3 & -9 \\
\end{bmatrix}
$$

* 第2個 row $\times 6$ 加到第3個 row

$$
\begin{bmatrix}
1 & 1 & 1 & 2 \\
0 & 1 & 1 & -4 \\
0 & 0 & 3 & -33 \\
\end{bmatrix}
$$

因為第二個 row 的 povit pos 下方皆為零，所以可以忽略該 row。
再來將第三個 row 處理一下就完成高斯消去法了。
* 第3個 row $\times \frac{1}{3}$

$$
\begin{bmatrix}
1 & 1 & 1 & 2 \\
0 & 1 & 1 & -4 \\
0 & 0 & 1 & -11 \\
\end{bmatrix}
$$

得到了一個階梯型矩陣！

**接著要做高斯-約當消去法化簡成簡化列階梯形矩陣：**
* 第3個 row $\times -1$ 加到第2個 row

$$
\begin{bmatrix}
1 & 1 & 1 & 2 \\
0 & 1 & 0 & 7 \\
0 & 0 & 1 & -11 \\
\end{bmatrix}
$$

* 第3個 row $\times -1$ 加到第1個 row

$$
\begin{bmatrix}
1 & 1 & 0 & 13 \\
0 & 1 & 0 & 7 \\
0 & 0 & 1 & -11 \\
\end{bmatrix}
$$

* 第2個 row $\times -1$ 加到第1個 row

$$
\begin{bmatrix}
1 & 0 & 0 & 6 \\
0 & 1 & 0 & 7 \\
0 & 0 & 1 & -11 \\
\end{bmatrix}
$$

得到了一個簡化列階梯形矩陣！

###### tags: `線性代數` `筆記`