《九章算术》第八章叫「方程」，第一题是这样的：上等的谷子三捆、中等的两捆、下等的一捆，一共打三十九斗；上等两捆、中等三捆、下等一捆，三十四斗；上等一捆、中等两捆、下等三捆，二十六斗。问三种谷子每捆各多少。这道题今天用消元法两分钟能算完，而书里给的做法两千年来几乎没有改动过。
一、把方程组写成一张表
设上、中、下三等每捆分别是 \(a,b,c\) 斗，题目就是三个方程：
\[ \begin{cases} 3a+2b+c=39,\\ 2a+3b+c=34,\\ a+2b+3c=26. \end{cases} \]像这样，未知数都是一次的若干个方程放在一起叫线性方程组；使所有方程同时成立的一组数 \((a,b,c)\) 叫它的解，全部解构成的集合叫解集。
古人抄题的时候不写 \(a,b,c\)，只把数字摆成一张表：一「程」写成一列，从上到下是常数项和三个系数，所谓「实」放在最上面。
今天的写法是把每一程横过来，三行四个数排在一起，再用一条竖线把常数列隔开，写成
\[ \left(\begin{array}{ccc|c} 3 & 2 & 1 & 39\\ 2 & 3 & 1 & 34\\ 1 & 2 & 3 & 26 \end{array}\right). \]这个对象叫增广矩阵，竖线左边是系数矩阵，右边是常数列。它把「未知数是谁」这件事完全省略了，只留数字。好处马上能看出来：既然未知数的名字无关紧要，变形的时候就只需要动数字。
方程个数不一定要等于未知数个数。三个未知数只给两个方程，解出来通常是一条直线；反过来两个未知数给三个方程，多半无解，因为第三个方程一般不会刚好被前两个满足。这一点等化成阶梯形之后会看得非常清楚，见本章第四节。
为什么可以只写数字不写未知数
因为方程组里各项的位置是固定的：第一列永远是 \(a\) 的系数，第二列永远是 \(b\) 的。只要列的顺序不变，每个数字代表什么就不会混。课本第四章讲向量组时会给这件事一个更正式的说法：解方程组的过程，本质上是在处理三列向量之间的线性关系。
二、三种同解变形
解方程组天天在做的事只有三件：换两个方程的位置、把一个方程两边同乘非零数、把一个方程乘上某个数加到另一个方程上，对应到表上就是三种初等行变换：
定义（初等行变换）
对矩阵的行做下面三种操作，叫初等行变换。一、交换两行；二、用非零数 \(k\) 乘某一行；三、把某一行的 \(k\) 倍加到另一行上。只做前两种的称为初等变换。
关键的一点是：做完这些操作，解集一点没变。交换行显然不影响；乘非零数只是把同一个方程两边放大了；把一行加到另一行，等于把两个成立的等式相加，得到的还是成立的等式，而且这个操作可以反着做回去，所以新旧两组方程是等价的。
定理
初等行变换把方程组变成同解方程组。也就是说，变换前后解集完全相同。
263 年，洛阳
刘徽给「方程」作的注
「令每行为率，二物者再程、三物者三程，皆如物数程之。」
刘徽《九章算术注》卷八
这句话说的是：有几个未知数就摆几程，摆成方阵再逐列相减。
刘徽还顺带解释了「方程」二字的来历：并列成方形叫「方」，比较程数叫「程」。后来这个词被借去翻译 equation，意思已经变了，今天说「方程」一般指含未知数的等式。
为什么第三种变换不算作弊
设第一个方程是 \(E_1=0\)，第二个是 \(E_2=0\)。把 \(E_2+kE_1\) 当新方程，它满足「原解代入为零」，所以新组不会多出解；反过来，由 \(E_1=0\) 与新方程可以减回去得到 \(E_2=0\)，所以也不会丢解。两个方向都成立，才叫同解。
三、化成阶梯形
三种变换配合起来用，目标是把表整理成一种特别好读的形状：每行第一个非零数出现在上一行第一个非零数的右边，它下面全是零。这种形状叫行阶梯形，每行第一个非零数叫主元。
要注意，我们做到阶梯形就收手，而不是继续消成对角线。若一路消下去，主元左右两侧全变零，解直接从表上读出来，但那要多花一倍的运算量。化成阶梯形再回代，是手算和机算都采用的折中。
具体的动作是：先拿第一行去消掉下面各行第一列的数，再拿第二行去消掉它下面第二列的数，一路做到最下面。课本把它叫消元法，欧洲则叫高斯消元法。
拿上面那道题做一遍。第一行和第三行换一下位置，让主元变成 1；再用第一行把后两行的第一列消成零；第二行乘 -1，然后把它加到第三行。三步之后是
\[ \left(\begin{array}{ccc|c} 1 & 2 & 3 & 26\\ 0 & 1 & 5 & 18\\ 0 & 0 & 12 & 33 \end{array}\right). \]从这里往下读最容易：第三行说 \(12c=33\)，所以 \(c=11/4\)；代回第二行得 \(b=18-5\cdot\tfrac{11}{4}=\tfrac{17}{4}\)；再代回第一行得 \(a=26-2\cdot\tfrac{17}{4}-3\cdot\tfrac{11}{4}=\tfrac{37}{4}\)。验算 \(3\cdot\tfrac{37}{4}+2\cdot\tfrac{17}{4}+\tfrac{11}{4}=\tfrac{111+34+11}{4}=39\)，对上了。这一步往回代的过程叫回代。
《九章》里没有矩阵，也没有「回代」这个词，它把整个动作叫「直除」，一路把每一程减到底，答案直接落在表上，办法一模一样，只是没人给它单独命名。
四、解有几个
化成阶梯形之后，答案的形状有三种，看清楚最后一行就够了。
- 唯一解。每一行都有主元，个数正好等于未知数个数，回代就有唯一答案。
- 无解。出现形如 \((0\ 0\ 0\mid d)\) 且 \(d\ne0\) 的一行，意思是 \(0=d\)，矛盾。
- 无穷多解。主元个数少于未知数个数，但没出现矛盾行。这时把没有主元的那几列对应的未知数取作自由参数，解可以写成 \(x=x_0+t v\) 的样子。
要一句话说清这三种情形，得用秩：系数矩阵的秩记作 \(r(A)\)，增广矩阵的秩记作 \(r(A\mid b)\)，未知数个数是 \(n\)。那么 \(r(A)\ne r(A\mid b)\) 时无解；\(r(A)=r(A\mid b)=n\) 时有唯一解；\(r(A)=r(A\mid b)<n\) 时有无穷多解。秩的正式定义放在第四章，这里只要知道它数的是「阶梯形里有几个主元」。
无穷多解的写法值得单独看一眼：取方程组 \(x+y+z=1,\ x-y=0\)，消元后主元落在前两个未知数上，\(z\) 没有主元就留给参数 \(t\)，代回去得 \(x=y=\tfrac{1-t}{2}\)，于是一整族解可以写成 \((x,y,z)=\left(\tfrac12,\tfrac12,0\right)+t\left(-\tfrac12,-\tfrac12,1\right)\)。前一项是解集里的一个定点，后一项说明方向：\(t\) 怎么变，点就沿着一条直线滑。这条直线才是方程组真正的答案。
五、齐次方程组
常数列全是零的方程组叫齐次线性方程组。它永远有解，所有未知数取零就是一组，叫零解，所以对它只剩一个问题：除零解之外还有没有别的解。
定理
设齐次方程组有 \(n\) 个未知数，系数矩阵的秩为 \(r\)。则 \(r=n\) 时只有零解；\(r \lt n\) 时有无穷多解，即存在非零解。
道理很直接：齐次组不会出现 \(0=d\) 那种矛盾行，所以只剩唯一解与无穷多解两种，而 \(r\) 数的是主元个数。\(r \lt n\) 说明至少有一个未知数没有主元，可以任取，解就多得数不清。
比如 \(x+y+z=0,\ x-y=0\)，两个方程把 \(x,y\) 都定成 \(z\) 的倍数：\(x=y=-\tfrac{z}{2}\)；取 \(z=2\) 得 \((-1,-1,2)\)，取 \(z=-2\) 得 \((1,1,-2)\)，两者只差一个常数倍。解集是一条过原点的直线，而这条直线由任何一个非零解完全决定。第四章会把这样的解叫基础解系，那时你会发现：齐次组解空间的维数正好是 \(n-r\)。
无解为什么不可能出现在齐次组里
无解要有矛盾行，而齐次组的常数项在行变换中始终是零的线性组合、始终为零，所以不可能出现 \(0=d\) 且 \(d\ne0\)；零向量永远是一个解，解集非空，能出问题的只剩「解是否唯一」。
怎么算
- 先看形状再动手。未知数个数 \(n\) 记下来，最后判断解的情形要用。
- 主元先凑 1。若第一列某个位置是 1，换到第一行；没有就用分数或直接相除，避免一路带着分母算。
- 只往下消。用第一行消掉它下面的第一列，再用第二行消掉它下面的第二列，不要来回折腾。
- 出现零行就记一笔。零行是正常的；零行右边不是零就是矛盾，立刻停手写「无解」。
- 回代从下往上。先解出最后一个未知数，再一路往上代。至少代回一个原方程验算。
主元能不能选得更好
手算时选哪个都行，机算时不一样：若主元是一个很小的数，舍入误差会被放大得很厉害。实际软件会先在当前列里挑绝对值最大的那个换上来，叫列主元消去法。考试不用管，写论文要用。
例题
例 1 解方程组 \(x+y+z=6,\ 2x-y+z=3,\ x+2y-z=2\)。
写出增广矩阵，第二行减两倍第一行得 \((0,-3,-1\mid-9)\)，第三行减第一行得 \((0,1,-2\mid-4)\)。交换这两行使主元为 1，再消一次得 \((0,0,-7\mid-21)\)，于是 \(z=3\)，回代得 \(y=2\)，\(x=1\)。
例 2 讨论 \(a,b\) 取何值时，方程组 \(x+y+z=1,\ x+ay+z=1,\ x+y+az=b\) 有唯一解、无解、无穷多解。
消去第一列后剩下两行 \((0,a-1,0\mid0)\) 与 \((0,0,a-1\mid b-1)\)。若 \(a\ne1\)，两行都有主元，唯一解。若 \(a=1\)，两行都变成零行，右边分别是 0 与 \(b-1\)：\(b\ne1\) 时出现矛盾，无解；\(b=1\) 时第三行整行是零，只剩一个方程，无穷多解。
例 3 \(\lambda\) 取何值时，齐次方程组 \(\lambda x+y+z=0,\ x+\lambda y+z=0,\ x+y+\lambda z=0\) 有非零解。
消元后阶梯形的第三行是 \((0,0,\lambda+2\mid0)\) 或类似形状，出现零主元的条件是 \(\lambda=1\) 或 \(\lambda=-2\)。\(\lambda=1\) 时三个方程相同，解是一个平面；\(\lambda=-2\) 时三行相加为零，解是一条直线。两者都对应 \(r \lt 3\)，所以有非零解。
习题
A 档 巩固定义与基本计算，每题五分钟内
1. 把 \(3x-2y+z=5,\ x+y-2z=0,\ 2x-y+3z=7\) 写成增广矩阵。
看答案
三行四列，前三列依次是 \(x,y,z\) 的系数，竖线后是常数：\((3,-2,1\mid5)\)、\((1,1,-2\mid0)\)、\((2,-1,3\mid7)\)。
2. 解 \(x+y=3,\ x-y=1\)。
看答案
两式相加得 \(2x=4\)，\(x=2\)，回代得 \(y=1\)。
3. 判断 \(\left(\begin{array}{cc|c}1&2&3\\2&4&6\end{array}\right)\) 对应方程组的解的情况。
看答案
第二行是第一行的两倍，消元后变成零行且右边为零，没有矛盾。主元只有 1 个，未知数 2 个，所以有无穷多解：\(x=3-2y\)，\(y\) 任意。
4. 用行变换把 \(\left(\begin{array}{ccc}2&1&3\\4&3&5\\1&1&1\end{array}\right)\) 化成行阶梯形。
看答案
先把第三行换到第一行，再消去后两行第一列，得 \((1,1,1)\)、\((0,-1,1)\)、\((0,1,3)\)；把第二行加到第三行，得 \((1,1,1)\)、\((0,-1,1)\)、\((0,0,4)\)。
5. 齐次方程组 \(x+y+z=0,\ 2x+2y+2z=0\) 有多少解。
看答案
两行成比例，秩为 1，未知数 3 个，\(1 \lt 3\)，所以有无穷多解，解是一个平面 \(x+y+z=0\)。
6. 解 \(3x+2y=7,\ 6x+4y=14\)。
看答案
第二行是第一行的两倍，消元后为零行。无穷多解：\(y=t\)，\(x=\dfrac{7-2t}{3}\)。
B 档 综合题，接近期末与考研难度
1. 解《九章》第一题：三禾问题。求出上、中、下禾每捆各多少斗。
看答案
化阶梯形得 \((0,0,12\mid33)\)，即 \(c=\tfrac{11}{4}\)；回代得 \(b=\tfrac{17}{4}\)，\(a=\tfrac{37}{4}\)。也就是上禾九斗二升五合、中禾四斗二升五合、下禾二斗七升五合。
2. 讨论 \(a\) 取何值时 \(x+y+z=1,\ x+ay+z=1,\ x+y+az=1\) 有唯一解、无解、无穷多解。
看答案
这是例 2 中 \(b=1\) 的情形。\(a\ne1\) 时唯一解 \(x=z=0,\ y=1\)；\(a=1\) 时三个方程相同，无穷多解 \(x+y+z=1\)。这个方程组不会出现无解。
3. 三个平面两两相交、三条交线互相平行，对应方程组有解吗？说明理由。
看答案
无解。三张平面没有公共点，说明方程组矛盾。阶梯形里会出现一行 \((0,0,0\mid d)\) 且 \(d\ne0\)，也就是 \(r(A) \lt r(A\mid b)\)。
4. \(\lambda\) 取何值时方程组 \(\lambda x+y+z=0,\ x+\lambda y+z=0,\ x+y+\lambda z=0\) 只有零解。
看答案
消元后主元全在的条件是 \(\lambda\ne1\) 且 \(\lambda\ne-2\)。此时秩为 3，等于未知数个数，只有零解。
C 档 拓展与历史原题
1.（高斯，1809）给三个数据点 \((0,1),(1,2),(2,4)\)，用最小二乘拟合直线 \(y=a+bx\)，写出关于 \(a,b\) 的方程组并求解。
看答案
两个正规方程是 \(3a+3b=7\) 与 \(3a+5b=10\)。解得 \(b=\tfrac{3}{2}\)，\(a=\tfrac{5}{6}\)，直线是 \(y=\tfrac56+\tfrac32x\)。高斯正是为这类最小二乘问题系统使用消元法的，所以后人把名字安在它头上。
2. 证明：\(n\) 个未知数、\(n\) 个方程的齐次方程组有非零解，当且仅当消元化出的阶梯形里主元少于 \(n\) 个。
看答案
充分性：主元少于 \(n\) 时至少有一个未知数可任取，取不为零即可得非零解。必要性：若主元恰有 \(n\) 个，每个未知数都被主元唯一确定，回代只能得全零。这条结论在第二章会换一个说法：系数行列式为零。
3. 举一个 \(m \gt n\) 却无解的方程组，再举一个 \(m \gt n\) 但有解的。说明「方程比未知数多」为什么不能保证有解。
看答案
无解的例子：\(x+y=1,\ x+y=2\)。有解的例子：\(x+y=1,\ x+y=1,\ 2x+2y=2\)。多出来的方程若与前面的相容，只是重复信息；若不相容，就是矛盾。所以关键在秩，不在个数。
思考题 不设标准答案，只给提示
1. 初等行变换里为什么规定乘数不能为零，也不允许「交换两列」？
看提示
乘零会把一个方程整条抹掉，丢掉的解拾不回来，反向操作不存在。交换列则是在给未知数换名字，方程本身没变，但你的 \(x\) 已经不再是原来那个 \(x\)。什么时候允许换列，第四章讲列向量时会回答。
2. 把某一行所有元素乘以 2，解集变不变？如果把整张表乘以 2 呢？
看提示
第一问不变，因为那只是把同一个等式两边放大。第二问要想清楚：整张表乘 2 等于所有方程两边都乘 2，仍然同解。真正会改变解集的是只乘左边的系数、不乘右边，那就变成另一个方程组了。
3. 三个未知数一般要几个方程才能定出唯一解？几何上这句话是什么意思。
看提示
一般需要三个，对应三张平面交于一点。少于三个时交出来的是线或面，点定不下来；多于三个则可能过度约束，多出来的平面未必穿过那个点。所谓「一般」是相对于「秩恰好等于未知数个数」说的，不是数个数就够。
延伸阅读
- 同济大学数学系《线性代数》第六版，第一章与第三章。本章的记号与例题口径以这本为准。
- 《九章算术》卷八「方程」，配合刘徽注一起看，能看出「直除」与消元法的对应。
- 莫里斯·克莱因《古今数学思想》，第一册关于中国古代代数的部分。
- Gilbert Strang, Introduction to Linear Algebra，第一章。用消元法切入的方式与本书一致，例题更多。