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

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 (1977). MR**0422300**, 10.1090/S0002-9939-1976-0422300-8**[2]**I. Borosh and L. B. Treybig,*Bounds on positive integral solutions of linear Diophantine equations*, Proc. Amer. Math. Soc.**55**(1976), no. 2, 299–304. MR**0396605**, 10.1090/S0002-9939-1976-0396605-3**[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]**Ernst Specker and Volker Strassen (eds.),*Komplexität von Entscheidungsproblemen—ein Seminar (1973/74)*, Springer-Verlag, Berlin-New York, 1976 (German). Lecture Notes in Computer Science, Vol. 43. MR**0478759****[6]**Josef Stoer and Christoph Witzgall,*Convexity and optimization in finite dimensions. I*, Die Grundlehren der mathematischen Wissenschaften, Band 163, Springer-Verlag, New York-Berlin, 1970. MR**0286498**

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