Skip to main content
added 1209 characters in body
Source Link
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

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: Clearly,Define $B$ to be the closurefollowing convex body. First we show that $B$ is contained in Dima'sa polyhedron. WeNext we will show the reverse. Clearly the closure ofthat $P \otimes Q$ contains the closure of$cl(P \otimes Q)=B$.

$\operatorname{conv}(P_p \otimes Q_p \cup ((P_p+P_c) \otimes Q_c) \cup (P_c \otimes (Q_p+Q_c)) \cup (P \otimes Q_l) \cup (P_l \otimes Q)) $$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)) $

ClearlySince $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(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)) $$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 Dima's polyhedronclearly 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, because $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$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?)

SoNext 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 caseis obvious - just split that element into a sum.

Finally we show that $B \subseteq cl(P \otimes Q)$. Since $P \otimes Q$ is convex, the closure of the$cl(P\otimes Q)$ is convex hull, 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 union containsgeneral caes, you just repeat the sumargument). But as I pointed out in my comment:Let $e$ be any element of $Q_p$. Then we notice that

$\lim _ {\lambda \to 0} \left(\lambda \frac{a}{\lambda} + (1-\lambda) b \right)= a+b $$\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 $

so the closure of the convex hull of the union contains the sum$a \otimes b$ and $c \otimes \frac{d}{\lambda}+ e$ are in $P \otimes Q$ as long as all but one$\lambda>0$, so a convex combination of them is as well, so the summandslimit as $\lambda \to 0$ is closed under multiplication by positive numbers. Sincein $P_p \otimes Q_p$$cl(P \otimes Q)$. The key fact is the only summand that $Q_c$ is not closed under multiplication by positive real numbers. Since $P_c$, this is okay$Q_l$, and the tensor product is Dima's polyhedron$P_l$ are as well, we can apply this trick again to get an arbitrary sum.

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: Clearly, the closure is contained in Dima's polyhedron. We will show the reverse. Clearly the closure of $P \otimes Q$ contains the closure of

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

Clearly

$\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)) $

is Dima's polyhedron, because $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$.

So it is enough to show that, in this case, the closure of the convex hull of the union contains the sum. But as I pointed out in my comment:

$\lim _ {\lambda \to 0} \left(\lambda \frac{a}{\lambda} + (1-\lambda) b \right)= a+b $

so the closure of the convex hull of the union contains the sum as long as all but one of the summands is closed under multiplication by positive numbers. Since $P_p \otimes Q_p$ is the only summand that is not closed under multiplication by positive numbers, this is okay, and the tensor product is Dima's polyhedron.

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.

added 190 characters in body
Source Link
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

Not always! However, the closure is a polyhedron.


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

$P \otimes Q = \{x,y,z,w| x,y,z,w \geq 0, y+w =1, (x = 0 \vee y\neq 0), (w=0 \vee z \neq 0) \}$$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: Clearly, the closure is contained in Dima's polyhedron. We will show the reverse. Clearly the closure of $P \otimes Q$ contains the closure of

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

Clearly

$\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)) $

is Dima's polyhedron, because $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$.

So it is enough to show that, in this case, the closure of the convex hull of the union contains the sum. But as I pointed out in my comment:

$\lim _ {\lambda \to 0} \left(\lambda \frac{a}{\lambda} + (1-\lambda) b \right)= a+b $

so the closure of the convex hull of the union contains the sum as long as all but one of the summands is closed under multiplication by realpositive numbers. Since $P_p \otimes Q_p$ is the only summand that is not closed under multiplication by realpositive numbers, this is okay, and the tensor product is Dima's polyhedron.

Not always! However, the closure is a polyhedron.


Not always: Take $P = \{a,b | a,b \geq 0, a+b=1\}$. Take $Q= \{ c,d | c\geq 0, d=1\}$. Then under the map $x=ac$, $y=ad$, $z=bc$, $w=bd$, we have:

$P \otimes Q = \{x,y,z,w| x,y,z,w \geq 0, y+w =1, (x = 0 \vee y\neq 0), (w=0 \vee z \neq 0) \}$

This not a polyhedron because it is not closed.


The closure is: Clearly, the closure is contained in Dima's polyhedron. We will show the reverse. Clearly the closure of $P \otimes Q$ contains the closure of

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

Clearly

$\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)) $

is Dima's polyhedron, because $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$.

So it is enough to show that, in this case, the closure of the convex hull of the union contains the sum. But as I pointed out in my comment:

$\lim _ {\lambda \to 0} \left(\lambda \frac{a}{\lambda} + (1-\lambda) b \right)= a+b $

so the closure of the convex hull of the union contains the sum as long as all but one of the summands is closed under multiplication by real numbers. Since $P_p \otimes Q_p$ is the only summand that is not closed under multiplication by real numbers, this is okay, and the tensor product is Dima's polyhedron.

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: Clearly, the closure is contained in Dima's polyhedron. We will show the reverse. Clearly the closure of $P \otimes Q$ contains the closure of

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

Clearly

$\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)) $

is Dima's polyhedron, because $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$.

So it is enough to show that, in this case, the closure of the convex hull of the union contains the sum. But as I pointed out in my comment:

$\lim _ {\lambda \to 0} \left(\lambda \frac{a}{\lambda} + (1-\lambda) b \right)= a+b $

so the closure of the convex hull of the union contains the sum as long as all but one of the summands is closed under multiplication by positive numbers. Since $P_p \otimes Q_p$ is the only summand that is not closed under multiplication by positive numbers, this is okay, and the tensor product is Dima's polyhedron.

Source Link
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

Not always! However, the closure is a polyhedron.


Not always: Take $P = \{a,b | a,b \geq 0, a+b=1\}$. Take $Q= \{ c,d | c\geq 0, d=1\}$. Then under the map $x=ac$, $y=ad$, $z=bc$, $w=bd$, we have:

$P \otimes Q = \{x,y,z,w| x,y,z,w \geq 0, y+w =1, (x = 0 \vee y\neq 0), (w=0 \vee z \neq 0) \}$

This not a polyhedron because it is not closed.


The closure is: Clearly, the closure is contained in Dima's polyhedron. We will show the reverse. Clearly the closure of $P \otimes Q$ contains the closure of

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

Clearly

$\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)) $

is Dima's polyhedron, because $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$.

So it is enough to show that, in this case, the closure of the convex hull of the union contains the sum. But as I pointed out in my comment:

$\lim _ {\lambda \to 0} \left(\lambda \frac{a}{\lambda} + (1-\lambda) b \right)= a+b $

so the closure of the convex hull of the union contains the sum as long as all but one of the summands is closed under multiplication by real numbers. Since $P_p \otimes Q_p$ is the only summand that is not closed under multiplication by real numbers, this is okay, and the tensor product is Dima's polyhedron.