Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
