行列式

行列式 (Determinant) 相关内容在课本上将得比较浅, 这里做一些补充.

定义排列 (Permutation) 为一个 $n$ 个元素的序列 $A$ 和另一个 $n$ 个元素序列 $B$ 的双射. 我们一般用长度为 $n$ 的, 包含所有前 $n$ 个正整数的序列 $P$ 来表示, $P_{i} = j$ 表示 $A_i$ 在 $B$ 里是 $B_j$.

$N(P)$ 表示 $P$ 中逆序的数量, 即 $N(P) = \sum_{i < j} [P_i > P_j]$.

定义排列 $P$ 的奇偶性为 $N(P)$ 的奇偶性. $\mathrm{sgn}(P) = (-1)^{N(P)}$.

对于一个 $n$ 阶方阵 $A$, 定义 $\det(A)$ 表示它的行列式. 如果认为 $S$ 是前 $n$ 个正整数所有 $n!$ 种排列的集合. 记 $A$ 第 $i$ 行第 $j$ 列的元素为 $a_{i, j}$, 那么方阵 $A$ 的行列式 $D$ 可以表示为:

$\det(A) = D = \sum_{P \in S} \mathrm{sgn}(P) \prod_{i = 1}^n a_{i, P_i}$

所以行列式由 $n!$ 项构成, 其中每一项是 $n$ 个元素的乘积, 且每个行和列都有且仅有一个元素在这一项中, 而每一项的符号还和这些元素按行排列后, 列数构成的排列的奇偶性有关. (当然, 也可以是元素按列排列后, 行数构成的排列的奇偶性)

另一种定义

定义二阶行列式:

$\begin{vmatrix} a & b\\ c & d\\ \end{vmatrix} = ad - bc$

定义 $n$ 阶行列式 $D$ 的余子式 $M_{i, j}$ 为 $D$ 去掉第 $i$ 行 第 $j$ 列得到的 $n - 1$ 阶行列式. 定义代数余子式 $A_{i, j} = (-1)^{i + j}M_{i, j}$.

那么定义 $n$ 阶行列式 $D$ 分别从第 $i$ 行和第 $j$ 列展开:

$D = \sum_{k = 1}^n a_{i, k}A_{i, k}\\ D = \sum_{k = 1}^n a_{k, j}A_{k, j}\\$

由于代数余子式都是 $n - 1$ 阶行列式, 因此可以递推地定义 $n$ 阶行列式.

两种定义的关系

我一开始尝试从行列式的消元本质入手, 但是走了几步发现过于繁琐. 所以只能从排列的角度解释递推定义的正确性.

矩阵初等变换和行列式

• 任意两行(列)交换, 结果取反

• 某行(列)加减另一行(列), 结果不变

• 某行(列)乘以 $k$ 倍, 结果乘以 $k$

高斯消元和行列式

如果直接求那复杂度将是 $O(n!n)$ 的, 我们仍然使用高斯消元. 其原理是:

我们用前面的变换将矩阵只留下第 $i$ 行后 $i$ 项的过程中记一下结果会变成之前的多少倍即可.

然后是求行列式, 发现所有第 $i$ 项不是 $i$ 的置换都不需要枚举了, 因为它的 $\prod$ 中一定有至少一项是 $0$, 对结果没有贡献. 我们只要对这个矩阵对角线上的元素求积即可.

当需要取模时, 模数任意的情况下我们可能无法找到所需的逆元, 所以我们采用辗转相减法进行消元. 两行之间的减法是 $O(n)$ 的, 每次消掉一个位置的元素需要 $O(\log p)$ 次减法. 一共需要消 $O(n^2)$ 个元素, 所以复杂度是 $O(n^3\log p)$. 但是因为我们是连续消掉一列的元素, 每次相减后, 对应位置剩下的元素是上面所有元素的 GCD, 所以消掉一列元素均摊需要 $O(n + \log p)$ 次减法, 因此更精确的复杂度应该是 $O(n^2(n + \log p))$.

下面是模板题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

unsigned long long Gcd(unsigned long long x, unsigned long long y) {
  unsigned long long SwT;
  while (y) SwT = x, x = y, y = SwT % y;
  return x;
}
unsigned long long a[605][605], Mod, G, Tms(1), Ans(1);
unsigned m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0);
inline void Dec(unsigned long long* f, unsigned long long* g, unsigned x) {
  while (g[x]) {
    unsigned long long Tmp(Mod - (f[x] / g[x]));
    for (unsigned i(x); i <= n; ++i) f[i] = (f[i] + g[i] * Tmp) % Mod;
    for (unsigned i(x); i <= n; ++i) swap(f[i], g[i]);
    Tms = Mod - Tms;
  }
}
signed main() {
  n = RD(), Mod = RD();
  for (unsigned i(1); i <= n; ++i) for (unsigned j(1); j <= n; ++j) a[i][j] = RD() % Mod;
  if (n == 1) { printf("%llu\n", a[1][1]);return 0; }
  for (unsigned i(1); i <= n; ++i) {
    G = Gcd(a[i][1], a[i][2]);
    for (unsigned j(3); j <= n; ++j) G = Gcd(G, a[i][j]);
    if (G > 1) for (unsigned j(1); j <= n; ++j) a[i][j] /= G;
    Tms = Tms * G % Mod;
  }
  for (unsigned i(1); i <= n; ++i) {
    G = Gcd(a[1][i], a[2][i]);
    for (unsigned j(3); j <= n; ++j) G = Gcd(G, a[j][i]);
    if (G > 1) for (unsigned j(1); j <= n; ++j) a[j][i] /= G;
    Tms = Tms * G % Mod;
  }
  for (unsigned i(1); i <= n; ++i) for (unsigned j(n); j > i; --j) if (a[j][i]) Dec(a[j - 1], a[j], i);
  for (unsigned i(1); i <= n; ++i) Ans = Ans * a[i][i] % Mod;
  printf("%llu\n", Ans * Tms % Mod);
  return Wild_Donkey;
}

