Cartesian product and convex hull

1.3k Views Asked by At

Let $X,Y \subseteq \mathbb{R}^n$. Then the following holds:

$$\text{conv}(X\times Y) = \text{conv}(X) \times \text{conv}(Y).$$

The inclusion "$\subseteq$" is clear. Whats about the other one? I don't think this holds in general but every example im thinking of works just fine. Is there any counterexample?

1

There are 1 best solutions below

0
On

Let $(x,y)\in \text{conv}(X)\times\text{conv}(Y)$, where $X\in\mathbb{R}^m$ and $Y\in\mathbb{R}^n$ are convex sets. Then, by the Carathéodory's theorem, there exist points $x_1,\dots,x_{m+1}\in X$, $y_1,\dots,y_{n+1}\in Y$ and non-negative numbers $\lambda_1,\dots,\lambda_{m+1},\gamma_1,\dots,\gamma_{n+1}\ge 0$ such that $$\sum_{i=1}^{m+1} \lambda_i = 1\ \ \text{and}\ \ \sum_{j=1}^{n+1}\gamma_j = 1,$$ and that $$x = \sum_{i=1}^{m+1}\lambda_i x_i\ \ \text{and}\ \ y=\sum_{j=1}^{n+1} \gamma_jy_j.$$ Then by the definitions of Cartesian product $(x_i,y_j)\in X\times Y, \forall\,i,j$. Since $$\sum_{i,j} \lambda_i\gamma_j = 1$$ and $$(x,y) = \left( \sum_{i=1}^{m+1} \lambda_i x_i, \sum_{j=1}^{n+1} \gamma_j y_j\right) = \left( \sum_{j=1}^{n+1}\gamma_j\sum_{i=1}^{m+1} \lambda_i x_i, \sum_{i=1}^{m+1} \lambda_i\sum_{j=1}^{n+1} \gamma_j y_j\right) = \sum_{i,j}\lambda_i\gamma_j (x_i,y_j),$$ we have $(x,y)\in \text{conv}(X\times Y)$ and hence $\text{conv}(X)\times\text{conv}(Y)\subseteq\text{conv}(X\times Y)$.