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 Free Access

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.

**[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)**

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