6
$\begingroup$

I wonder whether such a result is known, and if so, whether the proof is trivial.

By polytope I mean the convex hull of finitely many points in $\Bbb R^n$. Assume the simplex to be symmetric and centered at the origin, so that the subspace goes through its center. The subspace can have any dimension $k\in\{0,...,n\}$.

Question: Is every polytope combinatorially equivalent to the intersection of a simplex and a linear subspace through its center?

If this is true, are there estimations for the dimension of the simplex needed?

$\endgroup$
  • $\begingroup$ What do you mean by a hyperplane? An affine flat in $\mathbb{R}^k$ of dimension $k-1$? $\endgroup$ – Wlodek Kuperberg Aug 30 '18 at 16:50
  • 1
    $\begingroup$ @WlodekKuperberg I think hyperplane was the wrong term. I replaced hyperplane by subspace. The dimension of the subspace can be anything between $0$ and the dimension of the polytope. $\endgroup$ – M. Winter Aug 30 '18 at 16:53
  • 5
    $\begingroup$ Yes, this is true even if you replace 'combinatorially equivalent' by 'affinely isomorphic'. It's a standard result from polyhedral geometry, although it's dual is more well-known: every polytope is the projection of a simplex. (You can show the latter simply by writing every point in the polytope as a convex combination of vertices.) $\endgroup$ – Tobias Fritz Aug 30 '18 at 16:56
  • 4
    $\begingroup$ @M.Winter: yes, it's fairly easy to see: you mainly need to check that the dual of a simplex is a simplex, and that the dual of projecting down to smaller dimension is taking the intersection with an affine subspace. Then the claim follows upon applying the projection result to the dual of your original polytope. $\endgroup$ – Tobias Fritz Aug 30 '18 at 17:05
  • 7
    $\begingroup$ @TobiasFritz: I think it would be valuable if you put your comments together in an answer. Your explanation is quite clear and useful. $\endgroup$ – Joseph O'Rourke Aug 30 '18 at 20:35
10
$\begingroup$

The answer is yes.

The fact that any polytope is affinely equivalent to a section of a simplex is well-known (see the answer by Tobias Fritz).

Now in any simplex with vertices $(v_i)$ we may consider projective transformations via reweighting barycentric coordinates: given positive numbers $(a_i)$, such a transformation is given by $$ \sum \lambda_i v_i \mapsto \frac{\sum a_i \lambda_i v_i}{\sum a_i \lambda_i}.$$

Projective transformations act transitively on the interior of the simplex, so it follows that any polytope is combinatorially equivalent to a section of some regular simplex through its center.

What I don't know is whether every polytope is affinely equivalent to a section of some regular simplex through its center.

$\endgroup$
10
$\begingroup$

Update: This answers the question without the extra condition on the subspace passing through the centre.

The answer is yes. The following stronger statement is an elementary fact of polyhedral geometry:

Every polytope is affinely isomorphic to the intersection of a simplex with an affine subspace.

One of the most standard useful facts of polyhedral geometry is that every polytope $P$ is the projection of a simplex. This is very simple to see: if $(v_i)_{i=1,\ldots,m}$ with $v_i\in\mathbb{R}^n$ are the vertices of $P$, then $P$ consists of precisely those points $x\in\mathbb{R}^m$ which can be written in the form $$x = \sum_{i=1}^m c_i v_i, \qquad \sum_{i=1}^m c_i = 1, \qquad c_i \geq 0.$$ Here, the simplex is the standard simplex in $\mathbb{R}^m$, as per the second and third equation. The first equation defines the linear projection from $\mathbb{R}^m$ down to $\mathbb{R}^n$. So the vertices of the simplex map bijectively to the vertices of $P$, and this assignment extends uniquely to an affine map.

Now let's see what happens to this statement under duality. The dual of a simplex is again a simplex, and the dual of a surjective affine map is an injective affine map. Hence we prove the claim upon using $P^{\vee\vee} = P$ together with the fact that $P^{\vee}$ is the projection of a simplex.

We can also use similar reasoning as above to write $P$ directly as the intersection of a positive orthant with an affine subspace, which is easily seen to be equivalent to the claim. This time, we should use the $H$-representation of $P$. So there is a matrix $A\in\mathbb{R}^{k\times n}$ and a vector $b\in\mathbb{R}^k$ such that $P$ is the set of solutions of the linear system $$A x - b \geq 0.$$ If $P$ is full-dimensional, then $k$ is the number of facets. This inequality shows that $P$ is the intersection of the positive orthant $\mathbb{R}_+^k$ with the affine subspace parametrized by $Ax - b$.

$\endgroup$
  • 4
    $\begingroup$ it has to pass through the center, how do we get this? $\endgroup$ – Fedor Petrov Aug 31 '18 at 10:56
  • $\begingroup$ @FedorPetrov: thanks, somehow I forgot about that condition while turning my comments into an answer. Right now I don't see how to do it and have edited accordingly. $\endgroup$ – Tobias Fritz Aug 31 '18 at 12:24
  • 1
    $\begingroup$ Maybe you can make the affine space linear by increasing the dimensions by 1? $\endgroup$ – Sam Hopkins Aug 31 '18 at 12:30
  • 3
    $\begingroup$ If you just ask for combinatorial equivalence, you can afterwards compose with a projective transformation to have the subspace going through the center. $\endgroup$ – Guillaume Aubrun Aug 31 '18 at 12:38
  • $\begingroup$ @GuillaumeAubrun: that sounds like something that you could add as a separate answer, no? (At least I'd be interested in the details!) $\endgroup$ – Tobias Fritz Aug 31 '18 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.