【线性代数】高斯消元与行列式

· · 个人记录

本篇博文将对高斯消元与行列式进行讲解。

Part 1. 高斯消元

高斯消元是用来求解 n 元线性方程组的一种方法，时间复杂度为 O(n^3)。

Part 1.1 过程

假设当前有这样一个二元一次方程组 \begin{cases}4x+y=9\\x+y=3\end{cases}，我们的一般解法就是消元，即用 2 式减去 1 式消去 y 得到 3x=6，解得 x=2，代入 2 式中得到 2+y=3，解得 y=1，得到解为 \begin{cases}x=2\\y=1\end{cases}。

现在让我们将问题转化为下面这个 n 元一次线性方程组：

a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1 \\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2 \\\cdots \\a_{n,1}x_1+a_{n,2}x_2+\cdots+a_{n,n}x_n=b_n \end{cases}

仍然进行消元，如果我们要消去除 1 方程之外的 x_1，我们需要对第 j 个方程组 (j\neq i) 的第 k 个系数减去 \dfrac{a_{j,1}}{a_{1,1}}\times a_{1,k}，答案 b_j 也要减。

于是这样我们就消去 x_1，接下来消去 x_2,x_3,\cdots,x_n 相当于原问题的子问题，按照相同方法消去即可。

考虑如何把这种方法用程序写下来。我们可以将系数与答案写成矩阵的形式，得到一个 n\times (n+1) 的矩阵 A，那么每次选择第 i 行，将第 j 行的所有系数与答案减去 \dfrac{a_{j,i}}{a_{i,i}}\times a_{i,k}，最终就能得到一个这样的矩阵：

a'_{1,1}&0&\cdots&0&b'_1 \\0&a'_{2,2}&\cdots&0&b'_2 \\\cdots \\0&0&\cdots&a'_{n,n}&b'_n \end{bmatrix}

那么此时 x_i=\dfrac{b'_i}{a'_{i,i}}。

我们发现一个致命的问题：处理第 i 行时 a_{i,i}=0 会出错。解决方法也很简单，在未使用过的方程中寻找一行方程 j 使得 a_{j,i}\neq 0 即可。如果找不到则说明无解或者有无数个解。

那么如何判断无解或者无数个解呢？我们对于一个 a_{i,i}=0 且无法通过交换使得 a_{i,i}\neq 0 的未知数选择跳过，在最后时我们对每个未知数进行判断，如果出现 0=0 的情况则有无数个解，如果出现 0=非0 的情况则说明无解。注意无解的优先级大于无数个解。

例题 P3389，P2455。

Part 1.2 应用

我们构造一个 n\times 2n 的矩阵 (A,I)，然后对左半部分进行高斯消元将其消成单位阵，则我们得到新矩阵 (I,A^{-1})，即此时矩阵右半部分就是原矩阵的逆矩阵。

那么如果原矩阵无法消成单位阵，则该矩阵没有逆矩阵。大概类似于矩阵除法（？

Part 2. 行列式

行列式是对于方阵 A 的一种运算，记为 \det A。

Part 2.1 计算方法

公式：\det A=\sum\limits_{p}(-1)^{\sigma}\prod\limits_{i=1}^n a_{i,{p_i}}，其中 p 是一个 1,2,\cdots,n 的排列，\sigma 表示 p 的逆序对数。

Part 2.2 性质

很显然，交换后对应的 p 逆序对数会有奇数个的变化，则相应的 (-1)^{\sigma} 会对应取反。

显然每一行与每一列都会被选到，所以每个 \prod\limits_{i=1}^n a_{i,{p_i}} 都会乘上 k。

因为如果这两行相同的话在对应的 p 中交换这两行（列）的值之后得到的 \prod\limits_{i=1}^n a_{i,{p_i}} 不变，而逆序对数发生了奇数个变化，所以这样两两抵消，结果为 0。

考虑倍乘使得这两行（列）相同。

考虑乘法分配律。

用上一条性质可以将其拆成两个行列式的和，即原行列式 \det A 与某一行 j 均为第 i 行的 k 倍的行列式 \det A'，由性质 4 可得 \det A'=0，所以 \det A 不变。

Part 2.3 求解方法

注意到求解的时间复杂度是 O(n!\times n) 的，而它的最后一个性质恰好与上文中高斯消元的求解方法相符，所以行列式可以用高斯消元求解。

例题 P7112。