# Prove that $P=\text{conv}(x_1,...,x_m)\subset\mathbb R^n$ is the convex hull of its extreme points

Let $P\subseteq \mathbb{R}^{n}$ is convex hull of finite points: $P=conv(x_1,x_2,\ldots,x_m)$. I need to show that $P$ is convex hull of its extreme points.

I am thinking about such proof. Let $x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}}$ is minimal subset of $x_1,x_2,\ldots,x_m$ for which $P=conv(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}})$. How to prove that each $x_{i_{j}}$ is extreme point?

If some $x_{i_{j}}$ is not extreme point, it can be represented $x_{i_{j}}=\frac{1}{2}x'+\frac{1}{2}x''$ where $x'\in P$ and $x''\in P$ and $x' \neq x''$. How to continue?

• Use minimality, i.e. that removing $x_{i_j}$ produces a smaller convex hull. Jan 19 '13 at 15:47
• The interior points can be written with positive barycentric coordinates, while the extreme points will have one zero barycentric coordinate. Here is the type of algebra needed to show this precisely: users.eecs.northwestern.edu/~thanh/paper/alg.pdf Jan 19 '13 at 16:04

Let $x_1,x_2,\ldots,x_n$ is minimal set for which $P=conv(x_1,x_2,\ldots,x_n)$ and $x_1$ is not extreme point. $x_1=\frac{1}{2}x'+\frac{1}{2}x''$ and $x'\neq x''$
$x'=\sum_{i=1}^{n}\lambda_i'x_i$ and $\sum_{i=1}^{n}\lambda_i'=1$
$x''=\sum_{i=1}^{n}\lambda_i''x_i$ and $\sum_{i=1}^{n}\lambda_i''=1$
So $x_1=\sum_{i=1}^{n}\frac{\lambda_i'+\lambda_i''}{2}x_i=\sum_{i=1}^{n}\mu_ix_i$
If $\mu_1<1$ then $x_1=\frac{1}{1-\mu_1}\sum_{i=2}^{n}\mu_ix_i$ and we would have contrary to minimality of set $x_1,x_2,\ldots,x_n$
If $\mu_1=1$ then $\mu_i=0$ for $i\neq1$ or $\frac{\lambda_i'+\lambda_i''}{2}=0$ which means $\lambda_i'=\lambda_i''=0$ for $i\neq1$, so that $x'= x_1 = x''$.