# Homework Help: Polytope proofs

1. Sep 24, 2015

### squenshl

1. The problem statement, all variables and given/known data
Prove that the set $$\Delta = \left\{x \in \mathbb{R}^{n+1}: \sum_{i=1}^{n+1} x_i = 1 \quad \text{and} \quad x_i \geq 0 \; \text{for any} \; i\right\}$$ is a polytope. This polytope is called an $n$-dimensional simplex.

Prove that the set $$C = \left\{x \in \mathbb{R}^{n+1}: 0 \leq x_1 \leq 1 \; \text{for any} \; i\right\}$$ is a polytope. This polytope is called an $n$-dimensional cube.

Prove that the set $$O = \left\{x \in \mathbb{R}^{n+1}: \sum_{i=1}^{n+1} |x_i| \leq 1\right\}$$ is a polytope. This polytope is called a octahedron.

2. Relevant equations

3. The attempt at a solution
For the first one we claim that $\Delta = D = \text{conv}\left\{e_1, e_2, \ldots, e_{n+1}\right\}$. If $x = (x_1, x_2, \ldots, x_{n+1}) \in \Delta$ then $\sum_{i=1}^{n+1} x_i = 1$ and $x_i \geq 0$ for all $i$ and $x = \sum_{i=1}^{n+1} x_ie_i$ so $x \in D$. If $x \in D$ then $\sum_{i=1}^{n+1} \alpha_i e_i = (\alpha_1, \alpha_2, \ldots, \alpha_{n+1})$ with $\sum_{i=1}^{n+1} \alpha_i = 1$ and $\alpha_i \geq 0$ for all $i$. But then $x \in \Delta$. Thus, $\Delta$ and $D$ are the same set. Hence, $\Delta$ is a polytope.

For the second one we claim that $C = \text{conv}(S)$ where $S$ consists of all vectors $(x_1, x_2, \ldots, x_n)$ where $x_i \in \left\{-1,1\right\}$ for each $i$. Not sure what to do after that.

For the third one we claim that $O = P = \text{conv}(\pm e_1, \pm e_2, \ldots, \pm e_{n+1})$. If $x = (x_1, x_2, \ldots, x_{x+1}) \in O$ then $\sum_{i=1}^{n+1} \left|x_i\right| \leq 1$ and $x_i \geq 0$ for all $i$ and $x = \sum_{i=1}^{n+1} x_ie_i$ so $x \in O$. If $x \in P$ then $\sum_{i=1}^{n+1} \left|\alpha_i e_i\right| = (\alpha_1, \alpha_2, \ldots, \alpha_{n+1})$ with $\sum_{i=1}^{n+1} \alpha_i = 1$ and $\alpha_i \geq 0$ for all $i$. But then $x \in O$. Thus, $O$ and $P$ are the same set. Hence, $O$ is a polytope.

For the second and third cases, is it almost identical to the first one. Some help would be awesome!!!!!

2. Sep 24, 2015

### andrewkirk

In the first one, you haven't said what $e_1,...,e_{n+1}$ are. Is the origin one of them? If so, what are the others?

In the second one you've allowed coordinates to be negative, but the specification says they must be in the range [0,1] (assuming that when you wrote $x_1$ you meant $x_i$).

3. Sep 25, 2015

### squenshl

Oops right. $e_1, e_2, \ldots, e_{n+1}$ are the standard basis vectors so for example in $\mathbb{R}^2$ we have $e_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $e_2 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$.

Haha I did mean $x_i$ and clearly $x_i \in \left\{0,1\right\}$.

4. Sep 25, 2015

### Ray Vickson

What definition of "polytope" are you using?

5. Sep 25, 2015

### andrewkirk

You need to include the origin with all your $e_i$ points if you want to define the n-simplex as the convex hull of all the $e_i$, which is the usual definition. The origin is typically referred to as $e_0$. So then you have (n+1) points $e_0,e_1,...,e_n$ to define the canonical n-simplex as a subset of $\mathbb{R}^n$. I don't know why your question is using $\mathbb{R}^{n+1}$ instead of $\mathbb{R}^{n}$ in all three cases. Do you? Are they confusing the dimension of the affine space (usually taken to be $n$ for simplicity, clarity and tradition) with the number of points needed to define the n-simplex, which is (n+1)?

