1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ in the end its so simple :) $\endgroup$ – StefanH Apr 7 '14 at 22:32

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.