贡献者： addis
1线性方程组（有 $x_1\dots x_n$ 这 $n$ 个未知量，所以也叫 $\boldsymbol{n}$ 元一次方程组）
\begin{equation}
\left\{\begin{aligned}
&a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,n}x_n&=\quad &y_1\\
&a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,n}x_n&=\quad &y_2\\
&\qquad \qquad \dots \qquad \dots \qquad \dots\\
&a_{m,1}x_1 + a_{m,2}x_2 + \dots + a_{m,n}x_n&=\quad &y_m \end{aligned}\right. \\
~\end{equation}
可以写成矩阵和列矢量相乘的形式
\begin{equation}
\boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{y}} ~,
\end{equation}
其中 $ \boldsymbol{\mathbf{A}} $ 是维度 $m \times n$ 的矩阵，称为
系数矩阵。
\begin{equation}
\boldsymbol{\mathbf{A}} =
\begin{pmatrix}
a_{1,1} &a_{1,2} &\cdots &a_{1,n} \\
a_{2,1} &a_{2,2} &\cdots &a_{2,n} \\
\vdots &\vdots &\ddots &\vdots \\
a_{m,1} &a_{m,2} &\cdots &a_{m,n} \\
\end{pmatrix}~,
\end{equation}
$ \boldsymbol{\mathbf{x}} $ 是 $n$ 维列矢量 $(x_1,x_2,\dots,x_m,\dots,x_n) ^{\mathrm{T}} $。
$ \boldsymbol{\mathbf{y}} $ 是 $m$ 维列矢量 $(y_1,y_2,\dots,y_m) ^{\mathrm{T}} $，称为
常数列。$ \boldsymbol{\mathbf{A}} $ 和 $ \boldsymbol{\mathbf{y}} $ 通常看做已知的，而 $ \boldsymbol{\mathbf{x}} $ 看做未知的，即方程组待求的
解。下面我们介绍一种解线性方程组的简单的方法，
高斯消元法（Gauss elimination）。 先来看一个简单的例子。
例 1
我们先回顾一下初中阶段如何解线性方程组，例如
\begin{equation}
\left\{\begin{aligned}
&2x + 3y = 21\\
&5x - 2y = 5
\end{aligned}\right. ~\end{equation}
一种方法是将第一条等式两边除以 2 再移项得到
\begin{equation}
x = - \frac32 y + \frac{21}{2}~.
\end{equation}
再代入第二个条式消去 $x$ 得
\begin{equation}
-\frac{19}{2} y + \frac{105}{2} = 5~.
\end{equation}
解得 $y = 5$，再代入第一条等式得 $x = 3$。
另一种更方便的解法是，将第一条等式（两边）乘以 $-5/2$，加到第二条上消去 $x$ 得
\begin{equation}
-\frac{19}{2} y = -\frac{95}{2}~.
\end{equation}
解得 $y = 5$，再代入第一条等式得 $x = 3$。为什么可以这么做？ 简单来说是因为如果两条等式都成立，将它们两边相加得到的新的等式同样成立。下面我们来详细讲解第二种方法。
为了书写简单，我们可以用所谓的增广矩阵（augmented matrix）来表示矩阵和常数列，即把式 4 记为
\begin{equation}
\left(\begin{array}{cc|c}
2 & 3 & 21 \\
5 & -2 & 5
\end{array}
\right) ~\end{equation}
同样把第一行乘以 $-5/2$，加到第二行上得
\begin{equation}
\left(\begin{array}{cc|c}
2 & 3 & 21 \\
0 & -19/2 & -95/2
\end{array}
\right) ~\end{equation}
如果这个方程有多个未知数，且方程的数量和未知数相同（系数矩阵为方阵），理想情况下我们可以用第一行消去所有 $i > 1$ 行的第一个系数，再用第二行消去所有 $i > 2$ 行的第 2 个系数，以此类推，最后得到一个三角形系数矩阵。三角形系数矩阵的最后一行只有最后一个变量的系数不为零，我们求出这个变量后，再代入倒数第二行（只有两个未知量）求出另一个未知量，最后就可以得到所有未知量的值。这个过程叫做反向迭代（backward substitution）。
注意这只是一种理想的情况，如果在处理第 $i$ 行的时候发现 $a_{i,i} = 0$，则该方法无法进行下去。为此我们需要稍微复杂一些的方法，也就是高斯消元法的一般步骤。
1. 一般步骤
我们将式 1 形式的方程组用增广矩阵表示为
\begin{equation}
\boldsymbol{\mathbf{B}} =( \boldsymbol{\mathbf{A}} , \boldsymbol{\mathbf{y}} )={
\left(\begin{array}{cccc|c}
a_{1,1} &a_{1,2} &\cdots &a_{1,n} &y_1 \\
a_{2,1} &a_{2,2} &\cdots &a_{2,n} &y_2 \\
\vdots &\vdots &\ddots &\vdots &\vdots \\
a_{m,1} &a_{m,2} &\cdots &a_{m,n} &y_m \\
\end{array}
\right) }~
\end{equation}
定义以下三种矩阵（或增广矩阵）变换为初等行变换。初等行变换不改变方程组的解2。
- 对调矩阵中的第 $i$ 行与第 $j$ 行，记作 $ \boldsymbol{\mathbf{r}} _i \leftrightarrow \boldsymbol{\mathbf{r}} _j$
- 将矩阵第 $i$ 行的所有元素乘以一个非零数 $k$，记作 $ \boldsymbol{\mathbf{r}} _i \times k$
- 把矩阵第 $i$ 行的所有元素乘以数 $k$ 后加到第 $j$ 行上，下文简记为 $ \boldsymbol{\mathbf{r}} _j + \boldsymbol{\mathbf{r}} _i \times k$
任何非零矩阵（或增广矩阵）经过有限次初等行变换后总可以使系数矩阵 $ \boldsymbol{\mathbf{A}} $ 转化为梯形矩阵（echelon form）。我们把梯形矩阵定义为满足该条件的矩阵：第 $i$ 行的第一个非零系数3 $a_{i,q(i)}$ 的列标 $q(i)$ 总是大于第 $i-1$ 行的第一个非零元 $a_{i-1, q(i-1)}$ 的列标 $q(i-1)$。与例 1 不同的是，当系数矩阵经过行变换化为梯形矩阵后，最后若干行有可能都为零，最后一个非零行也未必只有一个非零元。
高斯消元法的一般步骤如下：
- 先处理第 $i = 1$ 行，如果 $a_{1,1} = 0$ 但某 $i' > 1$ 的行有 $a_{i', 1} \ne 0$，就先进行行变换4 $ \boldsymbol{\mathbf{r}} _i \leftrightarrow \boldsymbol{\mathbf{r}} _{i'}$。如果第一列全为 0，我们就无视第 1 列，从第 2 列重新开始，以此类推。记此时第 1 行第一个非零元的列标为 $q(1)$。接下来做若干次行变换 $ \boldsymbol{\mathbf{r}} _{i'} + \boldsymbol{\mathbf{r}} _1 \times k$ 使所有第 $i' > 1$ 行的 $a_{i', q(1)}$ 都为 0。
- 依次处理第 $i = 2\dots m-1$ 行5。要处理第 $i$ 行，先令 $q(i) = q(i-1)+1$，如果此时矩阵元 $a_{i, q(i)} = 0$，但某 $i' > i$ 的行有 $a_{i', q(i)} \ne 0$，就先进行行变换 $ \boldsymbol{\mathbf{r}} _i \leftrightarrow \boldsymbol{\mathbf{r}} _{i'}$。若不存在这样的 $i'$，我们就改令 $q(i) = q(i-1) + 2$ 并重新开始该步骤，以此类推。接下来做若干次行变换 $ \boldsymbol{\mathbf{r}} _{i'} + \boldsymbol{\mathbf{r}} _i \times k$ 使所有第 $i' > i$ 行的 $a_{i', q(i)}$ 都为 0。
完成后，系数矩阵就会变为梯形矩阵。
例 2 解线性方程组
\begin{equation}
\left\{\begin{aligned}
&x_1 &+ &x_2 &- &x_3 &+ &x_4&=\quad &3\\
&2x_1 &+ &2x_2 &- &2x_3 &+ &x_4&=\quad &7\\
&x_1 &+ &x_2 & & &+ &2x_4&=\quad &3\\
&2x_1 &+ &2x_2 &- &x_3 &+ &5x_4&=\quad &4 \end{aligned}\right. ~
\end{equation}
解：
将该方程组写成增广矩阵形式
\begin{equation}
\boldsymbol{\mathbf{B}} ={
\left(\begin{array}{cccc|c}
1 &1 &-1 &1 &3 \\
2 &2 &-2 &1 &7 \\
1 &1 &0 &2 &3 \\
2 &2 &-1 &5 &4 \\
\end{array}
\right) }~
\end{equation}
对第一列
\begin{equation}
\begin{aligned}
\boldsymbol{\mathbf{r}} _2 - 2 & \boldsymbol{\mathbf{r}} _1 \\
\boldsymbol{\mathbf{r}} _3 - 1 & \boldsymbol{\mathbf{r}} _1 \\
\boldsymbol{\mathbf{r}} _4 - 2 & \boldsymbol{\mathbf{r}} _1 \\
\end{aligned}
\quad \Longrightarrow \quad
\boldsymbol{\mathbf{B}} ={
\left(\begin{array}{cccc|c}
1 &1 &-1 &1 &3 \\
0 &0 &0 &-1 &1 \\
0 &0 &1 &1 &0 \\
0 &0 &1 &3 &-2 \\
\end{array}
\right) }~
\end{equation}
发现此时，矩阵第二列自第二行以下全为零，所以需要依次向下一列寻找不为零的元素。继续消元
\begin{equation}
\begin{aligned}
& \boldsymbol{\mathbf{r}} _2 \leftrightarrow \boldsymbol{\mathbf{r}} _4 \\
& \boldsymbol{\mathbf{r}} _3 - 1 \boldsymbol{\mathbf{r}} _2 \\
& \boldsymbol{\mathbf{r}} _4 - 0 \boldsymbol{\mathbf{r}} _2 \\
\end{aligned}
\quad \Longrightarrow \quad
\boldsymbol{\mathbf{B}} ={
\left(\begin{array}{cccc|c}
1 &1 &-1 &1 &3 \\
0 &0 &1 &3 &-2 \\
0 &0 &0 &-2 &2 \\
0 &0 &0 &-1 &1 \\
\end{array}
\right) }~
\end{equation}
\begin{equation}
\boldsymbol{\mathbf{r}} _4 - 0.5 \boldsymbol{\mathbf{r}} _3
\quad \Longrightarrow \quad
\boldsymbol{\mathbf{B}} ={
\left(\begin{array}{cccc|c}
1 &1 &-1 &1 &3 \\
0 &0 &1 &3 &-2 \\
0 &0 &0 &-2 &2 \\
0 &0 &0 &0 &0 \\
\end{array}
\right) }~
\end{equation}
我们按照上面的方法用第 3 行求 $x_4$，代入第 2 行求得 $x_3$。然而当我们想用第 1 行求 $x_1$ 的时候却出发现我们还没求出 $x_2$。解决办法是，我们令 $x_2 = c$ 且假设 $c$ 可以取任意值，再把 $x_1$ 用 $c$ 表示。方程的解可以表示为
\begin{equation}
\left\{\begin{aligned}
x_1 &= 5-c\\
x_2 &= c \\
x_3 &= 1\\
x_4 &= -1 \end{aligned}\right. ~
\end{equation}
或者写成列矢量的形式
\begin{equation}
\boldsymbol{\mathbf{x}} = c \begin{pmatrix}-1\\ 1\\ 0\\ 0\end{pmatrix} + \begin{pmatrix}5\\ 0\\ 1\\ -1\end{pmatrix} ~.
\end{equation}
将该式代入方程组，可以验证 $c$ 取任意值时方程组都成立。
如果多个 $x_i$ 的值都未知，我们就分别假设它们等于不同的任意常数 $c_i$ 即可。
2. 解的数量
根据以上步骤，当系数矩阵变为梯形矩阵后，可以用以下步骤判断解的数量：
- 若存在系数 $a_{i,j}$ 全为零的行 $i$，但是对应的常数 $y_i$ 却不为零，则方程组无解。
- 若存在 $d$ 个系数 $a_{i,j}$ 全为零的行 $i$，且对应的所有 $y_i$ 也都为零，则方程有无穷个解，且需要 $d$ 个任意常数来表示所有可能的解。
- 若不存在系数 $a_{i,j}$ 全为零的行，则系数矩阵可以化为三角矩阵，使对角线上的元素全不为零。此时方程有唯一解。
3. 解的结构
按照高斯消元法的一般步骤，如果方程有解，我们总可以将解表示为一些常矢量的线性组合加上一个常矢量。
\begin{equation}
\boldsymbol{\mathbf{x}} = \sum_{i=1}^{d} c_i \boldsymbol{\mathbf{x}} _i + \boldsymbol{\mathbf{x}} _0~.
\end{equation}
其中 $c_i$ 是 $d$ 个任意常数（当方程有唯一解时 $d = 0$），无论这些常数取什么值，$ \boldsymbol{\mathbf{x}} $ 都是方程的解。另一方面，给出方程的任意一个解，总能找到一些常数 $c_i$ 与之对应。
式 18 叫做方程的
通解（general solution），通解中的任意一个就做方程的
特解（special solution）。
将式 18 代入方程组，使用矩阵乘法分配律（式 14 ）得到
\begin{equation}
\boldsymbol{\mathbf{A}} \sum_{i=1}^{d} c_i \boldsymbol{\mathbf{x}} _i + \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} _0 = \boldsymbol{\mathbf{y}} ~,
\end{equation}
由于 $ \boldsymbol{\mathbf{x}} _0$ 是方程的一个特解，有 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} _0 = \boldsymbol{\mathbf{y}} $。所以
\begin{equation}
\boldsymbol{\mathbf{A}} \sum_{i=1}^{d} c_i \boldsymbol{\mathbf{x}} _i = \boldsymbol{\mathbf{0}} ~.
\end{equation}
线性方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{y}} $ 中，如果 $ \boldsymbol{\mathbf{y}} = \boldsymbol{\mathbf{0}} $（粗体的 $ \boldsymbol{\mathbf{0}} $ 表示零矢量，即每个元都是 $0$），则方程组被称为是
齐次（homogeneous）的。上式说明 $\sum_{i} c_i \boldsymbol{\mathbf{x}} _i$ 就是齐次方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{0}} $ 的通解。
综上所述，对于任意有解的非齐次（inhomogeneous）方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{y}} $，我们可以将通解（式 18 ）从形式上理解为齐次方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{0}} $ 的通解与非齐次方程组的任一特解相加。
1. ^ 参考 Wikipedia 相关页面。
2. ^ 这点我们留到以后证明
3. ^ 为了书写简单，我们将每次变换后的系数矩阵元仍然用 $a_{i,j}$ 来表示，虽然它的值可能已经发生变化。若需要区分，可以将第 $n$ 次变换后的矩阵元用 $a_{i,j}^{(n)}$ 表示。
4. ^ 如果 $a_{1,1} \ne 0$ 则不需要
5. ^ 如果在处理 $i = m-1$ 之前就得到了梯形矩阵，则可提前终止。