特征多项式。暂时不知道有什么用处。
特征多项式
矩阵
\[A= \left( \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{matrix} \right) \]的特征多项式定义为
\[\det(\lambda I-A)= \left( \begin{matrix} \lambda-a_{11} & -a_{12} & \cdots & -a_{1n}\\ -a_{21} & \lambda-a_{22} & \cdots & -a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ -a_{n1} & -a_{n2} & \cdots & \lambda-a_{nn} \end{matrix} \right) \]求解
对称矩阵显然是可以对角化的，然而一般的矩阵不一定可以对角化，但是一定可以消成上 Hessenberg 矩阵：
\[\left( \begin{matrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n}\\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n}\\ & a_{32} & a_{33} & \cdots & a_{3n}\\ & & a_{43} & \cdots & a_{4n}\\ \vdots & \vdots & \vdots & \ddots &\vdots\\ & & \cdots & a_{nn-1} & a_{nn} \end{matrix} \right) \]考虑化为相似矩阵的一般方法：构造矩阵 \(P\)，并令 \(A\leftarrow PAP^{-1}\) 完成消元。用 \(a_{i+1,i}\) 消掉 \(a_{j,i}(j>i+1)\) 时，相当于分别在第 \(j\) 行加上 \(k\) 个 \(i+1\) 行，并在第 \(i+1\) 列减去 \(k\) 个第 \(j\) 列。
消元成上 Hessenberg 矩阵之后，考虑如何计算。记 \(A_i\) 为保留矩阵前 \(i\) 行 \(i\) 列剩下的矩阵，并有 \(p_i(x)=\det(xI_i-A_i)\)，边界为 \(p_0(x)=1\)。
求解行列式的时候，我们选取 \(0\) 最多的一行/列余子式展开。这里我们展开最后一行，那么我们有公式：
\[p_i=(x-a_{i,i})p_{i-1}-\sum_{j=1}^{i-1}a_{i-j,i}\left(\prod_{k=i-m+1}^ia_{k,k-1}\right)p_{i-j-1} \]即可 \(O(n^3)\) 计算。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int mod=998244353;
int n,a[510][510],g[510][510],ans[510];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
for(int i=2;i<=n;i++){
int j=i;
while(j<=n&&!a[j][i-1])j++;
if(j>n)continue;
if(j>i){
for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);
for(int k=1;k<=n;k++)swap(a[k][j],a[k][i]);
}
int ret=a[i][i-1];
for(j=1;j<=n;j++)a[j][i]=1ll*a[j][i]*ret%mod;
ret=qpow(ret,mod-2);
for(j=i-1;j<=n;j++)a[i][j]=1ll*a[i][j]*ret%mod;
for(j=i+1;j<=n;j++){
ret=a[j][i-1];
for(int k=1;k<=n;k++)a[k][i]=(a[k][i]+1ll*a[k][j]*ret)%mod;
ret=mod-ret;
for(int k=i-1;k<=n;k++)a[j][k]=(a[j][k]+1ll*a[i][k]*ret)%mod;
}
}
g[0][0]=1;
for(int i=1;i<=n;i++){
int ret=mod-1;
for(int j=i;j>=1;j--){
int tmp=1ll*ret*a[j][i]%mod;
for(int k=0;k<j;k++)g[i][k]=(g[i][k]+1ll*tmp*g[j-1][k])%mod;
ret=1ll*ret*a[j][j-1]%mod;
}
for(int j=1;j<=i;j++)g[i][j]=(g[i][j]+g[i-1][j-1])%mod;
}
for(int i=0;i<=n;i++)ans[i]=g[n][i];
for(int i=0;i<=n;i++)printf("%d ",ans[i]);putchar('\n');
return 0;
}
Cayley-Hamilton定理
对于任意 \(n\) 阶矩阵 \(A\) ，特征多项式为 \(f(\lambda)\) ，则必有 \(f(A)=0\)。
标签：matrix,特征,多项式,矩阵,int,cdots,vdots From： https://www.cnblogs.com/gtm1514/p/17040810.html