Every set $A\subset\mathbb{R}^{d}$ of $d+2$ or more points can be partitioned into two disjoint sets $A_{1}$ and $A_{2}$ such that the convex hulls of $A_{1}$ and $A_{2}$ intersect.

###### Proof.

Without loss of generality we assume that the set $A$ consists of exactly $d+2$ points which we number $a_{1},a_{2},\ldots,a_{d+2}$. Denote by $a_{i,j}$ the $j$’th component of $i$’th vector, and write the components in a matrix as

 $M=\begin{bmatrix}a_{1,1}&a_{2,1}&\dots&a_{d+2,1}\\ a_{1,2}&a_{2,2}&\dots&a_{d+2,2}\\ \vdots&\vdots&\ddots&\vdots\\ a_{1,d}&a_{2,d}&\dots&a_{d+2,d}\\ 1&1&\dots&1\end{bmatrix}.$

Since $M$ has fewer rows than columns, there is a non-zero column vector $\mathbf{\lambda}$ such that $M\mathbf{\lambda}=0$, which is equivalent to the existence of a solution to the system

 $\displaystyle 0$ $\displaystyle=\lambda_{1}a_{1}+\lambda_{2}a_{2}+\cdots+\lambda_{d+2}a_{d+2}$ (1) $\displaystyle 0$ $\displaystyle=\lambda_{1}+\lambda_{2}+\cdots+\lambda_{d+2}$

Let $A_{1}$ be the set of those $a_{i}$ for which $\lambda_{i}$ is positive, and $A_{2}$ be the rest. Set $s$ to be the sum of positive $\lambda_{i}$’s. Then by the system (1) above

 $\frac{1}{s}\sum_{a_{i}\in A_{1}}\lambda_{i}a_{i}=\frac{1}{s}\sum_{a_{i}\in A_{% 2}}(-\lambda_{i})a_{i}$

is a point of intersection of convex hulls of $A_{1}$ and $A_{2}$. ∎

Title Radon’s lemma RadonsLemma 2013-03-22 13:56:48 2013-03-22 13:56:48 bbukh (348) bbukh (348) 8 bbukh (348) Theorem msc 52A20 msc 52C07