Convex Sets and extreme supports

187 Views Asked by At

Let the set $S$ in $R^n$ consists of the origin $0$ and $n$ lineary independent vectors $T_1, \ldots, T_n$. Show that $C(S)$, the convex hull of of $S$, is the intersection of its extreme supports, i.e. those which contain $n$ points from the set $S$.

Any hints how to prove this?

EDIT: For a hyperplane $H = \{ P : N\cdot P = a \} $ and a convex set $C$ such that $C$ is contained in $H^+ := \{ P : N\cdot P > a \}$, then $H$ is called a supporting hyperplane for $C$ and $H^+$ is called a support for $C$.

1

There are 1 best solutions below

1
On BEST ANSWER

The problem is affine, so we might as well assume the $T_i$ are the standard basis vectors: $T_i=e_i$. Then: \begin{align*} C(S) &= \left\{\lambda_0\cdot 0 + \sum_{i=1}^n\lambda_i e_i\;\colon\; \text{all $\lambda_i\ge 0$ and } \sum_{i=0}^n \lambda_i = 1 \right\} \\ &= \left\{\sum_{i=1}^n\lambda_i e_i \;\colon\; \text{all $\lambda_i\ge 0$ and } \sum_{i=1}^n \lambda_i \le 1 \right\} \\ &= \left\{x \;\colon\; \text{all $x_i\ge 0$ and } \sum_{i=1}^n x_i \le 1 \right\} \end{align*} where in the last step I'm writing $x=(x_1,\dotsc,x_n)$.

Now you just need to check that the halfspaces represented by the conditions $x_i\ge 0$ and $\sum_{i=1}^n x_i\le 1$ each contain $n$ points of $S$ on their respective boundaries.