# Product of two polytopes is a polytope

Please have a look at my attempt for this problem.

Let $$x = \begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix}, x_1 \in P_1, x_2 \in P_2$$. I want to show that $$x \in conv\{P_1 \times P_2\}$$, i.e. $$x$$ can be represented as the convex combination of some points of $$P_1 \times P_2$$.

Without loss of generality, suppose that $$d_1 \geq d_2$$. By Caratheodory's theorem, $$x_1$$ can be represented by at most $$d_1 + 1$$ points of $$P_1$$, i.e. there exists $$\{v_1,...,v_{d_1+1}\} \subset P_1$$, and $$\alpha_1,...,\alpha_{d_1+1}$$; $$\alpha_i \geq 0$$, $$\sum \alpha_i=1$$, such that: $$x_1 = \alpha_1v_1+...+\alpha_{d_1+1}v_{d_1+1}$$

$$x_2$$ can be represented similarly, with points $$\{w_1,...,w_{d_2+1},...,w_{d_1+1}\} \subset P_2$$, and coefficients $$\beta_i$$'s, such that $$\beta_{d_2+2},...,\beta_{d_1+1}$$(if exist) are all $$0$$'s: $$x_2 = \beta_1w_1+...+\beta_{d_2+1}w_{d_2+1} + 0.w_{d_2+2}+...+ 0.w_{d_1+1}$$

So now we have $$x$$ as:

$$x = \begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix} = \begin{pmatrix} \alpha_1v_1+...+\alpha_{d_2+1}v_{d_2+1}+\alpha_{d_2+2}v_{d_2+2}+...+\alpha_{d_1+1}v_{d_1+1}\\ \beta_1w_1+...+\beta_{d_2+1}w_{d_2+1} + 0.w_{d_2+2}+...+ 0.w_{d_1+1} \\ \end{pmatrix}$$

It is here that I got stuck. The points $$\begin{pmatrix} v_i\\ w_i \\ \end{pmatrix}$$ above are certainly in $$P_1 \times P_2$$, but are the coefficients right? Shouldn't the coefficients be in $$\mathbb{R}$$, instead of $$\mathbb{R}^2$$?

===================================

Edit: the polytopes here are all convex polytopes.

Edit 2: Caratheodory's theorem: https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_(convex_hull)

• Why can't $d_1=d_2$? Jan 1, 2019 at 15:31
• Could you please define polytope? Because from what I know, polytopes need not necessarily be convex. Jan 1, 2019 at 16:14
• @LordSharktheUnknown $d_1$ might or might not be equal to $d_2$. But I addressed this by representing $x_2$ with some extra terms of coefficients $0$, so that the representation of $x_1$ and $x_2$ both consist of $d_1+1$ terms. Jan 1, 2019 at 20:23
• @toric_actions this is from a class about convex polytopes, so the convexity of the polytopes is implied. Sorry for the confusion! Also, in our class we have two definitions for convex polytopes: (1) as the convex hull of finitely many points, and (2) as finite intersection of closed half-spaces. Jan 1, 2019 at 20:26
• Could you provide a definition of polytope you use? If you define it as a bounded polyhedron, the statement is trivial. Jan 2, 2019 at 15:21

There is a much easier way to do that.

Definition

let $$v,w\in \Bbb R^n$$. We define $$v\succeq w\iff v_i\ge w_i\quad,\quad 1\le i\le n$$

