§E13.23Birkhoff–von Neumann の定理

証明. 成分は$0$または$1$であるから非負である。第$i$行では$j=\sigma(i)$のときだけ成分が$1$であり、他は$0$であるから行の和は$1$である。第$j$列では、$p_{ij}=1$となる$i$は$\sigma(i)=j$を満たすもの、すなわち$i=\sigma^{-1}(j)$ただ一つであるから列の和も$1$である。▨

証明.$S\subseteq X$をとり、$I=\{i:\ x_i\in S\}$、$J=\{j:\ y_j\in N(S)\}$と置く。$\lvert I\rvert=\lvert S\rvert$かつ$\lvert J\rvert=\lvert N(S)\rvert$である。

$i\in I$かつ$j\notin J$ならば$a_{ij}=0$である。実際、$a_{ij}>0$とすると$x_iy_j\in E_A$であり$y_j\in N(S)$となって$j\in J$に反する。したがって、$I$に属する行についての行和を足し合わせると

となる。ここで最初の等号は行和がすべて$1$であることによる。次に、成分がすべて非負であることから、$J$に属する列について$I$に属する行だけの和を全体の列和で上から評価することができ、

となる。最後の等号は列和がすべて$1$であることによる。二つを合わせて$\lvert S\rvert=\lvert I\rvert\le\lvert J\rvert=\lvert N(S)\rvert$を得る。▨

証明.補題 2.2により$G_A$は Hall の条件を満たす。したがって§D2.12 定理 1.3により、$X$のすべての頂点を被覆するマッチング$M$が存在する。$M$の各辺はちょうど一つの$X$の頂点と一つの$Y$の頂点を端点にもち、$M$はマッチングであるから、$x_i$を被覆する$M$の辺はただ一本である。その辺を$x_iy_{\sigma(i)}$と書いて、写像$\sigma$を定める。

$\sigma$が単射であることを示す。$\sigma(i)=\sigma(i')=j$かつ$i\ne i'$とすると、$M$の二辺$x_iy_j$と$x_{i'}y_j$がともに$y_j$を端点にもち、$M$がマッチングであることに反する。$\{1,\dots,n\}$から自分自身への単射は全単射であるから、$\sigma$は置換である。$x_iy_{\sigma(i)}\in E_A$であるから$a_{i\sigma(i)}>0$が成り立つ。▨

証明. 各$i$について、第$i$行の成分はすべて非負でありその和は$1$であるから、$a_{ij}>0$を満たす$j$が少なくとも一つ存在する。行ごとにそのような対を一つずつ選ぶと相異なる$n$個の対が得られるので$p(A)\ge n$である。

$p(A)=n$とする。上の評価で等号が成り立つのは、各行に正の成分がちょうど一つある場合に限る。第$i$行の正の成分を$a_{i\tau(i)}$とすると、同じ行の他の成分は$0$であり行和が$1$であるから$a_{i\tau(i)}=1$である。第$j$列の和は$\tau(i)=j$を満たす$i$の個数に等しく、これが$1$であるから、各$j$に対して$\tau(i)=j$を満たす$i$はちょうど一つである。よって$\tau$は置換であり、定義 1.2により$A=P_\tau$である。

逆に$A=P_\tau$とすると、正の成分は各行の$(i,\tau(i))$ただ一つずつであるから$p(A)=n$である。▨

証明. 正の成分の個数$p(A)$についての累積帰納法で示す。命題 3.2により$p(A)\ge n$である。

$p(A)=n$の場合。命題 3.2により$A$は置換行列$P_\tau$である。$m=1$、$\lambda_1=1$ととれば主張が成り立つ。

$p(A)>n$の場合。正の成分の個数が$p(A)$より少ないすべての二重確率行列について主張が成り立つと仮定する。

補題 2.3により、すべての$i$について$a_{i\sigma(i)}>0$を満たす置換$\sigma$が存在する。$\lambda=\min_i a_{i\sigma(i)}$と置くと$\lambda>0$である。また、行和が$1$で成分が非負であるから各成分は$1$以下であり$\lambda\le1$である。$\lambda=1$と仮定すると、各$i$について$a_{i\sigma(i)}=1$となり、第$i$行の他の成分は非負で和が$0$であるからすべて$0$となる。すると各行の正の成分がちょうど一つとなり$p(A)=n$が成り立つので、$p(A)>n$という仮定に反する。よって$0<\lambda<1$である。

$B=(b_{ij})$を

で定める。$B$が二重確率行列であることを示す。$j=\sigma(i)$のとき$b_{ij}=(a_{i\sigma(i)}-\lambda)/(1-\lambda)$であり、$\lambda$が最小値であるから$a_{i\sigma(i)}-\lambda\ge0$となり$b_{ij}\ge0$である。$j\ne\sigma(i)$のとき$b_{ij}=a_{ij}/(1-\lambda)\ge0$である。行和については、命題 1.3により$P_\sigma$の第$i$行の和が$1$であるから

となる。列和についても、$P_\sigma$の各列の和が$1$であるから同じ計算により$\sum_{i}b_{ij}=1$となる。よって$B$は二重確率行列である。

次に$p(B)<p(A)$を示す。$b_{ij}>0$ならば$a_{ij}-\lambda(P_\sigma)_{ij}>0$であり、$(P_\sigma)_{ij}\ge0$かつ$\lambda>0$であるから$a_{ij}>0$である。よって$B$の正の成分の位置は$A$の正の成分の位置に含まれる。さらに、最小値を与える添字$i_0$、すなわち$a_{i_0\sigma(i_0)}=\lambda$を満たす$i_0$をとると、$b_{i_0\sigma(i_0)}=0$である一方$a_{i_0\sigma(i_0)}=\lambda>0$である。よって$p(B)\le p(A)-1$である。

帰納法の仮定を$B$へ適用すると、置換$\tau_1,\dots,\tau_l$と正の実数$\mu_1,\dots,\mu_l$が存在して

が成り立つ。$b_{ij}$の定め方から、すべての$i$と$j$について$a_{ij}=\lambda\,(P_\sigma)_{ij}+(1-\lambda)b_{ij}$が成り立つので、§D3.1 定義 2.1と§D3.1 定義 1.1の行列の相等により$A=\lambda P_\sigma+(1-\lambda)B$である。この右辺へ$B$の表示を代入し、§D3.1 命題 2.3の実数倍についての法則によって係数をまとめると

となる。$\lambda>0$かつ$(1-\lambda)\mu_k>0$であり、係数の総和は

である。よって$m=l+1$として主張の形の表示が得られる。▨

証明. 置換の個数は$n!$個で有限であるから$\gamma$は定まり、$\gamma$を与える置換$\sigma^{*}$が存在する。任意の置換$\sigma$について、定義 1.2により

が成り立つ。$\sigma=\sigma^{*}$ととると、この式の左辺は$\gamma$に等しい。命題 1.3により$P_{\sigma^{*}}$は二重確率行列であるから、等号を与える二重確率行列が存在する。

任意の二重確率行列$A$をとる。定理 3.3により、置換$\sigma_1,\dots,\sigma_m$と正の実数$\lambda_1,\dots,\lambda_m$が存在して$A=\sum_k\lambda_kP_{\sigma_k}$かつ$\sum_k\lambda_k=1$である。各成分について$a_{ij}=\sum_k\lambda_k(P_{\sigma_k})_{ij}$であるから、和の順序を入れ替えて

となる。ここで和はすべて有限和であるから、順序の入れ替えは加法の結合法則と交換法則による。各$k$について$\sum_i c_{i\sigma_k(i)}\ge\gamma$であり、$\lambda_k>0$であるから

を得る。▨