Bregmanの定理

同義語:Bregman–Mincの不等式Minc予想Bregman's theoremBregman–Minc inequality

概要

Bregmanの定理(Bregman's theorem)とは、行和が $r_1,\dots,r_n\ge1$ の $n\times n$ の $0,1$ 行列 $A$ のパーマネントについて $\operatorname{per}A\le\prod_i(r_i!)^{1/r_i}$ が成り立つという定理である。パーマネントは二部グラフの完全マッチングの個数なので、次数だけから個数を上から抑える評価になる。等号は、行と列の並べ替えで全部 $1$ の正方行列のブロック対角になるときに限る。Minc の予想を Bregman が証明したもので、順序を無作為にするエントロピーの短い証明があり、Latin 方陣の個数の評価などに使われる。

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

前提知識: 二部グラフ, Shannonエントロピー, Hallの結婚定理

二部グラフの完全マッチングはいくつあるか。左の頂点 $i$ の次数を $r_i$ とすると、各頂点が相手を選ぶ方法は高々 $r_i$ 通りなので、個数は $\prod_ir_i$ 以下である。しかしこの評価は粗く、$r_i=r$ で揃っているときは指数の底で約 $e$ 倍も損をする。先に選んだ頂点が相手を使ってしまう分を見込めば、底が $r$ から $(r!)^{1/r}$ へ下がるはずで、それが正しいと予想したのが MincMin63、証明したのが BregmanBre73 である。行列で言えば、$0,1$ を成分とする行列のパーマネントの上界になる。
パーマネントは定義こそ行列式に似ているが、$0,1$ 行列に限っても厳密な計算は $\#\mathrm{P}$ 完全で(Valiant の定理、AB07 Theorem 9.8)、行列式のような消去法がない。だからこそ、行和だけで書ける鋭い上界に値打ちがある。ここでは RadhakrishnanRad97 のエントロピーによる証明を示す。鍵は、頂点を選ぶ順序を無作為にして平均を取ると、「残っている候補の数」が $1,\dots,r_i$ の上で一様に分布することである。さらに同じ証明から等号の条件を取り出し、Latin 方陣の個数と一般のグラフの完全マッチングの個数へ応用する。

定義と定理の主張

パーマネント

$A=(a_{ij})$ を $n\times n$ 行列とする。パーマネント(permanent)を
$$\operatorname{per}A:=\sum_{\sigma\in\mathfrak{S}_n}\prod_{i=1}^na_{i\sigma(i)}$$
で定める。行列式から置換の符号を取り除いたものである。行や列を入れ替えても値は変わらない。

$A$ が $0,1$ 行列のとき、左の頂点 $1,\dots,n$ と右の頂点 $1,\dots,n$ を $a_{ij}=1$ のとき結ぶ二部グラフを考える。$A$ の行の和 $r_i:=\sum_ja_{ij}$ は左の頂点 $i$ の次数である。$\prod_ia_{i\sigma(i)}=1$ となる置換 $\sigma$ は完全マッチングと 1 対 1 に対応するので、$\operatorname{per}A$ は完全マッチングの個数に等しいPW25。
$\operatorname{per}A>0$ となる条件は Hall の条件である(Hallの結婚定理 の系「二部グラフの形」)。この記事はその先の量、つまり「いくつあるか」の上界を扱う。

Bregman の定理

$A$ をすべての行和 $r_i$ が $1$ 以上の $n\times n$ の $0,1$ 行列とする。このとき
$$\operatorname{per}A\le\prod_{i=1}^n(r_i!)^{1/r_i}$$
である。

仮定と証明の所在

和が $0$ の行があれば $\operatorname{per}A=0$ なので、仮定 $r_i\ge1$ は右辺を意味のある形にするためのものにすぎない。$A$ の転置に当てれば、列和 $s_j$ についても同じ不等式 $\operatorname{per}A\le\prod_j(s_j!)^{1/s_j}$ が成り立つ。行の上界と列の上界は一般に異なるので、小さい方を使えばよい(ex-bre-table)。証明は次の節の prf-bre-main で与える。

等号の条件

thm-bre-main の不等式で等号が成り立つのは、行と列をそれぞれ並べ替えると、$A$ が全部 $1$ の正方行列を対角に並べたブロック対角行列になるときに限る。

二部グラフの言葉

二部グラフで言えば、頂点を共有しない完全二部グラフ $K_{s,s}$ の和である。この条件は Bregman の結果として AF08 §2 の式 (2.1) の箇所にも述べられている。証明は次の節の prf-bre-equality で与える。

エントロピーによる証明

$\operatorname{per}A=0$ なら右辺は正なので成り立つ。以下 $\operatorname{per}A>0$ とする。$M\subset\mathfrak{S}_n$ を、すべての $i$ で $a_{i\sigma(i)}=1$ となる置換の全体とし、$|M|=\operatorname{per}A$ に注意する。$\log$ は自然対数とする。
順序を固定したまま進めると自明な上界しか得られない理由を先に見ておく。$M$ 上の一様分布に従う $X$ を取り、$X_i:=X(i)$ とする。$X_i$ は $r_i$ 個の列のどれかなので、Shannonエントロピー の定理「エントロピーの範囲」と「連鎖律と劣加法性」から $\log|M|=H(X_1,\dots,X_n)\le\sum_iH(X_i)\le\sum_i\log r_i$ となる。これが自明な上界 $\prod_ir_i$ である。連鎖律の条件付きを捨てずに使えば改善するはずだが、$X_1,\dots,X_{i-1}$ を知ったときに行 $i$ の候補がいくつ残るかは、グラフの細かい形に依存して次数だけでは書けない。そこで次の補題の出番になる。

残りの候補の数

行の並べ方 $\pi=(\pi_1,\dots,\pi_n)$($1,\dots,n$ の順列)と $\sigma\in M$、行 $k$ に対し、$\pi$ で $k$ より前に来る行の全体を $B_k(\pi)$ とし、
$$N_k(\sigma,\pi):=\#\bigl\{j:\ a_{kj}=1,\ j\notin\sigma(B_k(\pi))\bigr\}$$
とおく。前の行が $\sigma$ のとおりに列を取ったあと、行 $k$ に残っている列の数である。$j=\sigma(k)$ が数えられるので $N_k\ge1$ である。

残りの候補の数は一様に分布する

$\sigma\in M$ と行 $k$ を固定し、$\pi$ を $n!$ 個の並べ方から一様に選ぶ。このとき $N_k(\sigma,\pi)$ は $\{1,\dots,r_k\}$ 上の一様分布に従う。

同じ列の持ち主だけを見る

$a_{kj}=1$ となる列 $j$ は $r_k$ 個ある。それぞれの持ち主の行 $\sigma^{-1}(j)$ を集めた集合を $L$ とすると $|L|=r_k$ であり、$\sigma(k)$ が候補の列なので $k\in L$ である。列 $j$ が行 $k$ の前に取られるのは、$\sigma^{-1}(j)$ が $\pi$ で $k$ より前に来るときだから、
$$N_k(\sigma,\pi)=r_k-\#\bigl(L\cap B_k(\pi)\bigr)$$
である。$\pi$ が一様なら、$L$ の $r_k$ 個の要素の相対的な順序も一様で、$k$ が $L$ の中で $\ell$ 番目に来る確率は $\ell=1,\dots,r_k$ で等しく $1/r_k$ である。そのとき $N_k=r_k-\ell+1$ となる。$\square$

順序について平均する

$\pi$ を 1 つ固定する。$X$ は $M$ 上の一様分布に従うので $H(X)=\log|M|$ であり、連鎖律を繰り返し使って
$$\log|M|=\sum_{m=1}^nH\bigl(X_{\pi_m}\mid X_{\pi_1},\dots,X_{\pi_{m-1}}\bigr)$$
を得る。行 $k=\pi_m$ の項を調べる。前の行の値が決まると、$X_k$ の取りうる値は、$a_{kj}=1$ でまだ使われていない列に限られる。その個数は前の行の値だけで決まり、$X$ の値が $\sigma$ なら $N_k(\sigma,\pi)$ に等しい。したがって「エントロピーの範囲」より、条件付きのエントロピーは条件ごとに $\log N_k$ 以下であり、条件付きエントロピーの定義から
$$H\bigl(X_k\mid X_j\ (j\in B_k(\pi))\bigr)\le\frac1{|M|}\sum_{\sigma\in M}\log N_k(\sigma,\pi)\qquad(1)$$
となる。$k$ について足し、さらに $\pi$ について平均する。左辺の $\log|M|$ は $\pi$ によらないので、和の順序を入れ替えて
$$\log|M|\le\sum_{k=1}^n\frac1{|M|}\sum_{\sigma\in M}\Bigl(\frac1{n!}\sum_\pi\log N_k(\sigma,\pi)\Bigr)$$
である。括弧の中は、lem-bre-uniform より $\sigma$ によらず $\frac1{r_k}\sum_{\ell=1}^{r_k}\log\ell=\log(r_k!)^{1/r_k}$ に等しい。よって
$$\log\operatorname{per}A\le\sum_{k=1}^n\log(r_k!)^{1/r_k}$$
である。$\square$

この証明の組み立ては PW25 §8.3(pp. 161–164)による。順序の平均がなければ候補の数は次数だけで書けず、平均を取ってはじめてグラフの形が消える。また、全順序の平均を取るのは証明の中だけであり、$X$ の分布を変えているわけではない。

条件付き分布の一様性を使う

十分性。 大きさ $s$ のブロックは、パーマネントに $s!$ を掛け、右辺には $s$ 個の行から $\bigl((s!)^{1/s}\bigr)^s=s!$ を掛ける。パーマネントはブロック対角行列では各ブロックの積になるので等号が成り立つ。
必要性。 等号なら $\operatorname{per}A>0$ であり、prf-bre-main の不等式はすべて等号である。特にすべての $\pi$ と行 $k$ で (1) が等号となる。「エントロピーの範囲」の等号条件から、前の行の値が $M$ の元と両立するどの場合でも、$X_k$ は残りの候補の全部の上に一様に分布する。とくに、残りの候補はどれも実際に現れる。ここから次を導く。
(*) $\sigma\in M$ と相異なる行 $k,l$ について、$a_{k\sigma(l)}=1$ なら $a_{l\sigma(k)}=1$ である。
実際、$k,l$ を最後の 2 つ($k$ が先)とする並べ方 $\pi$ を取り、他の行は $\sigma$ の値を取るとする。残りの列は $\sigma(k),\sigma(l)$ の 2 つで、どちらも行 $k$ の候補である。すると $X_k=\sigma(l)$ となる $M$ の元があり、それは行 $l$ に列 $\sigma(k)$ を割り当てるので $a_{l\sigma(k)}=1$ である。
$\sigma\in M$ を 1 つ取り、列を並べ替えて $\sigma=\mathrm{id}$ とする。すると $a_{ii}=1$ で、(*) から $a_{kl}=1\Rightarrow a_{lk}=1$ である。次に、相異なる $k,l,m$ で $a_{kl}=a_{lm}=1$ とする。$k,l$ を入れ替える互換 $\sigma'$ は $a_{kl}=a_{lk}=1$ と $a_{ii}=1$ より $M$ に属する。(*) を $\sigma'$ と行 $l,m$ に当てると、$a_{l\sigma'(m)}=a_{lm}=1$ から $a_{m\sigma'(l)}=a_{mk}=1$ を得る。対称性と合わせて $a_{km}=1$ である。
したがって $a_{kl}=1$ は行番号の上の同値関係を定める。同値類の順に行と列を同時に並べ替えれば、同値類ごとに全部 $1$、それ以外は $0$ となる。$\square$

例

いくつかの行列での比較

小さい $0,1$ 行列での値を比べる。$J_n$ は全部 $1$ の行列、$P$ は巡回置換の行列である。上界の値は小数第 2 位までに丸めた。

行列$\operatorname{per}A$行の上界自明な上界 $\prod r_i$
$J_n$$n!$$n!$$n^n$
$J_2$ と $J_3$ のブロック対角$12$$12$$4\cdot27=108$
$J_3-I$$2$$2.83$$8$
$J_4-I$$9$$10.90$$81$
$J_5-I$$44$$53.12$$1024$
$4\times4$ の三重対角(全部 $1$)$5$$6.60$$36$
$I+P$($n=8$)$2$$16$$256$

$J_n-I$ のパーマネントは攪乱順列の個数である。行と列で上界が違う例として
$$A=\begin{pmatrix}1&1&1\\1&1&1\\1&0&0\end{pmatrix}$$
を取る。行 3 は列 1 を取るしかなく、残りの $2\times2$ の全部 $1$ の部分から $\operatorname{per}A=2$ である。行和 $(3,3,1)$ の上界は $6^{2/3}\approx3.30$、列和 $(3,2,2)$ の上界は $6^{1/3}\cdot2\approx3.63$ となる。
$I+P$ の行は最も遠い場合の一つである。$n$ を大きくしても $\operatorname{per}(I+P)=2$ のままで、上界は $2^{n/2}$ と増える。行和だけではグラフの連結性を見分けられない。実際、同じ行和 $2$ でも $J_2$ を $n/2$ 個並べれば上界に一致する。

正則な場合の上下の評価

$A$ の行和と列和がすべて $r$ のとき、
$$n!\Bigl(\frac rn\Bigr)^n\le\operatorname{per}A\le(r!)^{n/r}$$
である。$n\to\infty$ で $r$ を固定すると、$(\operatorname{per}A)^{1/n}$ は下の値の $n$ 乗根の極限 $r/e$ と、上の値 $(r!)^{1/r}$ のあいだにある。

右は定理、左は別の記事の定理

右の不等式は thm-bre-main そのものである。左の不等式は、$A/r$ が二重確率行列であることから、van der Waerden の予想「$n\times n$ の二重確率行列のパーマネントは $n!/n^n$ 以上」に帰着する。この予想は EgorychevEgo81 と FalikmanFal81 の定理であり(Huh18 §2.1 に主張がある)、証明は van der Waerden予想(パーマネント) にある。これを $A/r$ に当てて $r^n$ を掛ければよい。極限は Stirlingの公式 から $(n!)^{1/n}\sim n/e$ となることによる。$\square$

底の比較は次のとおりである。$(r!)^{1/r}/(r/e)$ は $r\to\infty$ で $1$ に近づくので、次数が大きいほど上下の評価は揃う。

$r$$r/e$$(r!)^{1/r}$比
$1$$0.37$$1$$2.72$
$2$$0.74$$1.41$$1.92$
$3$$1.10$$1.82$$1.65$
$10$$3.68$$4.53$$1.23$
$100$$36.79$$37.99$$1.03$

自明な上界の底 $r$ と比べると、$r$ が大きいとき Bregman の上界は底を約 $1/e$ 倍にする。導入で述べた「約 $e$ 倍の損」はこのことである。

応用

Latin 方陣の個数

Latin 方陣の個数の上界

$n$ 次の ラテン方陣 の個数を $L(n)$ とする(各行・各列に $1,\dots,n$ が 1 度ずつ現れる $n\times n$ の表で、行や記号の入れ替えで同一視しない)。このとき
$$L(n)\le\prod_{k=1}^n(k!)^{n/k}$$
である。

行を 1 行ずつ足す

上から $m$ 行($0\le m< n$)が決まったとする。列番号 $p$ と記号 $s$ について、$s$ が列 $p$ にまだ現れていないとき $b_{ps}=1$、それ以外で $0$ として $n\times n$ の行列 $B$ を作る。列 $p$ には $m$ 個の相異なる記号が現れているので、$B$ の行和はどれも $n-m$ である。第 $m+1$ 行の選び方は、列ごとに未使用の記号を重複なく選ぶ方法であり、$\operatorname{per}B$ 通りある。thm-bre-main より
$$\operatorname{per}B\le\bigl((n-m)!\bigr)^{n/(n-m)}$$
である。$m=0,\dots,n-1$ について掛け、$k=n-m$ とおけばよい。$\square$

小さい $n$ での比較は次のとおりである。

$n$$L(n)$上界
$2$$2$$2$
$3$$12$$16.97$
$4$$576$$1046.66$
$5$$161280$$714396.04$

一般のグラフの完全マッチング

次数列による完全マッチングの個数の上界

孤立点のない有限単純グラフ $G$ の頂点の次数を $d_v$ とする。$G$ の完全マッチングの個数 $m(G)$ について
$$m(G)\le\prod_{v}(d_v!)^{1/(2d_v)}$$
である。

2 つの完全マッチングの組を数える

$A$ を $G$ の隣接行列とする。$\operatorname{per}A$ は $\sigma(v)$ が常に $v$ の隣接点である置換 $\sigma$ の個数で、$\sigma$ の巡回分解の台を見ると、$G$ の全頂点を覆う互いに素な「辺 1 本を往復する長さ 2 の成分」と「長さ 3 以上の閉路」の族 $H$ を定める。1 つの族 $H$ は、長さ 3 以上の閉路の個数を $s$ として $2^s$ 個の置換から来る(閉路ごとに向きが 2 通り)。
一方、完全マッチングの順序対 $(M_1,M_2)$ の合併は、重なった辺と偶数の長さの閉路からなる同じ形の族 $H$ を与える。$H$ を固定すると、閉路ごとに辺の分け方が 2 通りで、順序対は $2^s$ 個ある(奇数の長さの閉路を含む $H$ には順序対はない)。したがって $m(G)^2\le\operatorname{per}A$ である。thm-bre-main を $A$ に当てて平方根を取ればよい。$\square$

この不等式は Kahn–Lovász にさかのぼり、上の短い導出は Alon–FriedlandAF08 による。同論文の Theorem 1.1 は、孤立点がないとき等号がちょうど $G$ が完全二部グラフ $K_{s,s}$ の頂点を共有しない和であるときに成り立つことも述べている。例:$K_4$ で $3\le3.30$、$K_6$ で $15\le17.68$、Petersen グラフで $6\le19.81$、長さ 6 の閉路で $2\le2.83$ である(右辺は小数第 2 位までに丸めた)。

使える条件と反例

外す条件反例成り立たなくなること
成分が $0,1$$A=(2)$thm-bre-main の不等式
右辺の $(r!)^{1/r}$ を $r/e$ に替える単位行列 $I_n$thm-bre-main の不等式
ブロックが正方下の $3\times3$ の行列 $C$thm-bre-equality の十分性
列和も $r$ で揃う同じ行列 $C$prop-bre-regular の左の不等式
反例の確かめ

成分。 $A=(2)$ は $\operatorname{per}A=2$、行和 $r=2$ で、右辺は $(2!)^{1/2}\approx1.41$ である。$\operatorname{diag}(2,2)$ なら左辺 $4$、右辺 $2$ となる。成分を $0,1$ に限る仮定は、証明では「行和 $r_k$ が候補の列の個数に等しい」という段に効いている。
右辺の形。 $I_n$ では $\operatorname{per}I_n=1$ で、$\prod_i(r_i/e)=e^{-n}< 1$ である。$r\to\infty$ の漸近形をそのまま上界に使うことはできない。
正方性。 第 3 列がすべて $0$ の行列
$$C=\begin{pmatrix}1&1&0\\1&1&0\\1&1&0\end{pmatrix}$$
は、行と列を並べ替えれば全部 $1$ の $3\times2$ のブロックと $0$ の列になるが、列 $3$ を使えないので $\operatorname{per}C=0$ で、右辺 $2^{3/2}\approx2.83$ に一致しない。
列和。 $C$ の行和はすべて $2$ である。$n=3$、$r=2$ の下界は $3!\,(2/3)^3=16/9$ だが、$\operatorname{per}C=0$ である。上の不等式は行和だけで成り立つのに対し、下の不等式には列和も揃っていることが要る。同じ例は、Bregman の上界が正であっても完全マッチングの存在は保証されないことも示す。

よくある誤り

誤り正しくは
$\operatorname{per}A$ は $\det A$ と同様に計算しやすい行列式と違い、積の公式も行の基本変形も使えない。$0,1$ 行列でも $\#\mathrm{P}$ 完全である
上界が整数でないので定理が弱い整数なので切り捨ててよい。$J_3-I$ なら $\lfloor2.83\rfloor=2$ で一致する
$\prod(r_i!)^{1/r_i}$ は $\prod r_i/e$ と同じ比は $(2\pi r)^{1/(2r)}$ 程度で $1$ より大きく、$r$ が小さいと無視できない
証明の $N_k$ は $\pi$ を固定しても一様である一様なのは $\pi$ を動かしたときである。$\sigma,\pi$ を両方固定すれば $N_k$ は 1 つの値である
等号の条件はグラフが正則なこと正則でなくても $J_2$ と $J_3$ の組は等号で、正則でも $J_4-I$ は等号でない

補足

別の証明。 最初の証明は BregmanBre73 により、のちに SchrijverSch78 が短い証明を与えた。エントロピーによる証明Rad97 は確率論の言葉で候補の数の平均を取るもので、個数の上界をエントロピーで出す方法の典型である。エントロピーと個数の関係は Shannonエントロピー の節「個数を数えるエントロピー」も参照してほしい。
下界との関係。 上の評価が言うのは「行和だけから分かる最大値」であり、最小値は prop-bre-regular の左側に現れる二重確率行列の問題である。パーマネントの最小化は混合判別式の不等式と結びつき、Huh18 §2.1 にその位置づけの解説がある。
行列式との比較。 $0,1$ 行列 $A$ では各置換の項が $0$ か $\pm1$ なので $|\det A|\le\operatorname{per}A$ であり、Bregman の上界は行列式の絶対値の上界にもなる。ただし行列式には Hadamard の不等式があって、そちらは行ベクトルの長さの積 $\prod_i\sqrt{r_i}$ で抑えられる。$r$ が大きいと $\sqrt r$ の方が $(r!)^{1/r}\approx r/e$ より小さく、符号による打ち消しが効いていることが分かる。

関連項目

参考文献

[2]
Henryk Minc, Upper bounds for permanents of (0, 1)-matrices, Bulletin of the American Mathematical Society, 1963, pp. 789–791
[3]
L. M. Bregman, Some properties of nonnegative matrices and their permanents, Soviet Mathematics Doklady, 1973, pp. 945–949
[4]
A. Schrijver, A short proof of Minc's conjecture, Journal of Combinatorial Theory, Series A, 1978, pp. 80–83
[5]
Jaikumar Radhakrishnan, An entropy proof of Bregman's theorem, Journal of Combinatorial Theory, Series A, 1997, pp. 161–164
[6]
Noga Alon, Shmuel Friedland, The maximum number of perfect matchings in graphs with a given degree sequence, The Electronic Journal of Combinatorics, 2008, #N13、Theorem 1.1 と §2
[7]
G. P. Egorychev, The solution of van der Waerden's problem for permanents, Advances in Mathematics, 1981, pp. 299–305
[8]
D. I. Falikman, Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix, Mathematical Notes of the Academy of Sciences of the USSR, 1981, pp. 475–479
[9]
June Huh, Combinatorial applications of the Hodge–Riemann relations, Proceedings of the International Congress of Mathematicians (Rio de Janeiro 2018), 2018, §2.1

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