特征多项式(特征多项式怎么求出来的)

一个比较慢的做法

　　你要知道矩阵的特征多项式是什么。

　　直接消元就可以了。

　　时间复杂度O(n5)O(n5)或O(n4)O(n4)。

一个稍微快一点的做法

　　观察到特征多项式的次数是nn。

　　我们就可以插值。

　　具体来说，先求出当x=0…nx=0…n时特征多项式对应的点值，然后直接用拉格朗日插值插出来。

　　时间复杂度O(n4)O(n4)

一个更快的做法

　　有一个性质相似矩阵的特征多项式相同。

　　所以可以把这个矩阵相似到一个可以快速求特征多项式的矩阵再求。

　　怎么相似呢？

　　AA和BB相似意味着A=PBP−1A=PBP−1

　　假设当前矩阵是AA。在消元过程中会左乘一个初等矩阵PP，这时在AA的右边乘上这个初等矩阵的逆矩阵P−1P−1，得到PAP−1PAP−1。

　　显然这个矩阵和矩阵AA相似。

　　我们只能把所有i≥j+2i≥j+2的部分消成00，也就是说会消成一个上海森堡矩阵。

　　接下来就要快速求一个上海森堡矩阵的特征多项式。

　　上海森堡矩阵长这样

⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜a1,1a2,10⋮0a1,2a2,2a3,2⋮0a1,3a2,3a3,3⋮0⋯⋯⋯⋱⋯a1,na2,na3,n⋮an,n⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟

(a1,1a1,2a1,3⋯a1,na2,1a2,2a2,3⋯a2,n0a3,2a3,3⋯a3,n⋮⋮⋮⋱⋮000⋯an,n)

　　设右下角i×ii×i的矩阵的特征多项式为fifi。

　　考虑对第一列展开。

　　那么肯定是连续的消掉若干个第二行后再消掉第一行。

　　即

fi=ai,ifi+1−ai+1,iai,i+1fi+2+ai+1,iai+2,i+1ai,i+2fi+3+⋯

fi=ai,ifi+1−ai+1,iai,i+1fi+2+ai+1,iai+2,i+1ai,i+2fi+3+⋯

　　注意到只有主对角线上的元素一次的，其他都是常数的，所以前面的系数的次数最多是11。

　　这样可以从后往前求出所有fifi。时间复杂度是O(n3)O(n3)。

　　这样我们就得到了一个时间复杂度是O(n3)O(n3)的优秀做法。

　　这个做法有什么用？

　　可以去卡别人。比如用O(n3+n2logm)O(n3+n2log⁡m)的做法卡O(n3logm)O(n3log⁡m)的矩阵快速幂。