# Why does a weighted sum of complex numbers stay in the convex hull

Given any set of complex numbers (or 2D vectors) $x_1,x_2,...x_n$ and real numbers $w_1,w_2,...,w_n$ if we have $\bar{x} = \frac{w_1x_1 + w_2x_2 ... + w_nx_n}{w_1 + w_2 ... + w_n}$, we will find that $\bar{x}$ is inside of the convex hull formed by $x_1, x_2,..., x_n$.

I guess I can sort of see why this is true but I don't know how to prove it. My main problem right now is that although I can imagine what a conex hull would look like, I don't know how to mathematically define it to determine whether or not $\bar{x}$ is in fact, in there.

I feel like this ought to be an easy problem, but I'm having some difficulty figuring it out.

• Your $\bar x$ is just a convex combination of your $x_i$. Hence, it belongs per definition to the convex hull (in your case: set of all convex combinations). – gerw Apr 11 '13 at 18:06
• @gerw: I think you're implicitly assuming that the $w_i$ all have the same sign; that wasn't given. – joriki Apr 11 '13 at 18:33
• Counter example: $x_1 = 0$ $x_2= 10$, $w_1=-1$ $w_2=2$. You forgot to specify that the weight $w_i$ are all positive (or all negative). – leonbloy Apr 11 '13 at 18:44

The convex hull of vectors $x_i$ is the set of vectors of the form $\sum_i\lambda_ix_i$ with $\lambda_i\ge0$ and $\sum_i\lambda_i=1$. In your case, the coefficients are $\lambda_i=w_i/\sum_iw_i$, and their sum is $1$. The $\lambda_i$ will be non-negative if and only if the $w_i$ all have the same sign, so in that case $\bar x$ is in the convex hull. If the $w_i$ have different signs, it will be more difficult to determine whether $\bar x$ is in the convex hull, since it may or may not be possible to express it as a different linear combination with non-negative coefficients.
A convex set $C$ is a set for which the line connecting any two points $x,y\in C$ is contained in the set, i.e. $\lambda x + (1-\lambda) y\in C$ for all $0\leq \lambda \leq 1$.
If we could show that this implies $\sum_{i=1}^n \lambda_i x_i$ for $x_i\in C$ and $\sum_{i=1}^n \lambda_i=1$ then your question is answered. This can be accomplished using induction. It holds for $n=1,2$ by definition, so assume it holds for all $n<m$ then we write $$\sum_{i=1}^m \lambda_i x_i = w_1 y_1 + w_2 y_2,$$ where we define $y_1 = \sum_{i=1}^{m-1} \frac{\lambda_i}{\sum_{i=1}^{m-1}\lambda_i} x_i$, $w_1 = \sum_{i=1}^{m-1}\lambda_i$, $y_2=x_m$, $w_2=\lambda_m$. By the induction hypothesis we have $y_1\in C$ and we also have $w_1+w_2=1$, so it follows by convexity that $w_1 y_1 + w_2 y_2$ is also in $C$.