5
$\begingroup$

If we arbitrarily choose a point from each orthant in $\mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but when I sit down and start thinking about it, I couldn't definitely find a set of $\lambda_i, i = 1,2,\cdots,2^n$ such that $0 \leq \lambda_i \leq 1, \sum_i \lambda_i = 1$ and $0 = \sum_i \lambda_i x_i$, where $x_i, i = 1,2,\cdots,2^n$ are any set of points satisfying the condition.

$\endgroup$
10
$\begingroup$

Induct on dimension.

In the $n=1$ base case, you have a positive number and a negative number; $0$ can be represented as a convex combination of them.

For $n>1$: Given your $2^n$ points, one from each orthant, divide them into 2 sets of size $2^{n-1}$, where the first set has points whose last coordinates are positive and the second set where the last coordinates are negative. By the inductive hypothesis there is a convex combo of the first set of points such that the first $n-1$ coordinates vanish, and similarly for the second set. The last coordinates of these two convex combos are positive and negative, so there is a convex combo of them that is zero.

$\endgroup$
3
$\begingroup$

Take in pairs the points that differ in sign for the coordinate $n$ (and only that one) and form the convex combinations such that that coordinate is cancelled.

Now you have $2^{n-1}$ points in each orthants of the diminished space.

The results holds because the convex combination of linear combinations is a convex combination.

enter image description here

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