# 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},\mathrm{\dots},{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=\left[\begin{array}{cccc}\hfill {a}_{1,1}\hfill & \hfill {a}_{2,1}\hfill & \hfill \mathrm{\dots}\hfill & \hfill {a}_{d+2,1}\hfill \\ \hfill {a}_{1,2}\hfill & \hfill {a}_{2,2}\hfill & \hfill \mathrm{\dots}\hfill & \hfill {a}_{d+2,2}\hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill {a}_{1,d}\hfill & \hfill {a}_{2,d}\hfill & \hfill \mathrm{\dots}\hfill & \hfill {a}_{d+2,d}\hfill \\ \hfill 1\hfill & \hfill 1\hfill & \hfill \mathrm{\dots}\hfill & \hfill 1\hfill \end{array}\right].$$ |

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

$0$ | $={\lambda}_{1}{a}_{1}+{\lambda}_{2}{a}_{2}+\mathrm{\cdots}+{\lambda}_{d+2}{a}_{d+2}$ | (1) | ||

$0$ | $={\lambda}_{1}+{\lambda}_{2}+\mathrm{\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 |