Next, we look at some properties of facs

Proposition 2.2
Let \(P\subseteq\mathbb{R}^d\) be a polytope.
  1. Every polytope is the convex hull of its vertices: \(P=\operatorname{conv}(\operatorname{vert}(P))\).
  2. If a polytope can be written as the convex hull of a finite point set, then the set contains all the vertices of the polytope: \(P=\operatorname{conv}(V)\) implies that \(\operatorname{vert}(P)\subseteq V.\)

Notes
If \(V\) is a finite set that generates \(P\) so \(P = \operatorname{conv}(V)\). Then we have the following implication as a result

$$ \begin{align*} v_i \not\in \operatorname{conv}(V \setminus \{v_i\}) \longleftrightarrow \ v_i \text{ is a vertex of } P \end{align*} $$

This is something that will be shown using Farkas Lemma II in the proof below but it’s good note since it will be used frequently.

Proof:
Let \(V\) be a finite set of points such that \(P=\operatorname{conv}(V)\). Let \(v_i\in V\). If we can write \(v_i\) as a convex combination of the other vectors in \(V\), then \(v_i\) is not needed to generate \(P\). Hence, we can remove \(v_i\) from the set. Note that \(P\) is still the convex hull of the points in \(V \setminus \{v_i\}\). Continue removing any point that is a convex combination of the other points in the set. Since \(V\) is finite, this process will stop. Let the final set be \(W\). Then

$$ \begin{align*} P = \operatorname{conv}(W) \tag{1} \end{align*} $$

It remains to show that \(W\) is the set of vertices of \(P\). That, is $W = \operatorname{vert}(P).

\(W \subseteq \operatorname{vert}(P)\): Let \(v_i \in W\) and define

$$ \begin{align*} V' = W \setminus \{v_i\}. \end{align*} $$

By construction, we know that \(v_i \not\in \operatorname{conv}(V')\). We claim that if \(v_i\) cannot be expressed as convex combination of the points in \(V'\), then it is a vertex of \(P\). Since \(v_i \not\in \operatorname{conv}(V')\), then this implies that

$$ \begin{align*} \nexists t \geq 0, \quad v_i = \sum_j v_j t_j, \quad \sum_j t_j = 1 \end{align*} $$

We can re-write this condition as follows:

$$ \begin{align*} \nexists t\geq0: \begin{pmatrix} \mathbf{1}\\ V' \end{pmatrix} t = \begin{pmatrix} 1\\ v_i \end{pmatrix} \\ \end{align*} $$

Now let \(A = \begin{pmatrix} \mathbf{1}\\ V' \end{pmatrix}\) and let \(b = \begin{pmatrix} 1\\ v_i \end{pmatrix}\). We know \(t \geq 0\). Recall that Farkas Lemma (II) says if \(t \geq 0\) and \(At = b\) has no solution, then there exists a vector \(a\) such that \(aA \geq 0\) and \(ab < 0\). We can re-write this as follows

$$ \begin{align*} \exists a: a \begin{pmatrix} \mathbf{1}\\ V' \end{pmatrix} \geq0,\quad a \begin{pmatrix} 1\\ v_i \end{pmatrix} < 0 \tag{2} \end{align*} $$

But now we can let \(a = \begin{pmatrix} \beta & -b \end{pmatrix}\) Then

$$ \begin{align*} \begin{pmatrix} \beta & -b \end{pmatrix} \begin{pmatrix} \mathbf{1}\\ V' \end{pmatrix} \geq 0 \\ \beta\mathbf{1} - bV' \geq 0 \\ \beta\mathbf{1} \geq bV' \tag{3} \end{align*} $$

while

$$ \begin{align*} \begin{pmatrix} \beta & -b \end{pmatrix} \begin{pmatrix} 1\\ v_i \end{pmatrix} < 0 \\ \beta - bv_i < 0 \\ \beta < bv_i \tag{4} \end{align*} $$

Using (3) and (4) we can re-write (2) as follows

$$ \begin{align*} &\exists(\beta,-b)=a \quad \text{such that} \quad bV'\leq\beta\mathbf{1}\quad \text{ and }\quad bv_i>\beta \end{align*} $$

This statement is equivalent to

$$ \begin{align*} \exists\beta,b \quad \text{such that} \quad bv_j\leq\beta\text{ for }j\neq i \quad \text{ and }\quad bv_i>\beta. \end{align*} $$

So by Farkas lemma (II), we see that

$$ \begin{align*} H = \{ x \mid bx = \beta\} \end{align*} $$

is a separating hyperplane where every point in \(V'\) lies on one side (in the halfspace \(bx \leq \beta)\) while \(v_i\) lies on the other side since it satisfies \(bv_i > \beta\).

Next, since \(bv_j \leq \beta\) for all \(v_j \in V'\) and since \(\beta < bv_i\). Then we get that

$$ \begin{align*} bv_j < bv_i \tag{5} \end{align*} $$

for any point \(v_j \in V'\). Moreover, we also get

$$ \begin{align*} bx \leq bv_i \end{align*} $$

is a valid inequality of \(P\). Since it’s a valid inequality, then define the face

$$ \begin{align*} F = P \cap \{x \mid bx = bv_i \} \end{align*} $$

We claim that \(F = \{v_i\}\). Clearly \(v_i \in F\) since \(bv_i = bv_i\). Hence \(\{v_i\} \subseteq F\). Now, consider any point \(x \in F\). Then \(x \in P\) so \(x\) can be written as a convex combination of the points in \(W\)

$$ \begin{align*} x = \sum_k \lambda_k v_k \end{align*} $$

Since \(x \in F\), then we also have that \(bx = bv_i\). Suppose now that there exists some \(k \neq i\) such that \(\lambda_k > 0\). Then by (5) we know that \(bv_k < bv_i\). Therefore

$$ \begin{align*} bx &= \lambda_i (bv_i) + \sum_{k \neq i} \lambda_{k} (bv_k) \\ &< \lambda_i (bv_i) + \sum_{k \neq i} \lambda_k (bv_i) \quad \text{(since at least one $\lambda_k > 0$ and $bv_k < bv_i$)}\\ &= (bv_i) \sum_k \lambda_k \\ &= bv_i \quad \text{(since $\sum_k \lambda_k = 1$)} \\ \end{align*} $$

This is a contradiction. Hence every coefficient corresponding to \(v_k \neq v_i\) must be zero. Since we must have \(\sum_k \lambda_k = 1\), then we must also have that \(x = v_i\). Thus, \(F \subseteq \{v_i\}\). Since we proved both directions, then \(F = \{v_i\}\). Hence \(v_i\) is a vertex and therefore \(W \subseteq \operatorname{vert}(P)\) as we wanted to show.

\(\operatorname{vert}(P) \subseteq W\): Take any vertex \(v \in \operatorname{vert}(P)\). Suppose for the sake of contradiction that \(v \not\in W\). Since \(P = \operatorname{conv}(W)\), then \(v\) can be written as a convex combination of the points of \(W\) with

$$ \begin{align*} v = \sum_k \lambda_k w_k \end{align*} $$

where \(\lambda_k \geq 0\) and \(\sum_k \lambda_k = 1\). Since we assumed \(v \not\in W\), then \(w_k \neq v\) for all \(k\) so \(v\) is a convex combination of points in \(P \setminus \{v_i\}\). This is a contradiction since a vertex in \(P\) can never be written as a convex combination of points in \(P \setminus \{v_i\}\).

References