多面体

1 ⇒ 2：$c$ を「$x\in P$、$x\ne v$ なら $c\cdot x< c\cdot v$」となるようにとる。$v=(1-t)y+tz$（$y,z\in P$、$0< t< 1$）とし、$y\ne v$ と仮定すると、$z=v$ ではありえない（$z=v$ なら $(1-t)y=(1-t)v$ から $y=v$）ので $c\cdot y< c\cdot v$ かつ $c\cdot z< c\cdot v$ となり、$c\cdot v=(1-t)c\cdot y+tc\cdot z< c\cdot v$ という矛盾が出る。よって $y=v$ であり、同様に $z=v$ である。
2 ⇒ 3：対偶を示す。$\{a_i\mid i\in I(v)\}$ が張る部分空間が $\mathbb{R}^n$ でないなら、その直交補空間から $d\ne0$ をとれる。すなわち $a_i\cdot d=0$（$i\in I(v)$）である。$i\notin I(v)$ では $a_i\cdot v< b_i$ なので、$\varepsilon>0$ を十分小さくとれば、すべての $i\notin I(v)$ について $a_i\cdot v+\varepsilon\lvert a_i\cdot d\rvert\le b_i$ となる（不等式は有限個）。このとき $v\pm\varepsilon d$ はどの不等式も満たし、$P$ に属する。$v=\frac12(v+\varepsilon d)+\frac12(v-\varepsilon d)$ なので、$v$ は端点でない。
3 ⇒ 1：$c:=\sum_{i\in I(v)}a_i$、$\delta:=\sum_{i\in I(v)}b_i$ とおく。$x\in P$ なら $c\cdot x=\sum_{i\in I(v)}a_i\cdot x\le\delta=c\cdot v$ であり、等号はすべての $i\in I(v)$ で $a_i\cdot x=b_i$ のときに限る。仮定より連立 1 次方程式 $a_i\cdot x=b_i$（$i\in I(v)$）の係数行列の階数は $n$ なので、解は $v$ ただ 1 つである。よって $P\cap\{c\cdot x=\delta\}=\{v\}$ であり、$v$ は頂点である。$\square$

$v$ が頂点なら、thm-polyh-vertex の 3 により $I(v)$ から 1 次独立な $n$ 個の番号 $i_1,\dots,i_n$ を選べ、$v$ は対応する $n$ 本の方程式のただ 1 つの解である。$n$ 個の番号の選び方は $\binom mn$ 通りで、選び方ごとに解は高々 1 つなので、頂点は高々 $\binom mn$ 個である。$\square$

要点：$J$ の不等式は $t^*$ までは破れず、$J$ の外の不等式は $d$ の向きに動いても左辺が増えない。最小値をとる番号の不等式が新しく等号になり、その係数ベクトルは $d$ との内積が正なので、それまでの活性な係数ベクトルの張る空間の外にある。

1 ⇒ 3：頂点 $v$ では thm-polyh-vertex の 3 により $\{a_i\mid i\in I(v)\}$ が $\mathbb{R}^n$ を張るので、$A$ の行も $\mathbb{R}^n$ を張る。
3 ⇒ 1：$x\in P$ をとり、$r(x):=\operatorname{rank}\{a_i\mid i\in I(x)\}$ とする。$r(x)=n$ なら $x$ は頂点である。$r(x)< n$ なら、$a_i\cdot d=0$（$i\in I(x)$）を満たす $d\ne0$ がとれる。$A$ の階数は $n$ なので $Ad\ne0$ であり、$d$ と $-d$ の一方について $J$ が空でない。そちらを $d$ として lem-polyh-move を使うと、$r(y)>r(x)$ となる $y\in P$ が得られる。これを高々 $n$ 回繰り返すと、$r=n$ の点、すなわち頂点に達する。
2 ⇔ 3：$P$ が直線 $\{x+td\mid t\in\mathbb{R}\}$（$d\ne0$）を含むとする。各 $i$ について $a_i\cdot x+t\,a_i\cdot d\le b_i$ がすべての $t\in\mathbb{R}$ で成り立つので $a_i\cdot d=0$、すなわち $Ad=0$ であり、$A$ の階数は $n$ より小さい。逆に階数が $n$ より小さければ $Ad=0$ となる $d\ne0$ があり、$x\in P$ について直線 $x+td$ は $P$ に含まれる。$\square$

$P=\{Ax\le b\}$ とする。有界な集合は直線を含まないので、thm-polyh-pointed により $V\ne\emptyset$ であり、cor-polyh-finite-vertices により $V$ は有限である。$P$ は凸で $V\subset P$ なので $\operatorname{conv}V\subset P$ である。
逆の包含を、$k(x):=n-\operatorname{rank}\{a_i\mid i\in I(x)\}$ についての帰納法で示す。$k(x)=0$ なら $x$ は頂点である（thm-polyh-vertex）。$k(x)>0$ とし、$a_i\cdot d=0$（$i\in I(x)$）を満たす $d\ne0$ をとる。もし $a_j\cdot d\le0$ がすべての $j$ で成り立てば、すべての $t\ge0$ で $x+td\in P$ となり、$P$ の有界性に反する。よって $d$ について lem-polyh-move の $J$ は空でなく、同じ理由で $-d$ についても空でない。補題を $d$ と $-d$ に使うと、$s,t>0$ と
$$ y:=x+sd\in P,\qquad z:=x-td\in P,\qquad k(y)< k(x),\quad k(z)< k(x) $$
が得られる。帰納法の仮定により $y,z\in\operatorname{conv}V$ であり、
$$ x=\frac{t}{s+t}\,y+\frac{s}{s+t}\,z $$
なので $x\in\operatorname{conv}V$ である。$\square$

要点：$I_+$ の行は $x_n$ の上界 $U_i$、$I_-$ の行は下界 $L_j$ を与え、組 $(i,j)$ の新しい不等式はちょうど $L_j\le U_i$ と同値である。すべての下界がすべての上界以下なら、その間に $x_n$ をとれる。

要点：像は $\{(y,x)\mid y=Mx+q,\ Ax\le b\}$ の $y$ への射影なので、$x$ の座標を 1 つずつ消去すればよい。

$\Lambda:=\{(\lambda,\mu)\in\mathbb{R}^{k+l}\mid\lambda\ge0,\ \mu\ge0,\ \sum_i\lambda_i=1\}$ は多面体であり、集合は $\Lambda$ の線形写像 $(\lambda,\mu)\mapsto\sum_i\lambda_iv_i+\sum_j\mu_jr_j$ による像なので、cor-polyh-image により多面体である。$l=0$ のとき集合は $\operatorname{conv}\{v_1,\dots,v_k\}$ で、$\|\sum\lambda_iv_i\|\le\max_i\|v_i\|$ なので有界である。$\square$

1 ⇒ 2 は thm-polyh-conv-vertices、2 ⇒ 1 は thm-polyh-weyl である。最後の主張：$S=\operatorname{conv}F$（$F$ は有限集合）なら、$S$ の頂点は端点であり（thm-polyh-vertex）、有限集合の凸包の端点はもとの集合に属する（凸包 の記事の定理「凸多面体の頂点」の 1）。$\square$

要点：$x\in tP$ は $a_i\cdot x\le t$（すべての $i$）と同値で、有界性から $x\ne0$ なら $\max_ia_i\cdot x>0$ である。

要点：活性な制約のない点は不等式の連続性から内部の点であり、$a_i\cdot x=b_i$ となる点は $a_i$ の向きに少し動くと $P$ の外に出る。