<p>I think this upper bound is tight. As an example, consider the following system</p>

<p>\begin{align*}
+x_0 &amp; +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
+x_0 &amp; +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
+x_0 &amp; +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
+x_0 &amp; +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
-x_0 &amp; +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
-x_0 &amp; +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
-x_0 &amp; -\frac{3}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
-x_0 &amp; -\frac{3}{2} x_1 -\frac{7}{4} x_2  \le 0 \\
\end{align*}</p>

<p>It has 8 inequalities. Though some of them are identical, it is not a problem since we do not remove redundant constraints. One can also add dummy variables to make them different. Reducing $x_0$, we obtain system with 16 inequalities. Then, reducing $x_1$, we obtain system with $64$ inequalities.</p>

<p>More generally, let $S_{n}^k$ denote the following system of inequalities over $x_0, x_1, \ldots, x_{k - 1}$. Here we assume that $k \le n, n\ge 2$. There will be $2^n$ inequalities in $S_{n}^ k$. Take any $m \in\{1, 2, \ldots, 2^n\}$.  Let $m^{th}$ inequality of $S_{n}^ k$ be
$$\alpha^m_0 x_0 + \ldots + \alpha^m_{k - 1} x_{k - 1} \le 0,$$
where
$$\alpha^m_i = \begin{cases} 2^{-i} &amp; \mbox{if $m \le 2^n - 2^{n - i - 1}$}, \\ -2 + 2^{-i} &amp; \mbox{otherwise.} \end{cases}$$</p>

<p>Here we use a restriction mentioned above : provided $k\le n$, we have that $2^{n - i - 1}$ is an integer. </p>

<p>For example, system above is $S_{3}^3$. It is easy to verify that if we eliminate $x_0$ from $S_{n} ^k$, we obtain $S_{2n - 2} ^{k - 1}$. Indeed, when we eliminate $x_0$, we add up all the inequalities from the first half with all the inequalities from the second half.  Thus we get $2^{n - 1} \cdot 2^{n - 1} = 2^{2n - 2}$ inequalities. What happens with $x_i$ for $i &gt; 0$? In the first $$2^{n - 1} \cdot (2^{n - 1} - 2^{n - i - 1}) = 2^{2n - 2} - 2^{2n - 2 - i} = 2^{2n - 2} - 2^{(2n - 2) - (i - 1) - 1}$$ inequalities a coefficient before $x_i$ will be $2^{-i} + 2^{-i} = 2^{-(i - 1)}$. In the last $2^{-i} + (-2 + 2^{-i}) =  2^{(2n - 2) - (i - 1) - 1}$ inequalities a coefficient before $x_i$ will be $2^{-i} + (-2 + 2^{-i}) = -2 + 2^{-(i - 1)}$. This is $S_{2n - 2}^{k - 1}$, but over variables $x_1, \ldots, x_{k - 1}$. Since, $2n - 2 \ge n - 1 \ge k - 1$, a restriction on the number of variables is also preserved.</p>

<p>Further, if we eliminate $x_1$, we obtain $S_{4n - 6}^{k - 2}$, and so on. After $d$ steps we will have $S^{k - d}_{2^d n - (2^{d + 1} - 2)}$. The latter has exactly
$$2^{2^d n - (2^{d + 1} - 2)} = N^{2^d}/ 2^{2^{d + 1} - 2}$$
inequalities, where $N = 2^n$ is the number of inequalities of the initial system.</p>

CC BY-SA 3.0
2018-04-05T20:56:35.790Z
Thank you very much. However, when I iterated Fourier-Motzkin 3 times from this original system of inequalities, I ended up with a system containing 1024 (the right number) inequalities all with a positive coefficient in column 3, thus the next step of elimination yields an empty set. Maybe I implemented it wrong.
David Monniaux
CC BY-SA 3.0
2018-04-06T21:46:32.567Z
Sorry, but do you  mean a system from the beginning of my answer? Applying Fourier-Motzkin 3 times elimininates all the variables in it; maybe I'm missing something?
Sasha Kozachinskiy
CC BY-SA 3.0
2018-04-08T06:34:54.737Z
I created a system with 8 inequalities and 10 variables according to these formulas and projected it 3 times. The last system I get has 1024 inequalities, but they all have a positive component on the next variable so the next system has 0 inequalities. Maybe I implemented something wrong.
David Monniaux
CC BY-SA 3.0
2018-04-08T08:56:20.760Z
As it turns out, my answer works only when the number of variables is at most logarithm of the number of inequalities, i.e., $k\le n$. This is because in my argument I use a fact that $2^{n - i - 1}$ is an integer. Modified my answer to make it explicit.
Sasha Kozachinskiy
CC BY-SA 3.0
2018-04-03T22:37:18.007Z
2018-04-08T08:51:00.157Z
2018-04-08T08:51:00.157Z
Sasha Kozachinskiy
<p>One round of <a href="https://en.m.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination" rel="nofollow noreferrer">Fourier-Motzkin elimination</a> may yield <span class="math-container">$n^2/4$</span> inequalities where <span class="math-container">$n$</span> is the original number of linear inequalities, whence an upper bound of <span class="math-container">$n^{2^d}/2^{2^{d+1}-2}$</span> for <span class="math-container">$d$</span> rounds of elimination without removal of redundant constraints.</p>

<p>I'm wondering whether it is possible to meet this upper bound.</p>

