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

TLDR

Recently, Frumkin noted that no known algorithm for converting an integer matrix into Smith or Hermite normal form runs in polynomial time, and Blankinship observed that intermediate numbers can become large during standard calculations. The authors propose new algorithms that bound both the number of algebraic operations and the size of intermediate numbers by polynomials in the binary input length. The algorithms compute multiplier matrices K, U′, and K′ so that AK and U′AK′ yield the Hermite and Smith normal forms of the input matrix. These algorithms establish the first proof that multiplier matrices with sufficiently small entries exist.

Abstract

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.