行列式 - Ning

定义

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

$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$ ，如果这个排列具有奇数个逆序对，我们称之为 奇排列，否则称之为 偶排列。

对于 $n\ge 2$ 的 $n$ 级排列，有 $\frac{1}{2}$ 的排列是奇排列， $\frac{1}{2}$ 的是偶排列。
交换 $p$ 的两个数，这种操作称为对换，奇偶性发生变化。

性质

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

交换行列式的两行，行列式的结果取反。
证明：容易发现交换两行，相当于对每一个排列进行了一次对换，每一个排列的奇偶性发生变化，结果就会取反。
转置方阵，行列式不变。
比较显然。
对于矩阵 $A,B,C$ ，如果有 $A$ 的某一行是 $B$ 的这一行和 $C$ 的这一行的和，那么 $\det{A}=\det{B}+\det{C}$ 。
想象一下代入的时候乘法分配律。
当一行的元素等比例变化时，行列式等比例变化。
多次运用性质 3 即可得到。
如果有两行成比例，那么 $\det(A)=0$ 。
假设一行是 $a_{i,j}$ ，另一行是 $ka_{i,j}$ ，那么根据性质 4，可以将 $k$ 提出来得到新方阵 $A'$ ，这个新方阵中有两行是完全相同的。交换这两行，行列式取反，但是方阵没变，所以行列式的值为 $0$ 。
将一个方阵一行 $a_{i,j}$ 乘上常数 $x$ 之后加到另一行 $a_{k,j}$ ，也就是第 $k$ 行变为 $xa_{i,j}+a_{k,j}$ ，行列式的值不变。
由性质 3 可以将方阵拆成一个和原方阵相同的方阵和一个第 $k$ 行为 $xa_{i,j}$ 的方阵。由性质 5 得到后一个方阵的行列式为 0，证毕。
一个上三角矩阵（即只有对角线及以上的部分可能不为 $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$ ）

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

Sample Code (C++)

cpp

#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;
}

定义 ​

排列的奇偶性 ​

性质 ​

求值 ​

定义

排列的奇偶性

性质

求值