Just having some difficulties with this system of inequalities... 


We know *E* is a system of **m** linear inequalities of the form:


a1,1x1+ ··· +a1,nxn ≤ b1


...


am,1x1+ ··· +am,nxn ≤ bm


And *E'* an equivalent system, derived from *E*:


a'1,2x2+ ··· +a'1,nxn ≤ b'1


...


a'm,2x2+ ··· +a'm,nxn ≤ b'm


I have proven that given that if *E* has a solution, then so does *E'* and vice-versa, on the set of *R* (real numbers). However, now we suppose that the coefficients *aij* and *bi* in the original system *E* are in fact integers with a maximum absolute value M.


Since the coefficients in the system *E* are integers, then the various coefficients in the system *E'* will be rational numbers, and so can be written in the form *a/b*, where *a* is the numerator and *b* the denominator.


How can I obtain a bound on the absolute values of these numerators and denominators as a function of M? I'm not quite sure which would be the right approach in order to correctly prove it..


Thanks for taking your time!



Equivalent linear inequalities system - Coefficients bound?
There is no such bound. Let's consider the simplest case: a single inequality in one variable:


$$a x \le b$$


For any $c > 0$ this is equivalent to


$$ c a x \le c b$$


But since $c$ is arbitrary, there is no way to bound numerator or denominator of $|c a|$ or $|c b|$.


