Computing rational forms of integer matrices
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.
scientific article; zbMATH DE number 1886749
scientific article