Birkhoff–von Neumann の定理 | 離散数学 II

1 二重確率行列と置換行列

定義 1.1. $n$ 次実正方行列 $A=(a_{ij})$ が二重確率行列 (doubly stochastic matrix) であるとは、次の三条件を満たすことをいう。

すべての $i,j$ について $a_{ij}\ge0$ である。
すべての $i$ について $\sum_{j=1}^{n}a_{ij}=1$ である。
すべての $j$ について $\sum_{i=1}^{n}a_{ij}=1$ である。

定義 1.2. 置換 $\sigma$ に対し、 $n$ 次実正方行列 $P_\sigma=(p_{ij})$ を

p_{ij}=\begin{cases}1 & (j=\sigma(i)),\\ 0 & (j\ne\sigma(i))\end{cases}

で定め、置換行列 (permutation matrix) という。

命題 1.3. 任意の置換 $\sigma$ に対し $P_\sigma$ は二重確率行列である。

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

2 正成分の定める二部グラフと Hall の条件

定義 2.1. $n$ 次二重確率行列 $A=(a_{ij})$ に対し、二部グラフ $G_A=(X\sqcup Y,E_A)$ を次で定める。 $X=\{x_1,\dots,x_n\}$ を行に対応する頂点集合、 $Y=\{y_1,\dots,y_n\}$ を列に対応する頂点集合とし、

E_A=\{\,x_iy_j:\ a_{ij}>0\,\}

とする。 $G_A$ を $A$ の正成分の二部グラフ (positive-entry bipartite graph) という。

補題 2.2. $n$ 次二重確率行列 $A$ に対し、任意の $S\subseteq X$ について $\lvert N(S)\rvert\ge\lvert S\rvert$ が成り立つ。ここで $N(S)$ は $S$ の頂点に隣接する $Y$ の頂点の全体である。

証明. $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$ に属する行についての行和を足し合わせると

\lvert I\rvert=\sum_{i\in I}\sum_{j=1}^{n}a_{ij}=\sum_{i\in I}\sum_{j\in J}a_{ij}

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

\sum_{i\in I}\sum_{j\in J}a_{ij}=\sum_{j\in J}\sum_{i\in I}a_{ij}\le\sum_{j\in J}\sum_{i=1}^{n}a_{ij}=\lvert J\rvert

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

補題 2.3. $n$ 次二重確率行列 $A=(a_{ij})$ に対し、すべての $i$ について $a_{i\sigma(i)}>0$ を満たす置換 $\sigma$ が存在する。

証明.補題 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$ が成り立つ。▨

3 置換行列の凸結合表示

定義 3.1. $n$ 次実正方行列 $A=(a_{ij})$ に対し、 $a_{ij}>0$ を満たす添字の対 $(i,j)$ の個数を $p(A)$ と書き、 $A$ の正の成分の個数 (number of positive entries) という。

命題 3.2. $n$ 次二重確率行列 $A$ に対し $p(A)\ge n$ が成り立つ。さらに $p(A)=n$ であることと、 $A$ が置換行列であることは同値である。

証明. 各 $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$ である。▨

3.1 証明方針

$p(A)$ についての累積帰納法で示す。

$p(A)$ の最小値は命題 3.2により $n$ であり、そのとき $A$ 自身が置換行列である。この場合が帰納法の基底である。

$p(A)>n$ のときは、補題 2.3により得られる置換 $\sigma$ をとり、係数を

\lambda=\min_{1\le i\le n}a_{i\sigma(i)}

と定める。 $\lambda>0$ である。まず $\lambda<1$ を示す。 $\lambda=1$ とすると、各行で $a_{i\sigma(i)}=1$ となり、行和が $1$ で成分が非負であることから同じ行の他の成分はすべて $0$ となって $p(A)=n$ になり、仮定に反するからである。

