行列式求值

· · 算法·理论

定义

行列式，是一种函数运算，对象是一个方阵，结果是一个标量，定义为：

det(A)=\vert A\vert=\sum_p (-1)^{\tau(p)}\prod_{i=1}^{n}a_{i,p_i}

其中 p 是一个 1 到 n 的一个排列，\tau(p) 是 p 的逆序对数。

排列的奇偶性

对于一个排列 p，如果这个排列具有奇数个逆序对，我们称之为 奇排列，否则称之为 偶排列。

性质

直接根据定义计算行列式的复杂度是 O(n!\times n) 的，这样的复杂度实在是难以承受。我们需要发掘行列式的性质，来加速其计算。下面的性质对于行和列都是一样的。

  1. 交换行列式的两行，行列式的结果取反。

    证明：容易发现交换两行，相当于对每一个排列进行了一次对换，每一个排列的奇偶性发生变化，结果就会取反。

  2. 转置方阵，行列式不变。

    比较显然。

  3. 对于矩阵 A,B,C，如果有 A 的某一行是 B 的这一行和 C 的这一行的和，那么 \det{A}=\det{B}+\det{C}。

    想象一下代入的时候乘法分配律。

  4. 当一行的元素等比例变化时，行列式等比例变化。

    多次运用性质 3 即可得到。

  5. 如果有两行成比例，那么 \det(A)=0。

    假设一行是 a_{i,j}，另一行是 ka_{i,j}，那么根据性质 4，可以将 k 提出来得到新方阵 A'，这个新方阵中有两行是完全相同的。交换这两行，行列式取反，但是方阵没变，所以行列式的值为 0。

  6. 将一个方阵一行 a_{i,j} 乘上常数 x 之后加到另一行 a_{k,j}，也就是第 k 行变为 xa_{i,j}+a_{k,j}，行列式的值不变。

    由性质 3 可以将方阵拆成一个和原方阵相同的方阵和一个第 k 行为 xa_{i,j} 的方阵。由性质 5 得到后一个方阵的行列式为 0，证毕。

  7. 一个上三角矩阵（即只有对角线及以上的部分可能不为 0）的行列式等于其对角线上元素的乘积。

    容易发现只有满足 p_i=i 的矩阵可能产生贡献。具体来说，若 p_1=j,j\not=1，那么必然存在一个 p_i=1,i\not=1，也就是 a_{i,1} 会被计算，但是由上三角矩阵的定义可以得知 a_{i,1}=0，这势必会导致乘积为 0 而产生不了任何贡献。其它排列的元素可以归纳地证明。

求值

根据定义对行列式进行求值的复杂度是难以接受的。我们利用性质将矩阵转化成上三角矩阵的形式，这样就可以在 O(n) 的时间内求得行列式。

如果将第 i(i\not=1) 行都减去 \dfrac{a_{i,1}}{a_{1,1}} 倍的第 i 行，根据性质 6 可以得到行列式的值不变，并且这样可以让第 i 行的第一个元素变为 0。

这个过程类似于高斯消元，可以将矩阵转化为上三角矩阵，然后快速求得行列式。

注意到实际情况下，可能需要进行取模并且模数不为质数，这导致 a_{i,i} 的逆元不存在，无法直接消元。

此时我们就需要另一种消元方法。注意到辗转相除的边界条件，被除数为 0，并且取模的过程和定理 6 的形式相同，也就是说行列式的值不变。

具体来说，假设要用第 i 行消去第 j 行，也就是将 a_{j,i} 消成 0。计算系数 t=\lfloor \dfrac{a_{j,i}}{a_{i,i}}\rfloor，第 j 行整行减去 t 倍的第 i 行，那么 a_{j,i} 相当于进行了 a_{j,i}\bmod a_{i,i}，交换 i 行和 j 行，重复直至 a_{j,i} 为 0，这样我们就达到了消元的目的。

注意交换两行时行列式的值会取反（由定理 1）

下面给出了洛谷模板题 【模板】行列式求值 的代码。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 608;
int a[MAXN][MAXN];
int main() {
  int n, p;
  scanf("%d%d", &n, &p);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      scanf("%d", &a[i][j]);
      a[i][j] %= p;
    }
  }
  int sign = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      while (a[i][i]) {
        int t = a[j][i] / a[i][i];
        for (int k = i; k <= n; k++) {
          a[j][k] -= 1ll * t * a[i][k] % p;
          if (a[j][k] < 0) a[j][k] += p;
        }
        swap(a[i], a[j]);
        sign = -sign;
      }
      swap(a[i], a[j]);
      sign = -sign;
    }
  }
  int ans = 1;
  for (int i = 1; i <= n; i++) {
    ans = 1ll * ans * a[i][i] % p;
  }
  ans *= sign;
  printf("%d\n", (ans % p + p) % p);
  return 0;
}