Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Algorithms for Hermite and Smith normal matrices and linear Diophantine equations


Author: Gordon H. Bradley
Journal: Math. Comp. 25 (1971), 897-907
MSC: Primary 65F30
DOI: https://doi.org/10.1090/S0025-5718-1971-0301909-X
MathSciNet review: 0301909
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: New algorithms for constructing the Hermite normal form (triangular) and Smith normal form (diagonal) of an integer matrix are presented. A new algorithm for determining the set of solutions to a system of linear diophantine equations is presented. A modification of the Hermite algorithm gives an integer-preserving algorithm for solving linear equations with real-valued variables. Rough bounds for the number of operations are cubic polynomials involving the order of the matrix and the determinant of the matrix. The algorithms are valid if the elements of the matrix are in a principal ideal domain.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1971-0301909-X
Keywords: Hermite normal form, Smith normal form, linear diophantine equations, integer-preserving Gaussian elimination, integer matrix algorithm
Article copyright: © Copyright 1971 American Mathematical Society