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

接下來的內容要有系統性的求出一個一般的 n 元一次聯立方程式的所有解，而這個聯立方程式不再限於未知數與限制式個數相同。

首先，必須要認知道的一項事實是，就單純要一眼判斷出一個聯立方程式是否有解是不可能的，因此退而求其次，要找一套固定的標準的流程，看最終結果來判斷。

換句話說，要找到一個演算法可以交給電腦來執行，而不是期待電腦能像人類可以見機行事，判斷當下哪種做法比較「好算」。

基本列運算

對於一個聯立方程式，或其所對應的增廣矩陣，其求解過程總是將方程式的各式，或增廣矩陣的各列，進行一些類似加加減減的運算。那麼，要研究出到底有哪些動作是可以被執行的，下面將舉盡所有的基本列運算：兩列互換、一列乘上非零常數、一列加上另一列的常數倍。

1. 兩列互換，例如

$\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]$

將第一列和第三列互換，而它所對應的聯立方程式是 $\left\{{\begin{aligned}3x_{1}-2x_{2}-x_{3}&=7\\-2x_{1}+3x_{4}&=5\\x_{1}+4x_{3}&=-2\end{aligned}}\right.\Longrightarrow \left\{{\begin{aligned}x_{1}+4x_{3}&=-2\\-2x_{1}+3x_{2}&=5\\3x_{1}-2x_{2}-x_{3}&=7\end{aligned}}\right.$。

2. 一列乘上非零常數，例如

$\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]$

是將第二列乘上常數 $-{\frac {1}{3}}$，而它所對應的聯立方程式是

$\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. 一列加上另一列的常數倍，例如

$\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]$

是將第三列加上 -2 倍的第一列，而它所對應的聯立方程式是

$\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.$

在第 2 點中，乘上的常數不可以是 0，否則會把整列歸零，換言之，會使一整條等式直接消失，可能造成最後解出不合的解；但在第 3 點中，一列加上另一列的常數倍，那個常數就可以是 0，因為一列加上另一列的 0 倍，等於是不對任何式子做變動，所以此作用雖然合法，但是沒有意義。

而基本列運算的名稱來源於，其他用於解方程式的複雜變換，都可以由多個基本列運算組合而成，例如多列的順序重排、多列同乘常數、一列加上多列的線性組合……等等。

求解過程

由於接着要處理的是給電腦來執行的一般性解法，因此必須照着 $x_{1},x_{2},\dots ,x_{n}$ 的順序依序消除便變數，並且要妥善安排消完變數後的列的上下順序。

第一步驟

首先，假設拿到一個增廣矩陣

$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]$

同時我們在心裏要秉記着它所對應的聯立方程式

$\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.$

第一個步驟要消掉 $x_{1}$，然後分成三種情況分別處理：

• 如果增廣矩陣 $A$ 的第一列各項皆 0，換句話說 $a_{11}=a_{21}=\dots =a_{m1}=0$，那麼這就意味着變數 $x_{1}$ 根本不存在於聯立方程式之中，因此不需要做任何處理，直接前往下一步處理 $x_{2}$。

• 如果 $A$ 的最左上角那一項 $a_{11}$ 不等於 0，那麼將第一行乘以 ${\frac {1}{a_{11}}}$，得到

$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]$

其中對所有 $j=2,3,\dots ,n+1$，有 $a'_{1j}={\frac {a_{1j}}{a_{11}}}$。然後下一步是要將 $a_{21}$、$a_{31}$、…、$a_{m1}$ 消掉，因此，分別將第二行、第三行、…、第 m 行減去 $a_{21}$、$a_{31}$、…、$a_{m1}$ 倍的第一行，得到

$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]$

特別要注意的是，從 $A'$ 到 $A''$ 的過程不是一個基本行運算，而是要將各行分別做，總共要做 $m-1$ 次。

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

第一步驟做完的結果

在此做個統整，順便看看下一步該怎麼操作，如果是第一點的情況

$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]$

接下來就對 $A$ 裏面的

${\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}}$

進行與第一步驟相同的處理，一樣如上分成三種情況討論；如果是第二或第三點的情況，經處理後得到

$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]$

接下來就對 $A''$ 裏面首行首列以外的部分

${\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}}$

進行與第一步驟相同的處理，一樣如上分成三種情況討論。

終止況態

依據前一節的步驟，不斷重複對 $A$ 進行列運算，由於每執行一次前一節的動作，$A$ 待處理的部分的長度或寬度會變小，因此在有限步的操作之內，上述的動作將會終止。而在上一節的操作中可以發現，在 $A$ 最後兩行之間的那一槓其實沒有起什麼作用，因此在就算重複到最後，出現形如

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

的部分，仍然可以繼續操作：將第一個非 0 元素換到最上面，並且將它除成 1，再將剩下的元素減成 0。

那麼接着來看看在終止時的狀態，先直接下結論，此時 $A$ 將形如

$\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]$

其中 $\mathbf {0} _{m}$ 代表連續 m 個 0，而 △ 則代表該項可以填入任意的數。

接下來解釋 $A$ 的終止狀態會形如上式的原因：最左邊的連續 $m_{1}$列的 0 代表前 $m_{1}$次操作都是第一點的狀況，也就首列全為 0；而第一行第 $m_{1}+1$ 列的 1 代表接着出現的狀況是第二或三點的狀況，因此操作完會使第 $m_{1}+1$ 列上除了第一行的 1 以外全部都是 0。再之後便沒有第一行的事了，因此在 1 之後全都是 △，可能填入任何的數。然後第二列的 $\mathbf {0} _{m_{2}}$又代表着連續 $m_{2}$次操作都是第一點的狀況，而接下去的 1 則代表接着出現的狀況是第二或三點的狀況，依此類推。

例子

實際上，在前述中的 $\mathbf {0} _{m_{1}}$、$\mathbf {0} _{m_{2}}$、$\mathbf {0} _{m_{3}}$…中，有可能下標中出現的是 0，也就連續出現零個 0，直接在 1 的右下角又出現一個 1，如果 $m_{1}=m_{2}=m_{3}=\dots =0$，那麼 $A$ 終止狀態是

$\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]$

在此這情況下，最下面好幾列的全零列對應到的方程式是 0 = 0，毫無任何意義。忽略那些全 0 列之後，最後一列有意義的列是 $\left[{\begin{array}{ccccc|c}0&0&0&\dots &0&1\end{array}}\right]$，對應到的方程式是 0 = 1，代表增廣矩陣 $A$ 無解。

階梯形矩陣

在很多時候，矩陣中的 0 常會被省略不寫，而如果這樣的話，增廣矩陣經過列運算後的最終狀態長得像是個階梯，這就是階梯型矩陣的名字由來。

定義

一個矩陣 $A$ 被稱為是階梯形矩陣如果 $A$ 滿足以下條件

• 所有 $A$ 的非零列（矩陣的列至少有一個非 0 元素）在所有全零列的上面。即全零列都在矩陣的底部。

• 非零列的首項非 0 系數，即最左邊的首個非零元素，必定是 1，而且其位置必需嚴格地比上面列的首項非 0 系數更靠右。

可以很容易的看出，一個增廣矩陣經過列運算後的最終狀態必然是一個階梯形矩陣。

例子

$\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]$、$\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]$ 都是階梯形矩陣。