特征多项式_成型笔记

线性代数。

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

本篇同时作为 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$ 个值然后拉格朗日插值。）

求解

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

• 利用初等矩阵消元为上海森堡矩阵。

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

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

• 将第 $i$ 行加上第 $j$ 行的 $k$ 倍后，将第 $j$ 列加上第 $i$ 列的 $-k$ 倍。
• 交换第 $i$ 行和第 $j$ 行后，交换第 $i$ 列与第 $j$ 列。

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

$$\begin{bmatrix} 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_{k,k-1}$ 前面的负号，每有一个 $a_{k,k-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]$ 求出逆序边数量为这些的树的数量。

$n\le 500,4\text{ seconds}$。

将非逆序边构成的 $\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$ 不一定有逆元，典型的例子是整张图一个逆序边也没有。

我们考虑采用如下方法：

• 同时对 $A,B$ 进行消元，我们不再寻找非空的一行交换过来，而是寻找非空的一列交换过来。
• 若 $B$ 这一行已经全空（找不到合法列）则将这一整行乘上 $x$（将 $A$ 这一行复制过来，同时 $A$ 清空）然后把前面消个元接着找。
• 若已经乘过 $n$ 次以上说明答案全为 $0$。

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

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

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

代码。

参考资料

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

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

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

AtCoder Beginner Contest 323G 题解