Also, what is your definition of polytope? There is no standard definition, but a number of alternatives, and they don't even always give the same sets. Some definitions give the solid set and some the boundaries (eg six faces of a cube+ interior, or just the six faces).

6. Sep 25, 2015

### squenshl

Right of course it's $\mathbb{R}^n$.
I'm an idiot.

The definition I'm using is a polytope is the convex hull of a finite set of points. That is, $S = \text{conv}\left\{x_1, x_2, \ldots, x_n\right\}$.

7. Sep 25, 2015

### andrewkirk

For the second one you need to show that any point in the unit n-dimensional hypercube can be expressed as a convex sum of the vertices. It's trivial for n=1. Maybe induction will help. A lemma that a convex sum of two convex sums is a convex sum may also be useful.

If you can do that, the third one is easily converted to the second one via a translation and a scaling.

8. Sep 25, 2015

### squenshl

Great cheers!!!

So I guess my first one is good then.

9. Sep 25, 2015

### Ray Vickson

I think it is clear that in the first question the origin is excluded: his simplex is an n-dimensional object located in an (n+1)-dimensional space. For example, when n = 1 it would be the line segment from (0,1) to (1,0) in the plane.

However, his planar simplex in $R^{n+1}$ is isomorphic to a solid simplex in $R^n$, if we regard the variable $x_{n+1}$ (for example) as akin to a "slack variable" in linear programming.

10. Sep 25, 2015

### andrewkirk

That's interesting Ray. I haven't seen simplices presented that way before, but you're right, it works! In fact it has one nice advantage, which is that the simplices thus defined are regular polyhedra, whereas those defined by including the origin as one of the points are not.

I still feel like it's kind of a waste of a dimension, and harder on the visualisation, to define a 3-simplex (tetrahedron) as a subset of $\mathbb{R}^4$ rather than of $\mathbb{R}^3$ but I daresay I'll get over it. At least dimensions have no greenhouse footprint

11. Sep 25, 2015

### squenshl

Okay I'm quite happy with my first solution.

For the third question instead of doing induction (because I suck at it) could my solution be:

We claim that $\Omega = O = \text{conv}(\pm e_1, \pm e_2, \ldots, \pm e_n)$. If $x = (x_1, x_2, \ldots, x_n) \in O$ then $\sum_{i=1}^n |x_i| \leq 1$ and $x_i \geq 0$ for all $i$ and $x = \sum_{i=1}^n |x_ie_i|$ so $x \in O$. If $x \in O$, then $x = \sum_{i=1}^n |\alpha_i e_i| = (\alpha_1, \alpha_2, \ldots, \alpha_n)$ with $\sum_{i=1}^n \alpha_i = 1$ and $\alpha_i \geq 0$ for all $i$. But then $x \in \Omega$. Thus, $\Omega$ and $O$ are the same set which means that $\Omega$ is a polytope.

12. Sep 26, 2015

### andrewkirk

On the first line you write $x_i\geq 0$. That is not given as a premise.
On the second line, what do you mean by $|x_ie_i|$ and $|\alpha_ie_i|$?

13. Sep 26, 2015

### Ray Vickson

I don't think you can write $x = \sum |x_i e_i|$, as that forbids negative values on some components---but negative values are allowed in your desired convex set. Anyway, the notation seems wrong: $|x_i e_i|$ looks like a scalar, but $x$ is supposed to be a vector.

14. Sep 26, 2015

### squenshl

I actually put this up before I realised that you can't have $x_i\geq 0$ therefore you can't have $|x_i e_i|$

15. Sep 26, 2015

### squenshl

In terms of the second problem, We claim that $C = \text{conv}(x_1, x_2, \ldots, x_n)$ where $x_i \in \left\{0,1\right\}$ for each $i$. Isn't that by definition a polytope so we can just end it there case closed.

16. Sep 26, 2015

### andrewkirk

You need to prove the claim true though, as $C$ is not defined that way in the question.

Also, what you have written in post 13 is the convex hull of $n$ numbers in $\mathbb{R}$, whereas what you need to write is the convex hull of $2^n$ points in $\mathbb{R}^n$.