A bound on solutions of linear integer equalities and inequalities
HTML articles powered by AMS MathViewer
- by Joachim von zur Gathen and Malte Sieveking PDF
- Proc. Amer. Math. Soc. 72 (1978), 155-158 Request permission
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
- I. Borosh, A sharp bound for positive solutions of homogeneous linear Diophantine equations, Proc. Amer. Math. Soc. 60 (1976), 19–21 (1977). MR 422300, DOI 10.1090/S0002-9939-1976-0422300-8
- 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 396605, DOI 10.1090/S0002-9939-1976-0396605-3 —, Bounds on positive integral solutions of linear diophantine equations. II, Texas A & M University, (preprint). S. A. Cook, A proof that the linear diophantine problem is in NP, unpublished manuscript, September 13, 1976.
- Ernst Specker and Volker Strassen (eds.), Komplexität von Entscheidungsproblemen—ein Seminar (1973/74), Lecture Notes in Computer Science, Vol. 43, Springer-Verlag, Berlin-New York, 1976 (German). MR 0478759
- 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
Additional Information
- © Copyright 1978 American Mathematical Society
- 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