范德蒙德行列式

形如:

$D = \begin{vmatrix} 1 & 1 & \cdots & 1\\ a_1 & a_2 & \cdots & a_n\\ {a_1}^2 & {a_2}^2 & \cdots & {a_n}^2\\ \vdots & \vdots & \ddots & \vdots\\ {a_1}^{n - 1} & {a_2}^{n - 1} & \cdots & {a_n}^{n -1}\\ \end{vmatrix}$

的行列式 $D$ 被称为范德蒙德 (Vandermonde) 行列式, 结论:

$D = \prod_{1 \leq i < j \leq n} (a_j - a_i)$

这个证明在书中被略过了, 但是结合我们对行列式的排列定义, 可以对这个结论进行证明.

因为行列式每一项中, 参与乘积的元素每行每列有且仅有一个, 所以发现每一项的 $a_i$ 都以 $[0, n - 1]$ 次出现, 且不同的 $a_i$ 次数互不相同.

一旦确定了每个 $a$ 的次数, 那么我们是可以唯一地找到在二项式连乘时, 每个二项式哪个项参与了乘法. 具体方法是: 找到 $n - 1$ 次的 $a_i$, 即这个项对应的排列 $P$ 满足 $P_{n} = i$, 发现含 $a_i$ 的二项式仅有 $n - 1$ 个, 因此这些二项式在连乘时, 都是 $a_i$ 参与了乘法. 而 $a_i$ 的携带相乘的 $-1$ 数量则是由有多少个 $j > i$ 决定的, 即 $n - i$, 而这恰恰是 $P_{n} = i$ 给 $N(P)$ 带来的贡献. 有归纳法知, 这些项都可以在连乘展开式中找到.

接下来我们来证明除了排列定义下的项, 剩下的项都会在展开时被消掉. 首先我们考虑连乘展开式的次数, 发现所有满足 $1 \leq i < j \leq n$ 的有序数对 $(i, j)$ 共有 $\binom n2$ 种, 因此次数为 $\binom n2$. 我们发现如果不满足每个元素的次数互不相同, 那么一定可以找到至少一对 $(i, j)$, 使得 $a_i$, $a_j$ 的次数相同. 假设构成这个项的每个二项式参与连乘的项已经被确定了.

暂时忽略每一项的符号, 找到所有包含 $a_i$ 的项 $(a_i - a_k)$, 和它对应的含 $a_j$ 的项 $(a_j - a_k)$. 交换它们选择参与连乘的项. 例如, 如果 $(a_i - a_k)$ 中 $a_i$ 参与连乘, 那么令 $(a_j - a_k)$ 中 $a_j$ 参与连乘, 否则令 $a_k$ 参与连乘. 并且用同样的方式确定 $(a_i - a_k)$ 的参与连乘的项. 特别地, 对于 $(a_i - a_j)$, 我们直接选择本来没有参与连乘的项参与连乘. 这时我们应该可以得到一个新的项, 其中每个 $a$ 的次数和原来保持一致.

接下来我们来讨论符号问题. 由于交换了 $a_i$, $a_j$ 参与连乘的位置, 因此对于 $k > i, j$ 或 $k < i, j$, $a_i$, $a_j$, $a_k$ 携带进入连乘的符号都不变; 不妨设 $i < j$, 对于 $k \in (i, j)$, $a_k$ 的符号取反, 但是同时, 每次一个 $a_k$ 的符号取反, 即 $(a_k - a_i)$, $(a_j - a_k)$ 从一开始的选择 $a_ka_j$ 变成 $(-a_k)(-a_i)$ 后, 存在一个 $a_i$ 或 $a_j$ 的符号取反, 因此这对因子贡献的符号也没有改变. 最后, 因为我们把 $(a_i - a_j)$ 这个二项式参与连乘的项改变了, 而这个项会使得整体的符号取反.

综上, 我们证明了连乘展开式中, 对于不符合排列定义的行列式的项, 存在符号相反, 绝对值相同的项的一一对应关系, 因此只会保留符合行列式排列定义的项, 到这里为止范德蒙德行列式结论证毕.