8.8. 魔法陣と Birkhoff–von Neumann の定理

目次

Hall の結婚定理 (定理 8.3.4) を線形代数に応用してみよう。

本書では \(\mathbb{N}=\left\{ 0,1,2,\ldots\right\} \) だったことを思い出してほしい。また、非負実数全体の集合を \(\mathbb{R}_{+} \) と書くことも本書の最初で定めた。

読者も知っているであろう概念の定義を三つ示す:

定義 8.8.1

\(\mathbb{N}\)-魔法陣 (\(\mathbb{N}\)-magic matrix) とは、次の三つの条件を満たす正方行列 \(M\) を意味する:

  1. \(M\) の要素は全て非負整数である。

  2. \(M\) の各行の和は全て等しい。

  3. \(M\) の各列の和は全て等しい。

定義 8.8.2

\(\mathbb{R}_{+}\)-魔法陣 (\(\mathbb{R}_{+}\)-magic matrix) とは、次の三つの条件を満たす正方行列 \(M\) を意味する:

  1. \(M\) の要素は全て非負実数である。

  2. \(M\) の各行の和は全て等しい。

  3. \(M\) の各列の和は全て等しい。

定義 8.8.3

二重確率行列 (doubly stochastic matrix) とは、次の三つの条件を満たす正方行列 \(M\) を意味する:

  1. \(M\) の要素は全て非負実数である。

  2. \(M\) の各行の和は全て \(1\) に等しい。

  3. \(M\) の各列の和は全て \(1\) に等しい。

明らかに、これら三つの概念は密接に関連している (例えば、全ての \(\mathbb{N}\)-魔法陣と全ての二重確率行列は \(\mathbb{R}_{+}\)-魔法陣である)。最も重要なのは最後の二重確率行列であり、特に majorization (不等式の証明における主要な手法の一つ) では二重確率行列がよく用いられる (例えば [MaOlAr11, Chapter 2] を見てほしい)。[BapRag97, Chapter 2] には一章を使った二重確率行列の解説がある。ここでは基礎的な性質を示すだけとする。まず、例をいくつか示す:

例 8.8.4

\(n\) を正整数とする。\(n\times n\) 行列

\[ \begin{pmatrix} 1 & 1 & \cdots & 1\\ 1 & 1 & \cdots & 1\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & \cdots & 1 \end{pmatrix} \]

は \(\mathbb{N}\)-魔法陣であり、\(\mathbb{R}_{+}\)-魔法陣でもある。しかし、各行および各列の和が \(n\) なので、この行列は (\(n = 1\) の場合を除いて) 二重確率行列ではない。この行列を \(n\) で割って得られる行列は二重確率行列である。

例 8.8.5

\(\mathbb{N}\)-魔法陣である \(3\times 3\)-行列の例を次に示す:

\[ \begin{pmatrix} 7 & 0 & 5\\ 2 & 6 & 4\\ 3 & 6 & 3 \end{pmatrix} \]

この行列を \(12\) で割って得られる行列は二重確率行列である。

例 8.8.6

置換行列 (permutation matrix) とは任意の要素が \(0\) または \(1\) の正方行列であって条件「各行に \(1\) がちょうど一個、各列に \(1\) がちょうど一個ある」を満たすものを言う。例えば、次の \(4 \times 4\) 行列は置換行列である:

\[ \begin{pmatrix}0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\end{pmatrix} \]

任意の \(n \in \mathbb{N}\) に対して、\(n \times n\) の置換行列は \(n!\) 個ある。なぜなら、このサイズの置換行列全体と \(\left\{ 1,2,\ldots,n\right\} \) の置換全体の間に全単射が存在するためである。具体的に言えば、\(\left\{ 1,2,\ldots,n\right\} \) の置換 \(\sigma\) に対応する置換行列を \(P\left( \sigma\right) \) とするとき、全ての \(i\in\left\{ 1,2,\ldots,n\right\} \) に対して \(P\left( \sigma\right) \) の \(\left( i,\sigma\left( i\right) \right) \) 要素は \(1\) であり、他の全ての要素は \(0\) である。例えば \(1,2,3\) をそれぞれ \(2,3,1\) に移す \(\left\{ 1,2,3\right\} \) の置換を \(\sigma\) とするとき、対応する置換行列 \(P\left( \sigma\right) \) は \({\begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}}\) となる。

任意の置換行列は \(\mathbb{N}\)-魔法陣、\(\mathbb{R}_{+}\)-魔法陣、二重確率行列のどれでもある。

置換行列は (ある意味で) 魔法陣と二重確率行列の基本単位となる！ 具体的には、次の命題が成り立つ:

定理 8.8.7

