Gale–Ryserの定理(Gale–Ryser theorem)とは、行和 $r$(大きい順)、列和 $c$ の $0$-$1$ 行列が存在するための必要十分条件は、$r$ が $c$ の共役 $c^*$ に優越されることである、という定理である。ここで $c^*_i$ は $c_j\ge i$ となる $j$ の個数で、優越は先頭からの部分和の不等式と総和の一致を意味する。必要性は数え上げで、十分性は最大流の整数性で示せる。二部グラフの次数列の判定でもあり、行列は 1 行ずつ欲張りに作れ、同じ行和・列和の行列は $2\times2$ の交換でつながる。
前提知識: 最大流最小カット定理, Young図形, 二部グラフ
Gale–Ryserの定理(Gale–Ryser theorem)とは、$0$ と $1$ だけを成分にもち、行和が $r$、列和が $c$ である行列が存在するための必要十分条件を与える定理である。$r$ を大きい順に並べるとき、その条件は「$r$ が $c$ の共役に優越される」、すなわち
$$
\sum_{i\le k}r_i\le\sum_{i\le k}c^*_i\quad(k\ge1),\qquad\sum_ir_i=\sum_jc_j
$$
である。ここで $c^*_i$ は $c_j\ge i$ となる $j$ の個数である。
同じことを次のように言い換えられる。$m$ 台のバスと $n$ 家族があり、同じ家族の 2 人を同じバスに乗せないように全員を乗せたい(Gal57 p. 1079)。行 $i$ をバス、列 $j$ を家族とし、席数を $r_i$、人数を $c_j$ とすると、席がちょうど埋まる割り当ては、行和 $r$、列和 $c$ の $0$-$1$ 行列である。また、行列は 二部グラフ の隣接の表なので、定理は二部グラフの次数列の判定でもある。
定理の見方はこうである。列 $j$ の $1$ をすべて上に詰めた行列(Young 図形の形)の行和が $c^*$ で、これは行和が最も偏った場合である。任意の行列はそこから $1$ を列の中で動かして得られるので、行和は $c^*$ に優越される。逆に、優越されるなら 最大流最小カット定理 の整数性で行列が作れる。定理は 1957 年に Gale(Gal57)と Ryser(Rys57)が独立に得た(Rys57 p. 372 の脚注)。
| 主張 | 内容 | この記事で |
|---|---|---|
| thm-gr-main | 行列の存在の必要十分条件 | 証明する |
| prop-gr-greedy | 欲張りの構成 | 証明する |
| thm-gr-switch | 同じ行和・列和の行列は $2\times2$ の交換でつながる | 証明する |
| prop-gr-unique | 行列がただ 1 つであることと $r=c^*$ の同値 | 証明する |
| cor-gr-symmetric | 基本対称関数の積の単項式展開の三角性 | 証明する |
$r=(r_1,\dots,r_m)$、$c=(c_1,\dots,c_n)$ を $0$ 以上の整数の組とする。成分が $0$ か $1$ で、第 $i$ 行の和が $r_i$、第 $j$ 列の和が $c_j$ である $m\times n$ 行列の全体を $\mathfrak{A}(r,c)$ と書く。行と列の並べ替えは行和と列和を並べ替えるだけなので、存在を問うときは $r_1\ge\dots\ge r_m$ としてよい。
$r_1\ge\dots\ge r_m\ge0$、$c_1,\dots,c_n\ge0$ を整数とする。$\mathfrak{A}(r,c)\ne\emptyset$ であるための必要十分条件は $r\prec c^*$ である。
必要性. $A\in\mathfrak{A}(r,c)$ とする。最初の $k$ 行の第 $j$ 列の $1$ の個数は、$k$ 以下かつ $c_j$ 以下である。よって (1) により
$$
\sum_{i\le k}r_i\le\sum_j\min(c_j,k)=\sum_{i\le k}c^*_i
$$
である($k>m$ では左辺の $r_i$ を $0$ と読む)。行和の総和と列和の総和はともに $1$ の個数なので等しい。
十分性. $r\prec c^*$ とし、$N:=\sum_ir_i=\sum_jc_j$ とおく。次のネットワークを作る。頂点は始点 $s$、終点 $t$、行に対応する $x_1,\dots,x_m$、列に対応する $y_1,\dots,y_n$ である。弧と容量は $s\to x_i$ が $r_i$、$x_i\to y_j$ が $1$、$y_j\to t$ が $c_j$ である。
任意のカットの容量が $N$ 以上であることを示す。カットの始点側に属する $x_i$ の番号の集合を $I$、$y_j$ の番号の集合を $J$ とすると、カットの容量は
$$
\sum_{i\notin I}r_i+\lvert I\rvert\,\lvert J^{\mathrm c}\rvert+\sum_{j\in J}c_j
$$
である。第 2 項と第 3 項を列 $j$ ごとに見ると、$j\notin J$ なら $\lvert I\rvert$、$j\in J$ なら $c_j$ を足しているので、その和は $\sum_j\min(c_j,\lvert I\rvert)$ 以上である。$k:=\lvert I\rvert$ とおき、(1) と $r$ の並びを使うと、容量は
$$
\ge N-\sum_{i\in I}r_i+\sum_{i\le k}c^*_i\ge N-\sum_{i\le k}r_i+\sum_{i\le k}c^*_i\ge N
$$
である。カット $\{s\}$ の容量は $N$ なので、最小カットの容量は $N$ である。
最大流最小カット定理 とその記事の整数性定理により、値 $N$ の整数値の流れ $f$ がある。$A_{ij}:=f(x_i\to y_j)\in\{0,1\}$ とおく。値が $N$ なので $s\to x_i$ と $y_j\to t$ はすべて満たされ、$A$ の行和は $r_i$、列和は $c_j$ である。$\square$
十分性の証明は Gal57(§3、p. 1080 の定理)と同じ流れの方法で、最小カットの評価を上の形に書いた。Gal57 は「行和は $a_i$ 以下、列和は $b_j$ 以上」の問題を扱い、$a,b$ を大きい順にして、条件をすべての $k$ についての $\sum_{j\le k}b_j\le\sum_{j\le k}a^*_j$ で与える($\sum a_i=\sum b_j$ の場合が行和・列和を指定した行列の問題になる)。Rys57 は Theorem 2.1(p. 372)で、ex-gr-ferrers の形の行列の行の中で $1$ を動かして目標の列和を作る。prop-gr-greedy と同じ型の手順は、行と列を入れ替えた形で Gal57 pp. 1081–1082 にある(列和の大きい列から順に、残りの行和の大きい行へ $1$ を配る)。
$c=(3,2,1,1)$ なら $c^*=(4,2,1)$ である。列の $1$ を上に詰めた行列は下の左のもので、行和は $c^*$ である。第 1 行の第 4 列の $1$ を第 2 行へ移すと、行和は $r=(3,3,1)\prec c^*$ になる。
$$
\begin{pmatrix}1&1&1&1\\1&1&0&0\\1&0&0&0\end{pmatrix}\ \longrightarrow\ \begin{pmatrix}1&1&1&0\\1&1&0&1\\1&0&0&0\end{pmatrix}
$$
上に詰めた行列では thm-gr-main の必要性の不等式がすべて等号になり、$1$ を下の行へ移すほど部分和の差が開く。
$c_1,\dots,c_n$ がすべて $m$ 以下で、$\sum_jc_j=km$ とする。このとき、各行の和が $k$、列和が $c$ の $0$-$1$ 行列が存在する。
$c_j\le m$ なので $c^*_i=0$($i>m$)で、$c^*_1\ge\dots\ge c^*_m\ge0$ の和は $km$ である。広義単調減少の列の先頭 $i$ 個の平均は全体の平均 $k$ 以上なので、$\sum_{l\le i}c^*_l\ge ik$ である。よって $(k,\dots,k)\prec c^*$ で、thm-gr-main から従う。$\square$
Rys57 pp. 374–375 はこの場合を応用として挙げ、Latin 方形の完成の研究に現れる問題(各行に $1$ を $k$ 個もつ行を付け足して、各列の $1$ も $k$ 個にそろえる問題)に用いている。列和の偏りが大きくても、列和が $m$ 以下で総和が $m$ で割り切れれば、行和は必ずそろえられる。とくに $m=n$、$c=(k,\dots,k)$($0\le k\le n$)とすると、$n$ 頂点ずつの $k$-正則な単純二部グラフが存在する。
存在の証明は流れによるが、行列は 1 行ずつ簡単に作れる。鍵は次の交換である。
行列の 2 行 $i,i'$ と 2 列 $p,q$ の交点の $2\times2$ 小行列が $\begin{pmatrix}1&0\\0&1\end{pmatrix}$ または $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ のとき、これをもう一方に替える操作を 交換(interchange)という。行和と列和は変わらない。
$A\in\mathfrak{A}(r,c)$、$i$ を行、$p,q$ を列とし、$c_p\ge c_q$、$A_{ip}=0$、$A_{iq}=1$ とする。このとき $A_{i'p}=1$、$A_{i'q}=0$ となる行 $i'$ があり、第 $i,i'$ 行と第 $p,q$ 列で交換できる。
第 $i$ 行以外で、列 $p$ の $1$ の個数は $c_p$、列 $q$ の $1$ の個数は $c_q-1$ で、前者が多い。よって列 $p$ が $1$ で列 $q$ が $0$ の行がある。$\square$
$A\in\mathfrak{A}(r,c)$ が存在するとし、$i$ を任意の行とする。$T$ を $r_i$ 個の列の集合で、$p\in T$、$q\notin T$ なら $c_p\ge c_q$ であるものとする。このとき、第 $i$ 行の $1$ の位置がちょうど $T$ である $\mathfrak{A}(r,c)$ の元がある。
したがって、$\sum_ir_i=\sum_jc_j$ のとき、各行について順に、残りの列和の大きい順に $r_i$ 個の列に $1$ を置き、その列の残りの列和を $1$ ずつ減らす手順は、$\mathfrak{A}(r,c)\ne\emptyset$ のときに限り最後まで進み、$\mathfrak{A}(r,c)$ の元を与える。
第 $i$ 行の $1$ の位置が $T$ と異なれば、$p\in T$ で $A_{ip}=0$、$q\notin T$ で $A_{iq}=1$ のものがある。lem-gr-exchange で交換すると、第 $i$ 行の $1$ の位置と $T$ の差が減る。これを繰り返す。
手順について:第 $i$ 行を $T$ に固定した行列から第 $i$ 行を除くと、$r$ から $r_i$ を除き $c$ の $T$ の成分から $1$ を引いた組の行列が得られ、逆も成り立つ。よって存在は各段で保たれる。手順が途中で止まる(残りの列和が正の列が $r_i$ 個未満)なら、その段の組に行列はない。最後まで進めば、総和が等しいので残りの列和はすべて $0$ になり、作った行列は $\mathfrak{A}(r,c)$ の元である。$\square$
ex-gr-ferrers の $r=(3,3,1)$、$c=(3,2,1,1)$ では、第 1 行を第 1・2・3 列に置くと残りは $(2,1,0,1)$、第 2 行を第 1・2・4 列に置くと残りは $(1,0,0,0)$、第 3 行を第 1 列に置いて、右の行列を得る。
$A,A'\in\mathfrak{A}(r,c)$ なら、$A$ は交換を有限回行って $A'$ に変形できる。
行の個数 $m$ についての帰納法による。$m=1$ なら行は列和で決まり、$A=A'$ である。$m\ge2$ とする。第 1 行について prop-gr-greedy の $T$ を 1 つ固定する。その証明のとおり、$A$ も $A'$ も交換だけで第 1 行が $T$ の行列に変形できる。この 2 つの行列から第 1 行を除くと、行和と列和が同じ $(m-1)\times n$ 行列なので、帰納法の仮定により交換でつながる。$\square$
定理は Rys57 Theorem 3.1(p. 375)である。上の証明は欲張りの補題から導くように書き直した。
$r_1\ge\dots\ge r_m\ge0$ とし、$\mathfrak{A}(r,c)\ne\emptyset$ とする。$\mathfrak{A}(r,c)$ がただ 1 つの元からなることと $r=c^*$($0$ の成分を除いて)は同値である。このとき、その元は各列 $j$ で上から $c_j$ 個が $1$ の行列である。
$r=c^*$ とする。$A\in\mathfrak{A}(r,c)$ に対して thm-gr-main の必要性の不等式はすべて等号なので、すべての $k$ と $j$ で、第 $j$ 列の最初の $k$ 行の $1$ の個数は $\min(c_j,k)$ である。よって第 $j$ 列の $1$ は上の $c_j$ 個である。
逆に、ただ 1 つの元 $A$ をもつとする。交換ができると別の元ができるので、交換はできない。よって任意の 2 行について、$1$ の位置の集合の一方が他方を含む(含まなければ交換できる $2\times2$ 小行列がある)。$r$ は広義単調減少なので、第 $i$ 行の $1$ の位置は第 $i+1$ 行のものを含む。ゆえに各列の $1$ は上に詰まっていて、$r_i=\#\{j\mid c_j\ge i\}=c^*_i$ である。$\square$
$x_1,x_2,\dots$ の基本対称関数を $e_d$、分割 $\mu$ について $e_\mu:=\prod_je_{\mu_j}$、単項対称関数を $m_\lambda$ とする(対称関数)。
$\lvert\lambda\rvert=\lvert\mu\rvert$ のとき、$e_\mu=\sum_\lambda M_{\lambda\mu}m_\lambda$ の係数 $M_{\lambda\mu}$ は、行和 $\lambda$、列和 $\mu$ の $0$-$1$ 行列の個数である。$M_{\lambda\mu}\ne0$ であることと $\lambda\prec\mu^*$ は同値で、$M_{\mu^*\mu}=1$ である。
$e_{\mu_j}$ は $\mu_j$ 元集合 $T_j$ にわたる単項式 $\prod_{i\in T_j}x_i$ の和である。積を展開すると、$(T_j)_j$ は第 $j$ 列の $1$ の位置が $T_j$ の行列に対応し、$x_i$ の指数はその行列の第 $i$ 行の和である。よって $x^\lambda$ の係数は $M_{\lambda\mu}$ である。後半は thm-gr-main と prop-gr-unique である。$\square$
$\mu\mapsto\mu^*$ は全単射なので、これは $(e_\mu)$ から $(m_\lambda)$ への変換が優越の順序について対角が $1$ の三角行列であることを意味し、$(e_\mu)$ が基底であること(対称多項式の基本定理)の組合せ的な証明になる。$d=3$ では
$$
e_3=m_{111},\qquad e_2e_1=m_{21}+3m_{111},\qquad e_1^3=m_3+3m_{21}+6m_{111}
$$
である。
$r\prec c^*$ と $c\prec r^*$($c$ も大きい順にして)が同値であることも、行列の転置から分かる。これは Young図形 の記事の命題「共役は優越順序を逆にする」と $(c^*)^*=c$ からも従う。また、優越は Karamataの不等式 の記事にあるとおり、二重確率行列による「ならし」でもある。
二部グラフの次数列の判定としては、$\mathfrak{A}(r,c)\ne\emptyset$ は「片側の次数が $r$、もう片側の次数が $c$ の単純二部グラフがある」と同じことである。一般の単純グラフの次数列については、同じ型の判定として Erdős–Gallaiの定理 がある。
| 外す条件 | 反例 | 成り立たなくなるもの |
|---|---|---|
| 総和の一致 | $r=(1)$、$c=(1,1)$:部分和の不等式 $1\le2$ は成り立つが、総和が異なる | 「部分和の不等式だけで存在」は偽 |
| $r$ を大きい順に並べる | $r=(0,3,3)$、$c=(3,2,1)$:このままの順では $0\le3$、$3\le5$、$6\le6$ と成り立つが、行列はない(ex-gr-compute の 2) | 並べずに判定すること |
| $c$ の共役をとる | $r=(2,2)$、$c=(3,1)$:$r\prec c$ だが、$2$ 行の行列で列和 $3$ はありえない | 「$r\prec c$ なら存在」は偽 |
| 成分が $0,1$ | $r=(3,3)$、$c=(3,2,1)$:$0$-$1$ 行列はなく $r\not\prec c^*$ だが、$\begin{pmatrix}2&1&0\\1&1&1\end{pmatrix}$ は $0$ 以上の整数の行列として存在する | 条件は成分の上限 $1$ に依存する。上限がなければ総和の一致だけで足りる |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する