二重確率行列

数学、特に確率論と組み合わせ論において、二重確率行列 （二項確率行列とも呼ばれる）は正方行列である。${\displaystyle X=(x_{ij})}$非負の実数で、各行と各列の合計が 1 になるもの、つまり、

${\displaystyle \sum _{i}x_{ij}=\sum _{j}x_{ij}=1,}$

したがって、二重確率行列は左確率行列と右確率行列の両方である。^{[ 1 ]}

実際、左確率行列と右確率行列の両方を持つ行列は正方行列でなければなりません。すべての行の合計が1になる場合、行列のすべての要素の合計は行数と等しくなければならず、列についても同様であるため、行数と列数は等しくなければなりません。

のクラス${\displaystyle n\times n}$二重確率行列は、バーコフ多面体として知られる凸多面体である。${\displaystyle B_{n}}$行列の要素をデカルト座標として使用すると、${\displaystyle (n-1)^{2}}$次元アフィン部分空間${\displaystyle n^{2}}$次元ユークリッド空間は次のように定義される。${\displaystyle 2n-1}$行と列の合計がすべて 1 に等しいことを指定する独立した線形制約。${\displaystyle 2n-1}$制約ではなく${\displaystyle 2n}$（これらの制約のうちの1つは従属的であるため、行の合計の合計は列の合計と等しくなければならない。）さらに、エントリはすべて非負で1以下であるという制約があります。

ビルコフ・フォン・ノイマンの定理（しばしば単にビルコフの定理として知られる^{[ 2 ] [ 3 ] [ 4 ]}）は、多面体が${\displaystyle B_{n}}$は、集合の凸包である。${\displaystyle n\times n}$置換行列、さらに頂点は ${\displaystyle B_{n}}$はまさに順列行列です。言い換えれば、${\displaystyle X}$が二重確率行列である場合、${\displaystyle \theta _{1},\ldots ,\theta _{k}\geq 0,\sum _{i=1}^{k}\theta _{i}=1}$および順列行列${\displaystyle P_{1},\ldots ,P_{k}}$そのため

${\displaystyle X=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.}$

（このようなXの分解は「凸結合」として知られています。）ホールの結婚定理に基づく定理の証明を以下に示します。

この表現はビルコフ・フォン・ノイマン分解として知られており、一意ではない場合がある。これは、グラフの隣接行列によって対応関係が確立されるケーニッヒの定理の実数値一般化として説明されることが多い。ビルコフ・フォン・ノイマンの定理は、整数線形計画法にも応用されている。^{[ 5 ]}

• 2つの二重確率行列の積は二重確率行列となる。しかし、非特異な二重確率行列の逆行列は必ずしも二重確率行列になるとは限らない（実際、逆行列の要素が非負であれば、その逆行列は二重確率行列となる）。
• 既約な非周期有限マルコフ連鎖の定常分布が一様であるのは、その遷移行列が二重確率的である場合に限る。
• シンクホーンの定理は、厳密に正の要素を持つ任意の行列は、対角行列による前後の乗算によって二重に確率的になることができると述べている。
• のために${\displaystyle n=2}$すべての二確率行列は単確率かつ直交確率であるが、より大きな${\displaystyle n}$それは事実ではありません。
• ファン・デル・ヴェルデンの予想によれば、 n × n の二重確率行列の中で最小のパーマネントは${\displaystyle n!/n^{n}}$すべてのエントリが等しい行列によって達成される${\displaystyle 1/n}$[ ^{6 ]}この予想の証明は、1980 年に B. Gyires [7] によって、また 1981 年に GP Egorychev [8] と DI Falikman [9] によって発表されました^{。この研究により}、^{EgorychevとFalikman}は^1982年にFulkerson賞を受賞しました。^{[ 10 ]}

X を二重確率行列とする。このとき、 p _ij ≠ 0のときx _ij ≠ 0となるような置換行列Pが存在することを示す。したがって、非ゼロのp _ijに対応する最小のx _ijをλとすると、差X – λ P は二重確率行列のスカラー倍となり、 Xより少なくとも 1 つ多くのゼロセルを持つことになる。したがって、置換行列のスカラー倍を取り除くことで、 Xの非ゼロセルの数を順次減らしていき、最終的にゼロ行列に到達すれば、元のXと等しい置換行列の凸結合を構築したことになる。^{[ 2 ]}      

例えば、${\displaystyle X={\frac {1}{12}}{\begin{pmatrix}7&0&5\\2&6&4\\3&6&3\end{pmatrix}}}$それから ${\displaystyle P={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}}$、${\displaystyle \lambda ={\frac {2}{12}}}$、 そして ${\displaystyle X-\lambda P={\frac {1}{12}}{\begin{pmatrix}7&0&3\\0&6&4\\3&4&3\end{pmatrix}}}$。

証明： Xの行が一方の部分に、列がもう一方の部分にリストされ、行iが列jに接続されるのはx _ij ≠ 0の場合のみであるような二部グラフを構築する  ${\displaystyle A}$行の任意の集合とし、${\displaystyle A'}$グラフのAの行に結合された列の集合として、サイズを表現したい。${\displaystyle |A|}$そして${\displaystyle |A'|}$x _ijに関して、2 つの集合の。

Aのすべてのiについて、 A'のjに関するx _ijの合計は1 です。なぜなら、 x _ij ≠ 0となるすべての列jがA 'に含まれており、X は二重に確率的だからです。したがって  ${\displaystyle |A|}$は、 i  ∈ A、j ∈ A 'のすべての i についてx _ijの合計です。   

その間${\displaystyle |A'|}$これは、すべてのi ( Aに含まれるか否かを問わず) とA 'に含まれるすべてのjについてのx _ijの合計であり、これは、iがAの行に限定されている場合の対応する合計以上である。したがって ${\displaystyle |A'|\geq |A|}$。

したがって、ホールの結婚定理の条件が満たされ、グラフにおいて、 Xの各行をちょうど1つの（異なる）列に接続するエッジの集合を見つけることができます。これらのエッジは、非ゼロのセルがXの非ゼロのセルに対応する置換行列を定義します。

• 確率行列
• ユニオキャスティック行列
• バーコフアルゴリズム

• ブルアルディ、リチャード A. (2006).組み合わせ行列クラス. 数学とその応用百科事典、第 108 巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-86565-4. Zbl 1106.05001 . 

• PlanetMathのバーコフ・フォン・ノイマンの定理に関するページ
• PlanetMathのバーコフ・フォン・ノイマンの定理の証明に関するページ