バーコフ--フォン・ノイマンの定理

二重確率行列のサイズ $n$ を固定して証明する（以下の議論は全ての $n$ で成立する）。

二重確率行列 $A$ に対して，$0$ でない要素の数を $N$ とおく。$N$ に関する帰納法で証明する。

$N=n$ のとき，$A$ は置換行列そのものなのでOK。

以下，$N\leq k$ のときに主張が正しいと仮定して，$N=k+1$ の場合を証明する。まず，Hall の結婚定理を使うと，ある置換 $\tau$ が存在して，$i=1,\cdots, n$ に対して $a_{i\tau(i)}\neq 0$ とできることが分かる（→難しいです，詳細は補足）。そこで，$\tau$ に対応する置換行列を $P$ として，$a_{i\tau(i)}$ の中での最小の値を $\alpha$ とおく。そして，$B=A-\alpha P$ という行列を考えると，これは，

• $A$ よりも $0$ である成分が多い
• 全ての行の和，全ての列の和が $1-\alpha$

を満たす。よって，$C=\dfrac{1}{1-\alpha}B$ は二重確率行列で，$A$ よりも $0$ である成分が多いので，帰納法の仮定により，置換行列の凸結合で表せる。

よって，$A=\alpha P +(1-\alpha)C$ は「置換行列 $P$」と「置換行列の凸結合で表せる $C$」の凸結合で表せるので，結局，置換行列の凸結合で表せる。

$A$ に対応する二部グラフ $G=(U,V)$ を考える。すなわち，

• $A$ の各行が $U$ の各頂点に対応
• $A$ の各列が $V$ の各頂点に対応
• $A$ の $0$ でない成分に対応するところに枝を引く

ような二部グラフを $G$ とする。

以下，頂点集合 $U'$ と辺で結ばれている頂点の集合を $\Gamma(U')$ と表記する。任意の $U$ の部分集合 $U'$ に対して，$|U'|\leq |\Gamma(U')|$ であることを証明する。そうすれば，Hall の定理により $G$ には完全マッチングが存在することが分かるので，その完全マッチングに対応する置換を $\tau$ とすればよい。

まず，$A$ を，図のように，$U'$ 部分，$\Gamma(U')$ 部分に対応するかどうかで，4つに分割する。 $U'$ は $\Gamma(U')$ 以外の頂点とは結ばれていないので，図の右上部分は $O$ である。よって，$A$ の各行の和は $1$ なので，図の左上部分の全成分の和は，$|U'|$ となる。

すなわち，$\Gamma(U')$ に対応する列の全成分の和は $|U'|$ 以上となる。一方，$A$ の各列の和は $1$ なので，$\Gamma(U')$ に対応する列の全成分の和は $|\Gamma(U')|$ である。

以上より，$|U'|\leq |\Gamma(U')|$ となる。