Двічі стохастична матриця

Двічі стохастична матриця — квадратна матриця $A=(a_{ij})$ з невід'ємними дійсними елементами, в якій усі її рядкові і стовпцеві суми дорівнюють 1, тобто:

$\mathrm{\forall }j\sum _i{a}_{ij}=1,\mathrm{\forall }i\sum _j{a}_{ij}=1$.

Множина всіх двічі стохастичних матриць позначається через ${\mathrm{\Omega }}_n$.

Теорема Біркгофа: множина ${\mathrm{\Omega }}_n$ усіх двічі стохастичних матриць утворює опуклий багатогранник, вершини якого — матриці перестановки. Інакше кажучи, якщо $A\in {\mathrm{\Omega }}_n$, то $A=\sum _{j=1}^s{\theta }_j{P}_j$, де $P_1,...,P_s$ — матриці перестановки, а ${\theta }_1,...,{\theta }_s$ — невід'ємні числа, $\sum _{j=1}^s{\theta }_j=1$Шаблон:Sfn.

Будь-яка двічі стохастична матриця $S$ порядку $n$ є опуклою лінійною комбінацією не більше ніж $n^2-2n+2$ матриць перестановокШаблон:Sfn.

Для $x_1⩾x_2⩾\dots ⩾x_n$ і $y_1⩾y_2⩾\dots ⩾y_n$, таких, що

$x_1+\dots +x_k⩽y_1+\dots +y_k$ за всіх $k<n$ і

$x_1+\dots +x_n=y_1+\dots +y_n$,

існує така двічі стохастична матриця $S$, що $Sy=x$Шаблон:Sfn.

Перманент двічі стохастичної $n$-матриці не менший, ніж $n!/n^n$ — гіпотеза ван дер Вардена,Шаблон:Sfn доведена 1980 Г. П. Єгоричевим і незалежно Д. Фалікманом (роботу подано до публікації 1979 року); за ці результати обох учених відзначено 1982 року премією Фалкерсона.Шаблон:Sfn

Див. також

• Стохастична матриця
• Багатогранник Біркгофа

Джерела

• Шаблон:Гантмахер.Теорія матриць
• Шаблон:Книга
• Шаблон:Книга