Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

Recently, Frumkin [9] pointed out that none of the well-known algorithms that transform an integer matrix into Smith [16] or Hermite [12] normal form is known to be polynomially bounded in its running time. In fact, Blankinship [3] noticed—as an empirical fact—that intermediate numbers may become quite large during standard calculations of these canonical forms. Here we present new algorithms in which both the number of algebraic operations and the number of (binary) digits of all intermediate numbers are bounded by polynomials in the length of the input data (assumed to be encoded in binary). These algorithms also find the multiplier-matrices K, $U'$ and $K'$ such that $AK$ and $U'AK'$ are the Hermite and Smith normal forms of the given matrix A. This provides the first proof that multipliers with small enough entries exist.