二重確率行列

数学の確率論や組合せ論の分野における二重確率行列（にじゅうかくりつぎょうれつ、英: doubly stochastic matrix）とは、各行の和および各列の和がそれぞれ 1 となる非負の実正方行列 ${\displaystyle A=(a_{ij})}$ のことである。すなわち、

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

が成り立つ行列 ${\displaystyle A=(a_{ij})}$ のことを二重確率行列と呼ぶ。この定義から、二重確率行列は左確率的であると同時に右確率的である^[1]。

このような遷移行列は必ず正方行列でなければならない。すなわち、もし各行の和が 1 であるならその行列の全ての成分の和は各行の数に等しく、同様のことが各列に対しても成り立つため、行の数と列の数は必ず等しくなければならない。

バーコフ多面体とバーコフ＝フォン・ノイマンの定理

n × n 二重確率行列の類は、バーコフ多面体（英語版）として知られる凸多面体 B_n である。この行列成分をデカルト座標系として用いることで、それは n²次元ユークリッド空間のある (n − 1)²次元アフィン部分空間に含まれる。その空間は、行の和および列の和がそれぞれ 1 であるという特別な 2n − 1 個の線型独立な制限によって定義される（そのような制限の数は 2n − 1 であって 2n ではない。なぜならば、行の和と列の和が等しくなる必要があるので、2n 個の条件の内の一つは線型依存であるからである）。さらに、行列の成分はすべて非負で 1 以下であるように制限されている。

バーコフ＝フォン・ノイマンの定理では、この多面体 B_n は n × n 置換行列の集合の凸包であること、さらに B_n の頂点は正しく置換行列であることが述べられている。

他の性質

シンクホーンの定理では、厳密に正な成分を持つ任意の行列は、適切な対角行列の前方および後方からの乗算によって二重確率行列へと変換することができることが述べられている。

n = 2 に対し、すべての二重確率行列はユニタリ型確率行列（英語版）かつ直交型確率行列（英語版）である。しかしより大きい n に対してこのことは成立しない。

Van der Waerden は、すべての n × n 二重確率行列の中での最小の永久式は ${\displaystyle {\frac {n!}{n^{n}}}}$ であり、そのような最小はすべての成分が 1/n である二重確率行列によって達成されると予想した^[2]。この予想の証明は、1980年の B. Gyires^[3]、1981年の G. P. Egorychev^[4]および D. I. Falikman によって行われた^[5]。この業績により、Egorychev と Falikman は1982年にファルカーソン賞を受賞した^[6]。