According to this definition, a closed half-space can be defined as following$$\{x|a^Tx\le b\}$$when $$a,x\in\Bbb R^n$$ and $$b\in \Bbb R$$. Therefore an intersection of finite number of half-spaces would become $$\{x\ \ |\ \ A^Tx\preceq b\}=\{x\ \ |\ \ a_i^Tx\preceq b_i \ \ ,\ \ 1\le i\le m\}$$when $$x\in\Bbb R^n , A\in \Bbb R^{m\times n},b\in\Bbb R^m$$ and $$a_i^T$$s are the rows of $$A$$. Then a convex polytope can be easily defined as$$P=\{x\ \ |\ \ A^Tx\preceq b\}$$Hence this problem, let $$P_1=\{x\ \ |\ \ A_1^Tx\preceq b_1\}\\P_2=\{y\ \ |\ \ A_2^Ty\preceq b_2\}$$where $${x\in\Bbb R^n,y\in\Bbb R^m \\ A_1\in \Bbb R^{m_1\times n},A_2\in \Bbb R^{m_2\times m}\\ b_1\in\Bbb R^{m_1},b_2\in\Bbb R^{m_2}}$$Now let $$P_3=P_1\times P_2{=\Big\{\begin{bmatrix}x\\y\end{bmatrix}\ \ \Big|\ \ x\in P_1\ \ ,\ \ y\in P_2\Big\}\\=\Big\{\begin{bmatrix}x\\y\end{bmatrix}\ \ \Big|\ \ A_1x\preceq b_1\ \ ,\ \ A_2y\preceq b_2\Big\}\\=\Big\{\begin{bmatrix}x\\y\end{bmatrix}\ \ \Big|\ \ \begin{bmatrix}A_1&0\\0&A_2\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}\preceq \begin{bmatrix}b_1\\b_2\end{bmatrix}\Big\}\\=\Big\{\begin{bmatrix}x\\y\end{bmatrix}\ \ \Big|\ \ A_3\begin{bmatrix}x\\y\end{bmatrix}\preceq b_3\Big\}\\=\Big\{z\in \Bbb R^{m+n}\ \ \Big|\ \ A_3z\preceq b_3\Big\}}$$where $$A_3=\begin{bmatrix}A_1^{m_1\times n}&0^{m_1\times m}\\\\0^{m_2\times n}&A_2^{m_2\times m}\end{bmatrix}_{(m_1+m_2)\times(m+n)}$$and $$b_3=\begin{bmatrix}b_1^{m_1\times 1}\\b_2^{m_2\times 1}\end{bmatrix}_{(m_1+m_2)\times1}$$with the coordinates $$z=\begin{bmatrix}x_{n\times 1}\\y_{m\times 1}\end{bmatrix}_{(m+n)\times1}$$ Since we could express $$P_3$$ as $$\Big\{z\in \Bbb R^{m+n}\ \ \Big|\ \ A_3z\preceq b_3\Big\}$$ with some matrices $$A_3$$ and $$b_3$$, then $$P_3$$ is also a convex polytope and we conclude that

If $$P_1$$ and $$P_2$$ are convex polytopes of dimensions $$m$$ and $$n$$ respectively, then their product $$P_1\times P_2=\Big\{\begin{bmatrix}x\\y\end{bmatrix}\ \ \Big| \ \ x\in P_1 \ \ , \ \ y\in P_2\Big\}$$ is a convex polytope of dimension $$m+n$$.

Try first to visualize the effect for low dimensions.

Let be $$P_1$$ and $$P_2$$ both be points along the x- resp. y-axis. Then $$P_1\times P_2$$ obviously is nothing but the point $$(P_1, P_2)$$.

Let $$P_1$$ still be some point on the x-axis, while $$P_2$$ be the line segment from $$a$$ to $$b$$ along the y-axis. Then $$P_1\times P_2$$ happens to be the line segment between the points $$(P_1, a)$$ and $$(P_1, b)$$.

Then let $$P_1$$ be such a line segment from $$a$$ to $$b$$ along the x-axis, and $$P_2$$ be the line segment from $$c$$ to $$d$$ along the y-axis. Then $$P_1\times P_2$$ happens to be the rectangle with vertices $$(a, c)$$, $$(a, d)$$, $$(b, c)$$, and $$(b, d)$$.

In fact, the Cartesian polytopal product is nothing but a brique product. The outcome $$P_1\times P_2$$ is just the $$(P_1, P_2)$$-duoprism. As seen from the above examples, a single point is the neutral element of that product. And for the dimensions you'd get the sum formula: $$dim(P_1\times P_2)=dim(P_1)+dim(P_2)$$.

Eg. take $$P_1$$ to be some regular $$n$$-gonal polygon of side length being unity and $$P_2$$ to be a line segment, also of unit size. Then $$P_1\times P_2$$ happens to be nothing but the Archimedean (uniform) $$n$$-prism. But you well can consider eg. the duoprism from a stellated dodecahedron and a great icosahedron, if you'd like. That one then happens to be $$3+3=6$$ dimensional!

--- rk

For every $$i$$ in $$\{1,2\}$$, let $$\mathcal{E}_i=\{v^i_1,\ldots, v^i_{m_i}\}$$ be the set of extremal points of $$P_i$$. We can regard $$P_i$$ as a subset of $$\mathbb{R}^{n_i}$$ for some natural number $$n_i$$ and the dimension of $$P_i$$ is simply the dimension of the linear spawn $$V_i$$ of the set $$G_i=\{v^i_1-v^i_1, v^i_2-v^i_1,\ldots, v^i_{m_i}-v^i_1\}$$ in $$\mathbb{R}^{n_i}$$.

