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

行列式定义

对一个矩阵

定义它的行列式

其中是排列的逆序对数。

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

行列式基本性质

最基本的性质几条:

行列式计算

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

二阶:

三阶:

高阶的消成上三角矩阵。

有这么个定理:

正好可以发现如果,说明矩阵无逆,则

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

代数余子式

选定一个,删去行列式的第行和第列,留下的部分的行列式就是元素的余子式,记为

的代数余子式

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

如果一个行列式非零,那么这个行列式取逆,转置,然后全部除以行列式值就得到代数余子式构成的矩阵。

拉普拉斯展开定理

某个计数定理

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

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

矩阵树定理

先讨论无向图。

定义度数矩阵,其中

再定义邻接矩阵,其中

则这个无向图的基尔霍夫矩阵

的每行每列和均为,所以

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

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

另外,对于完全图的基尔霍夫矩阵,对角线元素的余子式。(和Prufer序列结果相同)