凸包に関するカラテオドリの定理とその証明

$A$ が $S$ の凸包に含まれるので，$S$ の有限個の点 $P_i(\overrightarrow{p}_i)\:(i=1,\cdots, N)$ を用いて $\overrightarrow{a}=\displaystyle\sum_{i=1}^N\lambda_i\overrightarrow{p_i}$ と書ける(*)。

ただし，$\lambda_i\geq 0,\displaystyle\sum_{i=1}^N\lambda_i=1$

「今のところ $A$ は $N$ 個の点の凸結合で表現されているが，もし $N\geq n+2$ なら，係数 $\lambda$ を調整することで $N-1$ 個の凸結合でも表現できる」ことを証明すればOK（一つずつ減らしていって $n+1$ 個の点の凸結合で書けることが言える）。

さて，$N\geq n+2$ なら，$N-1$ 本のベクトル $\overrightarrow{p_i}-\overrightarrow{p_1}\:(i=2,\cdots N)$ は一次従属なので，

$\displaystyle\sum_{i=2}^N\mu_i(\overrightarrow{p_i}-\overrightarrow{p_1})=\overrightarrow{0}$ と表現できる。ただし，$\mu_k\neq 0$ となる $k$ が存在する。

これを使って $A$ を表す式（*）をズラす：

$\overrightarrow{a}=\displaystyle\sum_{i=1}^N\lambda_i\overrightarrow{p_i}+t \sum_{i=2}^N\mu_i(\overrightarrow{p_i}-\overrightarrow{p_1})\\ =\displaystyle\sum_{i=1}^N\lambda'_i\overrightarrow{p_i}$

ただし，$\lambda'_1=\lambda_1-t\displaystyle\sum_{i=2}^N\mu_i$

$\lambda'_i=\lambda_i+t\mu_i\:(i=2,\cdots, N)$

ここで，$\displaystyle\sum_{i=1}^N\lambda'_i=\sum_{i=1}^N\lambda_i=1$ に注意する。

$t$ を適切に選んでやると $\lambda'_i$ のいくつかは $0$ で残りは全て正になるようにできる（→注）。つまり，$\overrightarrow{a}$ が $N-1$ 個以下の $S$ の点の凸結合で表せたことになる。