Portal de Periódicos da CAPES

A bound on solutions of linear integer equalities and inequalities

1978; American Mathematical Society; Volume: 72; Issue: 1 Linguagem: Inglês

10.1090/s0002-9939-1978-0500555-0

1088-6826

Joachim von zur Gathen, Malte Sieveking,

Advanced Graph Theory Research

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.