高斯消元入门

数学上，高斯消元法（Gaussian Elimination），是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个行梯阵式。

解多元方程组特别方便。

从方程组到矩阵

很多题目里我们会遇到一种奇怪的 DP，就是你只知道 DP 里各个状态之间的关系，但是不知道其中任意一个的值，并且一旦知道任意一个的值其实就可以求出所有……这种尴尬的情况其实可以表示成这样的多元方程组：

很显然，上面这个方程组是有解的，容易解得：

那么能不能归纳出一种通法来解决这类问题呢？我们需要用到高斯消元（Gaussian Elimination）。

数学上，高斯消元法（Gaussian Elimination），是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个**行梯阵式**。

在此之前，我们还是请出我们的老朋友：矩阵。 上面的方程组，把系数拿出来，用矩阵表示就是：

可以把这个矩阵分开看：左边一个 3×3 的矩阵和右边一列。 我们需要把左边的 3×3 矩阵通过“某种神秘的变换”化成如下所示的单位矩阵，这时候右边一列的三个值就是 $x,y,z$ 分别对应的值了。

这个矩阵叫做“简化行梯阵式”。

消元

从前的消元

那么如何进行“神秘的变换”呢？回想一下我们在不知道矩阵之前这个方程组是怎么解的：

首先，①式×5-③式，②式×5-③式，这样可以消去 $z$ 了。得到：

接下来我们继续消元，②式×$\displaystyle \frac {14} {19}$-①式得到：

$\frac {14x* 14} {19}-9x=47*\frac {14} {19}-32$

简化一下可以得到：

$x=2$

太棒了！我们得出了一个解！其他的 $y,z$ 都可以推出来了。 其实上面的这种方法归纳一下就是高斯消元。

矩阵上的高斯消元

高斯消元这个方法无非就是把上面那个套到矩阵里。前面已经提到，把左边的 3×3 矩阵变换成单位矩阵，构造“简化行梯阵式”。具体如何操作呢？ 其实和上面几个式子的变换一模一样……

一个简单的例子

首先，第一行×5-第三行，第二行×5-第三行，这样可以让第一、第二行的第三个数字都变成0。得到：

然后第二行×$\displaystyle \frac {14} {19}$-第一行得到：

当然这时候虽然可以知道 $x=2$，但是这并不是我们所想要的“简化行梯阵式”。我们可以继续：交换第一行和第二行，同时对第一行可以处理下：

第二行可以减去第一行×9，顺便化简得到：

第三行同时减去第一行、第二行，得到：

大功告成！我们得到了 $x=2,y=1,z=0$。

神秘的变换操作

从上面的例子可以看出，和解方程组类似，我们用到了以下几种操作：

• 交换矩阵的某两行；
• 将某一行翻倍；
• 将一行减去另一行。

可以证明，通过这样的变换，矩阵表达的关系仍然不变。

奇怪的情况？

有时候得到的矩阵会是这样的：

最后一行全都是 0，似乎难以化成简化行梯阵式。这就说明 $z$ 这个未知数有无穷多个解。 类似地，如果是这样的：

显然，$z$ 无解。