Dobbelt Stokastisk Matrix

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. juli 2020; verifikation kræver 1 redigering .

En dobbelt stokastisk matrix er en kvadratisk matrix med ikke-negative reelle elementer, hvor alle dens række- og kolonnesummer er lig med 1, det vil sige: $A=(a_{{ij}})$

\forall j\sum _{i}a_{ij}=1,\;\forall i\sum _{j}a_{ij}=1

Sættet af alle dobbelt stokastiske matricer er angivet med . ${\displaystyle \Omega _{n))$

Birkhoffs sætning: mængden af alle dobbelt stokastiske matricer danner et konveks polyeder, hvis toppunkter er permutationsmatricer . Med andre ord, hvis , så , hvor er permutationsmatricer og er ikke-negative tal, [1] . ${\displaystyle \Omega _{n))$ ${\displaystyle A\in \Omega _{n))$ ${\displaystyle A=\sum _{j=1}^{s}\theta _{j}P_{j))$ $P_{1},...,P_{s}$ ${\displaystyle \theta _{1},...,\theta _{s))$ $\sum _{j=1}^{s}\theta _{j}=1$

Enhver dobbelt stokastisk ordensmatrix er en konveks lineær kombination af højst permutationsmatricer [2] . $S$ $n$ $n^{2}-2n+2$

For og , sådan at ${\displaystyle x_{1}\geqslant x_{2}\geqslant \ldots \geqslant x_{n))$ ${\displaystyle y_{1}\geqslant y_{2}\geqslant \ldots \geqslant y_{n))$

{\displaystyle x_{1}+\ldots +x_{k}\leqslant y_{1}+\ldots +y_{k))

for alle og

k<n

{\displaystyle x_{1}+\ldots +x_{n}=y_{1}+\ldots +y_{n))

der eksisterer en dobbelt stokastisk matrix, således at [2] . $S$ $Sy=x$

Permanenten af en dobbelt stokastisk matrix er ikke mindre end van der Waerden-formodningen [3] bevist i 1980 af G.P. Egorychev [4] og uafhængigt af D. Falikman [5] (indsendt til offentliggørelse i 1979); for disse resultater blev begge videnskabsmænd tildelt Fulkerson-prisen i 1982 . [3] $n$ $n!/n^{n}$

Noter

↑ Problemer og sætninger af lineær algebra, 1996 , s. 223.
↑ 1 2 Problemer og sætninger af lineær algebra, 1996 , s. 225.
↑ 1 2 Mink, 1982 , s. 211.
↑ Egorychev G.P. Løsning af Van der Waerden-problemet for permanente // Institut for Fysik. L. V. Kirensky SO AS USSR , fortryk IFSO-13M. - Krasnoyarsk, 1980.
↑ Falikman D. I. Bevis for Van der Waerdens formodning om permanentheden af en dobbelt stokastisk matrix // Matematiske noter . - 1981. - T. 29 , nr. 6 . - S. 931-938 .

Litteratur

Mink H. Permanenter. — M .: Mir, 1982. — 211 s.
Prasolov VV Problemer og sætninger af lineær algebra. — M .: Nauka, 1996. — 304 s. - ISBN 5-02-014727-3 .