标签：定理 矩阵 vmatrix times cdots 行列式 vdots

行列式

前言：作者能力不足，不建议阅读，直接记加粗字体结论就好

定义

下面是一个三阶行列式

\[ \begin{vmatrix} 3 & 1 & 2 \\ 1 & 2 & 3 \\ 2 & 3 & 1 \end{vmatrix} \]

\(n\) 阶行列式是一个 \(n\) 阶方阵的值（标量），记矩阵为 \(T\) ，行列式记为 \(det(T)\) 或 \(|T|\)

\[det(T) = |T| = \sum_{p} (-1)^{\varGamma(p)} \prod_{i = 1}^{n} a_{i, p_i} \]

其中 \(p\) 是所有 \(1\) 到 \(n\) 的全排列， \(\varGamma(p)\) 是 \(p\) 的逆序对个数

性质

1. 如果某一行和另一行成比例，那么行列式为0

\[ \begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \vdots & \vdots \\ k \times a_{1, 1} & k \times a_{1, 2} & \cdots & k \times a_{1, n} \\ \vdots & \vdots & \vdots & \vdots \\ \end{vmatrix} = 0 \]

2. 某一行可以按某种比例加到另一行上，行列式不变

\[ \begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \vdots & \vdots \\ a_{i, 1} & a_{i, 2} & \cdots & a_{i, n} \\ \vdots & \vdots & \vdots & \vdots \\ \end{vmatrix} = \begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \vdots & \vdots \\ a_{i, 1} + k \times a_{1, 1} & a_{i, 2} + k \times a_{1, 2} & \cdots & a_{i, n} + k \times a_{1, n} \\ \vdots & \vdots & \vdots & \vdots \\ \end{vmatrix} \]

3. 交换两行，行列式取反

4. 交换一行和一列（矩阵转置），行列式不变

5. 某一行（列）等比例变化，行列式也等比例变化

\[ \begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \vdots & \vdots \\ k \times a_{i, 1} & k \times a_{i, 2} & \cdots & k \times a_{i, n} \\ \vdots & \vdots & \vdots & \vdots \\ \end{vmatrix} = k \times \begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \vdots & \vdots \\ a_{i, 1} & a_{i, 2} & \cdots & a_{i, n} \\ \vdots & \vdots & \vdots & \vdots \\ \end{vmatrix} \]

6. 一个矩阵某一行是另两个矩阵的这一行的和（其他数一样），这个矩阵的行列式是另两个矩阵的行列式的和

怎么求行列式

肯定不能枚举全排列求行列式...

\(n\) 阶行列式去掉第 \(i\) 行和第 \(j\) 列后的 \(n - 1\) 阶行列式叫做 \(a_{i, j}\) 的余子式，记为 \(M_{i, j}\)

\(a_{i, j}\) 的代数余子式记为 \(A_{i, j}\) ，则有

\[A_{i, j} = (-1)^{i + j}M_{i, j} \]

那么 \(n\) 阶行列式的值为任意一行（列）的元素与他们的代数余子式的乘积的和

\[det(T) = \sum_{i = 1}^{n} a_{i, k} \times A_{i, k} = \sum_{i = 1}^{n} a_{k, i} \times A_{k, i} \]

然后可以通过一些推导得出，一个 上三角矩阵的行列式为对角线元素乘积

我们可以通过性质2， 3对行列式高斯消元，然后快速求行列式

如果题目给模数且为质数，那么复杂度即为 \(n^3\)

若不为质数，为了避免浮点数精度误差，可以改用辗转相减法求高斯消元，复杂度是 \(n^3 \log p\) （我认为是 \(n^3\) ，但是有人说势能分析是\(n^2\) ，不理解，留有疑问）

矩阵树定理

记度数矩阵 \(D\) ，\(D_{i, i} = i 点的度数\)

记邻接矩阵 \(E\) ， \(E_{i, j} = [(i, j) 这条边存在]\)

记基尔霍夫矩阵 \(A\) ，\(A = D - E\)

那么图的生成树个数为 \(A\) 矩阵去掉任意第 \(k\) 行和第 \(k\) 列剩下的 \(n - 1\) 阶主子式的行列式

无向图情况即为上式，有向图情况：

有向图情况若根为 \(k\) ，那么必须是去掉第 \(k\) 行和第 \(k\) 列（不能任意）

外向树（从根向外）：\(D\) 为入度矩阵

内向树（从外向根）： \(D\) 为出度矩阵

可以处理重边的情况，不能处理自环的情况

应用

这是求生成树个数，如果边有边权，可以求所有生成树的边权乘积的和，也可以求所有生成树的边权和

边权乘积的和：把一条边权为 \(w\) 的边看成 \(w\) 条边权为 \(1\) 的边，然后此时生成树个数就是答案

边权和：把一条边权为 \(w\) 的边看成一次函数 \(1 + wx\) ，然后求出行列式后一次项系数即为答案

这相当于是钦定一条边选，然后这条边边权 \(\times\) 选这条边的生成树个数

一些细节

如果原图有一些边是必选的，先缩点都缩起来（要是原图有环直接无解，没有生成树），缩点的时候需要重新编号，高消的时候注意是编号个数不是原图点的个数

一些例题：

P7112 【模板】行列式求值 （模板）

P6178 【模板】Matrix-Tree 定理 （模板）

P3317 [SDOI2014]重建 （注意概率，需要考虑某些边不出现）

P4455 [CQOI2018]社交网络 （外向树模板题）

P4111 [HEOI2015]小 Z 的房间 （需要缩点，然后就是模板）

P2144 [FJOI2007] 轮状病毒 （一眼模板题，再一眼凉心出题人不给模数要打高精... 可以直接上矩阵树定理，也可以直接 \(dp\)，也可以推行列式的递推式）

P6624 [省选联考 2020 A 卷] 作业题 （先反演一下，然后变成求生成树边权和）

P4208 [JSOI2008]最小生成树计数

最小生成树某一权值的边的个数是一定的，除去某一种边权，原最小生成树分成的连通块也是一定的

可以枚举每一种边权，其他原树边把图缩点，求出这种边权把森林联通的情况数，答案就是把所有边权的情况数乘起来

P4821 [中山市选]生成树 （非常良心的模板题，有模数，但是组合意义也很简单，甚至只需要快速幂，就不写矩阵树定理了...）

P4336 [SHOI2016]黑暗前的幻想乡 （需要枚举哪些公司修路然后子集容斥一下）

Mirror Box （见省选联测40 T4）

标签：定理,矩阵,vmatrix,times,cdots,行列式,vdots
From： https://www.cnblogs.com/wenqizhi/p/17156800.html