# Linear transformation of a polyhedron

Is there a simple proof that shows:

1. Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron.
2. Minkowski sum of two $\mathcal{H}$-polyhedrons is a $\mathcal{H}$-polyhedron.

I know a proof of (1.) based on Fourier-Motzkin elimination. and, I know (2.) is a simple consequence of (1.).

Every different approach is appreciated.

• Why would anybody need Fourier-Motzkin elimination to prove (1)? It is immediate from the definition. – Misha Jun 28 '14 at 18:32
• I might be missing something obvious, but I'm not convinced that 1. is immediate from the definition. That the image of a polyhedron in $\mathbb{R}^{n+1}$ under the projection map $\mathbb{R}^{n+1} \to \mathbb{R}^n$ to the first $n$ coordinates is again a polyhedron was apparently not considered too trivial to bother proving in Tame Topology and O-minimal Structures by van den Dries (see pp. 26-27). (The general result follows from this without too much pain.) – Todd Trimble Jun 28 '14 at 22:01
• @ToddTrimble: Todd, the definition that I had in mind is that a convex polytope $P$ is the convex hull of a finite set $V$. Now, if $L: R^n\to R^n$ is a linear map, then $L(P)$ is the convex hull of $L(V)$. (You can see this for instance by interpreting $P$ as a set of convex linear combinations of elements of $V$.) My guess is that van den Dries wanted to illustrate the quantifier elimination in a simple example. Or maybe the point is proving everything without first establishing equivalent characterizations of convex polyhedra. – Misha Jun 28 '14 at 22:45
• @Misha Thanks. I was just about to remark as Mahdi did, although you might have an easy workaround to handle the noncompact case (do you?). But I think Mahdi's question is legitimate, since he asks for a simple proof that presumably works from first principles, i.e., from the definition he gives of polyhedron. My own feeling is that the question should be honored. – Todd Trimble Jun 28 '14 at 23:37
• @DeaneYang Yes, convex polyhedra are implied in the post (intersection of finitely many closed half-spaces). The trouble with your argument is that the taking of images does not preserve intersections. – Todd Trimble Jun 29 '14 at 2:01

The claim is trivial if $A\in\mathbb R^{n\times n}$ is invertible, and a general $A$ can be written as $A=PB$, with $B$ invertible and $P$ a projection, so we can focus on projections. We can in fact also assume that $P$ is a projection on a codimension $1$ subspace, say $P(y+\alpha e)=y$, for $y\perp e$ and $\alpha\in\mathbb R$. Suppose the polyhedron $Q$ is defined by the constraints $x\cdot n_j\le c_j$. We are then interested in $$S=P(Q)=\{ y\in\{e\}^{\perp} : y\cdot n_j \le c_j + d_j\alpha \:\textrm{ for some }\alpha\in\mathbb R \textrm{ and }j=1,\ldots, N \}$$ (the same $\alpha$ for all $j$ of course). We can further assume that $d_j=0$ or $\pm 1$. Call a constraint zero, positive, or negative according to the sign of $d_j$. The zero constraints are already of the desired type and can be ignored. The case of only positive (or only negative) constraints is trivial ($S=\{e\}^{\perp}$ in both cases). In the remaining case, I claim that $y\in S$ precisely if $$y\cdot (n_k^+ + n_j^-) \le c_k^+ + c_j^-\quad\quad\quad (1)$$ for all choices of pairs $(k,j)$ of one positive and one negative condition. Indeed, we can rewrite (1) as $$y\cdot n_k^+ \le c_k^+ + \min (c_j^--y\cdot n_j^-) ,$$ and then observe that the largest $\alpha$ that satisfies all negative constraints for a given $y$ is $\alpha=\min (c_j^--y\cdot n_j^-)$. It is now clear that (1) is equivalent to $y\in S$.
• For clarification your answer, Please says that $S$ is the projection of the polyhedron and defines theses notations: $n_j$, $c_j$ in your answer. – Mahdi Jun 29 '14 at 11:14
• @Mahdi: Yes, $S$ is $P(Q)$, where $Q$ is the original polyhedron, defined by the constraints $x\cdot n_j\le c_j$. I'll edit. – Christian Remling Jun 29 '14 at 15:27
• I think that for compatibiliy of the dimensions of $y$ and $n_j$, it is better to write $y\in\{e\}^\perp$ instead of $y\in \mathbb{R}^{n-1}$ in definition of $S$. – Mahdi Jun 29 '14 at 20:16
• Are you definition $P(Q)$ in the way you write there of you are trying to prove $P(Q)$ has that form? Moreover, why the same $\alpha$ for all $j$? Thank you! – JumpJump Sep 9 '16 at 18:58