Gale変換(Gale transform)とは、$\mathbb R^d$ をアフィンに張る $n$ 個の点 $a_1,\dots,a_n$ に、それらのアフィン従属関係の空間の基底を行とする行列の列 $b_1,\dots,b_n\in\mathbb R^{n-d-1}$ を対応させる操作である。$b_i$ は和が $0$ で全空間を張り、この 2 条件を満たすベクトルの組はすべて Gale 変換として現れる。番号の集合 $I$ の点が凸包のある面の上の点のちょうど全体であることは、残りの番号が空でなければ、残りの番号の $b_j$ の凸包の相対内部が原点を含むことと同値である。これにより、頂点が $d+2$ 個の $d$ 次元凸多面体の組合せ型は $\lfloor d^2/4\rfloor$ 個と分かる。
前提知識: 多面体, 凸包, Radonの定理(凸幾何), 直交補空間
Gale変換(Gale transform)は、$\mathbb R^d$ の $n$ 個の点 $a_1,\dots,a_n$ に、それらの間のアフィン従属関係の全体を書き出した $\mathbb R^{n-d-1}$ の $n$ 本のベクトル $b_1,\dots,b_n$ を対応させる操作である。D. Gale が 1956 年に導入した(Gal56)。点の個数 $n$ が次元 $d$ に近いとき、$\mathbb R^d$ の点の配置は複雑でも、Gale 変換は $\mathbb R^1$ や $\mathbb R^2$ の小さな絵になる。しかも、凸包 $P=\operatorname{conv}\{a_1,\dots,a_n\}$ のどの点の組が面を張るかが、Gale 変換の側では「どの $b_j$ の組の凸包が原点を相対内部に含むか」という条件に言い換えられる(thm-gale-face)。
この記事では Gale 変換を定義し、それがどのベクトルの組になりうるかを決め(prop-gale-basic・prop-gale-converse)、面の判定法を証明する。応用として、頂点が $d+2$ 個の $d$ 次元凸多面体の組合せ型を分類し、その個数が $\lfloor d^2/4\rfloor$ であることを示す(thm-gale-d2)。頂点が $d+3$ 個の場合の Perles の方法は主張と文献を述べる。
以下、$\mathbb R^m$ の点を縦ベクトルとし、$\mathbf 1=(1,\dots,1)^{\mathsf T}\in\mathbb R^n$ とする。$a_1,\dots,a_n\in\mathbb R^d$ が $\mathbb R^d$ をアフィンに張る とは、どの点も含む最小のアフィン部分空間が $\mathbb R^d$ であることをいう。このとき $n\ge d+1$ である。
$(d+1)\times n$ 行列 $\hat A$ を、第 $i$ 列が $\binom{1}{a_i}$ であるものとする。$\lambda\in\mathbb R^n$ について $\hat A\lambda=0$ は
$$
\sum_{i=1}^n\lambda_i=0,\qquad \sum_{i=1}^n\lambda_ia_i=0
$$
と同じであり、これが点の アフィン従属関係(Radonの定理(凸幾何) の定義「アフィン従属とアフィン独立」)である。$a_i$ が $\mathbb R^d$ をアフィンに張ることは $\operatorname{rank}\hat A=d+1$ と同値なので、アフィン従属関係の全体 $D(A):=\ker\hat A$ は $k:=n-d-1$ 次元の部分空間である。
$a_1,\dots,a_n\in\mathbb R^d$ は $\mathbb R^d$ をアフィンに張るとし、$k=n-d-1$ とする。$k\times n$ 行列 $B$ で、その行が $D(A)$ の基底をなすものを 1 つとり、$B$ の第 $i$ 列を $b_i\in\mathbb R^k$ とする。ベクトルの組 $(b_1,\dots,b_n)$ を $(a_1,\dots,a_n)$ の Gale 変換(Gale transform)という。
基底の取り方を変えると $B$ は可逆な $k\times k$ 行列 $g$ による $gB$ に変わるので、Gale 変換は $\mathbb R^k$ の線形同型を除いて定まる。以下に述べる性質(どの $b_j$ の組の凸包が原点を相対内部に含むか、など)は線形同型で変わらない。点の側の平行移動や $\mathbb R^d$ の可逆なアフィン変換も $D(A)$ を変えないので、Gale 変換を変えない。この定義は Fus06 §2.1(p. 4)で使われているもの(各点の座標の前に $1$ を付けた行列の列空間の直交補空間の基底)と同じである。$n=d+1$(単体の頂点)のときは $k=0$ で、Gale 変換は $\mathbb R^0$ の零ベクトルの組である。
$P=\operatorname{conv}\{a_1,\dots,a_n\}$ の面は、多面体 の定義「面・頂点・辺・ファセット」の意味で用いる。すなわち、アフィン関数 $\ell(x)=c_0+c\cdot x$ が $P$ の上で $\ell\ge0$ を満たすときの $P\cap\{\ell=0\}$ である。番号の集合 $I\subset[n]:=\{1,\dots,n\}$ について、$P$ の面 $F$ で $\{i\mid a_i\in F\}=I$ となるものがあるとき、$I$ を 面の添字集合 と呼ぶことにする。$F$ は $P$ の点を $a_i$ の凸結合に書いたとき $\ell$ の値が $0$ になる点なので、$F=\operatorname{conv}\{a_i\mid i\in I\}$ である。
アフィン関数 $\ell$ の値を並べたベクトル $(\ell(a_1),\dots,\ell(a_n))$ の全体を $V(A)\subset\mathbb R^n$ とする。$\ell(x)=c_0+c\cdot x$ の値のベクトルは $(c_0,c^{\mathsf T})\hat A$ なので、$V(A)$ は $\hat A$ の行空間である。
$(b_1,\dots,b_n)$ を $(a_1,\dots,a_n)$ の Gale 変換とする。
実行列 $M$ について $\ker M$ は $M$ の行空間の直交補空間であり、有限次元なので行空間は $\ker M$ の直交補空間でもある(直交補空間)。よって
$$
\ker B=(\text{$B$ の行空間})^\perp=D(A)^\perp=(\ker\hat A)^\perp=\text{$\hat A$ の行空間}=V(A)
$$
である。$\sum_i\lambda_ib_i=B\lambda$ なので 1 が従う。定数関数 $\ell=1$ から $\mathbf 1\in V(A)=\ker B$ なので $\sum_ib_i=B\mathbf 1=0$ である。$B$ の行は $k$ 本の 1 次独立なベクトルなので $\operatorname{rank}B=k$ で、列 $b_i$ は $\mathbb R^k$ を張る。$\square$
逆に、この 2 の性質をもつベクトルの組はすべて Gale 変換として現れる。
$k\ge0$、$n\ge k+1$ とし、$d:=n-k-1$ とする。$b_1,\dots,b_n\in\mathbb R^k$ が $\mathbb R^k$ を張り、$\sum_ib_i=0$ を満たすとする。このとき $\mathbb R^d$ をアフィンに張る点 $a_1,\dots,a_n$ で、$(b_1,\dots,b_n)$ がその Gale 変換になるものがある。
$B$ を列が $b_i$ の $k\times n$ 行列とする。$\operatorname{rank}B=k$ なので $\ker B$ は $n-k=d+1$ 次元で、仮定から $\mathbf 1\in\ker B$ である。$\ker B$ の基底 $\mathbf 1,v_1,\dots,v_d$ をとり、$a_i:=(v_1(i),\dots,v_d(i))^{\mathsf T}\in\mathbb R^d$ とおく。このとき $\hat A$ の行は $\mathbf 1,v_1^{\mathsf T},\dots,v_d^{\mathsf T}$ で、1 次独立だから $\operatorname{rank}\hat A=d+1$、すなわち $a_i$ は $\mathbb R^d$ をアフィンに張る。$\hat A$ の行空間は $\ker B$ なので、
$$
D(A)=\ker\hat A=(\ker B)^\perp=\text{$B$ の行空間}
$$
であり、$B$ の行は $D(A)$ の基底をなす。よって $(b_i)$ は $(a_i)$ の Gale 変換である。$\square$
有限集合 $S\subset\mathbb R^k$ の凸包の 相対内部 $\operatorname{relint}\operatorname{conv}S$ とは、$\operatorname{conv}S$ の アフィン包 の中での内部である。次の補題で、原点が相対内部にあることを係数の言葉に直す。
$b_j$($j\in J$)を $\mathbb R^k$ の有限個のベクトルとし、$J\ne\emptyset$ とする。$0\in\operatorname{relint}\operatorname{conv}\{b_j\mid j\in J\}$ であることと、すべて正の実数 $\lambda_j$($j\in J$)で $\sum_{j\in J}\lambda_jb_j=0$ となるものがあることは同値である。
$C:=\operatorname{conv}\{b_j\}$、$L$ を $C$ のアフィン包とする。
正の係数があるとする。$\lambda_j$ を和で割って $\sum\lambda_j=1$ としてよい。$0=\sum\lambda_jb_j\in C\subset L$ なので $L$ は原点を含む部分空間で、$\{b_j\}$ で張られる。$y\in L$ に対して、$y=\sum_j\nu_jb_j$、$\sum_j\nu_j=0$ となる $\nu$ を $y$ について線形にとる($L$ の基底を $b_{j}-b_{j_0}$ の中から選び、その係数を使う)。$y$ が $0$ に十分近ければ $\lambda_j+\nu_j>0$ がすべての $j$ で成り立ち、$y=\sum_j(\lambda_j+\nu_j)b_j$ は係数の和が $1$ の正の結合なので $C$ に属する。よって $0\in\operatorname{relint}C$ である。
逆に $0\in\operatorname{relint}C$ とする。重心 $c:=\frac1{\lvert J\rvert}\sum_jb_j\in C$ をとる。$0\in L$ なので $L$ は部分空間で、$-\varepsilon c\in L$ である。$\varepsilon>0$ を小さくとれば $-\varepsilon c\in C$ なので、$\mu_j\ge0$、$\sum\mu_j=1$ で $-\varepsilon c=\sum_j\mu_jb_j$ と書ける。すると
$$
0=\frac{1}{1+\varepsilon}(-\varepsilon c)+\frac{\varepsilon}{1+\varepsilon}c=\sum_j\Bigl(\frac{\mu_j}{1+\varepsilon}+\frac{\varepsilon}{(1+\varepsilon)\lvert J\rvert}\Bigr)b_j
$$
で、係数はすべて正である。$\square$
$a_1,\dots,a_n\in\mathbb R^d$ は $\mathbb R^d$ をアフィンに張り、$(b_1,\dots,b_n)$ をその Gale 変換、$P=\operatorname{conv}\{a_i\}$ とする。$I\subset[n]$ で、$J:=[n]\setminus I$ が空でないとする。次は同値である。
1 は「アフィン関数 $\ell$ で、$i\in I$ では $\ell(a_i)=0$、$j\in J$ では $\ell(a_j)>0$ となるものがある」と同値である。実際、そのような $\ell$ は $P$ の各点($a_i$ の凸結合)で $\ell\ge0$ を満たすので、$F=P\cap\{\ell=0\}$ は面で、$a_i\in F$ となるのはちょうど $i\in I$ のときである。逆に、$P$ の上で $\ell\ge0$ となる $\ell$ による面 $F=P\cap\{\ell=0\}$ で $\{i\mid a_i\in F\}=I$ となるものがあれば、$j\in J$ では $a_j\notin F$ から $\ell(a_j)>0$ なので、この $\ell$ が条件を満たす。
値のベクトルで言えば、1 は「$v\in V(A)$ で、$v_i=0$($i\in I$)、$v_j>0$($j\in J$)となるものがある」と同値である。
一方 lem-gale-relint により、2 は「正の $\lambda_j$($j\in J$)で $\sum_{j\in J}\lambda_jb_j=0$ となるものがある」と同値である。$i\in I$ では $\lambda_i:=0$ と延ばすと、これは「$\lambda\in\mathbb R^n$ で $\sum_i\lambda_ib_i=0$、$\lambda_i=0$($i\in I$)、$\lambda_j>0$($j\in J$)となるものがある」と同じであり、prop-gale-basic の 1 により $\sum_i\lambda_ib_i=0$ は $\lambda\in V(A)$ と同値である。よって 1 と 2 は同じ条件である。$\square$
$I=\{i\}$ とすると、次の判定が出る。
thm-gale-face の記号で、$a_i$ が $P$ の頂点であり、かつ $j\ne i$ ならば $a_j\ne a_i$ であることは、$0\in\operatorname{relint}\operatorname{conv}\{b_j\mid j\ne i\}$ と同値である。
$I=\{i\}$ が面の添字集合であることは、$\{a_i\}$ がある面 $F$ に等しく、$a_j\notin F$($j\ne i$)であることである。$F$ は $\{a_i\}$ の凸包 $\{a_i\}$ なので、これは「$a_i$ は頂点で、他の $a_j$ は $a_i$ と異なる」ことにほかならない。thm-gale-face を当てればよい。$\square$
$J=[n]$($I=\emptyset$)のとき、1 は空集合が面であること、2 は $\sum_ib_i=0$ から常に成り立つ。$J=\emptyset$ は定理から除いてある($P$ 自身は面だが、空集合の凸包は原点を含まない)。
$d=3$ で、$a_1,a_2=\pm e_1$、$a_3,a_4=\pm e_2$、$a_5,a_6=\pm e_3$ とする($e_i$ は標準基底)。$\sum\lambda_ia_i=0$ は $\lambda_1=\lambda_2$、$\lambda_3=\lambda_4$、$\lambda_5=\lambda_6$ と同値で、$\sum\lambda_i=0$ と合わせて $D(A)=\{(x,x,y,y,z,z)\mid x+y+z=0\}$ は $k=6-3-1=2$ 次元である。基底 $(1,1,-1,-1,0,0)$、$(1,1,0,0,-1,-1)$ を行にとると、Gale 変換は
$$
b_1=b_2=(1,1),\qquad b_3=b_4=(-1,0),\qquad b_5=b_6=(0,-1)
$$
である。三角形 $\operatorname{conv}\{e_1,e_2,e_3\}$($I=\{1,3,5\}$)では、$J=\{2,4,6\}$ について $b_2+b_4+b_6=0$ なので、thm-gale-face によりこれは面である。対になる 2 頂点 $\{e_1,-e_1\}$($I=\{1,2\}$)では、$\{b_3,b_4,b_5,b_6\}$ の凸包は $(-1,0)$ と $(0,-1)$ を結ぶ線分で原点を含まないので、$\operatorname{conv}\{\pm e_1\}$ は面でない。どの $i$ についても $b_i$ を除いた 5 本は $(1,1)$ と $(-1,0)$ と $(0,-1)$ をすべて含むので、正の係数で $0$ を表せ(たとえば $i=1$ では $b_2+\frac12(b_3+b_4+b_5+b_6)=0$)、cor-gale-vertex により 6 点はすべて頂点である。
正方形 $a_1=(0,0,0)$、$a_2=(1,1,0)$、$a_3=(1,0,0)$、$a_4=(0,1,0)$ と頂点 $a_5=(0,0,1)$ をとる。$a_1+a_2-a_3-a_4=0$ から $D(A)$ は $(1,1,-1,-1,0)$ で張られ($k=1$)、Gale 変換は $b=(1,1,-1,-1,0)$ である。$J=\{5\}$ では $\operatorname{conv}\{b_5\}=\{0\}$ なので $I=\{1,2,3,4\}$(底面)は面である。$J=\{1,3\}$ では $\operatorname{conv}\{1,-1\}=[-1,1]$ の相対内部が原点を含むので、$I=\{2,4,5\}$(側面の三角形)は面である。$J=\{1,5\}$ では $\operatorname{conv}\{1,0\}=[0,1]$ の相対内部 $(0,1)$ は原点を含まないので、$I=\{2,3,4\}$ は面でない。
$P$ を $d$ 次元の凸多面体で頂点がちょうど $d+2$ 個のものとし、頂点を $a_1,\dots,a_{d+2}$ とする($d\ge2$)。このとき $k=1$ で、Gale 変換は実数 $b_1,\dots,b_{d+2}$ であり、prop-gale-basic により和は $0$ で、すべてが $0$ ではない。正・負・$0$ の $b_i$ の個数を $p,q,z$ とする($p+q+z=d+2$)。
2 つの凸多面体が 組合せ的に同値 であるとは、頂点の間の全単射で、頂点の集合がファセットになるかどうかを保つものがあることをいう(Fus06 p. 1 の定義)。
$d\ge2$ とする。
実数の空でない有限集合 $\{b_j\mid j\in J\}$ の凸包は区間 $[\min b_j,\max b_j]$ で、その相対内部が $0$ を含むのは、すべての $b_j$ が $0$ のとき(凸包は $\{0\}$)か、正の $b_j$ と負の $b_j$ がともにあるとき(相対内部は開区間 $(\min,\max)$)に限る。正と $0$ だけ、または負と $0$ だけからなり $0$ でないものを含むときは、$0$ は区間の端点なので相対内部にない。
1:thm-gale-face により、真の面の添字集合 $I$ はこの条件を $J$ が満たすものである。$a_i$ はすべて頂点で互いに異なるので、cor-gale-vertex により、どの $i$ についても $b_i$ を除いた残りが条件を満たす。残りがすべて $0$ なら、和が $0$ であることから $b_i=0$ となり $b$ がすべて $0$ になるので、残りは正と負をともに含む。$p=1$ なら唯一の正の $b_i$ を除くと正がなくなるので $p\ge2$、同様に $q\ge2$ である。
ファセットを決める。$\hat A$ の列のうち $I$ に属するものの階数は $\lvert I\rvert-\dim(D(A)\cap\mathbb R^I)$($\mathbb R^I$ は $I$ の外で $0$ のベクトルの全体)で、$\{a_i\mid i\in I\}$ のアフィン包の次元はそれより $1$ 小さい。$D(A)$ は $b=(b_1,\dots,b_{d+2})$ で張られるので、$D(A)\cap\mathbb R^I\ne0$ となるのは $J$ の上で $b$ がすべて $0$ のときに限る。よって面 $\operatorname{conv}\{a_i\mid i\in I\}$ の次元は、$J$ の上で $b$ がすべて $0$ なら $d-\lvert J\rvert$、そうでなければ $d+1-\lvert J\rvert$ である。これが $d-1$ になる真の面は、$J=\{j\}$($b_j=0$)と、$\lvert J\rvert=2$ で $b$ が $J$ の上で $0$ でないもの、すなわち面の条件から $J=\{j,j'\}$($b_j>0>b_{j'}$)に限る。
2:1 により、ファセットの頂点の集合の族は、各 $b_i$ の符号だけで決まる。符号の個数が同じ($p,q$ を入れ替えたものも含む)2 つの $P$ は、符号を保つ(または全体を反転する)番号の付け替えで、ファセットの族が一致する。逆に、頂点 $d+1$ 個のファセットの個数が $z$ であり、頂点 $d$ 個のファセットの個数が $pq$ である。$p+q=d+2-z$ と $pq$ から $\{p,q\}$ は 2 次方程式の 2 根として決まる。
3:$b=(q,\dots,q,-p,\dots,-p,0,\dots,0)$(それぞれ $p,q,z$ 個)は和が $0$ で $\mathbb R^1$ を張るので、prop-gale-converse により $\mathbb R^d$ をアフィンに張る $d+2$ 点 $a_i$ の Gale 変換になる。$p,q\ge2$ から、どの $b_i$ を除いても正と負が残るので、cor-gale-vertex により $a_i$ はすべて頂点で互いに異なる。$\operatorname{conv}\{a_i\}$ は $d$ 次元で頂点が $d+2$ 個である。
4:1〜3 により、組合せ型は $2\le p\le q$、$p+q\le d+2$ を満たす整数の組 $(p,q)$ と 1 対 1 に対応する($z=d+2-p-q$)。$m:=\lfloor(d+2)/2\rfloor$ とすると、$p$ を固定したときの $q$ の個数は $d+3-2p$ なので、
$$
\sum_{p=2}^{m}(d+3-2p)=(m-1)(d+3)-(m-1)(m+2)=(m-1)(d+1-m)
$$
である。$d=2r$ なら $m=r+1$ で値は $r^2=d^2/4$、$d=2r+1$ なら $m=r+1$ で値は $r(r+1)=(d^2-1)/4$ であり、どちらも $\lfloor d^2/4\rfloor$ である。$\square$
$d=2$ では $(p,q,z)=(2,2,0)$ の四角形だけ、$d=3$ では $(2,2,1)$ の四角錐(ex-gale-pyramid)と $(2,3,0)$ の三角形の双角錐の 2 つである。双角錐では、正の 2 点が 2 つの頂、負の 3 点が真ん中の三角形で、ファセットは「一方の頂と三角形の 1 辺」の $2\cdot3=6$ 個になる。$z\ge1$ の型では、$b_i=0$ のとき $\{a_j\mid j\ne i\}$ の凸包は $a_i$ を含まないファセット(頂点 $d+1$ 個)なので、$P$ はその上の角錐である。
頂点が $d+3$ 個なら Gale 変換は平面のベクトルの組になる。Perles は、Gale 変換を平面の正 $2k$ 角形の頂点と中心に集めた 既約 Gale 図(頂点と中心に非負の整数の重みを置いた図)に縮約し、$d$ 次元で頂点 $d+3$ 個の凸多面体の組合せ型が、重みの和が $d+3$ で 3 つの条件を満たす既約 Gale 図(回転と鏡映を除いて)と 1 対 1 に対応することを示した(Fus06 Theorem 2 と証明の概略、pp. 4–5)。これにより、この組合せ型の個数 $c(d+3,d)$ の数え上げは図の数え上げに帰着する。Fusy は母関数を求め、最初の値が $d=2,3,4,5,6$ で $1,7,31,116,379$ であることを与えた(Fus06 Theorem 1、p. 2)。$d=2$ の $1$ は五角形、$d=3$ の $7$ は頂点 6 個の 3 次元凸多面体の型の数である。
各行は定理の仮定を 1 つだけ外し、どの結論が成り立たなくなるかを示す。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| thm-gale-face の 2 の「相対内部」(凸包に弱める) | ex-gale-pyramid の四角錐、$J=\{1,5\}$ | $0\in\operatorname{conv}\{b_1,b_5\}$ だが、$I=\{2,3,4\}$ は面の添字集合でなく、2 ⇒ 1 が成り立たない |
| thm-gale-face の「$J$ は空でない」 | 任意の配置で $J=\emptyset$($I=[n]$) | 1 は成り立つ($P$ 自身が面)が、空集合の凸包は原点を含まず、1 ⇒ 2 が成り立たない |
| thm-gale-d2 の「$a_i$ はすべて頂点」 | 平面の $(0,0),(1,0),(0,1)$ と重心 $(\frac13,\frac13)$($d=2$、4 点) | Gale 変換は $(1,1,1,-3)$ で $q=1$ となり、1 の結論 $q\ge2$ が成り立たない |
| prop-gale-converse の「$\sum_ib_i=0$」 | $k=1$、$n=3$、$b=(1,1,1)$ | $\mathbb R^1$ を張るが、これを Gale 変換にもつ 3 点はない |
1 行目:$b_1=1$、$b_5=0$ の凸包 $[0,1]$ は $0$ を含む。$\{a_2,a_3,a_4\}=\{(1,1,0),(1,0,0),(0,1,0)\}$ を含む面は底面 $\{x_3=0\}$ を含むことになり、$\ell\ge0$ で $\ell(a_2)=\ell(a_3)=\ell(a_4)=0$ となる $\ell$ は底面の平面の上で $0$ だから $\ell(a_1)=0$ でもある。よって $a_1$ を含まない面で $a_2,a_3,a_4$ を含むものはない。2 行目:定義から明らか。3 行目:$a_1+a_2+a_3-3a_4=0$ で係数の和も $0$ なので $D(A)$ は $(1,1,1,-3)$ で張られる。重心は三角形の内部にあり頂点でない。4 行目:prop-gale-basic の 2 により Gale 変換は和が $0$ であり、$\mathbb R^1$ の線形同型($0$ でない数を掛けること)で和が $0$ であることは変わらない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する