Asymptotically fast triangularization of matrices over rings

Abstract

This paper considers the problems of triangularizing and diagonalizing matrices over rings, with particular emphasis on the integral case. It begins with a description of fast algorithms for the computation of Hermite and Smith normal forms of integer matrices. Then it shows how to apply fast matrix multiplication techniques to the problem of triangularizing a matrix over a ring using elementary column operations. These general results lead to an algorithm for triangularizing integer matrices that has a faster running time than the known Hermite normal form algorithms. The triangular matrix that is computed has small entries like the Hermite normal form, and will suffice for many applications.