Is the tensor product of polyhedra a polyhedron? - MathOverflow

Is the tensor product of polyhedra a polyhedron?

2012-12-07T04:53:17Z

Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be an intersection of finitely many closed halfspaces in $V$ (that is, the set of solutions of a system of finitely many non-strict linear inequalities on a vector in $V$). It is known that the polytopes are exactly the bounded polyhedra.

Note that, for me, $\mathbb R$ really can mean any ordered field, like $\mathbb Q$ or $\mathbb Q\left[\sqrt{2}\right]$ or many others. Every claim stated below holds when $\mathbb R$ is replaced by any ordered field, and an answer that makes use of special properties of $\mathbb R$ is welcomed but won't be considered final.

Background: The decomposition theorem for polyhedra yields the following facts as easy consequences:

1. If $f:V\to W$ is an $\mathbb R$-linear map between finite-dimensional $\mathbb R$-vector spaces, and $P$ is a polyhedron in $V$, then $f\left(P\right)$ is a polyhedron. (The same statement holds with "polyhedron" replaced by "polytope", but that is a triviality.)

2. If $f:V\to W$ is an $\mathbb R$-linear map between finite-dimensional $\mathbb R$-vector spaces, and $P$ is a polyhedron in $W$, then $f^{-1}\left(P\right)$ is a polyhedron. (This one is obvious, but just mentioned here for the sake of "symmetry".)

3. If $P$ is a polyhedron in a finite-dimensional $\mathbb R$-vector space $V$, and $Q$ is a polyhedron in a finite-dimensional $\mathbb R$-vector space $W$, then $P\times Q$ is a polyhedron in $V\times W$. (The same holds for polytopes.)

4. If $P$ and $Q$ are two polyhedra in one and the same finite-dimensional $\mathbb R$-vector space, then the Minkowski sum $P+Q$ and the intersection $P\cap Q$ are polyhedra as well. (Again, the same holds for polytopes.)

5. If $P$ is a polyhedron in a finite-dimensional $\mathbb R$-vector space $V$, and $Q$ is a polyhedron in a finite-dimensional $\mathbb R$-vector space $W$, then $\left\lbrace f\in\mathrm{Hom}_{\mathbb R}\left(V,W\right) \mid f\left(P\right) \subseteq Q\right\rbrace$ is a polyhedron in $\mathrm{Hom}_{\mathbb R}\left(V,W\right)$ . (This is inspired by Definition 9.16 in Günter M. Ziegler, Lectures on Polytopes, 1995.)

Question:

6. If $P$ is a polyhedron in a finite-dimensional $\mathbb R$-vector space $V$, and $Q$ is a polyhedron in a finite-dimensional $\mathbb R$-vector space $W$, then is it true that the convex hull of the set $\left\lbrace p \otimes q \mid p\in P,\ q\in Q \right\rbrace $ is a polyhedron in $V\otimes W$ ?

This holds for polytopes, and follows in that case from §2.5 of Lawrence Valby, A Category of Polytopes (caveat: my convex hull is not his $P\otimes Q$, but rather the image of his $P\otimes Q$ under a surjection which keeps the $p_iq_j$ coordinates and forgets the $p_i$, $q_j$ and $1$ coordinates); but the argument there does not generalize to polyhedra. On the other hand, I am at a loss when trying to find a counterexample. Any ideas?

Answer by Dima Pasechnik for Is the tensor product of polyhedra a polyhedron?

2012-12-07T11:45:33Z

An obvious route to a proof of 6 would be showing that conv($P\otimes Q$) decomposes as $$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}((P_p+P_c)\otimes Q_c+P_c\otimes (Q_p+Q_c))+\mathrm{conv}(P\otimes Q_\ell+P_\ell\otimes Q)\qquad (*)$$ where $P=P_p+P_c+P_\ell$, for $P_p$ a polytope, $P_c$ a pointed cone, and $P_\ell$ a linear subspace, and $Q=Q_p+Q_c+Q_\ell$ a similar decomposition for $Q$. You have mentioned that $\mathrm{conv}(P_p\otimes Q_p)$ is a polytope, and I think a proof of this should be easily adaptable to showing that the second $\mathrm{conv}(...)$ is a polyhedral cone. And the third $\mathrm{conv}(...)$ is linear subspace. Hence $(*)$ would imply that $\mathrm{conv}(P\otimes Q)$ is a polyhedron.

