Algorithms for Hermite and Smith normal matrices and linear Diophantine equations
HTML articles powered by AMS MathViewer
- by Gordon H. Bradley PDF
- Math. Comp. 25 (1971), 897-907 Request permission
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
- Erwin H. Bareiss, Sylvester’s identity and multistep integer-preserving Gaussian elimination, Math. Comp. 22 (1968), 565–578. MR 226829, DOI 10.1090/S0025-5718-1968-0226829-0 W. A. Blankinship, “Algorithm 287, matrix triangulation with integer arithmetic [F1],” Comm. ACM, v. 9, 1966, p. 513. W. A. Blankinship, “Algorithm 288, solution of simultaneous linear diophantine equations [F4],” Comm. ACM, v. 9, 1966, p. 514. J. Boothroyd, “Algorithm 290, linear equations, exact solutions,” Comm. ACM, v. 9, 1966, pp. 383-384.
- I. Borosh and A. S. Fraenkel, Exact solutions of linear equations with rational coefficients by congruence techniques, Math. Comp. 20 (1966), 107–112. MR 187379, DOI 10.1090/S0025-5718-1966-0187379-1
- Gordon H. Bradley, Equivalent integer programs and canonical problems, Management Sci. 17 (1971), 354–366. MR 270746, DOI 10.1287/mnsc.17.5.354
- Gordon H. Bradley, Algorithm and bound for the greatest common divisor of $n$ integers, Comm. ACM 13 (1970), 433–436. MR 0294244, DOI 10.1145/362686.362694
- Gordon H. Bradley, Algorithm and bound for the greatest common divisor of $n$ integers, Comm. ACM 13 (1970), 433–436. MR 0294244, DOI 10.1145/362686.362694 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.
- 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
- L. Fox, An introduction to numerical linear algebra, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436 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.
- F. R. Gantmaher, Teoriya matric, Gosudarstv. Izdat. Tehn.-Teor. Lit., Moscow, 1953 (Russian). MR 0065520
- 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 182454, DOI 10.1073/pnas.53.2.260 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. C. Hermite, “Sur l’introduction des variables continues dans la théorie des nombres,” J. Reine Angew. Math., v. 41, 1851, pp. 191-216.
- 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
- Nathan Jacobson, Lectures in abstract algebra. Vol. II. Linear algebra, D. Van Nostrand Co., Inc., Toronto-New York-London, 1953. MR 0053905
- 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
- Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
- Cyrus Colton MacDuffee, An Introduction to Abstract Algebra, John Wiley & Sons, Inc., New York, 1940. MR 0003591
- Morris Newman, Solving equations exactly, J. Res. Nat. Bur. Standards Sect. B 71B (1967), 171–179. MR 226834
- 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
- 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 232596, DOI 10.1287/opre.16.1.103
- David A. Smith, A basis algorithm for finitely generated abelian groups, Math. Algorithms 1 (1966), 13–26. MR 251136 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. H. W. Turnbull & A. C. Aitken, An Introduction to the Theory of Canonical Matrices, Blackie, London, 1932. B. L. van der Waerden, Moderne Algebra. Vol. 2, Springer, Berlin, 1931; English transl., Ungar, New York, 1950. L. A. Zadeh & E. Polak, Systems Theory, McGraw-Hill, New York, 1969.
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Math. Comp. 25 (1971), 897-907
- MSC: Primary 65F30
- DOI: https://doi.org/10.1090/S0025-5718-1971-0301909-X
- MathSciNet review: 0301909