二重確率行列

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

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

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

実際、左確率行列と右確率行列の両方が正方行列である必要があります。つまり、すべての行の合計が 1 になる場合、行列内のすべてのエントリの合計は行の数に等しくなければなりません。列についても同じことが当てはまるため、行数と列数は等しくなければなりません。

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

バーコフ・フォン・ノイマンの定理（バーコフの定理とも呼ばれる^{[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のこのような分解は「凸結合」として知られています。)ホールの結婚定理に基づく定理の証明を以下に示します。

この表現はバーコフ・フォン・ノイマン分解として知られており、一意ではない可能性があります。これは、グラフの隣接行列を通じて対応が確立されるケーニッヒの定理の実数値一般化として説明されることがよくあります。

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

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の行が一方の部分にリストされ、列がもう一方の部分にリストされ、 x _ij  ≠ 0 の場合に限り、行iが列jに接続される二部グラフを構築します。 A を任意の行の集合とし、 A ' をグラフ内のAの行に結合された列の集合として定義します。 2 つの集合のサイズ | A | と | A' | をx _ijで表します。

Aのすべてのiについて、 x _ijのA'のjの合計は1 です。これは、 x _ij ≠ 0となるすべての列j がA ' に含まれ、X は二重確率的であるためです。したがって、 | A | はx _ijのすべてのi  ∈  A、j  ∈  A 'の合計です。

一方、| A ' | は、 x _ijのすべてのi ( A内にあるかどうかに関係なく) とA '内のすべてのj の合計です。これは、 iがA内の行に限定されている 対応する合計よりも大きいです。したがって、| A ' | ≥ | A | です。

ホールの結婚定理の条件が満たされ、グラフ内でXの各行を正確に 1 つの (異なる) 列に結合するエッジのセットを見つけることができます。これらのエッジは、非ゼロのセルがXの非ゼロのセルに対応する順列行列を定義します。

より多くの列と行を持つ行列への簡単な一般化があり、i ^番目の行の合計はr _i (正の整数)に等しく、列の合計は 1 に等しく、すべてのセルは非負です (行の合計の合計は列の数に等しい)。 この形式の行列はどれも、0 と 1 で構成される同じ形式の行列の凸結合として表現できます。 証明するには、元の行列の i 番目の行を、それぞれ元の行を r i で割った値に等しい r i 個の別々の行で置き換え ^、結果_として得られる_正方行列にバーコフの定理を適用し、最後にr _i行を ^単一のi番目の行に 加法的に再結合します。

同様に、行だけでなく列も複製できますが、再結合の結果は必ずしも0と1に限定されるわけではありません。R. M. Caronらは、別の一般化（証明はかなり難しい）を提案しました。^[3]

• 確率行列
• 非確率行列
• バーコフアルゴリズム

• Brualdi, Richard A. (2006).組み合わせ行列クラス. 数学とその応用百科事典. 第108巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-86565-4.ZBL1106.05001  。​

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