次に $B=(A-\lambda P_\sigma)/(1-\lambda)$ が再び二重確率行列であることを、成分の非負性、行和、列和の順に確かめる。 $\lambda$ を最小値にとったことが非負性を保証する。さらに、最小値を与える位置の成分が $B$ では $0$ になるので $p(B)\le p(A)-1$ であり、帰納法の仮定を $B$ へ適用することができる。最後に、 $B$ の表示に $(1-\lambda)$ を掛けて $\lambda P_\sigma$ を加えると $A$ の表示が得られ、係数の総和が $\lambda+(1-\lambda)=1$ となることを確かめる。

定理 3.3 (Birkhoff–von Neumann の定理). $A$ を $n$ 次二重確率行列とする。このとき、有限個の置換 $\sigma_1,\dots,\sigma_m$ と正の実数 $\lambda_1,\dots,\lambda_m$ が存在して

A=\sum_{k=1}^{m}\lambda_kP_{\sigma_k}, \qquad \sum_{k=1}^{m}\lambda_k=1

が成り立つ。

証明. 正の成分の個数 $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_{ij}=\frac{a_{ij}-\lambda\,(P_\sigma)_{ij}}{1-\lambda}

で定める。 $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$ であるから

\sum_{j=1}^{n}b_{ij}=\frac{1}{1-\lambda}\Bigl(\sum_{j=1}^{n}a_{ij}-\lambda\sum_{j=1}^{n}(P_\sigma)_{ij}\Bigr)=\frac{1-\lambda}{1-\lambda}=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=\sum_{k=1}^{l}\mu_kP_{\tau_k}, \qquad \sum_{k=1}^{l}\mu_k=1

が成り立つ。 $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の実数倍についての法則によって係数をまとめると

A=\lambda P_\sigma+\sum_{k=1}^{l}(1-\lambda)\mu_kP_{\tau_k}

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

\lambda+\sum_{k=1}^{l}(1-\lambda)\mu_k=\lambda+(1-\lambda)\sum_{k=1}^{l}\mu_k=\lambda+(1-\lambda)=1

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

注意 3.4.定理 3.3では表示の存在が主張されるのみであり、一意性が主張されない。取り出す置換の選び方に応じて異なる表示が得られる。また、同じ置換が二度現れる表示が得られた場合には、その二項の係数を足し合わせて一つの項にまとめることができる。まとめた後も各係数は正であり、係数の総和は変わらず $1$ である。

4 線形割当問題

系 4.1. $C=(c_{ij})$ を成分が実数である $n$ 次正方行列とし、

\gamma=\min_{\sigma}\ \sum_{i=1}^{n}c_{i\sigma(i)}

と置く。ここで最小は置換 $\sigma$ の全体をわたる。このとき、任意の $n$ 次二重確率行列 $A=(a_{ij})$ に対し

\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}a_{ij}\ \ge\ \gamma

が成り立ち、 $\gamma$ を与える置換 $\sigma^{*}$ の置換行列 $A=P_{\sigma^{*}}$ で等号が成り立つ。したがって、二重確率行列の全体における $\sum_{i,j}c_{ij}a_{ij}$ の最小値は存在して $\gamma$ に等しく、置換行列で達成される。

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

\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}(P_\sigma)_{ij}=\sum_{i=1}^{n}c_{i\sigma(i)}

が成り立つ。 $\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}$ であるから、和の順序を入れ替えて

\sum_{i,j}c_{ij}a_{ij} =\sum_{k=1}^{m}\lambda_k\sum_{i,j}c_{ij}(P_{\sigma_k})_{ij} =\sum_{k=1}^{m}\lambda_k\sum_{i=1}^{n}c_{i\sigma_k(i)}

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

\sum_{i,j}c_{ij}a_{ij}\ \ge\ \sum_{k=1}^{m}\lambda_k\gamma=\gamma\sum_{k=1}^{m}\lambda_k=\gamma

を得る。▨

5 検算例

例 5.1.

A=\begin{pmatrix} 1/2 & 1/2 & 0\\ 0 & 1/2 & 1/2\\ 1/2 & 0 & 1/2 \end{pmatrix}

