Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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: http://dx.doi.org/10.1090/S0025-5718-1971-0301909-X
PII: S 0025-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