Proof that the Convex Hull of a finite set S is equal to all convex combinations of S

Question

In $C^n$, how would you prove that the convex hull of a finite set $S$(convex hull being the intersection of all convex sets which contain $S$) is equal to the set consisting of all convex combinations of $S$?

Answer 1

As you have correctly identified the definition of Convex Hull, it is more useful to think of the convex hull as the set of all convex combinations visually and computationally since you can span a set of vectors, but "intersecting all convex sets containing a set" isn't exactly something you can have an easy time explicitly computing.

In any case, the proof generally works as follows given the definition of convex combination as

A convex combination of points $x_{1},...,x_{n} \in \mathbb{R}$ is a linear combination $\lambda_{1}x_{1} + ... + \lambda_{n}x_{n}$, where $\lambda_{1} + ... + \lambda_{n} = 1$ and $\lambda_{1},...,\lambda_{n} \geq 0$.

For notational convenience in the following proof I will use $$^{c}\sum_{i=1}^{n}\lambda_{i}x_{i}$$ to denote that the linear combination $\lambda_{1}x_{1} + ... + \lambda_{n}x_{n}$ is convex.

---

We first prove the following lemma, letting $C$ be a subset of $\mathbb{R}^d$:

Lemma: If $C$ is convex, then any convex combination of points from $C$ is again in $C$.

Proof: Assume that $C$ is convex. We prove by induction on $n$ that any point from $\mathbb{R}^d$ which is a convex combination of $n$ points from $C$ is again in $C$. For $n=1$ this is trivial, and for $n=2$ it follows by definition. So, let $n \geq 3$, and assume that any convex combination of fewer than $n$ points from $C$ is in $C$, and let $$x= ^{c}\sum_{i=1}^{n}\lambda_{i}x_{i}$$ If $\lambda_{i} = 0$ for some $i$, then $x$ is in fact a convex combination of fewer than $n$ points from $C$, and so $x$ belongs to $C$ by hypothesis. If $\lambda_{i} \neq 0$ for all $i$, then $\lambda_{i} < 1$ for all $i$, so $1 - \lambda_{1} > 0$. Therefore, $$x = ^{c}\sum_{i=1}^{n}\lambda_{i}x_{i} = \lambda_{1}x_{1} + \sum_{i=2}^{n} \lambda_{i}x_{i}=\lambda_{1}x_{1} + (1 - \lambda_{1})\sum_{i=2}^{n} \frac{\lambda_{i}}{1-\lambda_{1}}x_{i}$$ We then have that $\sum_{i=2}^{n} \frac{\lambda_{i}}{1-\lambda_{1}}x_{i}$ is a convex combination since $\lambda_{2} + ... + \lambda_{n} = 1 - \lambda_{1}$, and so $\sum_{i=2}^{n} \frac{\lambda_{i}}{1-\lambda_{1}}x_{i}$ is in $C$ by hypothesis. By the convexity of $C$ then $$\lambda_{1}x_{1} + (1- \lambda_{1})\sum_{i=2}^{n} \frac{\lambda_{i}}{1-\lambda_{1}}x_{i}$$ is also in $C$, that is $x$ is in $C$.

---

With the use of this lemma we can then prove

For any subset $M$ of $\mathbb{R}^d$, the convex hull $\text{conv}\{M\}$ is the set of all convex combinations of points from $M$.

Let $C$ denote the set of all convex combinations of points from $M$. Since $M \subset \text{conv}\{M\}$, each $x \in C$ is also a convex combination of points from the convex set $\text{conv}\{M\}$; by the Lemma we then have that $C \subset \text{conv}\{M\}$. To prove the opposite inclusion, it suffices to show that $C$ is a convex set containing $M$. Since each $x \in M$ has the trivial representation $x = 1x$ as a convex combination of points from $M$, it follows that $M \subset C$. To see that $\lambda_{1}x_{1} + \lambda_{2}x_{2}$ is in $C$ for each $x_{1},x_{2} \in C$ and each $\lambda_{1},\lambda_{2} \geq 0$ with $\lambda_{1} + \lambda_{2}=1$, note that by definition $x_{1}$ and $x_{2}$ are convex combinations of points from $M$, say $$x_{1} = ^{c}\sum_{i=1}^{n}\mu_{i}y_{i}, \; \; \; x_{2} = ^{c}\sum_{i=n+1}^{m}\mu_{i}y_{i}$$ But then $$\lambda_{1}x_{1} + \lambda_{2}x_{2} = \sum_{i=1}^{n} \lambda_{1}\mu_{i}y_{i} + \sum_{i=n+1}^{m}\lambda_{2}\mu_{i}y_{i}$$ and $$\lambda_{1}\mu_{i} \geq 0, \;\;\; \lambda_{2}\mu_{i} \geq 0, \;\;\; \sum_{i=1}^{n}\lambda_{1}\mu_{i} + \sum_{n+1}^{m}\lambda_{2}\mu_{i} =1$$ This shows that $\lambda_{1}x_{1} + \lambda_{2}x_{2}$ is a convex combination of the points $y_{1},...,y_{m}$ from $M$, so $\lambda_{1}x_{1} + \lambda_{2}x_{2}$ is in $C$ as desired.

Answer 2

This is a standard proof for any real vector space, not just $\mathbb{C}^n$. Write $S=\{x_1,\dots,x_n\}$. Let $C(S)$ denote the convex hull of $S$ and let $X$ be the set of all convex combinations of $S$. It should be clear that $X \subseteq C(S)$ since any convex set that contains $S$ must contain all convex combinations of the points in $S$.^* Therefore we just need to show that $X$ is convex, for then $C(S) \subseteq X$.

Let $x=s_1 x_1 + \cdots + s_n x_n$ and $y = t_1 x_1 + \cdots + t_n x_n$ be convex combinations in $X$ with $0 \le s_i,t_i \le 1$ and $\sum s_i = \sum t_i = 1$. If $0 \le a,b \le 1$ and $a+b=1$ then $$ax+by=(as_1+bt_1)x_1+\cdots+(as_n+bt_n)x_n \in X$$ since $$\sum (as_i+bt_i) = a\sum s_i+b\sum t_i = a+b=1$$ and $$0 \le as_i+bt_i \le \max(s_i,t_i)(a+b) \le 1.$$

^* You might want to prove the following fact:

A set $D$ is closed under arbitrary convex combinations if and only if it is closed under taking line segments.