循环矩阵行列式
chengch
·
·
个人记录
咋快速求 \det(\begin{bmatrix}
a_0 & a_1 & \cdots & a_{n-1} \\
a_{n-1} & a_0 & \cdots & a_{n-2} \\
\vdots & \vdots & \ddots & \vdots \\
a_1 & a_2 & \cdots & a_0
\end{bmatrix})。
把上述矩阵记为 A，f(x)=a_0+a_1x+\cdots +a_{n-1}x^{n-1}。我们试图直接构造 A 的特征值。
取 \omega 为任意一个 n 次单位根，构造
\vec v=\begin{bmatrix}1\\
\omega\\
\omega^2\\
\vdots\\
\omega^{n-1}
\end{bmatrix}
$。
计算 $A\vec v=\begin{bmatrix}a_0+a_1\omega+a_2\omega^2+\cdots + a_{n-1}\omega^{n-1}\\
a_{n-1}+a_0\omega+a_1\omega^2+\cdots + a_{n-2}\omega^{n-1}\\
\vdots\\
a_1+a_2\omega+a_3\omega^2+\cdots + a_0\omega^{n-1}
\end{bmatrix}=f(\omega)\vec v$。
因此，$f(\omega)$ 是 $A$ 的特征值。而 $\omega$ 有 $n
$ 种取值，因此 $A$ 的 $n$ 个特征值全被找到了，$\det(A)=\prod f(\omega)$。
剩下问题就是咋求 $f$ 带入 $n$ 个单位根后的点值，FFT（CZT） 即可。
写完才发现[学长之前写过了](https://www.cnblogs.com/ac-evil/p/14734728.html)，但是证明似乎不太一样，就发上来了。
结合矩阵树定理的应用
> 引理 $1$：矩阵的 $k$ 阶主子式之和 = 矩阵的所有 $k$ 个特征值相乘的和。
证明：
> 引理2：对于图 $G$ 和其 Laplace 矩阵 $M$，$G$ 的生成树个数为 $\frac{1}{n}\prod_{i=2}^{n}\lambda_i$。
证明：由于以每个点为根的生成树数量相等，因此 $n-1$ 阶主子式也相等。把它们全加起来，就是 $n-1$ 个特征值乘积的和，而取特征向量全 $1$ 可知 $0$ 必然是 $M$ 的特征值。不妨设 $\lambda_1=0$，则生成树个数为 $\frac{1}{n}\prod_{i=2}^{n}\lambda_i$。
若 Laplace 矩阵 $M$ 是循环矩阵，设循环多项式为 $f$，则 $M$ 的特征值 $\lambda_i=f(\omega_n^i)$，因此生成树个数为 $\frac{1}{n}\prod_{0<i<n}f(\omega_n^i)$。