0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Perhaps we were meant to assume that, in each inequality, the numerators of the rationals are relatively prime, likewise the denominators. $\endgroup$ Nov 23 '17 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.