Dvojnásobně stochastická matice - Doubly stochastic matrix

v matematika, speciálně v pravděpodobnost a kombinatorika, a dvojnásobně stochastická matice (také zvaný bistochastická matice), je čtvercová matice ${ displaystyle A = (a_ {ij})}$ nezáporné reálná čísla, z nichž každý řádek a sloupec činí 1,^[1] tj.,

{ displaystyle sum _ {i} a_ {ij} = součet _ {j} a_ {ij} = 1}

,

Zůstává tedy dvojnásobně stochastická matice stochastický a pravý stochastický.^[1]^[2]

Ve skutečnosti musí být jakákoli matice, která je levá i pravá stochastická náměstí: pokud je každý řádek součtem jednoho, musí se součet všech položek v matici rovnat počtu řádků, a protože totéž platí pro sloupce, musí být počet řádků a sloupců stejný.^[1]

Birkhoffův mnohostěn

Třída ${ displaystyle n krát n}$ dvojnásobně stochastické matice je a konvexní mnohostěn známý jako Birkhoffův mnohostěn ${ displaystyle B_ {n}}$ . Použití záznamů matice jako Kartézské souřadnice, leží v ${ displaystyle (n-1) ^ {2}}$ -rozměrný afinní podprostor ${ displaystyle n ^ {2}}$ -dimenzionální Euklidovský prostor definován ${ displaystyle 2n-1}$ nezávislá lineární omezení určující, že součet řádků a sloupců je stejný. (Existují ${ displaystyle 2n-1}$ omezení spíše než ${ displaystyle 2n}$ protože jedno z těchto omezení je závislé, protože součet součtů řádků se musí rovnat součtu součtů sloupců.) Navíc jsou všechny položky omezeny na nezáporné a menší než nebo rovné jedné.

Birkhoff – von Neumannova věta

The Birkhoff – von Neumannova věta uvádí, že mnohostěn ${ displaystyle B_ {n}}$ je konvexní obal sady ${ displaystyle n krát n}$ permutační matice, a dále, že vrcholy z ${ displaystyle B_ {n}}$ jsou přesně permutační matice. Jinými slovy, pokud ${ displaystyle A}$ je dvojnásobně stochastická matice, pak existují ${ displaystyle theta _ {1}, ldots, theta _ {k} geq 0, sum _ {i = 1} ^ {k} theta _ {i} = 1}$ a permutační matice ${ displaystyle P_ {1}, ldots, P_ {k}}$ takhle

{ displaystyle A = theta _ {1} P_ {1} + cdots + theta _ {k} P_ {k}.}

Tato reprezentace je známá jako Birkhoff – von Neumannův rozklada nemusí to být obecně jedinečné. Podle Carathéodoryova věta, nicméně, tam existuje rozklad s ne více než ${ displaystyle (n-1) ^ {2} + 1 = n ^ {2} -2n + 2}$ podmínky, tj. s^[3]

{ displaystyle k leq n ^ {2} -2n + 2.}

Jinými slovy, zatímco existuje rozklad s ${ displaystyle n!}$ permutační matice, existuje alespoň jeden konstruktivní rozklad s ne více než ${ displaystyle (n-1) ^ {2} +1}$ matice. Takový rozklad lze najít v polynomiálním čase pomocí Birkhoffův algoritmus. Toto je často popisováno jako skutečné zobecnění Kőnigova věta, kde je korespondence zjišťována pomocí matic grafů sousednosti.

Další vlastnosti

Produkt dvou dvojnásobně stochastických matric je dvojnásobně stochastický. Inverze nonsingulární dvojnásobně stochastické matice však nemusí být dvojnásobně stochastická (inverze je dvojnásobně stochastická, pokud má nezáporné hodnoty).
Stacionární distribuce neredukovatelné neperiodické konečné Markovův řetězec je jednotná právě tehdy, když je její přechodová matice dvojnásobně stochastická.
Sinkhornova věta uvádí, že jakákoli matice s přísně pozitivními položkami může být dvojnásobně stochastická před a po rozmnožování diagonální matice.
Pro ${ displaystyle n = 2}$ , všechny bistochastické matice jsou unistochastický a ortohostochastický, ale pro větší ${ displaystyle n}$ toto není ten případ.
Van der Waerden domníval se, že minimum trvalý mezi všemi n × n dvojnásobně stochastické matice je ${ displaystyle n! / n ^ {n}}$ , dosažené maticí, pro kterou jsou všechny položky stejné ${ displaystyle 1 / n}$ .^[4] Důkazy o této domněnce byly publikovány v roce 1980 B. Gyiresem^[5] a v roce 1981 G. P. Egorychev^[6] a D. I. Falikman;^[7] za tuto práci Egorychev a Falikman vyhráli Fulkersonova cena v roce 1982.^[8]

