【笔记】矩阵的行列式

定义

行列式（Determinant）是对 \(n\) 阶方阵 \(A\) 定义的，是一个标量。\(A\) 的 \(n\) 阶行列式 \(\operatorname{det}(A)\) 或 \(|A|\) 定义如下：

这里将排列的奇偶性定义为了 \(\operatorname{sgn}(p)\)，\(p\) 是排列，\(\operatorname{sgn}(p)\) 是 \(p\) 的逆序对个数的奇偶性。枚举所有排列，每一行挑一个乘起来，拿逆序对相关的东西做系数。

排列奇偶性

对于排列 \(p\)，交换 \(p_i,p_j\)（其中 \(1\leq i<j\leq n\)），\(\operatorname{sgn}(p)\) 的奇偶性改变。

假设 \(i<j\)，令 \(l=j-i\)。先将 \(a_j\) 调至 \(a_i\) 前，考虑这一步操作的影响。原来 \(a_j\) 与 \(a_{[i,j)}\) 的组合，顺序对设为 \(a\) 个，逆序对设为 \(b\) 个，那么 \(a+b=l\)，现在将 \(a_j\) 调至 \(a_i\) 前，顺序对变为 \(b\) 个，逆序对变为 \(a\) 个，所以变化量 \(a-b\equiv a-b+2b\equiv a+b\equiv l\pmod 2\)。再将 \(a_i\) 调至原来 \(a_j\) 的位置，变化量与 \(l-1\) 同奇偶，那么总的变化量是 \(l+l-1\equiv 1\pmod 2\)。

行列式性质

Theorem 1

单位矩阵的行列式为 \(1\)，上三角矩阵、下三角矩阵（对角线下/上全零的矩阵）的行列式为对角线乘积。

考虑选数乘起来的过程，如果不选零，那么归纳发现只有一种选法，就是选对角线。

Theorem 2

交换两行，行列式变号。

对于每个排列，这个交换两行只会影响 \(\operatorname{sgn}(p)\) 的奇偶性，由 Lemma 1 得 \(\operatorname{sgn}(p)\) 奇偶性改变，所以 \((-1)^{\operatorname{sgn}(p)}\) 全部变号，行列式变号。

Theorem 3

某一行乘以 \(t\)，行列式值乘以 \(t\)。

因为每行只选一个数进行乘积。

Theorem 4

\(\displaystyle\begin{vmatrix}a_1+a_2&b_1+b_2\\c&d\end{vmatrix}=\begin{vmatrix}a_1&b_1\\c&d\end{vmatrix}+\begin{vmatrix}a_2&b_2\\c&d\end{vmatrix}.\)

由乘法分配律得到。

Theorem 4,5 合起来是行的线性性。

Theorem 5

有两行相同，行列式为 \(0\)。

如果交换这两行，行列式应该变号，但是方阵还是那个方阵，行列式的值应该没有改变。

Theorem 6

用一行的倍数加到另一行，行列式不变。即证明 \(\displaystyle\begin{vmatrix}a&b\\c&d\end{vmatrix}=\begin{vmatrix}a&b\\c+ka&d+kb\end{vmatrix}\)。

由 Theorem 4 得 \(\displaystyle\begin{vmatrix}a&b\\c+ka&d+kb\end{vmatrix}=\begin{vmatrix}a&b\\c&d\end{vmatrix}+\begin{vmatrix}a&b\\ka&kb\end{vmatrix}\)。

右边那个对第二行乘 \(\dfrac{1}{k}\)，行列式值变为 \(0\)，所以右边那个的行列式为 \(0\)。

行列式求值

Theorem 2,3,6 就是高斯消元用的三种操作，所以对方阵高斯消元，消成上三角矩阵，取其对角线乘积即可。

实现时，高斯消元要求有逆元；如果 \(\mathbb F_{mod}\) 下没有逆元，可以辗转消除消元。参考实现：

const int P = 998244353;
LL mod(LL x) { return (x % P + P) % P; }
void red(LL& x) { x = mod(x); }
LL det(vector<LL>* a, int n) {
  LL res = 1;
  for (int i = 0; i < n; i++)
    for (LL& x : a[i]) x = mod(x);  //最好是正数
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      while (a[i][i]) {  //最好是 a[i][i]，因为下面有个除法
        LL r = a[j][i] / a[i][i];  //整除
        for (int k = i; k < n; k++) red(a[j][k] -= a[i][k] * r);
        swap(a[i], a[j]), res = -res;
      }
      swap(a[i], a[j]), res = -res;
    }
  }
  for (int i = 0; i < n; i++) red(res *= a[i][i]);
  return mod(res);
}

范德蒙德行列式

代数余子式

有方阵 \(A\)，记 \(a_{ij}\) 为 \(A\) 的第 \(i\) 行第 \(j\) 列的元素。则定义 \(A\) 划去第 \(i\) 行第 \(j\) 列的行列式乘上 \((-1)^{i+j}\) 为 \(a_{ij}\) 的代数余子式，记作 \(A_{ij}\)。

有如下定理，不知道为什么：

1. \[\forall i, \sum_{j=1}^na_{ij}A_{ij}=|A| \]

2. \[\forall j, \sum_{i=1}^na_{ij}A_{ij}=|A| \]

3. \[\forall i\neq k, \sum_{j=1}^na_{ij}A_{kj}=0 \]

4. \[\forall j\neq k, \sum_{j=1}^na_{ij}A_{ik}=0 \]

克莱默法则

用于解形如 \(A\mathbf x=\mathbf b\) 的 \(n\) 元一次方程组，\(A\) 的大小为 \(n\times n\)，\(A\) 的行列式不为 \(0\)。

结论：\(x_i=\dfrac{|A_i|}{|A|}\)。其中 \(A_i\) 表示将 \(A\) 的第 \(i\) 列替换为 \(\mathbf b\) 得到的方阵，\(|A|\) 是 \(A\) 的行列式。

当 \(A\) 的行列式为 \(0\) 时，说明方程组无解或无穷解。

也可以写成 \(\mathbf x=A^{-1}\mathbf b\)。不知道为什么这两个东西等价。