Gale–Ryserの定理

同義語:Gale-Ryserの定理Gale–Ryser theoremGale-Ryser theorem

概要

Gale–Ryserの定理(Gale–Ryser theorem)とは、行和 $r$(大きい順)、列和 $c$ の $0$-$1$ 行列が存在するための必要十分条件は、$r$ が $c$ の共役 $c^*$ に優越されることである、という定理である。ここで $c^*_i$ は $c_j\ge i$ となる $j$ の個数で、優越は先頭からの部分和の不等式と総和の一致を意味する。必要性は数え上げで、十分性は最大流の整数性で示せる。二部グラフの次数列の判定でもあり、行列は 1 行ずつ欲張りに作れ、同じ行和・列和の行列は $2\times2$ の交換でつながる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 最大流最小カット定理, 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$ としてよい。

共役と優越
  1. $c$ の 共役(conjugate、Gal57 の dual sequence)を、$i\ge1$ について $c^*_i:=\#\{j\mid c_j\ge i\}$ で定める。列 $c^*=(c^*_1,c^*_2,\dots)$ は広義単調減少で、$i$ が大きければ $0$ である。$c$ を Young図形 の列の長さとみると、$c^*_i$ は第 $i$ 行の箱の個数である。とくに
    $$ \sum_{i\le k}c^*_i=\sum_{j=1}^n\min(c_j,k)\qquad(k\ge0)\qquad(1) $$
    であり(第 $j$ 列の箱のうち第 $k$ 行までのものを数える)、$\sum_ic^*_i=\sum_jc_j$ である。
  2. 広義単調減少の $0$ 以上の整数の列 $a,b$(末尾に $0$ を補って同じ長さとみる)について、すべての $k$ で $\sum_{i\le k}a_i\le\sum_{i\le k}b_i$ かつ全体の和が等しいとき、$a$ は $b$ に 優越される といい、$a\prec b$ と書く(Muirheadの不等式 の記事の優越と同じ順序である)。

主定理

Gale–Ryser の定理

$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$

  1. の右辺 $\sum_j\min(c_j,k)$ は、$k$ 個の行に置ける $1$ の個数の上限である。定理は、この「$k$ 行に入りきらない」という障害のほかに障害がないことを述べる。最小カットの計算では行の部分集合 $I$ を動かす $2^m$ 通りの条件が現れるが、$r$ を大きい順に並べると、先頭の $k$ 行を選ぶ最も厳しい場合に帰着して $m$ 個の不等式に減る。Hallの結婚定理 の部分集合ごとの条件と比べると、この減り方がこの問題の特徴である。
    条件から行列の大きさの制約が自動的に出ることにも注意する。$k=1$ の不等式は $r_1\le c^*_1\le n$ を含む。$k=m$ の不等式は $N\le\sum_j\min(c_j,m)$ なので、すべての $c_j\le m$ を含む。
文献

十分性の証明は 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$ を配る)。

詰めた行列と 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$ を下の行へ移すほど部分和の差が開く。

判定の計算
  1. $r=(3,3,1)$、$c=(2,2,2,1)$:$c^*=(4,3)$ で、$3\le4$、$6\le7$、$7\le7$。存在する(全部で 7 個)。
  2. $r=(3,3,0)$、$c=(3,2,1)$:$c^*=(3,2,1)$ で、$3\le3$ だが $6>5$。存在しない。実際、第 1・2 行がすべて $1$ なので、どの列の和も $2$ 以上になるが、第 3 列の和は $1$ である。
  3. $r=(4,2)$、$c=(2,2,1,1)$:$c^*=(4,2)=r$ で、等号の場合である(prop-gr-unique によりただ 1 個)。
    判定 thm-gr-main と prop-gr-greedy・prop-gr-unique は、$m,n\le4$ のすべての分割の組($800$ 通り)で全数の列挙と一致することを確かめた。
行和がそろう場合

$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 列に置いて、右の行列を得る。

Ryser の交換定理

$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)である。上の証明は欲張りの補題から導くように書き直した。

行列がただ 1 つになる条件

$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$ に依存する。上限がなければ総和の一致だけで足りる

関連項目

参考文献

[1]
H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canadian Journal of Mathematics, 1957, 371–377(Theorem 2.1、p. 372、Theorem 3.1、p. 375)
[2]
David Gale, A theorem on flows in networks, Pacific Journal of Mathematics, 1957, 1073–1082(§3、pp. 1079–1082)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する