[Birkhoff–von Neumann の定理 (Birkhoff–von Neumann theorem)] \(n\) を自然数とする。このとき:

  1. 任意の \(\mathbb{N}\)-魔法陣は有限個の置換行列の和として表現できる。

  2. 任意の \(\mathbb{R}_{+}\)-魔法陣は有限個の置換行列の \(\mathbb{R}_{+}\)-線形結合として表現できる。 [つまり、非負実数 \(\lambda_{1},\lambda_{2},\ldots ,\lambda_{k}\in\mathbb{R}_{+}\) と置換行列 \(P_{1},P_{2},\ldots ,P_{k}\) を使って \(\lambda_{1}P_{1}+\lambda_{2}P_{2}+\cdots+\lambda_{k}P_{k}\) と表現できる。]

  3. \(n\) を正整数とする。任意の \(n \times n\) 二重確率行列は置換行列の凸結合 (convex combination) として表現できる。 [つまり、\(\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k}=1\) を満たす非負実数 \(\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\in\mathbb{R}_{+}\) と置換行列 \(P_{1},P_{2},\ldots ,P_{k}\) を使って \(\lambda_{1}P_{1}+\lambda_{2}P_{2}+\cdots+\lambda_{k}P_{k}\) と表現できる。]

Hall の結婚定理を使った定理 8.8.7 の証明を本節の最後に示す。その証明に必要となる簡単な結果を二つ示す:

命題 8.8.8

\(n\) を正整数、\(A\) を \(n\times n\) の \(\mathbb{N}\)-魔法陣または \(\mathbb{R}_{+}\)-魔法陣とする。このとき、\(A\) の各行の和は \(A\) の各列の和に等しい。

[証明] どちらも \(A\) の全要素の和の \(\dfrac{1}{n}\) に等しい (\(A\) は \(n\) 個の行と \(n\) 個の列を持つため)。 □

補題 8.8.9

\(n\) を正整数、\(M\) を零行列でない \(\mathbb{N}\)-魔法陣または \(\mathbb{R}_{+}\)-魔法陣とする。このとき \(\left\{ 1,2,\ldots,n\right\} \) の置換 \(\sigma\) であって条件「行列 \(M\) の要素 \(M_{1,\sigma\left( 1\right) }\), \(M_{2,\sigma\left( 2\right) }\), ..., \(M_{n,\sigma\left( n\right) }\) がどれも \(0\) でない」を満たすものが存在する。 [\(M_{i,j}\) は行列 \(M\) の \(\left( i,j\right) \) 要素を意味する。]

例 8.8.10

\(n=3\) および \(M= {\begin{pmatrix} 2 & 7 & 1\\ 0 & 1 & 9\\ 8 & 2 & 0 \end{pmatrix}}\) とする。このとき \(1,2,3\) をそれぞれ \(3,2,1\) に移す置換 \(\sigma\) が補題 8.8.9 の条件を満たす。

[補題 8.8.9 の証明] \(M\) の任意の行の和を \(s\) とする (\(M\) は魔法陣なので、どの行を取っても和は変わらない)。このとき命題 8.8.8 より、\(s\) は \(M\) の任意の列の和でもある。また、\(M\) の全要素の和は \(ns\) である。\(M\) の任意の要素は非負実数で \(M\) は零行列でないので \(ns > 0\) であり、ここから \(s > 0\) が分かる。

\(X=\left\{ 1,2,\ldots,n\right\} \) および \(Y=\left\{ -1,-2,\ldots ,-n\right\} \) と定め、単純グラフ \(G\) を次のように定義する: \(G\) の頂点集合は \(X \cup Y\) であり、\(G\) の頂点 \(i \in X\) と頂点 \(-j \in Y\) は \(M_{i,j} > 0\) のとき、かつそのときに限って隣接する。これ以外に隣接する二頂点は存在しない。

このとき \(\left( G,X,Y\right) \) は二部グラフである。

続いて二部グラフ \(\left( G,X,Y\right) \) が Hall 条件を満たすことを証明する。つまり、\(\left\{ 1,2,\ldots,n\right\} \) の任意の部分集合 \(A\) が \(\left\vert N\left( A\right) \right\vert \geq\left\vert A\right\vert \) を満たすことを示す。