The hard part seems to be showing $(*)$. Any closed convex set $C$ in $\mathbb{R}^m$ has a decomposition into the sum of a convex set $C'$ which does not contain straight lines, and a subspace $C_\ell$, with $C'$ contained in the orthogonal complement of $C_\ell$, so this boils down to identifying $C'$ with the sum of the first two conv(...), and $C_\ell$ with the third conv(...).

Answer by Thomas Zaslavsky for Is the tensor product of polyhedra a polyhedron?

2012-12-19T05:14:02Z

Can you provide your definition of $p \otimes q$? How is it different from $(p,q) \in P \times Q$? (I don't see a definition in Ziegler.)

Answer by Will Sawin for Is the tensor product of polyhedra a polyhedron?

2012-12-19T21:57:50Z

Not always! However, the closure is a polyhedron.

Not always: Take $P = \{a | 0 \leq a \leq 1\}$ . Take $Q= \{ b,c | b\geq 0, c=1\}$ . Then under the map $x=ab$, $y=ac$. Since $P$ is the convex hull of $(0)$ and $(1)$, and $Q$ is the ray starting at $(0,1)$ and going in direction $(1,0)$, $P \otimes Q$ is the convex hull of $(0,0)$ and the ray starting at $(0,1)$ and going in direction $(1,0)$, which is:

$P \otimes Q = \{x,y | 0\leq x, 0 \leq y \leq 1, (y>0 \vee x=0) \}$

This not a polyhedron because it is not closed.

The closure is: Define $B$ to be the following convex body. First we show that $B$ is a polyhedron. Next we will show that $cl(P \otimes Q)=B$.

$B= \operatorname{conv}(P_p \otimes Q_p + ((P_p+P_c) \otimes Q_c) + (P_c \otimes (Q_p+Q_c)) + (P \otimes Q_l) + (P_l \otimes Q)) $

Since $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$,

$B= \operatorname{conv}(P_p \otimes Q_p) + \operatorname{conv}(((P_p+P_c) \otimes Q_c) + (P_c \otimes (Q_p+Q_c)) )+ \operatorname{conv}((P \otimes Q_l) + (P_l \otimes Q))) $

The first part is clearly a polytope. The last part is clearly a linear subspace. The cone is the tricky but one can view a cone as the convex hull of finitely many rays. A ray tensor a polytope is the convex hull of finitely many rays, thus a cone. A ray tensor a cone is the convex hull of finitely many rays, thus a cone again. Taking the convex hull of different cones could produce more linear subspaces but will not take you out of the world of polyhedra. (Dima might be able to produce a better argument than this?)

Next we show that $cl(P \otimes Q) \subseteq B$. As a polytope, it is convex and closed, so it is enough to show that any element in $P$ tensor an element in $Q$ is in $B$. But this is obvious - just split that element into a sum.

Finally we show that $B \subseteq cl(P \otimes Q)$. Since $P \otimes Q$ is convex, $cl(P\otimes Q)$ is convex, so need to show that a sum of an element in $P_p \otimes Q_p$, an element in $(P_p+P_c)\otimes Q_c$, etc. is in $B$. Assume for simplicity we merely need to add $a \otimes b$ in $P_p \times Q_p$ to $c \otimes d$ in $(P_p+P_c) \otimes Q_c$. (To get the general caes, you just repeat the argument). Let $e$ be any element of $Q_p$. Then we notice that

$\lim _ {\lambda \to 0} \left((1-\lambda) \left[a \otimes b\right] + \lambda \left[c \otimes \left(\frac{d}{\lambda}+ e \right)\right]\right)= a\otimes b+ c\otimes d $

$a \otimes b$ and $c \otimes \frac{d}{\lambda}+ e$ are in $P \otimes Q$ as long as $\lambda>0$, so a convex combination of them is as well, so the limit as $\lambda \to 0$ is in $cl(P \otimes Q)$. The key fact is that $Q_c$ is closed under multiplication by positive real numbers. Since $P_c$, $Q_l$, and $P_l$ are as well, we can apply this trick again to get an arbitrary sum.