特征多项式（ABC323G Sol）

· · 题解

upd on 2024.4.19：修了几处笔误。

线性代数。

为什么要学这个？都是矩阵树惹的祸。

本篇同时作为 ABC323G 的题解。

注：由于本篇写就的时候题解区只有一篇高深莫测极其简短的题解，看了半天没看懂又跑去学特征多项式，结果特征多项式题解也看了好久才看懂，所以笔者决定整理一篇详细易懂的题解。

特征值和特征向量

设 V 是 F 上的线性空间，T 是 V 上的线性变换。若存在 F 中的 \lambda 与 V 中的 非零向量 \xi，使得：

T\xi=\lambda\xi

则称 \lambda 为 T 的一个 特征值，而 \xi 为 T 的 属于特征值 \lambda 的一个特征向量。

这个定义式 T\xi=\lambda \xi 告诉我们矩阵对特征向量的唯一作用就是使它缩放了倍数。

特征分解

如果一个 n\times n 矩阵有 n 个特征向量 \xi_1,\cdots,\xi_n（这其实与可逆、满秩是同一概念），满足两两不共线，那么可以将该矩阵分解为 P^{-1}\Lambda P 的形式（常用记法是 P\Lambda P^{-1}），其中 P 是可逆矩阵，\Lambda 是对角阵。

对上述定理的理解：

考虑 A\vec a 时 A 对 \vec a 的影响，可以先将 \vec a 分解为这些特征向量的线性组合（P），然后每个向量缩放对应的倍数（\Lambda），最后再将这个线性组合变换回去（P^{-1}），写在一起就是 P^{-1}\Lambda P\vec a。

用处：可以把矩阵快速幂的 \log 去掉，朴实无华，但需要计算机对特征多项式求根，完全没有用，手算可能有点用。

原理：A^2=P\Lambda P^{-1}P\Lambda P^{-1}=P\Lambda^2P^{-1}，同理 A^n=P\Lambda^nP^{-1}，由于 \Lambda 是对角阵（各向量线性无关），所以只需要将每个元素 n 次幂即可。

或者理解成 n 次缩放 k 倍就是直接缩放 k^n 倍。

可以用来求数列通项公式，这个就是比较偏的应用了。

特征多项式

相似矩阵：对可逆矩阵 P，B=PAP^{-1} 称作 A 的相似矩阵，记作 A\sim B。

相似矩阵的行列式不变：|PAP^{-1}|=|P||A||P^{-1}|=|A|。

还有一些东西不变，此处仅需要这个性质。

定义一个矩阵 A 的特征多项式为 |xI-A|，此处的 x 是多项式里面的变量，而不是某种系数。

顺带一提，特征多项式的所有根就是矩阵的所有特征值，理由：

T\xi=\lambda\xi\iff T\xi=\lambda I\xi\iff (\lambda I-T)\xi=\vec 0

由于 \xi\ne\vec 0，所以 |\lambda I-T|=0。

定理：相似矩阵的特征多项式不变：|xI-A|=|xI-PAP^{-1}|，证明：

\begin{aligned}&|xI-PAP^{-1}|\\=&|xI(PP^{-1})-PAP^{-1}|\\=&|PxIP^{-1}-PAP^{-1}|\\=&|P||xI-A||P^{-1}|\\=&|xI-A|\end{aligned}

核心是利用了 xIP=xP=Px，所以 xI 是具有交换律的。

那这个特征多项式有啥用呢，从表面上看你很难看到它的用处，但这玩意是可以 \Theta(n^3) 求的！

（极其朴素的求法显然是把 x=0,1,\cdots,n 带进去求出 n+1 个值然后拉格朗日插值。）

求解

分为两个比较独立的步骤。

根据这篇文章详细的推导，我们可以魔改高斯消元的过程使每一步操作完都与原来相似。

其实就是把原来的每个操作都多执行一次共轭操作：

上海森堡矩阵指的是如下这种，即主对角线下方多了一条非零元素：

a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} \\a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} \\& a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\& & a_{4,3} & a_{4,4} & a_{4,5} \\ & & & a_{5,4} & a_{5,5} \end{bmatrix}\quad

观察这个矩阵，你发现如果我们想消成上三角矩阵，用第 i 行去消第 j 行的时候第 i 列就会受到污染，所以我们退而求其次使用上海森堡矩阵就可以保证消元。

这个递推叫做海森堡算法。

