Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Prove that the convex hull of a set is the smallest convex set containing that set

First prove that the convex hull of X is itself a convex set containing X. Then show it is the smallest such set.

How do I prove this?

The definition of the convex hull of a set X is the set of all convex combinations of elements from X.

share|improve this question

marked as duplicate by Zev Chonoles Oct 8 '11 at 22:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4  
What definition of convex hull are you using? –  Zev Chonoles Oct 8 '11 at 21:57
1  
What have you tried? Can you prove either (a) the convex hull of X is convex or (b) every convex set containing X contains the convex hull of X? –  Chris Eagle Oct 8 '11 at 22:05

1 Answer 1

up vote 1 down vote accepted

As the hint in your problem indicates, proving that the convex hull $C(X)$ of $X$ is "the smallest convex set containing $X$" consists of proving two facts:

  1. $C(X)$ is a convex set containing $X$.
  2. Any other convex set $D$ that contains $X$ must contain $C(X)$.

First, let's write down the definition of $C(X)$ in symbols: $$C(X)=\left\{\sum_{i=1}^na_ix_i\;\bigg\vert\; a_1,\ldots,a_n\geq0, \sum_{i=1}^n a_i=1\right\}$$ In other words, $C(X)$ is the union of all convex combinations of elements of $X$.

To show that $C(X)\supseteq X$ is very easy: for any $a\in X$, we have that $$1a=a\in C(X).$$ To show that $C(X)$ is convex, take any two elements $\sum_{i=1}^na_ix_i$ and $\sum_{j=1}^mb_ix_i$ in $C(X)$ (where each $x_i,y_i\in X$, each $a_i,b_j\geq0$, and $\sum_{i=1}^na_i=1$ and $\sum_{j=1}^mb_j=1$) and show that the line connecting them is contained in $C(X)$ (that is, after all, the definition of convex set). Note that the line connecting them consists of points of the form $$(1-t)\left(\sum_{i=1}^na_ix_i\right)+t\left(\sum_{j=1}^mb_jy_j\right)=\sum_{k=1}^nc_kx_k+\sum_{k=i+1}^{n+m}c_ky_k=\sum_{k=1}^{n+m}c_kz_k$$ where $$c_k=\begin{cases}(1-t)a_k\;\;\text{ if }1\leq k\leq i\\ tb_{k-n}\;\;\qquad\text{ if }n+1\leq k\leq n+m\end{cases}$$ and $$z_k=\begin{cases}x_k\;\;\;\;\;\;\;\text{ if }1\leq k\leq i\\ y_{k-n}\;\;\text{ if }n+1\leq k\leq n+m\end{cases}$$ Furthermore, note that $$\sum_{k=1}^{n+m}=(1-t)\left(\sum_{i=1}^na_i\right)+t\left(\sum_{j=1}^mb_j\right)=(1-t)(1)+(t)1=(1-t)+t=1$$ Therefore, we have shown that any point on the line connecting two elements of $C(X)$ is also in $C(X)$ (because it is of the correct form), and therefore that $C(X)$ is convex.

Finally, to show that any convex set $D$ that contains $X$ must contain $C(X)$, simply use that $D$ is a convex set.

share|improve this answer
    
How do u show the line connecting these two elemtns is contained in C(X)? –  xuan Oct 9 '11 at 7:08
    
@xuan: My sincere apologies, I gave an absolutely incorrect definition of $C(X)$ and consequently much of my answer was wrong. I have corrected my answer and given a full explanation of how to do it (now using the correct definition). –  Zev Chonoles Oct 9 '11 at 7:42
    
Thank you so much! Just one more question, how to use the fact that D is a convex set to show that when it contains X it must contain C(X)? –  xuan Oct 9 '11 at 8:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.