How to show that any polytope $P$ is spanned by the neighboring edges of any vertex $x$?

Question

Definitions:

A subset $P \subset \mathbb R^n$ is a polytope if it is the convex hull of finitely many points. Let $P \subset \mathbb R^n$ be a polytope. A face is a subset $F\subset P$ of the form $$F=\arg\max\{cx : x \in P\}$$ for some $c \in \mathbb R^n$. The dimension of a face is the dimension of its affine hull. A vertex is a zero dimensional face and an edge a one dimensional face. Two vertices $v, w$ are neighbors if their connecting line $\operatorname{conv}(\{v,w\})$ is an edge. Given a vertex $x$ define $$N(x) = \{y \in P: \text{ $y$ is a vertex neighboring $x$}\}$$ as the set of vertices that are neighbors of $x$, and define $$E(x) = \{y-x: y \in N(x)\}$$ as the set of edge vectors pointing from $x$ to its neighbors.

Question:

Let $P \subset \mathbb R^n$ be a polytope and let $x$ be a vertex. Let $$E(x) = \{y-x: \text{ $y$ is a vertex neighboring $x$}\}$$ be the set of vectors that point from $x$ to its neighboring vertices. How can we show that for any $z \in P$ there exist coefficients $\lambda_v\ge 0$ such that $$ z = x + \sum_{v \in E(x)}\lambda_v v$$

The question can also be phrased as:

How to show that the conical hull of $P-\{x\}$, $$K=\operatorname{cone}(P-\{x\}):=\{\sum_{i=1}^k \alpha_i (z_i-x): z_i \in P, \alpha_i\ge0, k =1,2\dots, \}$$ is generated by the edge vectors $E(x)$ ?

That is, show that $$K=\{\sum_{y \in N(x)} \alpha_y (y-x): \alpha_i\ge0 \}.$$

See also example and images below.

I think Farkas' Lemma should lead to the answer somehow, but so far I've had no success in my proof attempts.

---

Example:

Consider $\mathbb R^2$ and let $P$ be the polytope that is the convex hull of the points $(0,0), (0,1), (1,0)$. If we take the vertex $x=(0,0)$ then $N(x) = \{(0,1), (1,0)\} = E(x)$ and the set of vectors that are nonnegative linear combinations of elements of $E(x)$ is $\mathbb R^2$. In particular, any $z \in P$ can be expressed as a nonnegative linear combinations of elements of $E(x)$.

Here is an image (the shaded region is the set of points $z = x + \sum_{v \in E(x)}\lambda_v v$ for some nonnegative $\lambda_v$):

Here are two more images showing the idea for different polytopes: A polytope in $\mathbb R^2$: A polytope in $\mathbb R^3$:

Answer 1

Farkas' Lemma is indeed the way to go, but we need the right setting. Below I give a sketch.

For simplicity, assume that we work at a vertex $x=0$ of $P$. So we want to find a minimal set of generators for the cone $\DeclareMathOperator{\cone}{cone}C:=\cone(P)=\cone (\mathcal V)$, where $\mathcal V\subseteq P$ is the set of vertices of $P$. What we want to understand is whether every such "minimal generator" $y\in\mathcal V$ is a neighbor of $x$, because if so, then the edge-directions indeed generate $C$.

So, suppose that $y\in \mathcal V$ is part of such a minimal set of generators. Then $y\not\in C':=\cone(\mathcal V\setminus \{y\})$ (here you need to use that no three vertices of $P$ are colinear). By Farkas' Lemma, we can then separate $y$ from $C'$ via a hyperplane. In particular, we can choose this hyperplane with normal vector $n$ so that

$$\def\<{\langle}\def\>{\rangle}\<n,x\>=0,\quad\<n,y\> >0\quad\text{and}\quad\<n,z\><0\text{ for all $z\in \mathcal V\setminus\{x,y\}$}.$$

It is not too hard to argue that we can choose $n$ linearly independent from $y$ (if we are working in dimension $d\ge 2$). Then

$$n':=n-y\frac{\<n,y\>}{\<y,y\>} \not=0.$$

You can check that we have $\<n',x\>=\<n',y\>=0$ and $\<n',z\><0$ for all $z\in \mathcal V\setminus\{x,y\}$ (the latter needs some thought, but is possible). In other words, the hyperplane orthogonal to $n'$ supports $P$ exacty at the two vertices $x$ and $y$, which proves that these form an edge of $P$. In still other words, $\cone(P)$ is generated by the neighbors of $x$.

---

Some further explanation

As requested in the comments, I elaborate on $\<n',z\><0$ for all $z\in\mathcal V\setminus\{x,y\}$. As Epiousios noted, this is the same as

$$(*)\quad \underbrace{\<n,z\>}_{<0} < \underbrace{\frac{\<n,y\>}{\<y,y\>}}_{>0} \<y,z\>,$$

which would be obviously true if $\<y,z\>>0$. However, this is not always the case.

But, we can do a trick: before we start with any of our argument, we can tranform our polytope $P$ into an more convenient polytope $P'$, for which any two neighbors $y,z$ of $x=0$ satisfy $\<y,z\>>0$ (meaning $\sphericalangle(y,z)<90^\circ$). We can do this by stretching $P$ in a certain way. Hopefully, the following image makes this clearer:

Since this is a linear transformation, this changes nothing about the actual problem. But this time $(*)$ is trivially satified.

Answer 2

