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?)

  • [1] Erwin H. Bareiss, Sylvester’s identity and multistep integer-preserving Gaussian elimination, Math. Comp. 22 (1968), 565–578. MR 0226829, 10.1090/S0025-5718-1968-0226829-0
  • [2] W. A. Blankinship, ``Algorithm 287, matrix triangulation with integer arithmetic [F1],'' Comm. ACM, v. 9, 1966, p. 513.
  • [3] W. A. Blankinship, ``Algorithm 288, solution of simultaneous linear diophantine equations [F4],'' Comm. ACM, v. 9, 1966, p. 514.
  • [4] J. Boothroyd, ``Algorithm 290, linear equations, exact solutions,'' Comm. ACM, v. 9, 1966, pp. 383-384.
  • [5] I. Borosh and A. S. Fraenkel, Exact solutions of linear equations with rational coefficients by congruence techniques, Math. Comp. 20 (1966), 107–112. MR 0187379, 10.1090/S0025-5718-1966-0187379-1
  • [6] Gordon H. Bradley, Equivalent integer programs and canonical problems, Management Sci. 17 (1971), 354–366. MR 0270746
  • [7] Gordon H. Bradley, Algorithm and bound for the greatest common divisor of 𝑛 integers, Comm. ACM 13 (1970), 433–436. MR 0294244
  • [8] Gordon H. Bradley, Algorithm and bound for the greatest common divisor of 𝑛 integers, Comm. ACM 13 (1970), 433–436. MR 0294244
  • [9] G. H. Bradley & P. N. Wahi, An Algorithm for Integer Linear Programming: A Combined Algebraic and Enumeration Approach, Report #29, Administrative Sciences Dept., Yale University, New Haven, Conn., 1969.
  • [10] J. W. S. Cassels, An introduction to the geometry of numbers, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete, Bd. 99 Springer-Verlag, Berlin-Göttingen-Heidelberg, 1959. MR 0157947
  • [11] L. Fox, An introduction to numerical linear algebra, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436
  • [12] C.-E. Fröberg & A. Sundström, ``Contribution no. 20, Smith's normal form,'' Nordisk Tidskr. Informations-Behandling (BIT), v. 7, 1967, pp. 163-169.
  • [13] F. R. Gantmaher, Teoriya matric, Gosudarstv. Izdat. Tehn.-Teor. Lit., Moscow, 1953 (Russian). MR 0065520
  • [14] R. E. Gomory, On the relation between integer and noninteger solutions to linear programs, Proc. Nat. Acad. Sci. U.S.A. 53 (1965), 260–265. MR 0182454
  • [15] R. H. González-Zubieta, On Some Aspects of Integer Linear Programming, Technical Report #16, Center for Operations Res., M.I.T., Cambridge, Mass., 1965.
  • [16] C. Hermite, ``Sur l'introduction des variables continues dans la théorie des nombres,'' J. Reine Angew. Math., v. 41, 1851, pp. 191-216.
  • [17] T. C. Hu and R. D. Young, Integer programming and network flows, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0263420
  • [18] Nathan Jacobson, Lectures in abstract algebra. Vol. II. Linear algebra, D. Van Nostrand Co., Inc., Toronto-New York-London, 1953. MR 0053905
  • [19] R. E. Kalman, P. L. Falb, and M. A. Arbib, Topics in mathematical system theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1969. MR 0255260
  • [20] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456
  • [21] Cyrus Colton MacDuffee, An Introduction to Abstract Algebra, John Wiley & Sons, Inc., New York, 1940. MR 0003591
  • [22] Morris Newman, Solving equations exactly, J. Res. Nat. Bur. Standards Sect. B 71B (1967), 171–179. MR 0226834
  • [23] J. Barkley Rosser, A method of computing exact inverses of matrices with integer coefficients, J. Research Nat. Bur. Standards 49 (1952), 349–358. MR 0055796
  • [24] Jeremy F. Shapiro, Dynamic programming algorithms for the integer programming problem. I. The integer programming problem viewed as a knapsack type problem, Operations Res. 16 (1968), 103–121. MR 0232596
  • [25] David A. Smith, A basis algorithm for finitely generated abelian groups, Math. Algorithms 1 (1966), 13–26. MR 0251136
  • [26] H. J. S. Smith, ``On systems of linear indeterminate equations and congruences,'' Philos. Trans. Roy. Soc. London Ser. A, v. 151, 1861, pp. 293-326.
  • [27] H. W. Turnbull & A. C. Aitken, An Introduction to the Theory of Canonical Matrices, Blackie, London, 1932.
  • [28] B. L. van der Waerden, Moderne Algebra. Vol. 2, Springer, Berlin, 1931; English transl., Ungar, New York, 1950.
  • [29] L. A. Zadeh & E. Polak, Systems Theory, McGraw-Hill, New York, 1969.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

Keywords: Hermite normal form, Smith normal form, linear diophantine equations, integer-preserving Gaussian elimination, integer matrix algorithm
Article copyright: © Copyright 1971 American Mathematical Society