Let $P$ be a polytope of dimension $d$. Then for some $v \notin$ aff($P$), the pyramid $v \ast P$ has dimension $d+1$.

130 Views Asked by At

Let $P$ be a polytope of dimension $d$. Then for some $v \notin$ aff($P$), the pyramid $v \ast P$ has dimension $d+1$.

I’m looking for a straightforward argument to prove this statement. All the arguments I’ve come up with so far involve embedding $P$ in $\mathbb{R}^{d+1}$, and analyzing the number of linearly independent vectors. I’m hoping to find a simpler explanation, if possible.

Here are the definitions of the relevant terms in the course I’m doing:

$\cdot$ A polytope is defined as the convex hull of a finite set of points in some $\mathbb{R}^d$. Alternatively, it is a bounded polyhedron - defined as the intersection of finitely many closed halfspaces in $\mathbb{R}^d$.
$\cdot$ Let $P \subset \mathbb{R}^d$ be a (possibly empty) polytope of dimension $< d$. For a point $v \in \mathbb{R}^d \setminus \text{aff}(P)$, we define the pyramid $v \ast P$ with apex $v$ and base $P$ as the convex hull of $P \cup \{v\}$.

2

There are 2 best solutions below

0
On BEST ANSWER

I think if we review a few (standard) definitions that are missing from the Question statement, the sought "straightforward argument to prove" the quoted claim will quickly materialize.

Note the definition of a polytope added to the Question:

A polytope is defined as the convex hull of a finite set of points in some $\mathbb R^d$.

This is satisfactory, provided one knows how to define the convex hull of a finite set $S$ of points in a Euclidean space $\mathbb R^d$, or more generally in a vector space $V$ (or in an affine space). If one knows what it means for a set (in a vector space) to be convex, then one can say the convex hull of (finite) $S$ is the smallest convex set that contains $S$.

In any case our polytope $P$ will be a convex set in whatever vector space $V$ where it exists. As we are about to see, that space $V$ plays a critical role in proving the desired claim.

The notation $\operatorname{aff}(P)$ presumably means the affine hull of $P$, namely the smallest affine subset of $V$ that contains $P$. The affine subsets of $V$ are precisely the translates of its linear (vector) subspaces. That is:

$$ \operatorname{aff}(P) = \{w\} + W $$

for some vector $w \in V$ and some linear subspace $W \subset V$.

The dimension of $P$ is the same as the dimension of $\operatorname{aff}(P)$, which is defined to be the dimension of the linear subspace $W$ of which it is a translate.

If the dimension of $P$ is $d$, then in order to pick $v \in V \backslash \operatorname{aff}(P)$, $V$ will have to be of dimension greater than $d$. In other words, if $V$ were the same dimension as $\operatorname{aff}(P) \subset V$, then they would have to be equal as affine subsets, and we would be unable to choose $v\in V$ that is not in $\operatorname{aff}(P)$.

Thus we will assume $\operatorname{dim} V \gt d$ and choose $v \in V \backslash \operatorname{aff}(P)$. Then, since $\operatorname{aff}(v*P)$ is larger than $\operatorname{aff}(P)$, the dimension of pyramid $v*P$ must be greater than $d$, so its dimension is at least $d+1$.

Why is the dimension of $v*P$ not more than $d+1$? It suffices to show that $\operatorname{aff}(v*P)$ is contained the translate of a linear subspace of $V$ of dimension not more than $d+1$. We have all the facts necessary to show this. Since:

$$ P \subset \operatorname{aff}(P) = \{w\} + W $$

we have the pyramid:

$$ v*P \subset \operatorname{aff}(v*P) \subset \{w\} + W' $$

where $W'=\operatorname{span}(\{v-w\} \cup W)$ results from $W$ by extending its basis with vector $v-w$ (so that $v\in \{w\} + W'$). Hence $\operatorname{dim} W' \le d+1$ and the claim is proved.

3
On

When you say a set is of dimension $n$ it means that it can be embedded at least in $\mathbb{R}^n$. The idea of a dimension is that of this exercise: you are in $\mathbb{R}^d$; for a point here $v$ not in $\mathbb{R}^d$ we can join $v$ to $P$ by a segment in fact this segment (vector) is the added dimension if you want, this is the generalisation of moving from $\mathbb{R}^2$ to $\mathbb{R}^3$.