Notation. We assume that the polytope is $n$ dimensional, i.e the smallest affine subspace of $\mathbb{R}^n$ that contains the polytope is $\mathbb{R}^n$ itself; otherwise we restrict our attention to such affine subspace. We assume that $x$ is the origin for notational simplicity. At last, set $$ E:= \left \{\sum_{v \in E(x)} \lambda_v v: \lambda_v \ge 0 \right \} $$ to be the set we want to contain $P$. Let me also define $w( \ge b)= \{x: (x,w) \ge b\}$ for a vector $w$.

Overview. The heart of the proof is to show that if we cut the polytope very close to a vertex we obtain a tiny piramid. The other key observation is the fact that the thesis is local around the vertex: if we show that all points in P that are very close to zero belong to $E$, then for any $x$ and for sufficiently small $\varepsilon > 0$:

$$x = \frac{1}{\varepsilon} (\varepsilon x) = \frac{1}{\varepsilon} \left ( \sum_{v \in E(x) } \lambda_v v \right ) = \sum_{v \in E(x)} \frac{\lambda_v}{\varepsilon} v \in E$$

Because $\varepsilon x = (1-\varepsilon) 0 + \varepsilon x \in P$ by convexity.

Body. The main theorem in polytope theory states that a convex hull of finitely many points is the intersection of a finite number of half spaces (the ones defining faces), and viceversa a bounded intersection of a finite number of half spaces is the convex hull of its extreme points.

Let our polytope $P$ be defined by inequalities $w_i(\ge 0), z_k( \ge b_k)$ for some vectors $w_i, z_k$ and negative $b_k$. Indeed, a general half space is defined by $\{x: (y,x) \ge c\}$, and since $0 \in P$ we have that such $c$ is $\le 0$. Let $W= \cap_i w_i( \ge 0)$ and $Z= \cap_k z_k( \ge b_k)$. By definition we have that $P = W \cap Z$.

Let's get local. Since $0$ is in the interior of $Z$, there exist an $\varepsilon > 0$ such that $B_{\varepsilon}(0) \subset Z$, and thus

$$B_{\varepsilon}(0) \cap P = B_{\varepsilon}(0) \cap Z \cap W = B_{\varepsilon}(0) \cap W$$

This implies that the hyperplanes $w_i^{\perp}$ meet at a point: around zero we have

$$ B_{\varepsilon}(0) \cap \bigcap w_i^{\perp} = B_{\varepsilon}(0) \cap \bigcap w_i^{\perp} \cap W = B_{\varepsilon}(0) \cap \bigcap w_i^{\perp} \cap P = B_{\varepsilon}(0) \cap \bigcap_{F \text{ face at } 0 } F = \{0\} $$

and the dimension of a subspace can be checked around zero. Let me state the

Tiny piramid lemma. Let $y_1, \ldots, y_m$ be vectors generating $\mathbb{R}^n$ and set $Y= y_1(\ge 0) \cap \ldots y_m(\ge 0)$. Let also $\ell_1, \ldots, \ell_k$ be the lines obtained by intersecting some of the $y_i^{\perp}$. Then there exist a vector $u$ with the following properties:

1. $Y \subset u(\ge 0)$;
2. $Y \cap u^{\perp} = \{0\}$;
3. $X=Y \cap u(\le 1)$ is the convex hull of $\ell_i \cap u(\le 1)$ and $0$.

Proof. Firstly, note that if we show $X$ to be bounded (property 3'), then it will satisfy property (3). Indeed, by the main theorem in polytope theory, it would be the convex hull of its extreme points. It is easy to see that extreme points are the intersection of some hyperplanes that are zero dimensional. Take such intersection. If it does not contain $u(=1)$ as a factor, then it is $\{0\}$, because $0 \in y_i^{\perp}$. If it contains $u(=1)$, the other factors must meet at a line, because intersecting with an hyperplane can decrease dimension only by one.

Select a basis $y_1, \ldots, y_n$ out of the $y$'s and set $Y' = y_1(\ge 0) \cap \ldots y_n(\ge 0)$. Note that $Y \subset Y'$, so that if we show properties (1), (2) and (3') for $Y'$ we are done.

Let's do it. Up to a linear change of coordinates $A$ we can suppose $\{y_i\}$ is the canonical basis, i.e. $A y_i = e_i$. Set $u_0= \sum e_i$. It is evident that the first two properties are satisfied in this basis: if a vector $x$ has non negative coordinates, the sum of the coordinates is non negative, and if it is zero then $x=0$. Also, the space $$\bigcap_{i=1}^n e_i(\ge 0) \cap u_0(\le 1) = \{x: x_i \ge 0 , \sum x_i \le 1\}$$ is the standard simplex, thus it is bounded. When we change back basis, all the properties are still satisfied if we set $u:=A^tu_0$: indeed for any vector $z$ we have $$(A^{-1}z, A^t u_0) = z^t (A^t)^{-1} A^t u_0 = z^tu_0 = (z,u_0)$$

Conclusion. Using the fact that our $w_i$'s generate $\mathbb{R}^n$, we can use the tiny piramid lemma and find a cool $u$. A line obtained as an intersection of $w_i^{\perp}$'s is generated by a neighbour $v$, thus $W \cap u(\le 1)$ is the convex hull of zero and $v/(v,u)$ as $v$ varies in $E(x)$. Note that $v \in P \subset W$ implies that $(v,u) > 0$ by properties (1) and (2) of $u$.

Here we are. If we take $x \in P$, then $(x,u) > 0$ by properties (1), (2). We have that $x/(x,u) \in W \cap u(\le 1)$ is in the convex hull of zero and $v/(v,u)$, thus $x \in E$.