# elimination theory – Growth in constraint matrix sizes by eliminating variables in integer programming

Let $$underline{x},underline{y}$$ and $$underline{z}$$ be three sets of integer variables and let the relations be

$$A[underline{x},underline{y}]’leq b$$
$$B[underline{y},underline{z}]’leq c.$$

Rewriting in terms of $$underline{y}$$ we get

$$A_{mbox{left}}underline{x}+b_{mbox{left}}lequnderline{y}leq A_{mbox{right}}underline{x}+b_{mbox{right}}$$

$$B_{mbox{left}}underline{z}+c_{mbox{left}}lequnderline{y}leq B_{mbox{right}}underline{z}+c_{mbox{right}}.$$

Is it right to state the relations between $$underline{x}$$ and $$underline{z}$$ are

$$A_{mbox{left}}underline{x}+b_{mbox{left}}leq A_{mbox{right}}underline{x}+b_{mbox{right}}$$

$$B_{mbox{left}}underline{z}+c_{mbox{left}}leq B_{mbox{right}}underline{z}+c_{mbox{right}}?$$

And so by eliminating $$underline{y}$$ we get

$$C[underline{x},underline{z}]leq d$$

where the number of rows is $$C$$ is bound above in terms of the product of number of rows in $$A$$ and $$B$$.

Is it correct eliminating common variables grows the number of variables multiplicatively?