Computing Rational Forms of Integer Matrices

摘要

A new algorithm is presented for finding the Frobenius rational form F ∈ Z~(nxn) of any A ∈ Z~(nxn) which requires an expected number of O(n~4(log n + log ||A||) + n~3(log n + log ||A||)~2) word operations using standard integer and matrix arithmetic (where ||A|| = max_(ij) |A_(ij)|). 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.