0
$\begingroup$

Problem: Show that $S:= \lbrace v \in \mathbb{R}^m \mid v=\displaystyle \sum_{j=1}^n a_j v_j, \text{ with } a_1, \dots , a_m \in [0,1], \ \sum_{j=1}^m a_j=1 \rbrace$ the Simplex of $\mathbb{R}^n$ with vertices $v_1, \dots , v_m$ is convex.

So I have to verify the following definition

Definition (convex): $M \subset V$ where $V$ is a real or complex Vectorspace is called convex if $\forall (a,b) \in M^2$ and $\forall \lambda \in \mathbb{R}$ such that $0 \leq \lambda \leq 1$ the following always holds $\lambda a + (1-\lambda)b \in M$

My approach: Geometrically this property is very intuitive, for instance the 3-Simplex or Tetrahedron is of course convex, I will never be able to construct a line that somehow leaves the defined region. I do however fail when it comes to show this property in an analytic approach.

Let $(v,v^*) \in S^2$ and $\lambda \in [0,1]$, I then need to verify that: $$\lambda v+ (1-\lambda)v^* \in S \iff \lambda \sum_{j=1}^n a_j v_j + (1-\lambda) \sum_{j=1}^m a_j^* v_j^* \in S $$ What I can see is that for sure $\lambda \cdot a_j \in [0,1]$ and similarly $(1-\lambda) a_j^* \in [0,1]$ . But that is already the only thing I can grasp from this problem. Do I need to work with the norm and try to find an upper bound for the scalars? I would appreciate some hints on how to continue/get started on this problem

$\endgroup$
  • 1
    $\begingroup$ The vertices of the simplex are the same for $v$ and $v^\ast$, so $$\lambda v + (1-\lambda)v^\ast = \lambda\sum_{j=1}^n a_jv_j + (1-\lambda)\sum_{j=1}^n a_j^\ast v_j.$$ Can you see that you can group some terms to get what you need? $\endgroup$ – Daniel Fischer Apr 16 '14 at 16:33
  • $\begingroup$ @DanielFischer Intuitively I would merge the scalars into one and then say that $\lambda v + (1- \lambda)v^*= \sum_{j=1}^n b_jv_j$, then I would still have to verify that $\sum_{j=1}^n b_j=1 $right? But since the vertices are the same, the same argument should hold for the scalars I presume. $\endgroup$ – Spaced Apr 16 '14 at 16:38
  • $\begingroup$ The scalars are (generally) different, but you have a formula for $b_j$, what is that? $\endgroup$ – Daniel Fischer Apr 16 '14 at 16:44
  • $\begingroup$ $\lambda \sum_{j=1}^n a_j v_j + (1-\lambda) \sum_{j=1}^n a_j^* v_j = \sum_{j=1}^n ( \lambda a_j + (1-\lambda) a_j^*) v_j \implies b_j = \lambda a_j + (1-\lambda) a_j^*$. Summing these up leads to $ \sum_{j=1}^n b_j = \lambda \sum_{j=1}^n a_j + (1-\lambda) \sum_{j=1}^n a_j^* = \lambda + 1 - \lambda = 1$ Thanks @DanielFischer, your answers/comments never fail to enlighten me. $\endgroup$ – Spaced Apr 16 '14 at 16:49
3
$\begingroup$

There are many ways to approach this. Here is a brute force approach:

Let $u = \sum_k a_k v_k, v = \sum_k b_k v_k$, and $\lambda \in [0,1]$. We have $\sum_k a_k = \sum_k b_k = 1$ and $a_k,b_k \ge 0$.

Let $w = \lambda u + (1-\lambda) v = \sum_k (\lambda a_k + (1-\lambda) b_k) v_k$.

We have $\sum_k (\lambda a_k + (1-\lambda) b_k) = \lambda \sum_k a_k + (1-\lambda) \sum_k b_k = 1$, and $(\lambda a_k + (1-\lambda) b_k) \ge 0$ (where the latter follows because $\lambda, 1-\lambda, a_k,b_k$ are non-negative).

Hence $w \in S$.

$\endgroup$

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.