# Equivalent linear inequalities system - Coefficients bound?

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!

## 1 Answer

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

• Perhaps we were meant to assume that, in each inequality, the numerators of the rationals are relatively prime, likewise the denominators. Nov 23, 2017 at 6:11