Show that if z is an extreme point of X = co{$x_1,...,x_k$} then z = $x_i$ for some i

Question

A question on a quiz that I couldn't figure out:
Let X = co{$x_1, x_2,..., x_k$} where $x_i$ ∈ $\mathbb{R^n}$, $i = 1,2,...,k$. (Note: co{$x_1,...,x_k$} stands for convex hull of {$x_1,...,x_k$})
(a) Show that if $z$ is an extreme point of X then $z$ = $x_i$ for some $i$.
(b) Show that $x_1$ is NOT an extreme point of X if and only if $x_i$ ∈ co{$x_2, x_3,...,x_k$}.
Any help is greatly appreciated!

Answer 1

An alternate definition of convex hull may be helpful here: $$\text{co}(x_1, \ldots, x_k \} := \{z \in \mathbb{R}^d: z = a_1 x_1 + \ldots + a_k x_k , a_i \geq 0, ~ a_1 + \ldots + a_k =1 \}.$$

(a): Suppose $z \neq x_i$ for all $i=1, \ldots,k$, then $z = \sum_{i=1}^k a_k x_k$ where $0< a_j < 1$ for some $j=1, \ldots,k$. Define $$z_t := t\sum_{i=1}^k a_k x_k +(1-t)x_j = (1-t(1-a_j))x_j + t\sum_{i=1, i \neq j}^k a_k x_k,$$ then we note that $z_t$ is in the convex hull for all $t \in [0,\frac{1}{a_j-1}]$, thus as $z=z_1$ lies in the interior of the line we are done.

(b): Suppose $x_1$ is an extreme point and $x \in \text{co}\{x_2,\ldots,x_k\}$, then by part (a) $x_1= x_j$ for some $j =2, \ldots, k$. Assuming that each $x_i$ is suppose to be distinct we are done.

Now suppose $x_1$ is not an extreme point, then for some $t \in (0,1)$ we have $x_1$ lying on the line between two points: $$x_1= t\sum_{i=1}^k a_i x_i +(1-t)\sum_{i=1}^k b_i x_i = (ta_1 +(1-t)b_1)x_1 + \sum_{i=2}^k (ta_i +(1-t)b_i)x_i.$$ We can rearrange this to give us $$x_1= (1-(ta_1 +(1-t)b_1))^{-1}\sum_{i=2}^k (ta_i +(1-t)b_i)x_i $$ and then note $$(1-(ta_1 +(1-t)b_1))^{-1}\sum_{i=2}^k (ta_i +(1-t)b_i) = 1,$$ thus $x_1 \in \text{co}\{x_2,\ldots,x_k\}$.