背理法で示す。\(\left\vert N\left( A\right) \right\vert < \left\vert A\right\vert \) を満たす \(\left\{ 1,2,\ldots,n\right\} \) の部分集合 \(A\) が存在すると仮定し、この \(A\) に注目する。\(k\in\left\{ 0,1,\ldots ,n\right\} \) を使って \(A=\left\{ 1,2,\ldots,k\right\} \) と書けると一般性を失うことなく仮定する (そうでなければ \(M\) の行を置換する)。このとき、\(M\) の定義と \(\left\vert N\left( A\right) \right\vert < \left\vert A\right\vert =k\) から、\(M\) の最初の \(k\) 行にある非零要素は \(k\) 個未満だと分かる。言い換えれば、最初の \(k\) 行に非零要素を持つ \(M\) の列は \(k\) 個より少ない。つまり \(M\) の少なくとも一つの列は最初の \(k\) 行が全て \(0\) である。加えて \(M\) の各列の和は \(s\) なので、\(M\) の最初の \(k\) 行の和は \(ks\) より小さい。一方、\(M\) の各行の和は \(s\) なので、\(M\) の最初の \(k\) 行の和は \(ks\) に等しい。この二つの事実は矛盾するから、仮定が偽だと分かる。

以上で Hall 条件が満たされると分かった。よって Hall の結婚定理 (定理 8.3.4) より \(G\) は完全マッチングを持つ。このマッチングを

\[ \left\{ \left\{ 1,-a_{1}\right\} ,\ \left\{ 2,-a_{2}\right\} ,\ \ldots,\ \left\{ n,-a_{n}\right\} \right\} \]

とする。このとき \(a_{1},a_{2},\ldots,a_{n}\) は相異なるから、全ての \(i\in\left\{ 1,2,\ldots,n\right\} \) に対して \(a_{i}=\sigma\left( i\right) \) となるような \(\left\{ 1,2,\ldots,n\right\} \) の置換 \(\sigma\) が存在する。この \(\sigma\) は全ての \(i\in\left\{ 1,2,\ldots,n\right\} \) に対して \(M_{i,\sigma\left( i\right) }>0\) を満たす。これが見つけたかった置換だから、以上で補題 8.8.9 は証明された。□

[定理 8.8.7 の証明 (概略)] (a): \(M\) を \(n\times n\) の \(\mathbb{N}\)-魔法陣とする。どうすれば \(M\) を置換行列の和として表せるだろうか？

次のアルゴリズムを試してみよう: \(\mathbb{N}\)-魔法陣の条件が破られないように \(M\) から置換行列を引く操作を、結果が零行列になるまで繰り返す。零行列が得られたなら、それまでに引いた置換行列の和が \(M\) に等しくなる。

このアルゴリズムの例を示す。\(n = 3\) および \(M={\begin{pmatrix} 2 & 7 & 1\\ & 1 & 9\\ 8 & 2 & \end{pmatrix}}\) とする1。\(M\) から置換行列を引いて得られる行列は定義 8.8.1 の条件 (b) と (c) を常に満たす (各列と各列の和が全て \(1\) だけ小さくなるため)。しかし、条件 (a) が満たされるとは限らない: 置換行列を引いて得られる行列が負の要素を含む可能性がある。例えば、\(M\) から置換行列 \({\begin{pmatrix} 1 & & \\ & 1 & \\ & & 1 \end{pmatrix}} \) を引くと \((3,3)\) 要素が負になる。しかし幸い、補題 8.8.9 より \(M_{1,\sigma\left( 1\right) },\ M_{2,\sigma\left( 2\right) },\ \ldots,\ M_{n,\sigma\left( n\right) }\) がどれも \(0\) でないような \(\left\{ 1,2,\ldots,n\right\} \) の置換 \(\sigma\) が存在する。この条件を満たす置換 \(\sigma\) を取り、\(\sigma\) に対応する置換行列 \(P\left( \sigma\right) \) を \(M\) から引けば、得られる行列は \(\mathbb{N}\)-魔法陣となる。なぜなら、この減算は \(0\) でない要素 \(M_{1,\sigma\left( 1\right) }\), \(M_{2,\sigma\left( 2\right) }\), ..., \(M_{n,\sigma\left( n\right) }\) から \(1\) を引いているだけなので、負の要素が生じないためである。今考えている例では、\(1\), \(2\), \(3\) をそれぞれ \(3\), \(2\), \(1\) に移す置換を \(\sigma\) として取れる。対応する置換行列 \(P\left( \sigma\right) \) は \({\begin{pmatrix} & & 1\\ & 1 & \\ 1 & & \end{pmatrix}} \) であり、これを \(M\) から引くと次の行列を得る:

\[ \begin{pmatrix} 2 & 7 & 1\\ & 1 & 9\\ 8 & 2 & \end{pmatrix} -\begin{pmatrix} & & 1\\ & 1 & \\ 1 & & \end{pmatrix} =\begin{pmatrix} 2 & 7 & \\ & & 9\\ 7 & 2 & \end{pmatrix} \]

この行列もまた \(\mathbb{N}\)-魔法陣となる。よって、\(M\) に対して適用した操作をこの行列にも適用できる: 置換行列を引くことができる。

