行列式

基本性质

行列式

高斯消元不仅可以用于解方程，还可以用于行列式求值。
但是行列式满足的性质，和方程组略有不同

  1. 交换两行会改变行内列示符号
  2. 为了不改变最终行列式的值，只能是第ii行减去kk倍的第jj行。

行列式
n*n的矩阵 （方阵） 可以计算行列式
定义：
枚举所有n!长度为n的排列p
计算排列p逆序对的个数的奇偶性
如果逆序对个数是偶数，ans +=
如果逆序对个数是奇数，ans -=
a[1][p[1]] * a[2][p[2]] * a[3][p[3]] * ... * a[n][p[n]]

只会被用来计算 2 * 2 和 3 * 3 的行列式
对角线法则
a b
c d
a * d - b * c
二阶行列式对角线法则，有2项

c d
a b
c * b - a * d = -(a * d - b * c)
交换两行会改变符号

a b
c+k*a d+k*b
a*(d+k*b) - b*(c+k*a) = a*d - b*c
第j行加上若干倍的第i行，答案不变

a b
c*k d*k
a*d*k - b*c*k = k*(a*d - b*c)
第i行都乘以k，最终答案乘以k


a b c
d e f
g h i
a*e*i + b*f*g + c*d*h - c*e*g - b*d*i - a*f*h
1 2 3 + 2 3 1 + 3 1 2 - 3 2 1 - 2 1 3 - 1 3 2
三阶行列式对角线法则，有6项

更高阶的行列式计算方法，消元

行列式的基本性质

  1. 交换两行（两列）符号取反
  2. a[i] += a[j] * k，将第j行的k倍加到第i行上，行列式的值不变
    有了以上2个性质，就可以做高斯消元/辗转相除
  3. 行列式一行同时乘以k，那么最终结果也会乘以k，（如果一个矩阵中所有位置都乘以k，那么行列式的值会乘以k**n）

只有 j >= i的a[i][j]非0，其他位置都是0（上三角矩阵
a x x x
0 b x x
0 0 c x
0 0 0 d
行列式的值是abc*d

行列式的应用

  1. Matrix Tree Theorem / The BEST Theorem
  2. Lindström–Gessel–Viennot_lemma

a11 a12 a13
a21 a22 a23
a31 a32 a33

行列式
二维 cross product
三维 cross product

面积/体积/高维体积

叉积，混合积。

Matrix Tree Theorem

数无向图，生成树的个数。

BEST Theorem
数有向图，欧拉回路的个数。

LGV Lemma

LGV 引理

引入变量

冬令营中提到过这个题目的应用。

SP2832 DETER3 - Find The Determinant III

行列式模板题
高斯消元
枚举第i行：
将所有不是第i行的 第j行，我们要用a[i][i]把a[j][i]消成0

  1. 行列式
    1. 基本性质
    2. 行列式
    3. 面积/体积/高维体积
    4. Matrix Tree Theorem
    5. LGV Lemma
    6. 引入变量
      1. SP2832 DETER3 - Find The Determinant III
≡