On the computation of minimal polynomials, cyclic vectors, and Frobenius forms (Q1361771)

Algorithms related to the computation of the minimal polynomial of an \(n\times n\) matrix over a field \(K\) are introduced. The complexity of the first algorithm, where the complete factorization of the characteristic polynomial is needed, is \(O(\sqrt n\cdot n^3)\). An iterative algorithm for finding the minimal polynomial has complexity \(O(n^3+ n^2m^2)\), where \(m\) is a parameter of the shift Hessenberg matrix used. The method does not require the knowledge of the characteristic polynomial. The average value of \(m\) is \(O(\log n)\). Next methods are discussed for finding a cyclic vector for a matrix. The authors first consider the case when its characteristic polynomial is squarefree. Using the shift Hessenberg form leads to an algorithm at cost \(O(n^3+ n^2m^2)\). A more sophisticated recurrent procedure gives the result in \(O(n^3)\) steps. In particular, a normal basis for an extended finite field of size \(q^n\) will be obtained with complexity \(O(n^3+ n^2\log q)\). Finally, the Frobenius form is obtained with asymptotic average complexity \(O(n^3\log n)\).