PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
Radon's lemma (Theorem)

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,\dotsc, a_{d+2}$ . Denote by $a_{i,j}$ the $j$ 'th component of $i$ 'th vector, and write the components in a matrix as \begin{equation*} 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}. \end{equation*}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
0 $\displaystyle =\lambda_1 a_1+\lambda_2 a_2+\dotsb+\lambda_{d+2} a_{d+2}$ (1)
0 $\displaystyle =\lambda_1+\lambda_2+\dotsb+\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 \begin{equation*} \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 \end{equation*}is a point of intersection of convex hulls of $A_1$ and $A_2$ . $ \qedsymbol$




"Radon's lemma" is owned by bbukh.
(view preamble | get metadata)

View style:

Keywords:  convex hull
Log in to rate this entry.
(view current ratings)

Cross-references: intersection, sum, positive, solution, equivalent, column vector, columns, rows, matrix, components, vector, component, number, without loss of generality, intersect, convex hulls, disjoint, points
There are 2 references to this entry.

This is version 5 of Radon's lemma, born on 2003-09-07, modified 2006-02-05.
Object id is 4710, canonical name is RadonsLemma.
Accessed 3233 times total.

Classification:
AMS MSC52C07 (Convex and discrete geometry :: Discrete geometry :: Lattices and convex bodies in $n$ dimensions)
 52A20 (Convex and discrete geometry :: General convexity :: Convex sets in $n$ dimensions )

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)