カラテオドリの定理

項数$k$が最小になるように、$x_i \in S$、$\lambda_i > 0$、$\sum_{i=1}^{k} \lambda_i = 1$として$x = \sum_{i=1}^{k} \lambda_i x_i$と表す。$k \le d + 1$であることを示す。

背理法のため$k \ge d + 2$と仮定する。すると$\mathbb{R}^d$内の$k - 1 \ge d + 1$個の差ベクトル$x_2 - x_1, x_3 - x_1, \ldots, x_k - x_1$は線形従属であるから、すべてがゼロではないスカラー$\mu_2, \ldots, \mu_k$が存在して$\sum_{i=2}^{k} \mu_i (x_i - x_1) = 0$を満たす。$\mu_1 = -\sum_{i=2}^{k} \mu_i$とおくと、$\sum_{i=1}^{k} \mu_i x_i = 0$かつ$\sum_{i=1}^{k} \mu_i = 0$となり、少なくとも一つの$\mu_i > 0$が存在する。

任意の実数$t$に対して係数の和が$1$のまま$x = \sum_{i=1}^{k} (\lambda_i - t \mu_i) x_i$と書ける。$t = \min_{\mu_i > 0} (\lambda_i / \mu_i) > 0$と選べば、新しい係数$\lambda_i - t \mu_i$はすべて非負となり、少なくとも一つが$0$になる。これは$x$を$S$のたかだか$k - 1$個の点の凸結合として表すことになり、$k$の最小性に矛盾する。