Are vectors in $[-1,+1]^d$ a convex combination of vectors in $\{-1,+1\}^d$?

Question

Vectors in $[-1,+1]^d$ are definitely linear combinations of vectors in $\{-1,+1\}^d$. How to show there is a convex combination?

Answer 1

You can do this by induction.

Given a $u\in[-1,1]$ you can write $u=\lambda_1(-1)+\lambda_2\,1$ with $\lambda_1\geq0$, $\lambda_2\geq0$, $\lambda_1+\lambda_2=1$.

Assume that the proposed claim is true for $d-1$, and cosider a point $u=(u_1,u_2,\ldots,u_{d-1},u_d)\in[-1,1]^d$. Then $u':=(u_1,u_2,\ldots,u_{d-1})\in[-1,1]^{d-1}$ can be written as a convex linear combination $$u'=\sum_\iota \lambda_\iota{\bf e}_\iota'$$ of the vectors $${\bf e}_\iota'\in\bigl\{(x_1,\ldots,x_{d-1},0)\in{\mathbb R}^d\bigm| x_i\in\{-1,1\}\ (1\leq i\leq d-1)\bigr\}\ .$$ For each such ${\bf e}_\iota'$ write ${\bf e}_\iota^-:=(x_1,\ldots,x_{d-1},-1)\in\{-1,1\}^d$, and similarly ${\bf e}_\iota^+$. There are $\mu_1\geq0$, $\mu_2\geq0$ with $\mu_1+\mu_2=1$ such that $$u_d=\mu_1(-1)+\mu_2\,1\ .$$ It is then easy to see that $$u=\sum_\iota \lambda_\iota(\mu_1{\bf e}_\iota^-+\mu_2{\bf e}_\iota^+)\ .$$

Answer 2

Yes. More generally, if $X \subset \mathbb R^a$ and $Y \subset \mathbb R^b$ are convex sets which are 'generated' by $S$ resp. $T$, in the sense that every element of $X$ resp. $Y$ is a convex combination of $S$ resp. $T$, then $X \times Y$ is generated by $S \times T$.

Proof: if $x = \sum_i \lambda_i s_i$ and $y = \sum_j \mu_j t_j$ then $$(x,y) = \sum_{i,j} \lambda_i\mu_j (s_i, t_j)$$ because both sides have the same image under the projections $p_1 : X \times Y \to X$ and $p_2 : X\times Y \to Y$.