We could get the characteristic polynomial in O(n^3). First we use Gaussian elimination to reduce the matrix to an upper Hessenberg matrix and the characteristic polynomial won't change. Then we apply La Budde's method to get the characteristic polynomial. Both of the steps cost O(n^3).
Extention:
By applying the method in Bostan and Mori's paper, we could get a faster algorithm to compute the power of a given matrix (computing M^N is equal to evaluating f(x) = x^N mod p(x) (p(x) and M will be mentioned below) at the matrix M. According to the Cayley-Hamilton theorem, if we want to compute M^N and p(M)=O, we just need to compute f(M) and deg(f(x)) < n. By using baby step giant step in some way, we could do this faster.). But it seems too hard for me to understand and implement.
問題概要
compute the characteristic polynomial of a given matrix.
入力
n times n matrix M
n
a_{0,0} a_{0,1} ... a_{0,n-1}
...
a_{n-1,0} a_{n-1,1} ... a_{n-1,n-1}
出力
I denotes a n times n identity matrix.
p(x)=det(x I-M)
p(x) must be monic and deg(p(x))=n
p_0 p_1 ... p_n
制約
2 <= n <= 500, and the elements in matrix are in Z/998244353Z.
yosupo06
commented
3 years ago
(任意) 問題ID: characteristic_polynomial 問題名: characteristic polynomial
(任意) 想定アルゴリズム: Gaussian elimination/(Householder matrix & Hessenberg decomposition) & La Budde's Method (任意) 参考資料: Rizwana Rehman, Ilse C.F. Ipsen. La Budde's Method for Computing Characteristic Polynomials. , Gaussian elimination as similarity transformation.
We could get the characteristic polynomial in O(n^3). First we use Gaussian elimination to reduce the matrix to an upper Hessenberg matrix and the characteristic polynomial won't change. Then we apply La Budde's method to get the characteristic polynomial. Both of the steps cost O(n^3).
Extention: By applying the method in Bostan and Mori's paper, we could get a faster algorithm to compute the power of a given matrix (computing M^N is equal to evaluating f(x) = x^N mod p(x) (p(x) and M will be mentioned below) at the matrix M. According to the Cayley-Hamilton theorem, if we want to compute M^N and p(M)=O, we just need to compute f(M) and deg(f(x)) < n. By using baby step giant step in some way, we could do this faster.). But it seems too hard for me to understand and implement.
問題概要
compute the characteristic polynomial of a given matrix.
入力
n times n matrix M
出力
I denotes a n times n identity matrix.
p(x)=det(x I-M)
p(x) must be monic and deg(p(x))=n
制約
2 <= n <= 500, and the elements in matrix are in Z/998244353Z.