Viz také

Reference

^ ^A ^b ^C Gagniuc, Paul A. (2017). Markovovy řetězce: od teorie k implementaci a experimentování. USA, NJ: John Wiley & Sons. str. 9–11. ISBN 978-1-119-38755-8.
^ Marshal, Olkin (1979). Nerovnosti: Teorie majorizace a její aplikace. str.8. ISBN 978-0-12-473750-1.
^ Marcus, M .; Ree, R. (1959). "Diagonály dvojnásobně stochastických matic". Quarterly Journal of Mathematics. 10 (1): 296–302. doi:10.1093 / qmath / 10.1.296.
^ van der Waerden, B. L. (1926), „Aufgabe 45“, Jber. Deutsch. Math.-Verein., 35: 117.
^ Gyires, B. (1980), „Společný zdroj několika nerovností týkajících se dvojnásobně stochastických matic“, Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, 27 (3–4): 291–304, PAN 0604006.
^ Egoryčev, G. P. (1980), Reshenie problematické van-der-Vardena dlya permanentov (v ruštině), Krasnojarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., Str. 12, PAN 0602332. Egorychev, G. P. (1981), „Důkaz van der Waerdenova domněnky pro stálé“, Akademiya Nauk SSSR (v Rusku), 22 (6): 65–71, 225, PAN 0638007. Egorychev, G. P. (1981), „Řešení van der Waerdenova problému pro stálé zaměstnance“, Pokroky v matematice, 42 (3): 299–305, doi:10.1016 / 0001-8708 (81) 90044-X, PAN 0642395.
^ Falikman, D. I. (1981), „Důkaz van der Waerdenova domněnky o permanentu dvojnásobně stochastické matice“, Akademiya Nauk Soyuza SSR (v Rusku), 29 (6): 931–938, 957, PAN 0625097.
^ Fulkersonova cena, Mathematical Optimization Society, vyvoláno 19. 8. 2012.

Brualdi, Richard A. (2006). Třídy kombinatorické matice. Encyklopedie matematiky a její aplikace. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.

externí odkazy

[:0-1] A ^b ^C Gagniuc, Paul A. (2017). Markovovy řetězce: od teorie k implementaci a experimentování. USA, NJ: John Wiley & Sons. str. 9–11. ISBN 978-1-119-38755-8.

[2] Marshal, Olkin (1979). Nerovnosti: Teorie majorizace a její aplikace. str.8. ISBN 978-0-12-473750-1.

[3] Marcus, M .; Ree, R. (1959). "Diagonály dvojnásobně stochastických matic". Quarterly Journal of Mathematics. 10 (1): 296–302. doi:10.1093 / qmath / 10.1.296.

[4] van der Waerden, B. L. (1926), „Aufgabe 45“, Jber. Deutsch. Math.-Verein., 35: 117.

[5] Gyires, B. (1980), „Společný zdroj několika nerovností týkajících se dvojnásobně stochastických matic“, Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, 27 (3–4): 291–304, PAN 0604006.

[6] Egoryčev, G. P. (1980), Reshenie problematické van-der-Vardena dlya permanentov (v ruštině), Krasnojarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., Str. 12, PAN 0602332. Egorychev, G. P. (1981), „Důkaz van der Waerdenova domněnky pro stálé“, Akademiya Nauk SSSR (v Rusku), 22 (6): 65–71, 225, PAN 0638007. Egorychev, G. P. (1981), „Řešení van der Waerdenova problému pro stálé zaměstnance“, Pokroky v matematice, 42 (3): 299–305, doi:10.1016 / 0001-8708 (81) 90044-X, PAN 0642395.

[7] Falikman, D. I. (1981), „Důkaz van der Waerdenova domněnky o permanentu dvojnásobně stochastické matice“, Akademiya Nauk Soyuza SSR (v Rusku), 29 (6): 931–938, 957, PAN 0625097.

[8] Fulkersonova cena, Mathematical Optimization Society, vyvoláno 19. 8. 2012.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]