2018-03-05

以前接触了好多次行列式的题，然后口胡了好多行列式的做法，但到现在我也没写过行列式的题。准备恶补一下。

行列式定义

对一个N×NN×N矩阵A=⎡⎣⎢⎢⎢⎢a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮ann⎤⎦⎥⎥⎥⎥A=[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮an1an2⋯ann]，

定义它的行列式detA=|A|=∑P(−1)τ(P)∏iaiPidetA=|A|=∑P(−1)τ(P)∏iaiPi。

其中τ(P)τ(P)是排列PP的逆序对数。大大大

大大

这个定义了解一下就可以了，计算是阶乘复杂度，顶多用于二阶或三阶行列式。

行列式基本性质

最基本的性质几条：

转置行列式不变。

交换行列式两行（列），行列式取反。

同一行（列）乘数KK，行列式乘数KK。

如果两行（列）成比例，行列式为00。

一行（列）加上另一行（列）的KK倍，行列式不变。

detA=detATdetA=detAT

detA⋅detB=detABdetA⋅detB=detAB

detA≠0⇔rank(A)=n⇔∃B,A×B=I⇔detA≠0⇔rank(A)=n⇔∃B,A×B=I⇔所有行（列）向量线性无关。

行列式的组合意义是NN维空间下NN个向量组成的一个NN维体的有向体积。

行列式计算

二阶或者三阶行列式可以阶乘算。

二阶：detA=v1×v2=ad−bcdetA=v1×v2=ad−bc

三阶：detA=a1b2c3+a2b3c1+a3b1c2−a1b3c2−a2b1c3−a3b2c1detA=a1b2c3+a2b3c1+a3b1c2−a1b3c2−a2b1c3−a3b2c1

高阶的消成上三角矩阵。

有这么个定理：

上三角矩阵的行列式detA=∏iaiidetA=∏iaii。直接暴力带入原计算式可以证得。

正好可以发现如果∃aii=0∃aii=0，说明矩阵无逆，则detA=0detA=0。

利用行对换和一行乘另一行KK倍，使用辗转相除来实现类似高斯消元的过程。要注意行对换的时候行列式取反。这个复杂度是O(N3logN)O(N3log⁡N)。

代数余子式

选定一个(i,j)(i,j)，删去行列式的第ii行和第jj列，留下的部分的行列式就是元素aijaij的余子式，记为MijMij。

aijaij的代数余子式Aij=(−1)i+jMijAij=(−1)i+jMij

aijaij的代数余子式AijAij与aijaij的值无关，仅与其位置有关。

拉普拉斯展开定理

∑iakiAki=detA∑iakiAki=detA

∑iakiAli=0(k≠l)∑iakiAli=0(k≠l)

用这个定理可以多次单点修改询问行列式。

某个计数定理

从平面上NN个点依次连到另NN个点，不相交路径的方案数是一个行列式，其中aijaij表示一侧第ii个点连到另一侧第jj个点的方案数。

考虑两个相交的路径，在第一个交点对换后续路径的话相当于交换排列中两个数，容斥一下即可。

矩阵树定理

先讨论无向图。

定义度数矩阵DD，其中dii=degree(i)dii=degree(i)。

再定义邻接矩阵AA，其中aij=−[link(i,j)]aij=−[link(i,j)]。

则这个无向图的基尔霍夫矩阵C=D−AC=D−A。

CC的每行每列和均为00，所以detC=0detC=0。

生成树个数是MiiMii，即主对角线上的任意一个元素的余子式。

如果图是有向图，考虑求内向树还是外向树，度数和邻接变得有向，再枚举根，求这个根在主对角线上的元素的余子式。

另外，对于完全图的基尔霍夫矩阵，对角线元素的余子式Mii=nn−2Mii=nn−2。（和Prufer序列结果相同）