ただ今回は、単に置換行列をそのまま引くよりも効果的な操作ができる: 置換行列 \({\begin{pmatrix} & 1 & \\ & & 1\\ 1 & & \end{pmatrix}} \) を一度だけ引くのではなく、\(7\) 回引くことができる。この減算で影響を受ける要素は \(7\), \(9\), \(7\) なので、こうしたとしても負の要素は生じない。この操作の結果として、次の行列が得られる:

\[ \begin{pmatrix} 2 & 7 & \\ & & 9\\ 7 & 2 & \end{pmatrix} -7\cdot\begin{pmatrix} & 1 & \\ & & 1\\ 1 & & \end{pmatrix} =\begin{pmatrix} 2 & & \\ & & 2\\ & 2 & \end{pmatrix} \]

同じ操作はさらにもう一度行える。今回は置換行列を \(2\) 回引くことができ、次の行列が得られる:

\[ \begin{pmatrix} 2 & & \\ & & 2\\ & 2 & \end{pmatrix} -2\cdot\begin{pmatrix} 1 & & \\ & & 1\\ & 1 & \end{pmatrix} =\begin{pmatrix} \phantom{1} & & \\ & \phantom{1} & \\ & & \phantom{1} \end{pmatrix} =0_{3\times3} \]

[言うまでもないと思うが、最後の記号は \(3 \times 3\) の零行列を表す。]

以上の操作から、\(M\) から置換行列を何度か引くと零行列が得られると分かった。よって \(M\) はこれまでに引いた置換行列の和に等しい。具体的に言えば、次の等式が成り立つ:

\[ M=\begin{pmatrix} & & 1\\ & 1 & \\ 1 & & \end{pmatrix} +7\cdot\begin{pmatrix} & 1 & \\ & & 1\\ 1 & & \end{pmatrix} +2\cdot\begin{pmatrix} 1 & & \\ & & 1\\ & 1 & \end{pmatrix} \]

つまり \(M\) は \(1+7+2=10\) 個の置換行列の和として表現できる。

以上のアルゴリズムは一般的なケースでも動作する。一般的なアルゴリズムと、その正しさの説明は次の通りである:

以上で定理 8.8.7 (a) は証明された。

(b): (a) と同様の議論で証明できる (ただし、非零要素 \(M_{1,\sigma\left( 1\right) }\), \(M_{2,\sigma\left( 2\right) }\), ..., \(M_{n,\sigma\left( n\right) }\) が \(1\) 以上とは限らないので、(b) の証明では \(m\) の利用が必須となる。(a) では \(m\) を使わなくても議論の正しさは変わらない)。

(c): \(M\) を \(n\times n\) の二重確率行列とする。このとき \(M\) は \(\mathbb{R}_{+}\)-魔法陣でもあるから、(b) より \(M = \lambda_{1}P_{1}+\lambda_{2}P_{2}+\cdots+\lambda _{k}P_{k}\) となるような置換行列 \(P_{1},P_{2},\ldots,P_{k}\) と非負実数 \(\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\in\mathbb{R}_{+}\) が存在する。これらの \(\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\) と \(P_{1},P_{2},\ldots,P_{k}\) に注目する。

\(M\) の第 \(1\) 行の和を考える。容易に分かるように、この和は \(\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k}\) に等しい (前段落で見たように \(M=\lambda_{1}P_{1}+\lambda_{2}P_{2}+\cdots+\lambda_{k}P_{k}\) であり、それぞれの置換行列は和の第 \(1\) 行に \(1\) だけ寄与するため)。一方 \(M\) は二重確率行列なので、この和は \(1\) である。両者を比較すれば \(\lambda_{1}+\lambda_{2}+\cdots+\lambda _{k}=1\) を得る。よって \(M\) は \(\lambda _{1}+\lambda_{2}+\cdots+\lambda_{k}=1\) を満たす非負実数 \(\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\in\mathbb{R}_{+}\) と置換行列 \(P_{1},P_{2},\ldots,P_{k}\) を使って \(\lambda_{1}P_{1}+\lambda _{2}P_{2}+\cdots+\lambda_{k}P_{k}\) と表現できる。以上で定理 8.8.7 (c) は証明された。□

  1. 行列の \(0\) に等しい要素を省略する記法を使っている。例えば \({\begin{pmatrix} 2 & 7 & 1\\ & 1 & 9\\ 8 & 2 & \end{pmatrix}} \) は行列 \({\begin{pmatrix} 2 & 7 & 1\\ 0 & 1 & 9\\ 8 & 2 & 0 \end{pmatrix}}\) を意味する。 ↩︎

広告
このページの文章はテキストゆれないくんを使って校正されました。