Product of two polytopes is a polytope

Question

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)

Answer 1

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

Answer 2

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

Answer 3

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