<p>(Note: this is a distinct question from that of counting the number of true faces in a projection, that is, after removal of redundant constraints, for which McMullen's upper bound provides a tighter bound.)</p>

<linear-programming><polytope>
Reaching the double exponential upper bound in Fourier-Motzkin elimination
David Monniaux
# Reaching the double exponential upper bound in Fourier-Motzkin elimination

(Asked by: username_0 on 2018-04-03)

One round of [Fourier-Motzkin elimination](https://en.m.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination) may yield $n^2/4$ inequalities where $n$ is the original number of linear inequalities, whence an upper bound of $n^{2^d}/2^{2^{d+1}-2}$ for $d$ rounds of elimination without removal of redundant constraints.

I'm wondering whether it is possible to meet this upper bound.

(Note: this is a distinct question from that of counting the number of true faces in a projection, that is, after removal of redundant constraints, for which McMullen's upper bound provides a tighter bound.)

**Tags:** linear-programming, polytope


---

## 1 answers

### Answer by username_1 on 2018-04-03. Score: 6

I think this upper bound is tight. As an example, consider the following system

\begin{align\*}
+x\_0 & +\frac{1}{2} x\_1 +\frac{1}{4} x\_2 \le 0 \\
+x\_0 & +\frac{1}{2} x\_1 +\frac{1}{4} x\_2 \le 0 \\
+x\_0 & +\frac{1}{2} x\_1 +\frac{1}{4} x\_2 \le 0 \\
+x\_0 & +\frac{1}{2} x\_1 +\frac{1}{4} x\_2 \le 0 \\
-x\_0 & +\frac{1}{2} x\_1 +\frac{1}{4} x\_2 \le 0 \\
-x\_0 & +\frac{1}{2} x\_1 +\frac{1}{4} x\_2 \le 0 \\
-x\_0 & -\frac{3}{2} x\_1 +\frac{1}{4} x\_2 \le 0 \\
-x\_0 & -\frac{3}{2} x\_1 -\frac{7}{4} x\_2 \le 0 \\
\end{align\*}

It has 8 inequalities. Though some of them are identical, it is not a problem since we do not remove redundant constraints. One can also add dummy variables to make them different. Reducing $x\_0$, we obtain system with 16 inequalities. Then, reducing $x\_1$, we obtain system with $64$ inequalities.

More generally, let $S\_{n}^k$ denote the following system of inequalities over $x\_0, x\_1, \ldots, x\_{k - 1}$. Here we assume that $k \le n, n\ge 2$. There will be $2^n$ inequalities in $S\_{n}^ k$. Take any $m \in\{1, 2, \ldots, 2^n\}$. Let $m^{th}$ inequality of $S\_{n}^ k$ be
$$\alpha^m\_0 x\_0 + \ldots + \alpha^m\_{k - 1} x\_{k - 1} \le 0,$$
where
$$\alpha^m\_i = \begin{cases} 2^{-i} & \mbox{if $m \le 2^n - 2^{n - i - 1}$}, \\ -2 + 2^{-i} & \mbox{otherwise.} \end{cases}$$

Here we use a restriction mentioned above : provided $k\le n$, we have that $2^{n - i - 1}$ is an integer.

For example, system above is $S\_{3}^3$. It is easy to verify that if we eliminate $x\_0$ from $S\_{n} ^k$, we obtain $S\_{2n - 2} ^{k - 1}$. Indeed, when we eliminate $x\_0$, we add up all the inequalities from the first half with all the inequalities from the second half. Thus we get $2^{n - 1} \cdot 2^{n - 1} = 2^{2n - 2}$ inequalities. What happens with $x\_i$ for $i > 0$? In the first $$2^{n - 1} \cdot (2^{n - 1} - 2^{n - i - 1}) = 2^{2n - 2} - 2^{2n - 2 - i} = 2^{2n - 2} - 2^{(2n - 2) - (i - 1) - 1}$$ inequalities a coefficient before $x\_i$ will be $2^{-i} + 2^{-i} = 2^{-(i - 1)}$. In the last $2^{-i} + (-2 + 2^{-i}) = 2^{(2n - 2) - (i - 1) - 1}$ inequalities a coefficient before $x\_i$ will be $2^{-i} + (-2 + 2^{-i}) = -2 + 2^{-(i - 1)}$. This is $S\_{2n - 2}^{k - 1}$, but over variables $x\_1, \ldots, x\_{k - 1}$. Since, $2n - 2 \ge n - 1 \ge k - 1$, a restriction on the number of variables is also preserved.

Further, if we eliminate $x\_1$, we obtain $S\_{4n - 6}^{k - 2}$, and so on. After $d$ steps we will have $S^{k - d}\_{2^d n - (2^{d + 1} - 2)}$. The latter has exactly
$$2^{2^d n - (2^{d + 1} - 2)} = N^{2^d}/ 2^{2^{d + 1} - 2}$$
inequalities, where $N = 2^n$ is the number of inequalities of the initial system.

> **Comments:**
> **username_0**: Thank you very much. However, when I iterated Fourier-Motzkin 3 times from this original system of inequalities, I ended up with a system containing 1024 (the right number) inequalities all with a positive coefficient in column 3, thus the next step of elimination yields an empty set. Maybe I implemented it wrong.  
> **username_1**: Sorry, but do you  mean a system from the beginning of my answer? Applying Fourier-Motzkin 3 times elimininates all the variables in it; maybe I'm missing something?  
> **username_0**: I created a system with 8 inequalities and 10 variables according to these formulas and projected it 3 times. The last system I get has 1024 inequalities, but they all have a positive component on the next variable so the next system has 0 inequalities. Maybe I implemented something wrong.  
> **username_1**: As it turns out, my answer works only when the number of variables is at most logarithm of the number of inequalities, i.e., $k\le n$. This is because in my argument I use a fact that $2^{n - i - 1}$ is an integer. Modified my answer to make it explicit.  

---

