查看“︁線性代數/增廣矩陣的高斯消去法”︁的源代码

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

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

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

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

: 1. 兩列互換，例如 
::<math>\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 ]</math> 
:將第一列和第三列互換，而它所對應的聯立方程式是 <math>\left \{
\begin{aligned}
3 x_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\\
3 x_1 -2x_2 -x_3&=7
\end{aligned}
\right .</math>。

: 2. 一列乘上非零常數，例如
::<math>\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 ]</math>
:是將第二列乘上常數 <math> -\frac{1}{3}</math>，而它所對應的聯立方程式是
::<math>\left \{
\begin{aligned}
2 x_1 +x_3 &= 0\\
-3 x_1 + 6x_2 + 3x_3 &= -3
\end{aligned}
\right .
\Longrightarrow
\left \{
\begin{aligned}
2 x_1 + x_3 &= 0\\
 x_1 - 2x_2 - x_3 &= 1
\end{aligned}
\right .</math>

: 3. 一列加上另一列的常數倍，例如
::<math>\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 ]</math>
:是將第三列加上 -2 倍的第一列，而它所對應的聯立方程式是
::<math>\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\\
3 x_2 &=2
\end{aligned}
\right .</math>

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

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

== 求解過程 ==
由於接著要處理的是給電腦來執行的一般性解法，因此必須照著 <math>x_1,x_2,\dots,x_n</math> 的順序依序消除便變數，並且要妥善安排消完變數後的列的上下順序。

=== 第一步驟 ===
首先，假設拿到一個增廣矩陣
:<math>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]</math>
同時我們在心裡要秉記著它所對應的聯立方程式
:<math>\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.</math>
第一個步驟要消掉 <math>x_1</math>，然後分成三種情況分別處理：

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

* 如果 <math>A</math> 的最左上角那一項 <math>a_{11}</math> 不等於 0，那麼將第一行乘以 <math> \frac{1}{a_{11}} </math>，得到
:: <math> 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]</math>
: 其中對所有 <math>j=2,3,\dots , n+1</math>，有 <math>a'_{1j}=\frac{a_{1j}}{a_{11}}</math>。然後下一步是要將 <math>a_{21}</math>、<math>a_{31}</math>、…、<math>a_{m1}</math> 消掉，因此，分別將第二行、第三行、…、第 m 行減去 <math>a_{21}</math>、<math>a_{31}</math>、…、<math>a_{m1}</math> 倍的第一行，得到
: <math> 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]</math>

: 特別要注意的是，從 <math>A'</math> 到 <math>A''</math> 的過程不是一個基本行運算，而是要將各行分別做，總共要做 <math>m-1</math> 次。
* 如果 <math>A</math> 的最左上角那一項 <math>a_{11}</math> 等於 0，但 <math>a_{21}</math>、<math>a_{31}</math>、…、<math>a_{m1}</math> 不全為 0，那麼設 k 是最小的正整數使得 <math>a_{k1}\ne 0</math>，接著將 <math>A</math> 的第一行和第 k 行互換，就回到上面第二點的情況。

=== 第一步驟做完的結果 ===
在此做個統整，順便看看下一步該怎麼操作，如果是第一點的情況
:<math>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]</math>
接下來就對 <math>A</math> 裡面的
:<math>\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}</math> 
進行與第一步驟相同的處理，一樣如上分成三種情況討論；如果是第二或第三點的情況，經處理後得到
:<math> 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]</math>

接下來就對 <math>A''</math> 裡面首行首列以外的部分
:<math> \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}</math>
進行與第一步驟相同的處理，一樣如上分成三種情況討論。

== 終止況態 ==

依據前一節的步驟，不斷重複對 <math>A</math> 進行列運算，由於每執行一次前一節的動作，<math>A</math> 待處理的部分的長度或寬度會變小，因此在有限步的操作之內，上述的動作將會終止。而在上一節的操作中可以發現，在 <math>A</math> 最後兩行之間的那一槓其實沒有起什麼作用，因此在就算重複到最後，出現形如
:<math>
\begin{array}{c|c}
&\bar a_{i \, n+1}\\
&\bar a_{i+1 \, n+1}\\
&\vdots\\
&\bar a_{m \, n+1}
\end{array}</math>
的部分，仍然可以繼續操作：將第一個非 0 元素換到最上面，並且將它除成 1，再將剩下的元素減成 0。

那麼接著來看看在終止時的狀態，先直接下結論，此時 <math>A</math> 將形如
:<math>\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]</math>
其中 <math>\mathbf 0_m</math> 代表連續 m 個 0，而 △ 則代表該項可以填入任意的數。

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

=== 例子 ===
實際上，在前述中的 <math>\mathbf 0_{m_1}</math>、<math>\mathbf 0_{m_2}</math>、<math>\mathbf 0_{m_3}</math>…中，有可能下標中出現的是 0，也就連續出現零個 0，直接在 1 的右下角又出現一個 1，如果 <math>m_1=m_2=m_3=\dots =0</math>，那麼 <math>A</math> 終止狀態是
:<math>\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]</math>

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

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

{{TextBox|1=
;定義{{anchor|階梯形矩陣}}:
一個矩陣 <math>A</math> 被稱為是'''階梯形矩陣'''如果 <math>A</math> 滿足以下條件

* 所有 <math>A</math> 的非零列（矩陣的列至少有一個非 0 元素）在所有全零列的上面。即全零列都在矩陣的底部。

* 非零列的首項非 0 係數，即最左邊的首個非零元素，必定是 1，而且其位置必需嚴格地比上面列的首項非 0 係數更靠右。
}}
可以很容易的看出，一個增廣矩陣經過列運算後的最終狀態必然是一個階梯形矩陣。

=== 例子 ===
<math>\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]</math>、<math>\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]</math> 都是階梯形矩陣。