# Convex hull of a set of points

Let $a_1,a_2...a_r \in R^n$ be points in $R^n$. Prove:$$CH(\{a_1,...,a_r\})=\left\{\sum_{i=1}^r\alpha_ia_i|\sum_{i=1}^r\alpha_i=1,\alpha_i\ge0\right\}=:K$$i.e. the convex hull of the $a_i$ is the set of all convex combinations of the $a_i$.

I have an idea of how to prove this but I am not sure if it's correct. I want to take two elements and show the line connecting them is contained in the set. But the problem is I don't know what K is.

• $K$ is the set on the right. The convex hull is usually defined as the smallest convex set containing the points in question. It is straightforward to show that $K$ is convex, so the left hand side is contained in $K$. You need to show that any element of $K$ is in the convex hull. Dec 2, 2014 at 17:47
• I think you must have a mistake in the last comment. If the convex hull is the smallest convex set containing $\{a_k\}$ then it must be contained in $K$ if $K$ is convex. Dec 2, 2014 at 18:07
• @copper.hat Yes Sorry I edited
– Erik
Dec 2, 2014 at 18:10
• It is also said that we need to show $K\subseteq CH(\{a_1,...a_r\})$ and $K$ is convex
– Erik
Dec 2, 2014 at 18:12
• How do you define the convex hull of a set of points? Dec 2, 2014 at 18:15

Let $\Sigma_m = \{ \mu \in [0,1]^m | \sum_k \mu_k =1 \}$. Call an element of $\Sigma_m$ a convex multiplier.

Suppose $x,y \in K$, then $x=\sum_k \xi_k a_k$, $y = \sum_k \upsilon_k a_k$ for some convex multipliers $\xi, \upsilon \in \Sigma_r$. Let $\mu \in [0,1]$, then it is easy to check that $\mu \xi+(1-\mu)\upsilon$ is also a convex multiplier and so $\mu x + (1-\mu) y = \sum_k (\mu \xi_k +(1-\mu)\upsilon_k) a_k \in K$. Hence $K$ is convex.

Since the convex hull $C=\operatorname{co} \{a_k \}$ is the smallest convex set, it follows that $C \subset K$.

Since $C$ is convex, if $x,y \in C$ and $\mu \in [0,1]$, we have $\mu x + (1-\mu) y \in C$ (note $(\mu, 1-\mu) \in \Sigma_2$).

Now proceed by induction. Suppose $x_k \in C$ and for that any $\mu \in \Sigma_m$ that $\sum_{k=1}^m \mu_k x_k \in C$. This is obvious for $m=1$ and the previous sentence shows that this is true for $m=2$.

Let $\mu \in \Sigma_{m+1}$. If $\mu_{m+1} = 1$, then $\sum_{k=1}^{m+1} \mu_k x_k = x_{m+1}$ which is in $C$ by assumption. So, suppose $\mu_{m+1} < 1$. Then note that ${1 \over {1-\mu_{m+1} } }(\mu_1,...,\mu_m) \in \Sigma_m$, and so $y={1 \over {1-\mu_{m+1} } } \sum_{k=1}^m \mu_k x_k \in C$. Hence $\mu_{m+1} + (1-\mu_{m+1}) y = \sum_{k=1}^{m+1} \mu_k x_k \in C$, and so the result it true for all $m$.

Since the $a_k \in C$, this shows that $K \subset C$.

Aside: The above shows that if $A \subset X$, where $X$ is some vector space, then $\operatorname{co} A = \{ \sum_{k=1}^m \mu_k a_k | m \in \mathbb{N}, a_k \in A, \mu \in \Sigma_m\}$