Solution: Proof of Convex Hull's Convexity and Intersection Property

[Chris L T521]

Here's this week's problem.

-----

Problem: The convex hull of a subset $A$ in a vector space $V$ is the set of all convex combinations of vectors from $A$, that is,\[t_1x_1+t_2x_2+\cdots+t_nx_n,\]
where $t_i\in[0,1]$ and $\sum_{i=1}^n t_i=1$, $x_1,x_2,\ldots,x_n\in A$ and $n\in\mathbb{N}$ any natural number. Prove that the convex hull of $A$ is convex and that it is the intersection of all convex sets that contain $A$.

-----

 

[Chris L T521]

No one answered this week's question. Here's my solution:

Spoiler

Denote the convex hull of $A$ by\[C=\left\{\lambda_1x_1+\lambda_2x_2+\cdots+\lambda_nx_n : \lambda_i\in[0,1],\,\sum_{i=1}^n \lambda_i=1.\right\}\]
We first show that $C$ is convex. Let $\sum_i\alpha_ix_i,\sum_i \beta_ix_i\in C$. Consider the combination
\[t\left(\sum_i \alpha_ix_i\right) + (1-t)\left(\sum_i \beta_ix_i\right) = \sum_i x_i(t\alpha_i + (1-t)\beta_i)\]
for $t\in[0,1]$. Note that for all $i$,
\[t\alpha_i + (1-t)\beta_i\geq 0\]
since $\alpha_i,\beta_i\in[0,1]$. Furthermore,
\[\sum_i t\alpha_i + (1-t)\beta_i = t\left(\sum_i \alpha_i\right) + (1-t)\left(\sum_i \beta_i\right) = t(1)+(1-t)(1) = 1\]
Thus, $\sum_i x_i(t\alpha_i + (1-t)\beta_i)\in C$. Therefore $C$ is convex.Now, assume that $S$ is the intersection of all convex sets containing $x_1,\ldots,x_i$. We just showed that $C$ is convex, so we must have $S\subseteq C$. To show $C\subseteq S$, we proceed by induction on $i$. The base is trivial. Suppose that convex combinations of $n-1$ of the $x_i$'s are in $S$. WLOG, let $y=t_1x_1+\ldots + t_{n-1}x_{n-1}+t_nx_n$ for $x_i\in A$. If one of the $t_i=0$, then we are done by the inductive hypothesis. Otherwise, we note that
\[y=(1-t_n)\left( \frac{1}{1-t_n} (t_1x_1+\ldots + t_{n-1}x_{n-1})\right) + t_nx_n.\]
Since $\sum_{i=1}^n t_i=1$, we know that
\[1-t_n= t_1+\ldots +t_{n-1};\]
thus, the equation for $y$ reduced to $y=(1-t_n)z+t_nx_n$ where $z$ is a convex combination of $n-1$ of the $x_i$'s. This now reduces to the case where $n=2$, implying that $(1-t_n)z+t_n x_n$ is convex. Thus, $C\subseteq S$ which now implies that the convex hull is the intersection of all convex sets that contain $A$.$\hspace{.25in}\blacksquare$