Let $P=\{(x,y)\in \mathbb{R}^{n+m} : Ax\ge b \}$ be a polyhedron in $\mathbb {R}^{n+m}$, with $x\in \mathbb {R}^n$ and $y\in \mathbb {R}^m$.

How can I show that the projection $\pi _X(P) = \{x\in \mathbb {R}^n : (x,y)\in P \ \mathrm{for \ some} \ y\in \mathbb{R}^m\}$ is also a polyhedron in $\mathbb{R^n}$?

A polyhedron must be a set of points that satisfy a finite number of linear inequalities, or equivalently, a finite intersection of half-spaces.

  • $\begingroup$ What is the context of your question? There are several approaches to this. (one approach is via proving that the theory of real linear arithmetic admits quantifier elimination, but if that doesn't mean anything to you, it isn't going to help.) $\endgroup$ – Rob Arthan Sep 18 '17 at 21:29
  • $\begingroup$ Try to keep it as elementary as possible, just using tools from linear algebra. If it's not possible, post what is needed so I can search it. $\endgroup$ – user438334 Sep 18 '17 at 21:37
  • 1
    $\begingroup$ That doesn't really tell me the context of your question: why are you interested in this and what have you tried? (By the way, imperatives are not an effective way of getting responses on MSE.) $\endgroup$ – Rob Arthan Sep 18 '17 at 21:43

May assume $m=1$, and then do induction.

Here is a way to produce the inequalities that define the projection of $P$ on $\mathbb{R}^n$.

Say $P$ is defined by finitely many inequalities $$L_i(x) + a_i y \ge 0$$ for $i \in I$. Dividing by the coefficient of $y$ in each inequality, we get the equivalent system $$L_i'(x) \ge y$$ $$y \ge L''_j(x)$$ $$L_k'''(x)\ge 0$$ for $i \in I_1$, $j \in. I_2$, $k \in I_3$.( if $a_i<0$ we get an inequality of first type, $a_i >0$ , one of second type, $a_i =0$, one of third type). Now it should be clear that the projection of $P$ is defined by the inequalities $$L_i'(x) \ge L_j''(x)$$ $$L_k'''(x) \ge 0$$ for $i \in I_1$, $j \in I_2$, $k \in I_3$.


Your Answer

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