学习笔记 矩阵的特征多项式 & 快速矩阵快速幂

定理：相似矩阵特征多项式相同。 证明：$|\rm PAP^{-1}-\lambda E|$ $=|\rm PAP^{-1}-\lambda PP^{-1}|$ $=|\rm (PA-\lambda P)P^{-1}|$ $=|\rm P(A-P^{-1}\lambda P)P^{-1}|$ $=|\rm P(A-\lambda E)P^{-1}|$ $=|\rm P|\times|A-\lambda E|\times |P^{-1}|$ $=|A-\lambda E|$ 考虑如何求出矩阵特征多项式。 朴素的消元方法由于涉及多项式运算，复杂度显然高于 $O(n^3)$。 实对称阵可以相似对角化，但一般数域上的矩阵并不都能相似对角化，但可以消成如下类似对角矩阵的形式。 $ \begin{pmatrix} 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{pmatrix} \quad $ 方法：构造初等矩阵 $\rm P$ 令 $\rm A\leftarrow PAP^{-1}$ 实现消元。 则用 $a_{i+1,i}$ 消 $a_{j,i}(j>i+1)$ 时，左乘和右乘分别相当于进行初等行变换 $R_{j}\leftarrow R_j+kR_{i+1}$ 和初等列变换 $C_{i+1}\leftarrow C_{i+1}-kC_j$，由于 $i<i+1<j$，可以注意到初等列变换不影响已消元部分，初等行变换仅影响当前要消的以及未消元部分。 化成如上矩阵后，可以轻易计算特征多项式。 考虑递推求解前 $i$ 行 $i$ 列的答案多项式 $f_i(x)$。显然边界是 $f_0(x)=1$。 观察矩阵可以发现，选取位于 $a_{1,1},a_{2,2},\cdots,a_{j-1,j-1},a_{j,i},a_{j+1,j},a_{j+2,j+1},\cdots,a_{i,i-1}(1\le j\le i)$ 的元素是唯一有贡献部分，其贡献为 $-f_{j-1}a_{j,i}\prod\limits_{k=j}^{i-1}a_{k+1,k}(j<i)$。后面这部分显然可以直接递推。特别地，对于 $j=i$，有**额外**贡献 $xf_{i-1}$。 于是我们可以 $O(n^3)$ 地计算出矩阵的特征多项式。 用途：写奇怪的 $|\rm A-kE|$ 多点求值板子。 据说可以加速矩阵快速幂，先咕着。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=502,p=998244353; int a[N][N],f[N]; int n,i,j,k,x,y,r,q; template<typename typC> void read(register typC &x) { register int c=getchar(),fh=1; while ((c<48)||(c>57)) { if (c=='-') {c=getchar();fh=-1;break;} c=getchar(); } x=c^48;c=getchar(); while ((c>=48)&&(c<=57)) { x=x*10+(c^48); c=getchar(); } x*=fh; } inline void inc(register int &x,const int y) { if ((x+=y)>=p) x-=p; } inline void dec(register int &x,const int y) { if ((x-=y)<0) x+=p; } inline int ksm(register int x,register int y) { register int r=1; while (y) { if (y&1) r=(ll)r*x%p; x=(ll)x*x%p;y>>=1; } return r; } void calmatrix(int a[N][N],register int n) { register int i,j,k,r; for (i=2;i<=n;i++) { for (j=i;j<=n&&!a[j][i-1];j++); if (j>n) {continue;} if (j>i) { swap(a[i],a[j]);//exit(-1); for (k=1;k<=n;k++) swap(a[k][j],a[k][i]); } r=a[i][i-1]; for (j=1;j<=n;j++) a[j][i]=(ll)a[j][i]*r%p; r=ksm(r,p-2); for (j=i-1;j<=n;j++) a[i][j]=(ll)a[i][j]*r%p; for (j=i+1;j<=n;j++) { r=a[j][i-1]; for (k=1;k<=n;k++) a[k][i]=(a[k][i]+(ll)a[k][j]*r)%p; r=p-r; for (k=i-1;k<=n;k++) a[j][k]=(a[j][k]+(ll)a[i][k]*r)%p; } } } void calpoly(int a[N][N],register int n,int *f) { static int g[N][N]; memset(g,0,sizeof(g)); g[0][0]=1; register int i,j,k,r,rr; for (i=1;i<=n;i++) { r=p-1; for (j=i;j;j--)//第 j 行选第 n 列 { rr=(ll)r*a[j][i]%p; for (k=0;k<j;k++) g[i][k]=(g[i][k]+(ll)rr*g[j-1][k])%p; r=(ll)r*a[j][j-1]%p; } for (k=1;k<=i;k++) inc(g[i][k],g[i-1][k-1]); } memcpy(f,g[n],n+1<<2); // if (n&1) for (i=0;i<=n;i++) if (f[i]) f[i]=p-f[i];//这题特殊（A-kE），否则注释掉 } int main() { read(n);//read(q); for (i=1;i<=n;i++) for (j=1;j<=n;j++) read(a[i][j]); calmatrix(a,n);calpoly(a,n,f); for (i=0;i<=n;i++) printf("%d%c",f[i]," \n"[i==n]); } ```