ON THE COMPUTATION OF MINIMAL POLYNOMIALS, CYCLIC VECTORS, AND FROBENIUS FORMS

Various algorithms connected with the computation of the minimal polyn omial of an n x n matrix over a field K are presented here. The comple xity of the first algorithm, where the complete factorization of the c haracteristic polynomial is needed, is O(root nn(3)). It produces the minimal polynomial and all characteristic subspaces of a matrix of siz e n. Furthermore, an iterative algorithm for the minimal polynomial is presented with complexity O(n(3) + n(2)m(2)), 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 ave rage value of m or m(A) is O(log n). Next we are concerned with the to pic of finding a cyclic vector for a matrix. We first consider the cas e where its characteristic polynomial is square-free. Using the shift Hessenberg form leads to an algorithm at cost O(n(3) + m(2)n(2)). A mo re 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 deterministic complexity O(n(3) + n(2) log q ). Finally, the Frobenius form is obtained with asymptotic average com plexity O(n(3)logn). AU algorithms are deterministic. In all four case s, the complexity obtained is better than for the heretofore best know n deterministic algorithm. (C) Elsevier Science Inc., 1997.