I am coping Daniel's responses here:

• This is not Mathematica specific but rather related to the field of Symbolic Computation (also know as Computer Algebra). You might consider investigating efficient algorithms for putting symbolic matrices into the rational canonical form (which, I'll add, is not in Mathematica proper; we do have JordanDecomposition but that requires arithmetic over radical extensions of the base field). There is some literature on the topic but there may well be room for algorithmic improvements sufficiently strong as to qualify for dissertation-level work.

• Of course for rational canonical form, or related types of work, Mathematica can be used for reference implementation, experimenting with different approaches, etc.

• There is some work in the past decade or so on symbolic row reduction, in terms of developing efficient methods and new notions of "canonical" forms that might be better suited than older ones for symbolic computation. Check work coauthored by David Jeffrey, e.g. "Fraction-free matrix factors: new forms for LU and QR factors".