On the complexity of inverting integer and polynomial matrices

An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n × n integer matrix A using $${({n^3(\log||A||+\log \kappa(A)))}^{1+o(1)}}$$ bit operations. Here, $${||A||= \max_{ij}|A_{ij}|}$$ denotes the largest entry in absolute value, $${\kappa(A) := n ||A^{-1}||\,||A||}$$ is the condition number of the input matrix, and the “+o(1)” in the exponent indicates a missing factor $${c_1 {(\log n)}^{c_2}{({\rm loglog} ||A||)}^{c_3}}$$ for positive real constants c 1, c 2, c 3. A variation of the algorithm is presented for polynomial matrices that computes the inverse of a nonsingular n × n matrix whose entries are polynomials of degree d over a field using $${{(n^3d)}^{1+o(1)}}$$ field operations. Both algorithms are randomized of the Las Vegas type: failure may be reported with probability at most 1/2, and if failure is not reported, then the output is certified to be correct in the same running time bound.