特征多项式_成型笔记
JueFan 一只绝帆

线性代数。

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

本篇同时作为 ABC323G 的题解。

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

特征值和特征向量

设 VV 是 FF 上的线性空间,TT 是 VV 上的线性变换。若存在 FF 中的 λ\lambda 与 VV 中的 非零向量 ξ\xi,使得:

Tξ=λξT\xi=\lambda\xi

则称 λ\lambda 为 TT 的一个 特征值,而 ξ\xi 为 TT 的 属于特征值 λ\lambda 的一个特征向量。

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

特征分解

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

对上述定理的理解:

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

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

原理:A2=PΛP−1PΛP−1=PΛ2P−1A^2=P\Lambda P^{-1}P\Lambda P^{-1}=P\Lambda^2P^{-1},同理 An=PΛnP−1A^n=P\Lambda^nP^{-1},由于 Λ\Lambda 是对角阵(各向量线性无关),所以只需要将每个元素 nn 次幂即可。

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

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

特征多项式

相似矩阵:对可逆矩阵 PP,B=PAP−1B=PAP^{-1} 称作 AA 的相似矩阵,记作 A∼BA\sim B。

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

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

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

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

Tξ=λξ  ⟺  Tξ=λIξ  ⟺  (λI−T)ξ=0⃗T\xi=\lambda\xi\iff T\xi=\lambda I\xi\iff (\lambda I-T)\xi=\vec 0

由于 ξ≠0⃗\xi\ne\vec 0,所以 ∣λI−T∣=0|\lambda I-T|=0。

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

∣xI−PAP−1∣=∣xI(PP−1)−PAP−1∣=∣PxIP−1−PAP−1∣=∣P∣∣xI−A∣∣P−1∣=∣xI−A∣\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=PxxIP=xP=Px,所以 xIxI 是具有交换律的。

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

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

求解

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

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

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

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

  • 将第 ii 行加上第 jj 行的 kk 倍后,将第 jj 列加上第 ii 列的 −k-k 倍。
  • 交换第 ii 行和第 jj 行后,交换第 ii 列与第 jj 列。

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

[a1,1a1,2a1,3a1,4a1,5a2,1a2,2a2,3a2,4a2,5a3,2a3,3a3,4a3,5a4,3a4,4a4,5a5,4a5,5]\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

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

  • 递推计算矩阵的特征多项式。

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

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

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

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

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

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

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

∑σ∑i=1n(−1)τ(σ)∏i=1nai,σi\sum\limits_\sigma\sum\limits_{i=1}^n(-1)^{\tau(\sigma)}\prod\limits_{i=1}^na_{i,\sigma_i}

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

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

[⋮⋮⋮⋮⋮⋮∗∗∗∗∗X∗∗∗∗XXXX∗∗∗X∗X]\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}

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

(考场上把上面这个图印在脑子里。)

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

g0=1,gi=∑k=1iak,igk−1∏j=k+1i(−aj,j−1)g_{0}=1,g_i=\sum_{k=1}^{i} a_{k,i}g_{k-1}\prod_{j=k+1}^i(-a_{j,j-1})

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

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

fi(x)=(x−ai,i)fi−1(x)−∑k=1i−1ak,ifk−1(x)∏j=k+1iaj,j−1f_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=ik=i 时 (xI−A)k,i=(x−ai,i)(xI-A)_{k,i}=(x-a_{i,i}),需要特判。

可以简化上式至:

fi(x)=xfi−1(x)−∑k=1iak,ifk−1(x)∏j=k+1iaj,j−1f_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}

更好写一点。

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

应用:[ABC323G] Inversion of Tree

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

n≤500,4 secondsn\le 500,4\text{ seconds}。

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

(这个逆序边很没意思,可以任意规定每条边是否重要。)

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

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

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

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

我们考虑采用如下方法:

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

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

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

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

代码。

参考资料

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

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

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

AtCoder Beginner Contest 323G 题解

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量