|
|
|
Viewing Version
3
of
'Radon's lemma'
|
[ view 'Radon's lemma'
|
back to history
]
| Title of object: |
Radon's lemma |
| Canonical Name: |
RadonsLemma |
| Type: |
Theorem |
| Created on: |
2003-09-07 22:44:58 |
| Modified on: |
2004-01-25 00:40:00 |
| Classification: |
msc:52C07, msc:52A20 |
| Keywords: |
convex hull |
Revision comment (for changes between this and next version):
| Changes for correction #5659 ('Absolute value of the negative coefficients'). |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
%\usepackage{xypic}
\makeatletter
\@ifundefined{bibname}{}{\renewcommand{\bibname}{References}}
\makeatother |
Content:
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.
\begin{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 existence of a solution to the system
%aligned inside equation with a tag does not work with LaTeX2HTML
\begin{align}\label{eqn:sys}
0&=\lambda_1 a_1+\lambda_2 a_2+\dotsb+\lambda_{d+2} a_{d+2}\\
0&=\lambda_1+\lambda_2+\dotsb+\lambda_{d+2}\notag
\end{align}
Let $A_1$ to be the set of those $a_i$ for which $\lambda_i$ is positive, and $A_2$ is the rest. Set $s$ to be the sum of positive $\lambda_i$'s. Then by the system~\eqref{eqn:sys} 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$.
\end{proof} |
|
|
|
|
|
