Radon’s lemma

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
Canonical name	RadonsLemma
Date of creation	2013-03-22 13:56:48
Last modified on	2013-03-22 13:56:48
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	8
Author	bbukh (348)
Entry type	Theorem
Classification	msc 52A20
Classification	msc 52C07