Algorithms for Hermite and Smith Normal Matrices and Linear Diophantine Equations
- 1 October 1971
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 25 (116) , 897-907
- https://doi.org/10.2307/2004354
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.Keywords
This publication has 8 references indexed in Scilit:
- Equivalent Integer Programs and Canonical ProblemsManagement Science, 1971
- Dynamic Programming Algorithms for the Integer Programming Problem—I: The Integer Programming Problem Viewed as a Knapsack Type ProblemOperations Research, 1968
- Solving equations exactlyJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967
- Exact Solutions of Linear Equations with Rational Coefficients by Congruence TechniquesMathematics of Computation, 1966
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMSProceedings of the National Academy of Sciences, 1965
- An Introduction to the Geometry of Numbers. By J. W. S. Cassels. Pp. 344. DM. 69. 1959. (Springer, Berlin)The Mathematical Gazette, 1961
- A method of computing exact inverses of matrices with integer coefficientsJournal of Research of the National Bureau of Standards, 1952
- An Introduction to Abstract AlgebraNational Mathematics Magazine, 1941