A sharp bound for solutions of linear Diophantine equations

Borosh, I.; Flahive, M.; Rubin, D.; Treybig, B.

doi:10.1090/S0002-9939-1989-0955458-1

A sharp bound for solutions of linear Diophantine equations
HTML articles powered by AMS MathViewer

by I. Borosh, M. Flahive, D. Rubin and B. Treybig PDF

Proc. Amer. Math. Soc. 105 (1989), 844-846 Request permission

Abstract:

Let $Ax = b$ be an $m \times n$ system of linear equations with rank $m$ and integer coefficients. Denote by $Y$ the maximum of the absolute values of the $m \times m$ minors of the augmented matrix $\left ( {A,b} \right )$. It is proved that if the system has an integral solution, then it has an integral solution $x = \left ( {{x_i}} \right )$ with $\max \left | {{x_i}} \right | \leq Y$. The bound is sharp.

References

E. Bombieri and J. Vaaler, On Siegel’s lemma, Invent. Math. 73 (1983), no. 1, 11–32. MR 707346, DOI 10.1007/BF01393823
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
I. Borosh and L. B. Treybig, Bounds on positive integral solutions of linear Diophantine equations. II, Canad. Math. Bull. 22 (1979), no. 3, 357–361. MR 555166, DOI 10.4153/CMB-1979-045-2
I. Borosh, M. Flahive, and B. Treybig, Small solutions of linear Diophantine equations, Discrete Math. 58 (1986), no. 3, 215–220. MR 831816, DOI 10.1016/0012-365X(86)90138-X

Small solutions of linear diophantine equations

J. W. S. Cassels, An introduction to Diophantine approximation, Cambridge Tracts in Mathematics and Mathematical Physics, No. 45, Cambridge University Press, New York, 1957. MR 0087708
Joachim von zur Gathen and Malte Sieveking, A bound on solutions of linear integer equalities and inequalities, Proc. Amer. Math. Soc. 72 (1978), no. 1, 155–158. MR 500555, DOI 10.1090/S0002-9939-1978-0500555-0
Robert S. Garfinkel and George L. Nemhauser, Integer programming, Series in Decision and Control, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1972. MR 0381688
Ralph E. Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), 451–558. MR 256718, DOI 10.1016/0024-3795(69)90017-2
Christos H. Papadimitriou, On the complexity of integer programming, J. Assoc. Comput. Mach. 28 (1981), no. 4, 765–768. MR 677087, DOI 10.1145/322276.322287