Computing the Characteristic Polynomial of a Matrix.

Michael Monagan, CECM

Let F be a field and let A be an n by n matrix over F.
Using Gaussian elimination we can compute the determinant of A
in O(n^3) operations over F.  Can we also compute the
characteristic polynomial in O(n^3) operations over F?
The direct ways to compute the characteristic polynomial of A
starting with the characteristic matrix lead to algorithms which 
require O(n^5) arithmetic operations in F.
Evaluation and interpolation leads to an O(n^4) algorithm.
An O(n^3) algorithm transforming A into upper Hessenberg form
leads to an O(n^3) algorithm but if F = Q an exponential growth
in the size of the rational numbers appearing in A.
I will describe a simple deterministic O(n^3) algorithm and
propose it as an answer to a quesiton of Mark van Hoeij:
``What is the best way to compute the characteristic
  polynomial of A over F = GF(q)(t) in Maple?''.