# Is the tensor product of polyhedra a polyhedron?

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?

-
I'm not entirely sure that your definition of tensor product match the one of Lawrence Valby. In particular yours depends heavily on where is the origin, whereas the one of Valby is about affine spaces. The question remains valid of course ! –  Lierre Dec 7 '12 at 17:15
No, Lierre, it doesn't match, as I have pointed out in the parentheses. Unfortunately the title of the question didn't reflect that -- sorry. –  darij grinberg Dec 7 '12 at 17:22
Oh... I should have read the parenthesis ;) –  Lierre Dec 7 '12 at 17:26
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.) –  Thomas Zaslavsky Dec 19 '12 at 5:14

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.

-
Sorry, but why is $P\otimes Q$ what you claim it to be? –  darij grinberg Dec 20 '12 at 0:44
$P$ is the convex hull of two pointts, so $P\otimes Q$ is the convex hull of two rays. Clearly anything in between the two rays is in that set. Similarly everything in the set can be (uniquely) decomposed into an average of elements from the two rays. I have a simpler example which takes place in two dimensions which I'll put up soon. –  Will Sawin Dec 20 '12 at 1:43
Ah, I see! More concretely, the point $\left(1,0,0,1\right)$ lies in the closure of $P\otimes Q$, because it is the limit for $c\to +\infty$ of $\frac{1}{c}\left(1,0\right)\otimes\left(c,1\right) + \frac{c-1}{c}\left(0,1\right)\otimes\left(0,1\right) = \frac{1}{c}\left(c,1,0,0\right) + \frac{c-1}{c}\left(0,0,0,1\right) = \left(1,\frac{1}{c},0,\frac{c-1}{c}\right)$. But it does not lie in $P\otimes Q$, since otherwise it would be a convex combination of points of the form $\left(a,b\right)\otimes\left(c,1\right)=\left(ac,a,bc,b\right)$ with $a+b=1$, but then all the points ... –  darij grinberg Dec 20 '12 at 2:12
... which occur in this combination with nonzero coefficient would have to satisfy $a=0$ and $bc=0$, so that $a=0$, $b=1$ and $c=0$, so that the point $\left(1,0,0,1\right)$ would have to be $\left(0,1\right)\otimes\left(0,1\right) = \left(0,0,0,1\right) \neq \left(1,0,0,1\right)$. Thus, $P\otimes Q$ is not closed. Thanks for the counterexample! –  darij grinberg Dec 20 '12 at 2:14
Nice proof, too. But "real numbers" should be "nonzero real numbers"! –  darij grinberg Dec 20 '12 at 2:32

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(...).

-
Yes, this is the approach I have tried too. Unfortunately, while proving that my convex hull is a subset of your $(*)$ is easy, the other inclusion is not, and I am not even sure that it is true. (By the way, is there really much use in separating $P_c$ from $P_{\ell}$ ?) –  darij grinberg Dec 7 '12 at 17:23
One wants to separate $P_c$ from $P_\ell$ to be able to say that $P_p+P_c$ are in the orthogonal complement to $P_\ell$. Whether it's useful here, is another question, of course. –  Dima Pasechnik Dec 7 '12 at 18:41
and once there are no $P_\ell$ and $Q_\ell$, a seemingly natural finite set of generators (?) of conv($P\otimes Q$) would be pairs of vertices and extreme rays. –  Dima Pasechnik Dec 8 '12 at 7:30
Clearly it contains $P_a \otimes Q_b$, for $a,b\in \{p,c,l\}$. We need to prove it contains the sum of these objects. Write $x+y = \lim _\lambda \to 0 \lambda (x/\lambda) + (1-\lambda) y$. So we get the sum as long as one of the objects is closed under multiplication of positive reals, and the convex hull is closed. Cones and linear subspaces both have this property, and tensor product preserves it. So we only need to check closure. Unfortunately, closure is not preserved by taking the convex hull, so this is a bit tricky. –  Will Sawin Dec 19 '12 at 6:20