线性代数/增广矩阵的高斯消去法

接下来的内容要有系统性的求出一个一般的 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]$ 都是阶梯形矩阵。