二重確率行列のソースを表示

[[数学]]の[[確率論]]や[[組合せ数学|組合せ論]]の分野における'''二重確率行列'''（にじゅうかくりつぎょうれつ、{{Lang-en-short|doubly stochastic matrix}}）とは、各行の和および各列の和がそれぞれ 1 となる[[非負行列|非負]]の[[実数|実]][[正方行列]] <math>A=(a_{ij})</math> のことである。すなわち、
:<math>\sum_i a_{ij}=\sum_j a_{ij}=1</math>
が成り立つ行列 <math>A=(a_{ij})</math> のことを二重確率行列と呼ぶ。この定義から、二重確率行列は左[[確率行列|確率的]]であると同時に右確率的である<ref>{{Cite book |author=Marshal, Olkin |title=Inequalities: Theory of Majorization and Its Applications |year=1979 |isbn=0-12-473750-1 |page=8}}</ref>。

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

== バーコフ多面体とバーコフ＝フォン・ノイマンの定理 ==
{{math2|''n'' × ''n''}} 二重確率行列の類は、{{仮リンク|バーコフ多面体|en|Birkhoff polytope}}として知られる[[凸多面体]] {{mvar|B{{sub|n}}}} である。この行列成分を[[デカルト座標系]]として用いることで、それは {{math2|''n''{{sup|2}}}}次元[[ユークリッド空間]]のある {{math2|(''n'' &minus; 1){{sup|2}}}}次元[[アフィン空間|アフィン部分空間]]に含まれる。その空間は、行の和および列の和がそれぞれ 1 であるという特別な {{math|2''n'' &minus; 1}} 個の線型独立な制限によって定義される（そのような制限の数は {{math|2''n'' &minus; 1}} であって {{math|2''n''}} ではない。なぜならば、行の和と列の和が等しくなる必要があるので、{{math|2''n''}} 個の条件の内の一つは線型依存であるからである）。さらに、行列の成分はすべて非負で 1 以下であるように制限されている。

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

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

{{math2|1=''n'' = 2}} に対し、すべての二重確率行列は{{仮リンク|ユニタリ型確率行列|en|unistochastic matrix}}かつ{{仮リンク|直交型確率行列|en|orthostochastic matrix}}である。しかしより大きい {{mvar|n}} に対してこのことは成立しない。

[[:en:Bartel Leendert van der Waerden|Van der Waerden]] は、すべての {{math2|''n'' × ''n''}} 二重確率行列の中での最小の{{仮リンク|永久式|en|permanent}}は <math>\frac{n!}{n^n}</math> であり、そのような最小はすべての成分が {{math|{{sfrac|1|''n''}}}} である二重確率行列によって達成されると予想した<ref>{{Citation |last=van der Waerden |first=B. L. |authorlink = :en:Bartel Leendert van der Waerden |journal=Jber. Deutsch. Math.-Verein. |page=117 |title=Aufgabe 45 |volume=35 |year=1926}}.</ref>。この予想の証明は、1980年の B. Gyires<ref>{{Citation |last=Gyires |first=B. |issue=3-4 |journal=Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis |mr=604006 |pages=291-304 |title=The common source of several inequalities concerning doubly stochastic matrices |volume=27 |year=1980}}.</ref>、1981年の G. P. Egorychev<ref>{{Citation |last=Egoryčev |first=G. P. |language=Russian |location=Krasnoyarsk |mr=602332 |page=12 |publisher=Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz. |title=Reshenie problemy van-der-Vardena dlya permanentov |year=1980}}. {{Citation |last=Egorychev |first=G. P. |issue=6 |journal=Akademiya Nauk SSSR |language=Russian |mr=638007 |pages=65-71, 225 |title=Proof of the van der Waerden conjecture for permanents |volume=22 |year=1981}}. {{Citation |last=Egorychev |first=G. P. |doi=10.1016/0001-8708(81)90044-X |issue=3 |journal=Advances in Mathematics |mr=642395 |pages=299-305 |title=The solution of van der Waerden's problem for permanents |volume=42 |year=1981}}.</ref>および D. I. Falikman によって行われた<ref>{{Citation |last=Falikman |first=D. I. |issue=6 |journal=Akademiya Nauk Soyuza SSR |language=Russian |mr=625097 |pages=931-938, 957 |title=Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix |volume=29 |year=1981}}.</ref>。この業績により、Egorychev と Falikman は1982年に[[ファルカーソン賞]]を受賞した<ref>[http://www.mathopt.org/?nav=fulkerson Fulkerson Prize], Mathematical Optimization Society, retrieved 2012-08-19.</ref>。

== 参考文献 ==
{{Reflist}}
* {{Cite book |last=Brualdi |first=Richard A. |title=Combinatorial matrix classes |series=Encyclopedia of Mathematics and Its Applications |volume=108 |location=Cambridge |publisher=[[ケンブリッジ大学出版局|Cambridge University Press]] |year=2006 |isbn=0-521-86565-4 |zbl=1106.05001}}

== 関連項目 ==
* [[確率行列]]

== 外部リンク ==
* {{高校数学の美しい物語|957|バーコフ--フォン・ノイマンの定理}}

{{DEFAULTSORT:にしゆうかくりつきようれつ}}
[[Category:行列]]
[[Category:線型代数学]]
[[Category:数学に関する記事]]