本文作者的线性代数水平还很低，如果有什么更简单的方法请告诉 TA。
结论：对于一张无向图 \(G\)，设其 Laplace 矩阵为 \(A\)，而 \(A\) 的特征值分别为 \(\lambda_1,\lambda_2,\ldots,\lambda_n\)。则其中必然有一个为 0，不妨设 \(\lambda_n=0\)。
若以 \(T(G)\) 表示 \(G\) 的生成树个数，以下等式成立：
简单的说就是，Laplace 矩阵的特征值中去掉一个零后，其乘积等于点数乘生成树个数。
这个结论想来没有任何作用，不过它的证明可能会带来一些启发。
考虑特征多项式 \(f_A(\lambda)=|\lambda I-A|=(\lambda-\lambda_1)(\lambda-\lambda_2)\ldots(\lambda-\lambda_n)\)。
这其实提供了同一个多项式的两种表示形式，一种是行列式方面的，而另一种是因式分解方面的。二者又分别关系了原矩阵和特征值，于是可以通过它把原矩阵和特征值直接的连接起来。
观察到 \(f_A(0)=|-A|=0\)，又有 \(f_A(0)=(-1)^n\lambda_1\lambda_2\ldots\lambda_n\)，于是显然必有一个特征值为 0。依上文不妨设 \(\lambda_n=0\)。
在此基础下，观察到 \([\lambda^1]f_A(\lambda)=(-1)^{n-1}\lambda_1\lambda_2\ldots\lambda_{n-1}\)，去掉 \((-1)^{n-1}\) 后恰为欲证式的左部。
从行列式的角度，现在就是要考虑计算 \([\lambda^1]|\lambda I-A|\) 了。
对于 \(|A+B|\) 型的行列式，我们有一个经典的处理方法。考虑到
结合组合意义，行列式的原定义可以看成枚举排列，计算带权和，一共是 \(n!\) 项求和；而此视角下，\(|A+B|\) 可以看成枚举排列后，再枚举每一行是从 \(A\) 中选元素，还是从 \(B\) 中选元素，计算带权和，一共是 \(n!2^n\) 项求和。这个视角在 \(A\) 十分稀疏时往往可以起到奇怪的效果。
将此方法应用到 \(|\lambda I-A|\) 上，若第 \(i\) 行是在 \(\lambda I\) 中选元素，则为了不选到 0，必须选择第 \(i\) 列的 \(\lambda\)。于是对于我们想探索的 \([\lambda^1]|\lambda I-A|\) 而言，必须恰好有一行是在 \(\lambda I\) 中选了非零的那一列，而剩下的行列都是在 \(-A\) 中选。
最终，我们得到 \([\lambda^1]|\lambda I-A|=\sum_{i=1}^n (-1)^{n-1}M_{i,i}\)，其中 \(M_{i,j}\) 表示 \(A\) 关于第 \(i\) 行第 \(j\) 列的代数余子式。
细心的读者可能发现，上式没有考虑在 \(\lambda I\) 中选的那个元素对 \(\text{sgn}(p)\) 的影响，然而，其实可以发现贡献总与 \((-1)^{i+i}=1\) 相同，这与 Laplace 展开的证明是一样的。
无论如何，结合 Matrix-tree 定理后我们已经得到 \([\lambda^1]|\lambda I-A|=(-1)^{n-1}nT(G)\)。于是结合上文得到的 \([\lambda^1]f_A(\lambda)=(-1)^{n-1}\lambda_1\lambda_2\ldots\lambda_{n-1}\)，我们已经完成了证明。
回顾证明的过程，我们利用特征多项式建立了原矩阵和特征值的联系，并对零次项、一次项系数分别应用了“算两次原理”。之后应用了 \(|A+B|\) 型的行列式的一个经典处理方法。这些方法虽然可能用得不多，但都是很初等的，因此也只能得到一个很初等的结果。
ps：对 \([\lambda^1]|\lambda I-A|\) 的探索没有用到 \(A\) 作为 Laplace 矩阵的性质。因此我们事实上对任意矩阵证明了 \([\lambda^1]f_A(\lambda)=\sum_{i=1}^n(-1)^{n-1}M_{i,i}\)。进一步使用这个方法，我们其实可以进一步得到 \([\lambda^k]f_A(\lambda)\) 关于 \(n-k\) 阶余子式的表达式，虽然暂时不知道有什么应用。
标签：推论,特征值,matrix,tree,sum,矩阵,text,ldots,lambda From： https://www.cnblogs.com/black-swallow/p/17092912.html