2014/12/27

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

分野: 線形代数  レベル: 大学数学

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

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

二重確率行列,置換行列

・各要素が非負で各行の和が1であるような行列を確率行列と言います。
注:列和が1のものを確率行列ということもある。

  • 各要素が非負で各行,各列の和が1であるような行列を二重確率行列と言います。
  • 各行,各列に1が1つありそれ以外の要素は0であるような行列を置換行列と言います。

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

確率行列の例:$\begin{pmatrix}
0.2 & 0.8 \\
0.3 & 0.7
\end{pmatrix}$
二重確率行列の例:$\:\begin{pmatrix}
0.7 & 0.3 \\
0.3 & 0.7
\end{pmatrix}$
置換行列の例:$\:\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}$

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

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

バーコフ–フォン・ノイマンの定理(Birkhoff–von Neumann):
二重確率行列 $P$ が与えられたとき,置換行列 $P_i$ をいくつか持ってくると,その凸結合で表せる。
つまり,$P=\displaystyle\sum_{i}\sigma_iP_i$ と書ける。
($\sigma_i\geq 0$,$\displaystyle\sum_{i}\sigma_i=1$)

$\:\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の結婚定理とその証明

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

高次元の多面体

各成分を座標軸に取ると $n\times n$ 行列は $n^2$ 次元空間の一点とみなすことができます。
例えば,$\begin{pmatrix}
1 & 0 \\
0 & 1\end{pmatrix}$ は4次元空間中の一点$(1,0,0,1)$ とみなせます。

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

多次元の多面体はもはや頭の中で形を想像できませんがわくわくしますね。
分野: 線形代数  レベル: 大学数学