# 線性代數/增廣矩陣的高斯消去法

## 基本列運算

1. 兩列互換，例如
${\displaystyle \left[{\begin{array}{cccc|c}3&-2&-1&0&7\\-2&0&0&3&5\\1&0&4&0&-2\end{array}}\right]\Longrightarrow \left[{\begin{array}{cccc|c}1&0&4&0&-2\\-2&0&0&3&5\\3&-2&-1&0&7\end{array}}\right]}$

2. 一列乘上非零常數，例如
${\displaystyle \left[{\begin{array}{ccc|c}2&0&1&0\\-3&6&3&-3\\\end{array}}\right]\Longrightarrow \left[{\begin{array}{ccc|c}2&0&1&0\\1&-2&-1&1\\\end{array}}\right]}$

{\displaystyle \left\{{\begin{aligned}2x_{1}+x_{3}&=0\\-3x_{1}+6x_{2}+3x_{3}&=-3\end{aligned}}\right.\Longrightarrow \left\{{\begin{aligned}2x_{1}+x_{3}&=0\\x_{1}-2x_{2}-x_{3}&=1\end{aligned}}\right.}
3. 一列加上另一列的常數倍，例如
${\displaystyle \left[{\begin{array}{cc|c}1&-2&1\\-2&0&1\\2&-1&4\end{array}}\right]\Longrightarrow \left[{\begin{array}{cc|c}1&-2&1\\-2&0&1\\0&3&2\end{array}}\right]}$

{\displaystyle \left\{{\begin{aligned}x_{1}-2x_{2}&=1\\-2x_{1}&=1\\2x_{1}-x_{2}&=4\end{aligned}}\right.\Longrightarrow \left\{{\begin{aligned}x_{1}-2x_{2}&=1\\-2x_{1}&=1\\3x_{2}&=2\end{aligned}}\right.}

## 求解過程

### 第一步驟

${\displaystyle A=\left[{\begin{array}{cccc|c}a_{11}&a_{12}&\dots &a_{1n}&a_{1\,n+1}\\a_{21}&a_{22}&\dots &a_{2n}&a_{2\,n+1}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\dots &a_{mn}&a_{m\,n+1}\\\end{array}}\right]}$

{\displaystyle \left\{{\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}&=a_{1(n+1)}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}&=a_{2(n+1)}\\\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}&=a_{m(n+1)}\end{aligned}}\right.}

• 如果增廣矩陣 ${\displaystyle A}$  的第一列各項皆 0，換句話說 ${\displaystyle a_{11}=a_{21}=\dots =a_{m1}=0}$ ，那麼這就意味著變數 ${\displaystyle x_{1}}$  根本不存在於聯立方程式之中，因此不需要做任何處理，直接前往下一步處理 ${\displaystyle x_{2}}$
• 如果 ${\displaystyle A}$  的最左上角那一項 ${\displaystyle a_{11}}$  不等於 0，那麼將第一行乘以 ${\displaystyle {\frac {1}{a_{11}}}}$ ，得到
${\displaystyle A'=\left[{\begin{array}{cccc|c}1&a'_{12}&\dots &a'_{1n}&a'_{1(n+1)}\\a_{21}&a_{22}&\dots &a_{2n}&a_{2(n+1)}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\dots &a_{mn}&a_{m(n+1)}\\\end{array}}\right]}$

