Reduction of Smith normal form transformation matrices (Q2487958): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 08:20, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reduction of Smith normal form transformation matrices |
scientific article |
Statements
Reduction of Smith normal form transformation matrices (English)
0 references
17 August 2005
0 references
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.
0 references
Smith normal form
0 references
lattice basis reduction
0 references
linear Diophantine equations
0 references
matrices of integers
0 references
reduction matrices
0 references
algorithm
0 references
numerical results
0 references