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

解多元方程组特别方便。

从方程组到矩阵

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

$$ \begin{alignedat}{3} 2&x+ &3&y+ &&z = 7 \\ 3&x+ &4&y+ &&z = 10 \\ &x+ &&y+ &5&z = 3 \end{alignedat} $$

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

$$ \begin{cases} x=2 \\ y=1 \\ z=0 \end{cases} $$

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

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

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

$$ \begin{bmatrix} 2 & 3 & 1 & 7 \\ 3 & 4 & 1 & 10 \\ 1 & 1 & 5 & 3 \end{bmatrix} $$

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

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix} $$

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

消元

从前的消元

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

$$ \begin{alignedat}{3} 2&x+ &3&y+ &&z = 7 \\ 3&x+ &4&y+ &&z = 10 \\ &x+ &&y+ &5&z = 3 \end{alignedat} $$

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

$$ \begin{alignedat}{3} 9&x+ &14&y = 32 \\ 14&x+ &19&y = 47 \end{alignedat} $$

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

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

简化一下可以得到：

$$x=2$$

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

矩阵上的高斯消元

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

一个简单的例子

$$ \begin{bmatrix} 2 & 3 & 1 & 7 \\ 3 & 4 & 1 & 10 \\ 1 & 1 & 5 & 3 \end{bmatrix} $$

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

$$ \begin{bmatrix} 9 & 14 & 1 & 32 \\ 14 & 19 & 1 & 47 \\ 1 & 1 & 5 & 3 \end{bmatrix} $$

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

$$ \begin{bmatrix} 9 & 14 & 0 & 32 \\ 25 & 0 & 0 & 50 \\ 1 & 1 & 5 & 3 \end{bmatrix} $$

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

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 9 & 14 & 0 & 32 \\ 1 & 1 & 5 & 3 \end{bmatrix} $$

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

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 5 & 3 \end{bmatrix} $$

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

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} $$

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

神秘的变换操作

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

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

奇怪的情况？

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

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

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

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 5 \end{bmatrix} $$

显然，$z$ 无解。