Computing Rational Forms of Integer Matrices

A new algorithm is presented for finding the Frobenius rational form F Zn × nof any A Zn × nwhich requires an expected number of O(n4( n + A ) + n3( n + A )2) word operations using standard integer and matrix arithmetic (where A = ijAij). This substantially improves on the fastest previously known algorithms. The algorithm is probabilistic of the Las Vegas type: it assumes a source of random bits but always produces the correct answer. Las Vegas algorithms are also presented for computing a transformation matrix to the Frobenius form, and for computing the rational Jordan form of an integer matrix.