特征多项式

定义一个大小为$ k$矩阵$ M$的特征多项式$ P$要求满足

$$ \sum_{i=0}^k P_iM^i=0$$

其中$ 0$是一个全$ 0$矩阵

Cayley-Hamilton定理

一个矩阵$ P$的特征多项式为

$$P(\lambda)=|\lambda E-M|=\lambda^n+P_1\lambda^{n-1}+P_2\lambda^{n-2}+...+P_n$$

其中$ E$是单位矩阵,$ |\lambda|$表示$ \lambda$的行列式

显然有$P(A)=0$

快速求一般矩阵的特征多项式

暴力插值+消元是$ O(n^4)$的

有$ O(n^3)$的奇妙做法

咕咕咕

常系数线性齐次递推

就是给定转移式$ f_i=\displaystyle\sum_{j=1}^k a_j f_{i-j}$求$ f_n$

$ n \leq 10^9 k \leq 5·10^4$

直接矩阵快速幂是$ k^3 \log n $的，显然无法通过

这类转移矩阵$ M$有一个非常好的性质：其特征多项式$ P(\lambda)=\lambda^k-\lambda^{k-1}a_1-\lambda^{k-2}a_2-..-a_k$

证明

将行列式第一行展开

咕咕咕

食用方法

对于该矩阵的特征多项式式$ P$有$ P(M)=0$

因此有$ M^k=a_1M^{k-1}+a_2M^{k-2}+..+a_k$

这意味着我们可以通过降次将$ M^n$转化成$ b_0+b_1M+b_2M^2+..+b_kM^k$

我们令$ M^n$的系数多项式为$ b$

显然矩阵的乘积等价于对应系数多项式的乘积

即设$ M^x$的系数多项式为$ a$，$ M^y$的系数多项式为$ b$

则$ M^{x+y}$的系数多项式为$ a*b$

初始令$ M$的系数多项式为$ \{0,1,0,0..0\}$然后快速幂即可

诶等等..这样求多项式快速幂的话..多项式的长度不会过长吗..?

回到原特征方程式，我们发现$ P(M)=0$

意味着我们可以对求出来的系数多项式进行任意的加减特征多项式

即我们可以对特征多项式进行取模操作，将系数多项式的长度控制在$ k+1$

计算答案

如果我们用系数多项式化出原矩阵的话复杂度还没有优化到最优

发现我们只是要求一个向量乘上前$ k$个矩阵

而前$ k$个矩阵只有对应位置上有值

因此答案就是$ \displaystyle\sum_{i=0}^k b_if_i$

其中$ b$是$ M^n$的系数多项式的对应位系数

用多项式板子优化复杂度可以达到$ O(n \log n \log k)$