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?''.