Radonの定理(凸幾何)

アフィン関係 $\mu$ があるとする。$\mu$ には正の係数と負の係数がともにあるので、$I$ と $J$ はどちらも空でなく、交わらず、合わせて $\{1,\dots,m\}$ である。$\sum_i\mu_i=0$ から $s=\sum_{i\in I}\mu_i=\sum_{j\in J}(-\mu_j)$ であり、$s>0$ である。$\sum_i\mu_ix_i=0$ を
$$ \sum_{i\in I}\mu_ix_i=\sum_{j\in J}(-\mu_j)x_j $$
と移項して $s$ で割ると、$p$ の 2 つの表示が等しいことが分かる。左の表示の係数 $\mu_i/s$ は正で和が $1$、右の表示の係数 $-\mu_j/s$ は $0$ 以上で和が $1$ なので、$p\in\operatorname{conv}x_I\cap\operatorname{conv}x_J$ である。
逆に Radon 分割 $I,J$ と Radon 点 $p$ があるとし、$p=\sum_{i\in I}\alpha_ix_i=\sum_{j\in J}\beta_jx_j$（$\alpha_i,\beta_j\ge0$、$\sum_{i\in I}\alpha_i=\sum_{j\in J}\beta_j=1$）と書く。$\nu_i:=\alpha_i$（$i\in I$）、$\nu_j:=-\beta_j$（$j\in J$）とおくと、$\sum_k\nu_kx_k=p-p=0$、$\sum_k\nu_k=1-1=0$ であり、$\sum_{i\in I}\alpha_i=1$ なので $\nu$ は全部は $0$ でない。よって $\nu$ はアフィン関係であり、$x_1,\dots,x_m$ はアフィン従属である。$\square$

$\hat x_i=(x_i,1)\in\mathbb{R}^{n+1}$ を考える。$n+1$ 次元の空間の $m\ge n+2$ 個のベクトルは線形独立でない（基底と次元）ので、すべては $0$ でない $\mu_i$ で $\sum_i\mu_i\hat x_i=0$ となるものがある。この等式の最初の $n$ 成分が $\sum_i\mu_ix_i=0$、最後の成分が $\sum_i\mu_i=0$ である。$\square$

lem-rd-dependence により $x_1,\dots,x_m$ はアフィン従属である。prop-rd-iff により、そのアフィン関係 $\mu$ の正の係数の添字 $I$ と、残りの添字 $J$ が Radon 分割を与える。$\square$

$\hat x_i=(x_i,1)$ を列とする $(n+1)\times(n+2)$ 行列を $A$ とすると、アフィン関係は $A$ の核の $0$ でないベクトルである。仮定と def-rd-affine の後の注意により、$A$ のどの $n+1$ 列も線形独立なので、$A$ の階数は $n+1$ で、核は 1 次元である。核を張るベクトルを $\mu$ とする。もし $\mu_k=0$ となる $k$ があれば、$\mu$ から第 $k$ 成分を除いたものは $k$ 以外の $n+1$ 点のアフィン関係になり、仮定に反する。よって $\mu$ の成分はすべて $0$ でない。
いま Radon 分割 $I,J$ と Radon 点 $p$ が与えられたとする。prf-rd-iff の後半の作り方で、$I$ 上で $0$ 以上、$J$ 上で $0$ 以下のアフィン関係 $\nu$ が得られ、$\nu|_I$ は $p$ を表す凸結合の係数である。$\nu$ は核に属するので、ある $c\ne0$ について $\nu=c\mu$ であり、$\nu$ の成分もすべて $0$ でない。したがって $I=\{i\mid\nu_i>0\}$ であり、これは $c>0$ なら $\{i\mid\mu_i>0\}$、$c< 0$ なら $\{i\mid\mu_i< 0\}$ である。どちらの場合も、分割は $\{\mu_i>0\}$ と $\{\mu_i< 0\}$ の組に一致する。さらに $\sum_{i\in I}\nu_i=1$ から $c$ が決まるので、係数 $\nu|_I$ と点 $p=\sum_{i\in I}\nu_ix_i$ も一つに決まる。$\square$

平面の 3 点がアフィン独立であることは一直線上にないことなので、prop-rd-unique の仮定が成り立つ。thm-rd-main により Radon 分割があり、2 つの部分はどちらも空でないので、点の個数の組は $(2,2)$ か $(1,3)$ である。2 点の凸包は線分なので $(2,2)$ は 1 にあたり、1 点の凸包はその点なので $(1,3)$ は 2 にあたる。逆に 1 や 2 が起これば、その 2 組は Radon 分割である。prop-rd-unique により Radon 分割はただ 1 つなので、1 と 2 が同時に起こることはない。$\square$

1. $I,J$ を Radon 分割、$p$ を Radon 点とする。半空間 $H$ が $x_I$ をすべて含めば、$H$ は凸なので $p\in\operatorname{conv}x_I\subset H$ である。$H$ が $x_J$ を 1 つも含まなければ、$x_J$ は補集合 $H^c$ に含まれ、$H^c$ も凸なので $p\in\operatorname{conv}x_J\subset H^c$ となって矛盾する。
2. $I$ または $J$ が空なら、すべての点を含む半空間（$a\ne0$ を 1 つとり $b$ を十分大きくする）か、どの点も含まない半空間（$b$ を十分小さくする）をとればよい。どちらも空でないとする。線形写像
   $$ L\colon\mathbb{R}^n\times\mathbb{R}\to\mathbb{R}^m,\qquad L(a,b):=(a\cdot x_1-b,\ \dots,\ a\cdot x_m-b) $$
   の各成分は $(a,b)$ と $(x_i,-1)$ の内積である。アフィン独立性から $(x_i,1)$ は線形独立であり、最後の成分の符号を変えた $(x_i,-1)$ も線形独立なので、$L$ は全射である（線形独立なベクトルとの内積の値は自由に指定できる）。そこで $i\in I$ では $-1$、$j\in J$ では $1$ という値をとる $(a,b)$ を選ぶ。$I,J$ がともに空でないので値が定数でなく、$a\ne0$ である。開半空間 $\{x\mid a\cdot x< b\}$ と閉半空間 $\{x\mid a\cdot x\le b\}$ は、どちらも $x_I$ を含み、$x_J$ を含まない。$\square$