Product of two polytopes is a polytope

convex-geometryconvex-hullsdiscrete geometrypolytopes

Please have a look at my attempt for this problem.

enter image description here

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)

Best Answer

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

Related Question