设左上角 i\times i 的矩阵（显然也是一个上海森堡矩阵）的特征多项式为 f_i(x)，边界条件是 f_0(x)=1。

如果你对这个过程没有比较直观的感受（我卡了一下午/fn），那你需要回顾一下行列式的求法：

还记得上三角矩阵是如何求行列式的吗？

直接把主对角线上的元素乘起来！

如果你清晰地记得推导过程，那么这部分你就不会费劲。

我们写出行列式的定义式：

\sum\limits_\sigma\sum\limits_{i=1}^n(-1)^{\tau(\sigma)}\prod\limits_{i=1}^na_{i,\sigma_i}

而你发现想要保证 \prod\limits_{i=1}^n a_{i,\sigma_i}\ne 0，当且仅当 \sigma_i=i 才行（第一列别无选择只能选第一个，然后到第二列就仍然别无选择了）。

上海森堡矩阵稍微菜一点，它可以 \Theta(n^2) 求出行列式的值。

\begin{bmatrix} \color{magenta}\vdots&\color{magenta}\vdots&\color{magenta}\vdots&\vdots&\vdots&\vdots\\[0.5em]\color{magenta}*&\color{magenta}*&\color{magenta}*&*&*&X\\[0.5em]&\color{magenta}*&\color{magenta}*&*&*&X\\[0.5em]&&X&X&X&\color{red}*\\[0.5em]&&&\color{orange}*&*&X\\[0.5em]&&&&\color{cyan}*&X\end{bmatrix}

我们枚举最后一列被哪行选了，那么下面那些行就一定确定了，接下来就要解决左上角这个子问题。

（考场上把上面这个图印在脑子里。）

考虑设 g_{i} 为左上角 i\times i 的行列式的值。

g_{0}=1,g_i=\sum_{k=1}^{i} a_{k,i}g_{k-1}\prod_{j=k+1}^i(-a_{j,j-1})

这就可以求出行列式的值了，注意 a_{j,j-1} 前面的负号，每有一个 a_{j,j-1} 逆序对数量就增加 1。

那我们就可以得到特征多项式的递推公式了（注意新的矩阵是 (xI-A)）：

f_i(x)=(x-a_{i,i})f_{i-1}(x)-\sum_{k=1}^{i-1}a_{k,i}f_{k-1}(x)\prod_{j=k+1}^ia_{j,j-1}

其中第一项是因为第 k=i 时 (xI-A)_{k,i}=(x-a_{i,i})，需要特判。

可以简化上式至：

f_i(x)=xf_{i-1}(x)-\sum_{k=1}^{i}a_{k,i}f_{k-1}(x)\prod_{j=k+1}^ia_{j,j-1}

更好写一点。

使用多项式运算就可以 \Theta(n^3) 求出特征多项式。

应用：[ABC323G] Inversion of Tree

给定一个排列 p，定义一棵树上的「逆序边」为 u<v\wedge p_u>p_v，对 k\in[0,n-1] 求出逆序边数量为这些的树的数量。

将非逆序边构成的 \text{Laplacian Matrix} 视为 A，逆序边的 \text{Laplacian Matrix} 视为 B，其实就是要求 \forall k\in[0,n-1],[x^k]|A+xB|。

（这个逆序边很没意思，可以任意规定每条边是否重要。）

朴素的做法是将 x 赋值为 0,1,\cdots,n 跑矩阵树然后得到一个系数方程，用多项式插值或者高斯消元搞一搞，\Theta(n^4)。

考虑到 |A+xB| 长得很像特征多项式，既然那个东西可以 \Theta(n^3) 求，那我们努力往上凑一凑。

我们肯定希望求出 D=B^{-1} 使得 BD=I，那么我们就可以求出 |A+xB|=\frac{|AD+xBD|}{|D|}=\frac{|AD+xI|}{|D|}。

很不幸的，B 不一定有逆元，典型的例子是整张图一个逆序边也没有。

我们考虑采用如下方法：

这样只要没有返回 0 那就是消元成功了。

此时就变成了 |A'+xI|，将 A 取个反算特征多项式即可。

这也是 \Theta(n^3) 求出 |A+xB| 的通用方法。

代码。

参考资料

上海森堡矩阵快速求解行列式

P7776 【模板】特征多项式 题解

特征多项式优化矩阵快速幂

AtCoder Beginner Contest 323G 题解