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

二重確率行列は置換行列の凸結合で表せる。

主張がシンプルで美しい&証明が美しい&名前がかっこいい定理を紹介します。

二重確率行列,置換行列

  • 各要素が非負で,各行の和が1であるような行列を確率行列と言います。

  • 各要素が非負で,各行・各列の和が1であるような行列を二重確率行列と言います。

  • 各行・各列に1が1つありそれ以外の要素は0であるような行列を置換行列と言います。

確率行列の例: (0.20.80.30.7)\begin{pmatrix} 0.2 & 0.8 \\ 0.3 & 0.7 \end{pmatrix}

二重確率行列の例: (0.70.30.30.7)\:\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}

置換行列の例: (0110)\:\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

置換行列は二重確率行列,二重確率行列は確率行列です。それぞれ応用上も重要で有名な行列です。

注:行和ではなく,列和が1のものを確率行列ということもあります。

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

バーコフ--フォン・ノイマンの定理(Birkhoff--von Neumann)

二重確率行列 PP が与えられたとき,置換行列 PiP_i をうまいこといくつか持ってくると,その凸結合で表せる。

つまり,P=iσiPiP=\displaystyle\sum_{i}\sigma_iP_i と書ける。

σi0\sigma_i\geq 0iσi=1\displaystyle\sum_{i}\sigma_i=1

凸結合というのは,係数が非負で和が1であるような重みつき和です。例を見ると分かりやすいでしょう。

(0.70.30.30.7)=0.7(1001)+0.3(0110)\:\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}=0.7\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}+0.3\begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}

2×2行列だと当たり前の定理ですが,一般の正方行列で成り立つというのが驚きです。

バーコフ–フォン・ノイマンの定理の証明には,完全マッチングが存在する必要十分条件であるHallの定理を使います。→Hallの結婚定理とその証明

証明

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

二重確率行列 AA に対して,00 でない要素の数を NN とおく。NN に関する帰納法で証明する。

N=nN=n のとき,AA は置換行列そのものなのでOK。

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

  • AA よりも 00 である成分が多い
  • 全ての行の和,全ての列の和が 1α1-\alpha

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

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

補足(長いです)

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

  • AA の各行が UU の各頂点に対応
  • AA の各列が VV の各頂点に対応
  • AA00 でない成分に対応するところに枝を引く

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

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

バーコフフォンノイマンの定理の証明

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

すなわち,Γ(U)\Gamma(U') に対応する列の全成分の和は U|U'| 以上となる。一方,AA の各列の和は 11 なので,Γ(U)\Gamma(U') に対応する列の全成分の和は Γ(U)|\Gamma(U')| である。

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

組合せ,グラフ理論の定理を使って行列の美しい定理が証明できるというのは感動ですね!

高次元の多面体

各成分を座標軸に取ると n×nn\times n 行列は n2n^2 次元空間の一点とみなせます。

例えば,(1001)\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix} は4次元空間中の一点 (1,0,0,1)(1,0,0,1) とみなせます。

バーコフ–フォン・ノイマンの定理は別の言い方をすると二重確率行列がなす多面体の頂点が置換行列ということになります。この多面体は「バーコフ多面体」「完全二部グラフの完全マッチング多面体」と呼ばれます。

多次元の多面体はもはや頭の中で形を想像できませんがわくわくしますね。