${\displaystyle A''=\left[{\begin{array}{cccc|c}1&a'_{12}&\dots &a'_{1n}&a'_{1(n+1)}\\0&a_{22}-a_{21}a'_{12}&\dots &a_{2n}-a_{21}a'_{1n}&a_{2(n+1)}-a_{21}a'_{1(n+1)}\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&a_{m2}-a_{m1}a'_{12}&\dots &a_{mn}-a_{m1}a'_{1n}&a_{m(n+1)}-a_{21}a'_{m(n+1)}\\\end{array}}\right]}$

• 如果 ${\displaystyle A}$  的最左上角那一項 ${\displaystyle a_{11}}$  等於 0，但 ${\displaystyle a_{21}}$ ${\displaystyle a_{31}}$ 、…、${\displaystyle a_{m1}}$  不全為 0，那麼設 k 是最小的正整數使得 ${\displaystyle a_{k1}\neq 0}$ ，接著將 ${\displaystyle A}$  的第一行和第 k 行互換，就回到上面第二點的情況。

### 第一步驟做完的結果

${\displaystyle A=\left[{\begin{array}{cccc|c}0&a_{12}&\dots &a_{1n}&a_{1\,n+1}\\0&a_{22}&\dots &a_{2n}&a_{2\,n+1}\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&a_{m2}&\dots &a_{mn}&a_{m\,n+1}\\\end{array}}\right]}$

${\displaystyle {\begin{array}{ccc|c}a_{12}&\dots &a_{1n}&a_{1\,n+1}\\a_{22}&\dots &a_{2n}&a_{2\,n+1}\\\vdots &\ddots &\vdots &\vdots \\a_{m2}&\dots &a_{mn}&a_{m\,n+1}\\\end{array}}}$

${\displaystyle A''=\left[{\begin{array}{cccc|c}1&a'_{12}&\dots &a'_{1n}&a'_{1\,n+1}\\0&a_{22}-a_{21}a'_{12}&\dots &a_{2n}-a_{21}a'_{1n}&a_{2\,n+1}-a_{21}a'_{1\,n+1}\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&a_{m2}-a_{m1}a'_{12}&\dots &a_{mn}-a_{m1}a'_{1n}&a_{m\,n+1}-a_{21}a'_{m\,n+1}\\\end{array}}\right]}$

${\displaystyle {\begin{array}{ccc|c}a_{22}-a_{21}a'_{12}&\dots &a_{2n}-a_{21}a'_{1n}&a_{2\,n+1}-a_{21}a'_{1\,n+1}\\\vdots &\ddots &\vdots &\vdots \\a_{m2}-a_{m1}a'_{12}&\dots &a_{mn}-a_{m1}a'_{1n}&a_{m\,n+1}-a_{21}a'_{m\,n+1}\\\end{array}}}$

## 終止況態

${\displaystyle {\begin{array}{c|c}&{\bar {a}}_{i\,n+1}\\&{\bar {a}}_{i+1\,n+1}\\&\vdots \\&{\bar {a}}_{m\,n+1}\end{array}}}$

${\displaystyle \left[{\begin{array}{ccccccccc|c}\mathbf {0} _{m_{1}}&1&\triangle &\dots &\triangle &\dots &\triangle &\dots &\triangle &\triangle \\\mathbf {0} _{m_{1}}&0&\mathbf {0} _{m_{2}}&1&\triangle &\dots &\triangle &\dots &\triangle &\triangle \\\mathbf {0} _{m_{1}}&0&\mathbf {0} _{m_{2}}&0&\mathbf {0} _{m_{3}}&1&\triangle &\dots &\triangle &\triangle \\\vdots &&\vdots &&\vdots &&\ddots &&\vdots &\vdots \\\end{array}}\right]}$

### 例子

${\displaystyle \left[{\begin{array}{ccccc|c}1&\triangle &\triangle &\dots &\triangle &\triangle \\0&1&\triangle &\dots &\triangle &\triangle \\\vdots &\vdots &&\ddots &\vdots &\vdots \\0&0&0&\dots &1&\triangle \\0&0&0&\dots &0&1\\0&&\dots &&0&0\\\vdots &&&&\vdots &\vdots \\0&&\dots &&0&0\end{array}}\right]}$

## 階梯形矩陣

• 所有 ${\displaystyle A}$  的非零列（矩陣的列至少有一個非 0 元素）在所有全零列的上面。即全零列都在矩陣的底部。
• 非零列的首項非 0 係數，即最左邊的首個非零元素，必定是 1，而且其位置必需嚴格地比上面列的首項非 0 係數更靠右。

### 例子

${\displaystyle \left[{\begin{array}{ccccc|c}0&1&0&2&0&-1\\0&0&1&-3&0&0\\0&0&0&0&1&-2\end{array}}\right]}$ ${\displaystyle \left[{\begin{array}{ccc|c}1&0&0&-1\\0&1&-3&2\\0&0&0&1\\0&0&0&0\\0&0&0&0\end{array}}\right]}$  都是階梯形矩陣。