Is every matrix similar to a polynomial in a companion matrix? (Q445817)

The paper gives sufficient conditions for a matrix \(A\) of arbitrary size \(n\) over a finite field \(F\) to be of polynomial type i.e. \(\left| F\right| \geq n-2\). The authors also provide an algorithm that, given \( g\in F\left[ X\right] \) and the invariant factors of any \(A\in M_{n}\left( F\right) \), returns the elementary divisors of \(g\left( A\right) \) without computing \(g\left( A\right) \). This results to constructive criteria for \( g\left( A\right) \) to be semisimple, cyclic or diagonizable. Finally, they show that for an integrally closed ring \(R\) with field of fractions \(F\) and companion matrices \(C,D\) the subalgebra \(R\left\langle C,D\right\rangle \) of \(M_{n}\left( R\right) \) is necessarily a free \(R\)-module of rank \(n+\left( n-m\right) \left( n-1\right) \) where \(\;m\) is the degree of \(\gcd \left( f,g\right) \in F\left[ X\right] \) and gives a presentation of \(R\left\langle C,D\right\rangle \) in terms of \(C,D\).