二重確率行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

\sum_i a_{ij}=\sum_j a_{ij}=1

が成立するような行列 A=(a_{ij}) のことを二重確率行列と呼ぶ。この定義から、二重確率行列は左確率的英語版であると同時に右確率的である[1]

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

バーコフ多面体とバーコフ=フォン・ノイマンの定理[編集]

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

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

他の性質[編集]

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

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

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

関連項目[編集]

外部リンク[編集]

参考文献[編集]

  1. ^ Marshal, Olkin (1979). Inequalities: Theory of Majorization and Its Applications. pp. 8. ISBN 0-12-473750-1. 
  2. ^ van der Waerden, B. L. (1926), “Aufgabe 45”, Jber. Deutsch. Math.-Verein. 35: 117 .
  3. ^ Gyires, B. (1980), “The common source of several inequalities concerning doubly stochastic matrices”, Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis 27 (3-4): 291–304, MR604006 .
  4. ^ Egoryčev, G. P. (1980) (Russian), Reshenie problemy van-der-Vardena dlya permanentov, Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR602332 . Egorychev, G. P. (1981), “Proof of the van der Waerden conjecture for permanents” (Russian), Akademiya Nauk SSSR 22 (6): 65–71, 225, MR638007 . Egorychev, G. P. (1981), “The solution of van der Waerden's problem for permanents”, Advances in Mathematics 42 (3): 299–305, doi:10.1016/0001-8708(81)90044-X, MR642395 .
  5. ^ Falikman, D. I. (1981), “Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix” (Russian), Akademiya Nauk Soyuza SSR 29 (6): 931–938, 957, MR625097 .
  6. ^ Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.