5
$\begingroup$

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 is an image showing the idea of the example.

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

$\endgroup$
7
  • $\begingroup$ The vertex cone of polytope P as you define it (including $P$) looks less usual than $-P$, its opposite (obtained by reversing all the vectors, therefore non including the interior of $P$) $\endgroup$
    – Jean Marie
    Aug 29 '20 at 12:41
  • $\begingroup$ @JeanMarie Thank you for your comment - I made an error when first asking this question and have now reformuated it. $\endgroup$
    – Epiousios
    Sep 3 '20 at 9:43
  • $\begingroup$ Isn't it sufficient to show that $E$ is a free family of cardinal $n$, then show the positivity of coefficients in this basis? $\endgroup$
    – Joce
    Sep 7 '20 at 9:29
  • $\begingroup$ @Joce Thanks for your comment! I'm not familiar with free families, unfortunately. Could you recommend a book or another resource that introduces them and explains their relation to cones/polytopes? $\endgroup$
    – Epiousios
    Sep 7 '20 at 10:09
  • $\begingroup$ Oh, a free family is simply a set of linearly independent vectors. Very general linear algebra. en.wikipedia.org/wiki/Basis_(linear_algebra) $\endgroup$
    – Joce
    Sep 7 '20 at 11:22
4
+150
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @MWinter thank you for your nice answer! I have understood that we can choose $n$ to satisfy the inequalities resulting from Farkas' lemma with strict inequality by adding $\varepsilon c$ to $n$, if necessary, where $\{0\} = \arg\max\{cz: z \in P\}$. Provided the dimension is at least two, we can then pick $n$ linearly independent from $y$ by adding $\varepsilon e^1$ to $n$, if necessary, where $e^1$ is the first unit vector. $\endgroup$
    – Epiousios
    Sep 9 '20 at 17:39
  • $\begingroup$ However I don't understand why $\def\<{\langle}\def\>{\rangle}\<n',z\><0$ for all $z\in \mathcal V\setminus\{x,y\}$ holds. If we pick $z \in V\setminus\{x,y\}$ then $$\<n', z\> = \<n, z\>-\frac{\<n, y\>}{\<y, y\>}\<y, z\>.$$ Now, $\<n, z\>$ is negative, $\frac{\<n, y\>}{\<y, y\>}$ is positive, but $\<y, z\>$ could have either sign, right? I'm not really sure how to continue from here... Could you give me a pointer on how to proceed? $\endgroup$
    – Epiousios
    Sep 9 '20 at 17:39
  • 1
    $\begingroup$ @Epiousios I added an explanation. It comes down to: if $\<y,z\>>0$ is not true for your polytope, then transform it linearly to make this true. $\endgroup$
    – M. Winter
    Sep 9 '20 at 19:53
  • $\begingroup$ @MWinter thank you very much for your explanation, this answers my question, I think! By the way, I really like your visualizations: May I ask which software you use? $\endgroup$
    – Epiousios
    Sep 9 '20 at 20:59
  • 1
    $\begingroup$ @Epiousios For the graphics I use InkScape, but probably any (vector) graphics software would do. I am just most familiar with this one :) $\endgroup$
    – M. Winter
    Sep 9 '20 at 21:02
1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ i think the solution of M. Winter is more clever, but my proof use a substantially different approach so I posted it anyway. (also, I have worked on it quite a bit, and here is for sure more useful than on my drafts ^^) $\endgroup$ Sep 8 '20 at 0:43
  • 1
    $\begingroup$ Thank you for this very creative and well-explained answer! I briefly thought about trying to apply the main theorem of polytope theory but I didn't really know how to do it. I learned a lot from your answer - thank you again! $\endgroup$
    – Epiousios
    Sep 9 '20 at 20:57
  • $\begingroup$ Thank you very much :D $\endgroup$ Sep 10 '20 at 10:06

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.