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}$ .∎