Reduction of Smith normal form transformation matrices (Q2487958)

A matrix \(A\in \mathbb{Z}^{m\times n}\) can be reduced to Smith normal form \(C\) by unimodular matrices \(U\in GL_m(\mathbb{Z})\) and \(V\in GL_n(\mathbb{Z})\) such that \(A=UCV\). If \(A\) has rank \(r\), then \(C\) is zero except for the first \(r\) diagonal elements which satisfy: \(C_{ii}\) divides \(C_{i+1,i+1}\), \(i=1,\dots,r-1\). The \(U\) and \(V\) are not unique. For the application to the solution of linear Diophantine equations it is essential that the entries of \(U\) and \(V\) are as small as possible. In this paper, the sets of reduction matrices \(U\) and \(V\) are characterized, and an algorithm is given to reduce the size of a given pair of reduction matrices. The algorithm is based on optimization techniques studied by \textit{C. P. Schnorr, M. Euchner} [Math. Program. 66, No. 2(A), 181--199 (1994; Zbl 0829.90099)] and \textit{A. K. Lenstra, H. W. Lenstra} jun. and \textit{László Lovász} [Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)]. Numerical results for a wide class of test matrices illustrate the performance of the algorithm.