と置く。行の和は順に $1/2+1/2+0=1$ 、 $0+1/2+1/2=1$ 、 $1/2+0+1/2=1$ である。列の和は順に $1/2+0+1/2=1$ 、 $1/2+1/2+0=1$ 、 $0+1/2+1/2=1$ である。成分はすべて非負であるから $A$ は二重確率行列であり、正の成分の個数は $p(A)=6$ である。

Hall の条件の確認。正成分の二部グラフ $G_A$ の辺は $x_1y_1$ 、 $x_1y_2$ 、 $x_2y_2$ 、 $x_2y_3$ 、 $x_3y_1$ 、 $x_3y_3$ である。一元集合の近傍はいずれも二元であり、 $\lvert N(S)\rvert\ge\lvert S\rvert$ が成り立つ。二元集合については、 $N(\{x_1,x_2\})=\{y_1,y_2,y_3\}$ 、 $N(\{x_1,x_3\})=\{y_1,y_2,y_3\}$ 、 $N(\{x_2,x_3\})=\{y_1,y_2,y_3\}$ であり、いずれも三元である。三元集合については $N(X)=\{y_1,y_2,y_3\}$ である。よって Hall の条件が成り立つ。

置換の取り出しと分解。恒等置換 $\sigma=\mathrm{id}$ について $a_{11}=a_{22}=a_{33}=1/2>0$ であるから、 $\sigma$ は補題 2.3の条件を満たす。 $\lambda=\min\{1/2,1/2,1/2\}=1/2$ である。恒等置換の置換行列は、§D3.1 定義 3.6の単位行列にほかならない。 $3$ 次の単位行列を $I$ と書くと $P_{\mathrm{id}}=I$ であり、

B=\frac{A-\tfrac12 I}{1-\tfrac12} =2\begin{pmatrix} 0 & 1/2 & 0\\ 0 & 0 & 1/2\\ 1/2 & 0 & 0 \end{pmatrix} =\begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}

となる。 $B$ の正の成分の個数は $3$ であり、 $p(A)=6$ より真に小さい。 $B$ は $\tau(1)=2$ 、 $\tau(2)=3$ 、 $\tau(3)=1$ で定まる置換 $\tau$ の置換行列 $P_\tau$ である。よって

A=\frac12 P_{\mathrm{id}}+\frac12 P_\tau

であり、係数はいずれも正でその和は $1$ である。右辺を成分ごとに計算すると、第 $1$ 行は $(1/2,\,1/2,\,0)$ 、第 $2$ 行は $(0,\,1/2,\,1/2)$ 、第 $3$ 行は $(1/2,\,0,\,1/2)$ となり $A$ に一致する。

割当の最適値。費用行列を

C=\begin{pmatrix}1&2&3\\ 2&3&1\\ 3&1&2\end{pmatrix}

とする。六つの置換について総費用を数え上げる。恒等置換では $c_{11}+c_{22}+c_{33}=1+3+2=6$ 、 $\tau$ では $c_{12}+c_{23}+c_{31}=2+1+3=6$ 、 $1$ と $2$ を入れ替える置換では $c_{12}+c_{21}+c_{33}=2+2+2=6$ 、 $1$ と $3$ を入れ替える置換では $c_{13}+c_{22}+c_{31}=3+3+3=9$ 、 $2$ と $3$ を入れ替える置換では $c_{11}+c_{23}+c_{32}=1+1+1=3$ 、残る置換 $1\mapsto3,\ 2\mapsto1,\ 3\mapsto2$ では $c_{13}+c_{21}+c_{32}=3+2+1=6$ である。よって $\gamma=3$ である。

上の $A$ については

\sum_{i,j}c_{ij}a_{ij}=\tfrac12(c_{11}+c_{12}+c_{22}+c_{23}+c_{31}+c_{33})=\tfrac12(1+2+3+1+3+2)=\tfrac12\cdot12=6

