Computing rational forms of integer matrices (Q1864883)

A new Las Vegas type algorithm is presented for finding the Frobenius rational form of any \(n\times n\) integer matrix. The expected number of word operations is \(O(n^4(\log n+\log \|A\|)+ n^3(\log n+\log \|A\|)^2)\), where \(\|A\|=\max |A_{ij} |\). Las Vegas algorithms are also introduced to compute a transformation matrix to the Frobenius form, and to compute the rational Jordan form of an integer matrix.