3

Let's $K\subset\mathbb{R}^n$ compact. If $K$ is convex then who to prove that any point of $K$ is convex combination of one or two extremal points of $K$?

Intuitively, for any closed ball that is true.

Elias Costa
  • 14,658
  • 3
    It won't be "one or two". Think of a simplex. In ${\mathbb R}^n$ you need $n+1$ points. – Robert Israel Apr 03 '12 at 21:08
  • Got it. I was thinking implicitly when the boundary of K coincides with its set of extremal point. For the ball in R ^ n this makes sense. But not for the simplex. Thank you. – Elias Costa Apr 03 '12 at 21:13

2 Answers2

6

The fact that in ${\mathbb R}^n$ each point of a compact convex set is a convex combination of at most $n+1$ extreme points is a theorem of Carathéodory. You can prove this by induction on $n$.

The case $n=0$ is easy. For the induction step, if $K$ is a compact convex set in ${\mathbb R}^{n+1}$ and $x \in K$, choosing some extreme point $y$ of $K$ we have $x = t y + (1-t) z$ where $0 \le t \le 1$ and $z$ is a boundary point of $K$. $K$ has a supporting hyperplane $H$ at $z$, and $H \cap K$ is a compact convex set in the $n$-dimensional space $H$ whose extreme points are extreme points of $K$. So represent $z$ as a convex combination $z = \sum_{i=1}^{n+1} c_i z_i$ of at most $n+1$ of these extreme points, and $x = t y + \sum_{i=1}^{n+1} (1-t) c_i z_i$ is a convex combination of at most $n+2$ extreme points of $K$.

Robert Israel
  • 448,999
1

This is the Krein-Milman Theorem. Just do a search for the proof of this, and you should find the answer you are looking for. The proof can be kind of complicated depending on how much generality you proof it for (it holds in general for locally compact Hausdorff spaces, which can be much nastier than $\mathbb{R}^n$).

Edit: Your claim breaks down even in $\mathbb{R}^2$. Consider the square determined by points (0,0), (0,1), (1,1), (1,0). Note that the extreme points of the square are exactly these corner points. Then consider the point $(1/2,1/3)$. Can you write this point as the convex combination of only one or two points?

Keaton
  • 1,214
  • I hoped that in the case of $\mathbb{R}^n$ in the proof would be easy. Thank you. – Elias Costa Apr 03 '12 at 20:36
  • If you want a reference that proves it for the simple case of $\mathbb{R}^n$ here is one that looks decent. It has a fair amount of buildup though, in proving the theorem you always have to go through what extreme points are, some facts about the convex hull, etc. http://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes.pdf – Keaton Apr 03 '12 at 20:44
  • I'm not interested in the existence of convex combination. But in the amount of extremal points of the convex combination. – Elias Costa Apr 03 '12 at 21:15
  • 1
    locally compact should be locally convex. – t.b. Apr 04 '12 at 05:48