であり、分解 $A=\tfrac12P_{\mathrm{id}}+\tfrac12P_\tau$ から得られる $\tfrac12\cdot6+\tfrac12\cdot6=6$ と一致する。 $6\ge3=\gamma$ であり、系 4.1の不等式と整合する。

6 演習

問題 6.1.

$n$ 次二重確率行列 $A$ と $S\subseteq X$ をとり、 $I=\{i:\ x_i\in S\}$ 、 $J=\{j:\ y_j\in N(S)\}$ と置く。 $\lvert N(S)\rvert-\lvert S\rvert=\sum_{i\notin I}\sum_{j\in J}a_{ij}$ を示せ。さらに、空でなく $X$ と異なる $S\subseteq X$ であって $\lvert N(S)\rvert=\lvert S\rvert$ を満たすものが存在することと、ある整数 $1\le k\le n-1$ と置換 $\alpha,\beta$ について、 $b_{ij}=a_{\alpha(i)\beta(j)}$ で定まる行列 $B=(b_{ij})$ が「 $i\le k<j$ または $j\le k<i$ ならば $b_{ij}=0$ 」を満たすことが同値であることを示せ。
$n$ 次二重確率行列 $A$ について、定理 3.3の表示を、置換の個数 $m$ が $p(A)-n+1$ 以下であるようにとることができることを示せ。これを用いて、すべての $n$ 次二重確率行列は $n^{2}-n+1$ 個以下の置換行列の凸結合として表されることを示せ。
$p(A)>n$ である $n$ 次二重確率行列 $A$ と、補題 2.3による置換 $\sigma$ をとり、 $0<\lambda'<\min_ia_{i\sigma(i)}$ を満たす実数 $\lambda'$ に対して $B'=(A-\lambda'P_\sigma)/(1-\lambda')$ と置く。 $B'$ が二重確率行列であり $p(B')=p(A)$ を満たすことを示せ。さらに、 $n=2$ の二重確率行列 $A_0$ から出発し、各回でこの形の置き換え $A_k\mapsto A_{k+1}$ を行って得られる列 $A_0,A_1,A_2,\dots$ であって、どの $A_k$ も置換行列でないものを作れ。
$n\ge2$ とする。成分が非負で行和がすべて $1$ である $n$ 次正方行列であって、 $p(A)=n$ を満たすが置換行列でないものの例を挙げよ。さらに、 $n$ 次二重確率行列 $A$ が置換行列でないならば $p(A)\ge n+2$ であることを示し、 $p(A)=n+2$ を満たす $n$ 次二重確率行列の例を作れ。
系 4.1の証明を、最小化ではなく最大化について書き直せ。すなわち、任意の二重確率行列 $A$ について $\sum_{i,j}c_{ij}a_{ij}$ が置換にわたる最大値以下であることを、同じ線形性の議論で示せ。

解答.

(1)を示す。補題 2.2の証明のとおり、 $i\in I$ かつ $j\notin J$ ならば $a_{ij}=0$ であり、行和がすべて $1$ であるから $\lvert I\rvert=\sum_{i\in I}\sum_{j\in J}a_{ij}$ である。列和がすべて $1$ であるから

\lvert J\rvert=\sum_{j\in J}\sum_{i=1}^{n}a_{ij}=\sum_{i\in I}\sum_{j\in J}a_{ij}+\sum_{i\notin I}\sum_{j\in J}a_{ij}

である。 $\lvert S\rvert=\lvert I\rvert$ 、 $\lvert N(S)\rvert=\lvert J\rvert$ であるから、二つの等式の差をとって $\lvert N(S)\rvert-\lvert S\rvert=\sum_{i\notin I}\sum_{j\in J}a_{ij}$ を得る。

空でなく $X$ と異なる $S$ が $\lvert N(S)\rvert=\lvert S\rvert$ を満たすとし、 $k=\lvert S\rvert$ と置くと $1\le k\le n-1$ である。前段の等式の右辺は非負の数の和であり $0$ に等しいので、 $i\notin I$ かつ $j\in J$ ならば $a_{ij}=0$ である。また $i\in I$ かつ $j\notin J$ ならば $a_{ij}=0$ である。 $\lvert I\rvert=\lvert J\rvert=k$ であるから、 $\alpha(\{1,\dots,k\})=I$ を満たす置換 $\alpha$ と $\beta(\{1,\dots,k\})=J$ を満たす置換 $\beta$ が存在する。このとき $\alpha(\{k+1,\dots,n\})$ は $I$ の補集合であり、 $\beta(\{k+1,\dots,n\})$ は $J$ の補集合である。 $i\le k<j$ ならば $\alpha(i)\in I$ 、 $\beta(j)\notin J$ であるから $b_{ij}=a_{\alpha(i)\beta(j)}=0$ である。 $j\le k<i$ ならば $\alpha(i)\notin I$ 、 $\beta(j)\in J$ であるから $b_{ij}=0$ である。

逆に、 $1\le k\le n-1$ と置換 $\alpha,\beta$ について $B$ が条件を満たすとする。 $I=\alpha(\{1,\dots,k\})$ 、 $S=\{x_i:\ i\in I\}$ と置くと、 $\lvert S\rvert=k$ であるから $S$ は空でなく $X$ と異なる。 $i\in I$ と $j$ について、 $i=\alpha(i')$ （ $i'\le k$ ）と書き $j'=\beta^{-1}(j)$ と置くと $a_{ij}=b_{i'j'}$ であり、 $j'>k$ ならばこれは $0$ である。よって $y_j\in N(S)$ ならば $j\in\beta(\{1,\dots,k\})$ であり、 $\lvert N(S)\rvert\le k=\lvert S\rvert$ である。補題 2.2により $\lvert N(S)\rvert\ge\lvert S\rvert$ であるから $\lvert N(S)\rvert=\lvert S\rvert$ である。

(2)を、 $p(A)$ についての累積帰納法で示す。 $p(A)=n$ のとき、命題 3.2により $A$ はある置換 $\tau$ の置換行列 $P_\tau$ であり、 $m=1=p(A)-n+1$ の表示 $A=1\cdot P_\tau$ がある。 $p(A)>n$ とし、正の成分の個数が $p(A)$ より少ないすべての二重確率行列 $B$ について、置換の個数が $p(B)-n+1$ 以下の表示が存在すると仮定する。定理 3.3の証明で示したとおり、補題 2.3による置換 $\sigma$ と $\lambda=\min_ia_{i\sigma(i)}$ について $0<\lambda<1$ であり、 $B=(A-\lambda P_\sigma)/(1-\lambda)$ は二重確率行列であって $p(B)\le p(A)-1$ を満たす。帰納法の仮定により、置換 $\tau_1,\dots,\tau_l$ （ $l\le p(B)-n+1\le p(A)-n$ ）と、総和が $1$ である正の実数 $\mu_1,\dots,\mu_l$ が存在して $B=\sum_k\mu_kP_{\tau_k}$ である。同じ証明のとおり

A=\lambda P_\sigma+\sum_{k=1}^{l}(1-\lambda)\mu_kP_{\tau_k}

は係数が正で総和が $1$ の表示であり、置換の個数は $l+1\le p(A)-n+1$ である。よって主張が成り立つ。

成分の位置は $n^{2}$ 個であるから $p(A)\le n^{2}$ であり、すべての $n$ 次二重確率行列は $n^{2}-n+1$ 個以下の置換行列 $P_{\sigma_k}$ と正の係数 $\lambda_k$ （ $\sum_k\lambda_k=1$ ）によって $A=\sum_k\lambda_kP_{\sigma_k}$ と表される。たとえば例 5.1の行列では $p(A)=6$ 、 $n=3$ であり、上界は $4$ である。実際に得られた表示の置換の個数は $2$ であり、上界の範囲に収まる。

(3)を示す。 $\lambda=\min_ia_{i\sigma(i)}$ と置く。定理 3.3の証明により、 $p(A)>n$ のとき $\lambda<1$ であるから $0<\lambda'<\lambda<1$ であり、 $1-\lambda'>0$ である。 $b'_{ij}=(a_{ij}-\lambda'(P_\sigma)_{ij})/(1-\lambda')$ と置く。 $j=\sigma(i)$ のとき $a_{i\sigma(i)}-\lambda'\ge\lambda-\lambda'>0$ であるから $b'_{i\sigma(i)}>0$ であり、 $a_{i\sigma(i)}>0$ でもある。 $j\ne\sigma(i)$ のとき $b'_{ij}=a_{ij}/(1-\lambda')$ であるから、 $b'_{ij}\ge0$ であり、 $b'_{ij}>0$ と $a_{ij}>0$ は同値である。よって $B'$ の成分は非負であり、 $B'$ の正の成分の位置は $A$ の正の成分の位置に一致して $p(B')=p(A)$ である。命題 1.3により $P_\sigma$ の行和と列和は $1$ であるから、第 $i$ 行の和は $(1-\lambda')/(1-\lambda')=1$ であり、列和も同様に $1$ である。よって $B'$ は二重確率行列である。

列を作る。 $0<a<1$ に対して

M(a)=\begin{pmatrix}a&1-a\\ 1-a&a\end{pmatrix}

と置くと、 $M(a)$ は二重確率行列であり $p(M(a))=4>2$ であるから、命題 3.2により置換行列ではない。 $a_0=1/2$ 、 $A_0=M(a_0)$ とする。 $A_k=M(a_k)$ （ $0<a_k<1$ ）に対し、 $\sigma$ を恒等置換にとると $a_{11}=a_{22}=a_k>0$ であるから $\sigma$ は補題 2.3の条件を満たし、 $\min_ia_{i\sigma(i)}=a_k$ である。 $\lambda'=a_k/2$ と置くと $0<\lambda'<a_k$ であり、置き換えの結果の対角成分は $(a_k-a_k/2)/(1-a_k/2)=a_k/(2-a_k)$ 、非対角成分は $(1-a_k)/(1-a_k/2)=1-a_k/(2-a_k)$ である。よって $a_{k+1}=a_k/(2-a_k)$ と置くと $A_{k+1}=M(a_{k+1})$ である。 $a_k=1/(2^{k}+1)$ ならば

a_{k+1}=\frac{1/(2^{k}+1)}{2-1/(2^{k}+1)}=\frac{1}{2(2^{k}+1)-1}=\frac{1}{2^{k+1}+1}

であるから、帰納法によりすべての $k$ について $a_k=1/(2^{k}+1)$ であり、 $0<a_k<1$ が保たれる。したがって列 $A_0,A_1,\dots$ はすべての段で定まり、どの $A_k$ も置換行列ではない。

(4)を示す。第 $1$ 列の成分がすべて $1$ で、他の成分がすべて $0$ である $n$ 次正方行列を $A$ とする。成分は非負であり、各行の和は $1$ であり、 $p(A)=n$ である。 $n\ge2$ であるから第 $2$ 列の和は $0$ であり、命題 1.3により置換行列の列和はすべて $1$ であるから、 $A$ は置換行列ではない。

次に、 $A$ を置換行列でない $n$ 次二重確率行列とする。命題 3.2により $p(A)\ge n$ であり、 $p(A)=n$ ならば $A$ は置換行列であるから $p(A)\ge n+1$ である。 $p(A)=n+1$ と仮定する。各行は少なくとも一つの正の成分をもつので、ある一つの行 $i_0$ はちょうど二つの正の成分をもち、他の各行 $i\ne i_0$ はちょうど一つの正の成分 $a_{i\tau(i)}$ をもつ。 $i\ne i_0$ のとき、行和が $1$ であるから $a_{i\tau(i)}=1$ である。相異なる $i,i'\ne i_0$ について $\tau(i)=\tau(i')$ とすると第 $\tau(i)$ 列の和が $2$ 以上になるので、 $\tau(i)\ne\tau(i')$ である。よって集合 $K=\{\tau(i):\ i\ne i_0\}$ は $n-1$ 個の列からなる。 $j=\tau(i)\in K$ について第 $j$ 列の和は $1=a_{ij}$ であり成分は非負であるから、 $a_{i_0j}=0$ である。したがって行 $i_0$ の正の成分は $K$ に属さない列にあり、そのような列は $n-(n-1)=1$ 個しかない。これは行 $i_0$ が相異なる二つの列に正の成分をもつことに反する。よって $p(A)\ge n+2$ である。

等号の例として、 $a_{11}=a_{12}=a_{21}=a_{22}=1/2$ 、 $3\le i\le n$ について $a_{ii}=1$ とし、他の成分を $0$ とする $n$ 次正方行列 $A$ をとる。成分は非負であり、第 $1$ 、 $2$ 行と第 $1$ 、 $2$ 列の和は $1/2+1/2=1$ 、第 $i$ 行と第 $i$ 列（ $i\ge3$ ）の和は $1$ であるから、 $A$ は二重確率行列である。正の成分は左上の四つと $a_{ii}$ （ $3\le i\le n$ ）であるから $p(A)=4+(n-2)=n+2$ である。

(5)を示す。 $C=(c_{ij})$ を成分が実数である $n$ 次正方行列とし、

\gamma'=\max_{\sigma}\ \sum_{i=1}^{n}c_{i\sigma(i)}

と置く。ここで最大は置換 $\sigma$ の全体をわたる。置換の個数は $n!$ 個で有限であるから $\gamma'$ は定まり、 $\gamma'$ を与える置換 $\sigma^{\sharp}$ が存在する。定義 1.2により $P_\sigma$ の第 $i$ 行で $1$ に等しい成分は第 $\sigma(i)$ 列の成分だけであるから、任意の置換 $\sigma$ について

\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}(P_\sigma)_{ij}=\sum_{i=1}^{n}c_{i\sigma(i)}

が成り立つ。任意の二重確率行列 $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}$ であり、和はすべて有限和であるから、加法の結合法則と交換法則により和の順序を入れ替えて

\sum_{i,j}c_{ij}a_{ij}=\sum_{k=1}^{m}\lambda_k\sum_{i,j}c_{ij}(P_{\sigma_k})_{ij}=\sum_{k=1}^{m}\lambda_k\sum_{i=1}^{n}c_{i\sigma_k(i)}

を得る。 $\gamma'$ の定義により各 $k$ について $\sum_ic_{i\sigma_k(i)}\le\gamma'$ であり、 $\lambda_k>0$ であるから

\sum_{i,j}c_{ij}a_{ij}\ \le\ \sum_{k=1}^{m}\lambda_k\gamma'=\gamma'\sum_{k=1}^{m}\lambda_k=\gamma'

が成り立つ。さらに命題 1.3により $P_{\sigma^{\sharp}}$ は二重確率行列であり、上の等式により $\sum_{i,j}c_{ij}(P_{\sigma^{\sharp}})_{ij}=\gamma'$ である。よって二重確率行列の全体における $\sum_{i,j}c_{ij}a_{ij}$ の最大値は存在して $\gamma'$ に等しく、置換行列で達成される。最小化の場合の証明と異なるのは、各項の評価 $\sum_ic_{i\sigma_k(i)}\le\gamma'$ の不等号の向きだけである。正の係数 $\lambda_k$ を掛けて足し合わせる段は、どちらの向きの不等号も保つ。▨

注意 6.2. 表示の一意性、二重確率行列全体が定める多面体の面の構造、および無限次への拡張は、本記事では扱っていない。

§E16.23Birkhoff–von Neumann の定理