faster algorithms for the characteristic polynomial
A new randomized algorithm is presented for computing the characteristic polynomial of an n x n matrix over a field. Over a suffciently large field the asymptotic expected complexity of the algorithm is O ( n ? )field operations, improving by a factor of log n on the worst case complexity of Keller-Gehrig's algorithm [11].
characteristic polynomial complexity frobenius normal form