Convex hull of a set of points

381 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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\}$