Duh! This is apparently called 'Frobenius Normal Form', which handles the case where the polynomial splits (over the rationals) into factors. https://en.wikipedia.org/wiki/Frobenius_normal_form At 10:18 AM 8/3/2017, Henry Baker wrote:

Given a square matrix M (over the integers, e.g.), is there a standard algorithm for 'companionization' -- i.e., rational reduction to companion matrix form?

Clearly, the initial and final states are representable, because p(x)=|M-xI|, so I would imagine that such a procedure is possible, but I've never encountered it.