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.

  • $\begingroup$ $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. $\endgroup$ – copper.hat Dec 2 '14 at 17:47
  • $\begingroup$ 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. $\endgroup$ – copper.hat Dec 2 '14 at 18:07
  • $\begingroup$ @copper.hat Yes Sorry I edited $\endgroup$ – Erik Dec 2 '14 at 18:10
  • $\begingroup$ It is also said that we need to show $K\subseteq CH(\{a_1,...a_r\})$ and $K$ is convex $\endgroup$ – Erik Dec 2 '14 at 18:12
  • $\begingroup$ How do you define the convex hull of a set of points? $\endgroup$ – copper.hat Dec 2 '14 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\}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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