Is every matrix similar to a polynomial in a companion matrix?

Given a field F, an integer n⩾1, and a matrix A∈Mn(F), are there polynomials f,g∈F[X], with f monic of degree n, such that A is similar to g(Cf), where Cf is the companion matrix of f? For infinite fields the answer is easily seen to positive, so we concentrate on finite fields. In this case we give an affirmative answer, provided |F|⩾n-2. Moreover, for any finite field F, with |F|=m, we construct a matrix A∈Mm+3(F) that is not similar to any matrix of the form g(Cf).Of use above, but also of independent interest, is a constructive procedure to determine the similarity type of any given matrix g(Cf) purely in terms of f and g, without resorting to polynomial roots in F or in any extension thereof. This, in turn, yields an algorithm that, given g and the invariant factors of any A, returns the elementary divisors of g(A). It is a rational procedure, as opposed to the classical method that uses the Jordan decomposition of A to find that of g(A).Finally, extending prior results by the authors, we show that for an integrally closed ring R with field of fractions F and companion matrices C,D the subalgebra R〈C,D〉 of Mn(R) is a free R-module of rank n+(n-m)(n-1), where m is the degree of gcd(f,g)∈F[X], and a presentation for R〈C,D〉 is given in terms of C and D. A counterexample is furnished to show that R〈C,D〉 need not be a free R-module if R is not integrally closed. The preceding information is used to study Mn(R), and others, as R[X]-modules.