矩阵树定理学习笔记
不好意思本垃圾只会记结论
(largecolor{pink}{link1})
(largecolor{pink}{link2})
还是瞎bb两句了
行列式
对矩阵
[A=egin{bmatrix}a_{1,1}&a_{1,2}&a_{1,3}&dots&a_{1,n}\a_{2,1}&a_{2,2}&a_{2,3}&cdots&a_{2,n}\vdots&vdots&vdots&ddots&vdots\a_{n-1,1}&a_{n-1,2}&a_{n-1,3}&dots&a_{n-1,n}\a_{n,1}&a_{n,2}&a_{n,3}&dots&a_{n,n}end{bmatrix}
]
它的行列式定义为
[det A=sum (-1)^ra_{1,p_1}a_{2,p_2}cdots a_{n,p_n}
]
其中(p)是(1sim n)的排列，(r)是这个排列的逆序对数
求行列式
-
[A=egin{bmatrix}a_{1,1}&a_{1,2}&a_{1,3}&dots&a_{1,n}\0&a_{2,2}&a_{2,3}&cdots&a_{2,n}\vdots&vdots&vdots&ddots&vdots\0&0&0&dots&a_{n-1,n}\0&0&0&dots&a_{n,n}end{bmatrix} ]
这样类似的上or下三角矩阵，有(det A=prod_{i=1}^n a_{i,i})
-
交换矩阵的任意两行or两列，矩阵的行列式变为原来的相反数。
- 可以从元素不变，逆序对改变说明
推论：矩阵有两行or两列的元素一样，矩阵的行列式为(0)
-
矩阵某行or某列全乘上(k)，那么矩阵的行列式也乘上(k)
推论：可以提取某行or某列的公因数
推论：某两行或某两列成系数，行列式为(0)
-
两个只有一行or一列不同的矩阵的行列式之和等于这一行or一列相加，其他不变元素的矩阵的行列式。
-
如果把矩阵的某一行(列)加上另一行(列)的k倍，则行列式的值不变。
-
于是我们可以使用高斯消元把矩阵削成三角形，然后直接求出来就行了。
- 在(R)意义下做高斯校园还是用小数就可以了，最后输出(.0lf)
- 在(mod)某些数的意义下，如果为质数比较好弄，如果不是质数，使用辗转相除法做，多一个(log)，例题，小Z的房间
-
一些可以用的好东西
- 行列式等于它的任一行（列）的各元素与其对应的代数余子式乘积之和
- 余子式：在(n)阶行列式中，把元素(a_{i,j})所在第(i)行和第(j)行划去后，留下的(n-1)阶行列式叫元素(a_{i,j})的余子式，记做(M_{i,j})，定义代数余子式为(A_{i,j}=(-1)^{i+j}M_{i,j})
- 你可以用它来找一些特殊矩阵的规律，然后说不定可以找到行列式的简单求法。
矩阵树定理
- 定义一个无向图(G)的度数矩阵(D(G))为(d_{i,i})为点(i)的度数，其余为(0)
- 定义一个无向图(G)的邻接矩阵(A(G))，就是你不用前向星存边的那个存边矩阵。
- 定义一个无向图(G)的基尔霍夫矩阵(C(G)=D(G)-A(G))
- (G)的所有不同生成树个数等于其基尔霍夫矩阵的(n-1)阶主子式的行列式的值
- 主子式：你把矩阵随便削一行和一列之后拼起来的矩阵。