Prove that the cross polytope $C_n=\{x\in\mathbb{R}^n: \pm x_1 \pm x_2 \pm \ldots \pm x_n \leq 1\}$ is the projection of $Q_n:= \{(x,y)\in\mathbb{R}^{2n} : \sum_{i=1}^n y_i =1, -y_i\leq x_i\leq y_i \forall i=1,\ldots,n\}$ onto the $x$ coordinates.

## Solution:

Let $\pi$ denote the projection onto the $x$ coordinates. Suppose that $x=(x_1,\ldots,x_n)\in C_n$, then we have that $\sum_{i=1}^n |x_i| \leq 1$ which implies that $\left(\sum_{i=1}^n |x_i|\right)+\varepsilon = 1$ for some $\varepsilon \geq0$. We have $(x_1,\ldots,x_n, |x_1|+\varepsilon,|x_2|,\ldots, |x_n|) \in Q_n$ with $\pi(x_1,\ldots,x_n, |x_1|+\varepsilon,|x_2|,\ldots, |x_n|) = x$, so $C_n \subset \pi(Q_n)$.

For any $(x_1,\ldots,x_n,y_1,\ldots,y_n) \in Q_n$, we have $\pm x_1 \pm x_2 \pm \cdots \pm x_n\leq \sum_{i=1}^n |x_i| \leq \sum_{i=1}^n |y_i| = \sum_{i=1}^n y_i = 1$, thus $\pi (x_1,\ldots,x_n,y_1,\ldots,y_n) = (x_1,\ldots, x_n) \in C_n$, so $\pi(Q_n)\subset C_n$. Since we have containment both ways, these sets are equal.