二重確率行列

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/05/09 14:58 UTC 版)

が成立するような行列のことを二重確率行列と呼ぶ。この定義から、二重確率行列は左確率的（英語版）であると同時に右確率的である^[1] 。

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

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

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

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

他の性質

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

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

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

外部リンク

参考文献

Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.

参考文献

^ Marshal, Olkin (1979). Inequalities: Theory of Majorization and Its Applications. pp. 8. ISBN 0-12-473750-1.
^ van der Waerden, B. L. (1926), “Aufgabe 45”, Jber. Deutsch. Math.-Verein. 35: 117 .
^ Gyires, B. (1980), “The common source of several inequalities concerning doubly stochastic matrices”, Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis 27 (3-4): 291–304, MR 604006 .
^ Egoryčev, G. P. (1980) (Russian), Reshenie problemy van-der-Vardena dlya permanentov, Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR 602332 . Egorychev, G. P. (1981), “Proof of the van der Waerden conjecture for permanents” (Russian), Akademiya Nauk SSSR 22 (6): 65–71, 225, MR 638007 . 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, MR 642395 .
^ 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, MR 625097 .
^ Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.