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

Various algorithms connected with the computation of the minimal polynomial of an n X n matrix over a field K are presented here. The complexity of the first algorithm, where the complete factorization of the characteristic polynomial is needed, is O(√nn³). It produces the minimal polynomial and all characteristic subspaces of a matrix of size n. Furthermore, an iterative algorithm for the minimal polynomial is presented with complexity O(n³ + n²m²), where m is a parameter of the shift Hessenberg matrix used. It does not require knowledge of the characteristic polynomial. Important here is the fact that the average value of m or m_A is O(log n). Next we are concerned with the topic of finding a cyclic vector for a matrix. We first consider the case where its characteristic polynomial is square-free. Using the shift Hessenberg form leads to an algorithm at cost O(n³ + m²n²). A more sophisticated recurrent procedure gives the result in O(n³) steps. In particular, a normal basis for an extended finite field of size qⁿ will be obtained with deterministic complexity O(n³ + n² log q). Finally, the Frobenius form is obtained with asymptotic average complexity O(n³ log n). All algorithms are deterministic. In all four cases, the complexity obtained is better than for the heretofore best known deterministic algorithm.