Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A bound on solutions of linear integer equalities and inequalities


Authors: Joachim von zur Gathen and Malte Sieveking
Journal: Proc. Amer. Math. Soc. 72 (1978), 155-158
MSC: Primary 52A40; Secondary 15A39, 90C10
DOI: https://doi.org/10.1090/S0002-9939-1978-0500555-0
MathSciNet review: 0500555
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Consider a system of linear equalities and inequalities with integer coefficients. We describe the set of rational solutions by a finite generating set of solution vectors. The entries of these vectors can be bounded by the absolute value of a certain subdeterminant. The smallest integer solution of the system has coefficients not larger than this subdeterminant times the number of indeterminates. Up to the latter factor, the bound is sharp.


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

  • [1] I. Borosh, A sharp bound for positive solutions of homogeneous linear diophantine equations, Proc. Amer. Math. Soc. 60 (1976), 19-21. MR 0422300 (54:10291)
  • [2] I. Borosh and L. B. Treybig, Bounds on positive integral solutions of linear diophantine equations, Proc. Amer. Math. Soc. 55 (1976), 299-304. MR 0396605 (53:467)
  • [3] -, Bounds on positive integral solutions of linear diophantine equations. II, Texas A & M University, (preprint).
  • [4] S. A. Cook, A proof that the linear diophantine problem is in NP, unpublished manuscript, September 13, 1976.
  • [5] E. Specker and V. Strassen, Komplexität von Entscheidungsproblemen, Lecture Notes in Comput. Sci., vol. 43, Springer, Berlin and New York, 1976. MR 0478759 (57:18232)
  • [6] J. Stoer and C. Witzgall, Convexity and optimization in finite dimensions, I, Grundlehren der math. Wissenschaften, Band 163, Springer, Berlin and New York, 1970. MR 0286498 (44:3707)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 52A40, 15A39, 90C10

Retrieve articles in all journals with MSC: 52A40, 15A39, 90C10


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1978-0500555-0
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society