9
$\begingroup$

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.

$\endgroup$
20
  • 7
    $\begingroup$ Why would anybody need Fourier-Motzkin elimination to prove (1)? It is immediate from the definition. $\endgroup$
    – Misha
    Jun 28, 2014 at 18:32
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Todd Trimble
    Jun 28, 2014 at 22:01
  • 2
    $\begingroup$ @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. $\endgroup$
    – Misha
    Jun 28, 2014 at 22:45
  • 2
    $\begingroup$ @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. $\endgroup$
    – Todd Trimble
    Jun 28, 2014 at 23:37
  • 4
    $\begingroup$ @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. $\endgroup$
    – Todd Trimble
    Jun 29, 2014 at 2:01

1 Answer 1

5
$\begingroup$

I'm not familiar with Fourier-Motzkin, so I don't know how different the following argument is from what one usually does, but it's direct and elementary (and constructive, it in principle produces the new constraints from the old ones).

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$.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer. Your Approach is similar to Fourier-Motzkin elimination. $\endgroup$
    – Mahdi
    Jun 29, 2014 at 10:07
  • $\begingroup$ 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. $\endgroup$
    – Mahdi
    Jun 29, 2014 at 11:14
  • $\begingroup$ @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. $\endgroup$ Jun 29, 2014 at 15:27
  • $\begingroup$ 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$. $\endgroup$
    – Mahdi
    Jun 29, 2014 at 20:16
  • $\begingroup$ 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! $\endgroup$
    – JumpJump
    Sep 9, 2016 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.