Двічі стохастична матриця — квадратна матриця з невід'ємними дійсними елементами, в якій усі її рядкові і стовпцеві суми дорівнюють 1, тобто:
- .
Множина всіх двічі стохастичних матриць позначається через .
Теорема Біркгофа: множина усіх двічі стохастичних матриць утворює опуклий багатогранник, вершини якого — матриці перестановки. Інакше кажучи, якщо , то , де — матриці перестановки, а — невід'ємні числа, .
Будь-яка двічі стохастична матриця порядку є опуклою лінійною комбінацією не більше ніж матриць перестановок.
Для і , таких, що
- за всіх і
- ,
існує така двічі стохастична матриця , що .
Перманент двічі стохастичної -матриці не менший, ніж — гіпотеза ван дер Вардена, доведена 1980 Г. П. Єгоричевим і незалежно Д. Фалікманом (роботу подано до публікації 1979 року); за ці результати обох учених відзначено 1982 року премією Фалкерсона.
Див. також
Примітки
- Задачи и теоремы линейной алгебры, 1996, с. 223.
- Задачи и теоремы линейной алгебры, 1996, с. 225.
- Минк, 1982, с. 211.
- Егорычев Г. П. Решение проблемы Ван дер Вардена для перманентов // [ru], препринт ИФСО-13М. — Красноярск, 1980. — 16 січня.
- Фаликман Д. И. Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы // . — 1981. — Т. 29, № 6 (16 січня). — С. 931—938. Архівовано з джерела 23 квітня 2021. Процитовано 23 квітня 2021.
Джерела
- Гантмахер Ф. Р. Теорія матриць. — 2024. — 703 с.(укр.)
- Минк Х. Перманенты. — М. : Мир, 1982. — 211 с.
- Задачи и теоремы линейной алгебры. — М. : Наука, 1996. — 304 с. — .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Dvichi stohastichna matricya kvadratna matricya A a i j displaystyle A a ij z nevid yemnimi dijsnimi elementami v yakij usi yiyi ryadkovi i stovpcevi sumi dorivnyuyut 1 tobto j i a i j 1 i j a i j 1 displaystyle forall j sum i a ij 1 forall i sum j a ij 1 Mnozhina vsih dvichi stohastichnih matric poznachayetsya cherez W n displaystyle Omega n Teorema Birkgofa mnozhina W n displaystyle Omega n usih dvichi stohastichnih matric utvoryuye opuklij bagatogrannik vershini yakogo matrici perestanovki Inakshe kazhuchi yaksho A W n displaystyle A in Omega n to A j 1 s 8 j P j displaystyle A sum j 1 s theta j P j de P 1 P s displaystyle P 1 P s matrici perestanovki a 8 1 8 s displaystyle theta 1 theta s nevid yemni chisla j 1 s 8 j 1 displaystyle sum j 1 s theta j 1 1 Bud yaka dvichi stohastichna matricya S displaystyle S poryadku n displaystyle n ye opukloyu linijnoyu kombinaciyeyu ne bilshe nizh n 2 2 n 2 displaystyle n 2 2n 2 matric perestanovok 2 Dlya x 1 x 2 x n displaystyle x 1 geqslant x 2 geqslant ldots geqslant x n i y 1 y 2 y n displaystyle y 1 geqslant y 2 geqslant ldots geqslant y n takih sho x 1 x k y 1 y k displaystyle x 1 ldots x k leqslant y 1 ldots y k za vsih k lt n displaystyle k lt n i x 1 x n y 1 y n displaystyle x 1 ldots x n y 1 ldots y n isnuye taka dvichi stohastichna matricya S displaystyle S sho S y x displaystyle Sy x 2 Permanent dvichi stohastichnoyi n displaystyle n matrici ne menshij nizh n n n displaystyle n n n gipoteza van der Vardena 3 dovedena 1980 G P Yegorichevim 4 i nezalezhno D Falikmanom 5 robotu podano do publikaciyi 1979 roku za ci rezultati oboh uchenih vidznacheno 1982 roku premiyeyu Falkersona 3 Div takozhred Stohastichna matricya Bagatogrannik BirkgofaPrimitkired Zadachi i teoremy linejnoj algebry 1996 s 223 a b Zadachi i teoremy linejnoj algebry 1996 s 225 a b Mink 1982 s 211 Egorychev G P Reshenie problemy Van der Vardena dlya permanentov Institut fiziki im L V Kirenskogo SO AN SSSR ru preprint IFSO 13M Krasnoyarsk 1980 16 sichnya Falikman D I Dokazatelstvo gipotezy Van der Vardena o permanente dvazhdy stohasticheskoj matricy Matematicheskie zametki 1981 T 29 6 16 sichnya S 931 938 Arhivovano z dzherela 23 kvitnya 2021 Procitovano 23 kvitnya 2021 Dzherelared Gantmaher F R Teoriya matric 2024 703 s ukr Mink H Permanenty M Mir 1982 211 s Prasolov V V Zadachi i teoremy linejnoj algebry M Nauka 1996 304 s ISBN 5 02 014727 3 Otrimano z https uk wikipedia org w index php title Dvichi stohastichna matricya amp oldid 43581851