Various algorithms connected with the computation of the minimal polynomial of an n × 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(√nn3). 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^3 + n^2m^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 average value of m or mA 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^3 + m^2n^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 qn will be obtained with deterministic complexity O(n^3 + n^2log q). Finally, the Frobenius form is obtained with asymptotic average complexity O(n^3log n). All algorithms are deterministic. In all four cases, the complexity obtained is better than for the heretofore best known deterministic algorithm.