We know that a point $$x_i$$ in $$\mathbb{R}^{n_i}$$ belongs to $$P_i$$ if and only if there exists non-negative real numbers $$t_1^i,\ldots, t_{m_i}^i$$ such that $$\sum_{j=1}^{m_i}t^i_j = 1$$ and $$\sum_{j=1}^{m_i}t^i_jv^i_j = x_i$$.

Now, consider the cartesian product $$P_1\times P_2$$, which is a subset of $$\mathbb{R}^{n_1}\times \mathbb{R}^{n_2} \cong \mathbb{R}^{n_1+n_2}$$. For every $$k_1$$ in $$\{1,\ldots,m_1\}$$ and $$k_2$$ in $$\{1,\ldots,m_2\}$$ let us call $$v_{k_1k_2}=(v^1_{k_1},v^2_{k_2})$$. We will prove that $$P_1\times P_2$$ is the convex hull $$\mathcal{C}$$ of the set $$\mathcal{E}_1\times\mathcal{E}_2 = \{v_{k_1k_2}\mid 1\leq k_1 \leq m_1,\enspace 1\leq k_2 \leq m_2\}$$ in $$\mathbb{R}^{n_1+n_2}$$.

Let $$x=(x_1,x_2)$$ be a point in $$P_1\times P_2$$ then we can write $$x = (\sum_{k_1=1}^{m_1}t^1_{k_1}v^1_{k_1},\enspace \sum_{k_2=1}^{m_2}t^2_{k_2}v^2_{k_2})$$, in the way it was detailed above. So $$x = \bigg{(}\sum_{k_1=1}^{m_1}t^1_{k_1}v^1_{k_1},\enspace \sum_{k_2=1}^{m_2}t^2_{k_2}v^2_{k_2}\bigg{)} =\sum_{k_1=1}^{m_1}\sum_{k_2=1}^{m_2}t^1_{k_1}t^2_{k_2}(v^1_{k_1}, v^2_{k_2}) = \sum_{k_1=1}^{m_1}\sum_{k_2=1}^{m_2}t_{k_1k_2}v_{k_1k_2},$$ where $$t_{k_1k_2}=t^1_{k_1}t^2_{k_2}$$ for every $$k_1$$ and $$k_2$$. Note that, for every $$k_1$$ and $$k_2$$, $$t_{k_1k_2}$$ is a non-negative real number and also $$\sum_{k_1=1}^{m_1}\sum_{k_2=1}^{m_2}t_{k_1k_2} = \sum_{k_1=1}^{m_1}\sum_{k_2=1}^{m_2}t^1_{k_1}t^2_{k_2} = \bigg{(}\sum_{k_1=1}^{m_1}t^1_{k_1}\bigg{)}\bigg{(}\sum_{k_2=1}^{m_2}t^2_{k_2}\bigg{)} =(1)(1)=1.$$ Thus $$x=(x_1,x_2)$$ belongs to the convex hull $$\mathcal{C}$$ of the set $$\mathcal{E}_1\times\mathcal{E}_2$$. So $$P_1\times P_2 \subseteq \mathcal{C}$$.

On the other hand, $$\mathcal{E}_1\times\mathcal{E}_2 \subseteq P_1\times P_2$$ and $$P_1\times P_2$$ is convex, so $$\mathcal{C}\subseteq P_1\times P_2$$. Thus $$\mathcal{C} = P_1\times P_2$$.

Finally, the set $$G=\{v_{k_1k_2}-v_{11}\mid 1\leq k_1 \leq m_1,\enspace 1\leq k_2 \leq m_2\}$$ is equal to the cartesian product $$G_1\times G_2$$, of the sets defined in the first paragraph. So the linear spawn $$V$$ of $$G$$ in $$\mathbb{R}^{n_1+n_2}$$ is simply the cartesian product $$V_1\times V_2$$ of the linear spawns of $$G_1$$ and $$G_2$$. Thus the dimension of $$P_1\times P_2$$ is equal to the sum of the dimension of $$P_1$$ and $$P_2$$.

Note that we do not need the set $$\mathcal{E}_i$$ to be extremal, only its convex hull is $$P_i$$. But it is interesting to note that $$\mathcal{E}_1\times \mathcal{E}_2$$ is exactly the set of extremal points of $$P_1\times P_2$$.

• Looking at the computations involved in my answer I think that the product of polytopes has in some sense similar properties to the universal property of the tensor product of modules over a given ring. Perhaps there is a category of polytopes and a categorical notion of product that gives rigor to this idea Feb 18, 2019 at 3:20