(Solved): Exercise 2.20* Consider the Fourier-Motzkin elimination algorithm. (a) Suppose that the number m of ...

Exercise 2.20* Consider the Fourier-Motzkin elimination algorithm. (a) Suppose that the number $m$ of constraints defining a polyhedron $P$ is even. Show, by means of an example, that the elimination algorithm may produce a description of the polyhedron ${?}_{n?1}(P)$ involving as many as $m^2/4$ linear constraints, but no more than that. (b) Show that the elimination algorithm produces a description of the onedimensional polyhedron ${?}_1(P)$ involving no more than $m^{2^{n?1}}/2^{2^n?2}$ constraints. (c) Let $n=2^p+p+2$, where $p$ is a nonnegative integer. Consider a polyhedron in ${?}^n$ defined by the $8\left(\begin{array}{l}n\\ 3\end{array}\right)$ constraints $\pm x_i\pm x_j\pm x_k?1,1?i<j<k?n,$ where all possible combinations are present. Show that after $p$ eliminations, we have at least $2^{2^p+2}$ constraints. (Note that this number increases exponentially with $n$.)