Proving Polytopes: Simplex, Cube, & Octahedron

[squenshl]

Homework Statement

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.

Homework Equations

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!

 

[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##).

 

[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\}##.

 

[Ray Vickson]

Homework Statement

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.

What definition of "polytope" are you using?

 

[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).

 

[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\}##.

 

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

 

[squenshl]

Great cheers!

So I guess my first one is good then.

 

[Ray Vickson]

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

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.

 

[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

 

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

 

[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|##?

 

[Ray Vickson]

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.

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.

 

[squenshl]

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

 

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

 

[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##.