Equivalent linear inequalities system - Coefficients bound?

Question

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

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

a₁,₁x₁+ ··· +a₁,_nx_n ≤ b₁

...

a_m,₁x₁+ ··· +a_m,_nx_n ≤ b_m

And E' an equivalent system, derived from E:

a'₁,₂x₂+ ··· +a'₁,_nx_n ≤ b'₁

...

a'_m,₂x₂+ ··· +a'_m,_nx_n ≤ 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 a_ij and b_i 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!

Answer 1

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|$.