Matrice dublu stocastică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 29 iulie 2020; verificarea necesită 1 editare .

O matrice dublu stocastică este o matrice pătrată cu elemente reale nenegative în care toate sumele de rând și coloane sunt egale cu 1, adică: $A=(a_{{ij}})$

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

Mulțimea tuturor matricelor dublu stocastice se notează cu . $\Omega _{n)$

Teorema lui Birkhoff: mulțimea tuturor matricelor dublu stocastice formează un poliedru convex ale cărui vârfuri sunt matrici de permutare . Cu alte cuvinte, dacă , atunci , unde sunt matrice de permutare și sunt numere nenegative, [1] . $\Omega _{n)$ $A\in \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$

Orice matrice de ordin dublu stocastic este o combinație liniară convexă de cel mult matrice de permutare [2] . $S$ $n$ $n^{2}-2n+2$

Pentru și , astfel încât $x_{1}\geqslant x_{2}\geqslant \ldots \geqslant x_{n)$ $y_{1}\geqslant y_{2}\geqslant \ldots \geqslant y_{n)$

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

pentru toti si

k<n

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

există o matrice dublu stocastică astfel încât [2] . $S$ $Sy=x$

Permanentul unei matrici dublu stocastice nu mai puțin decât este conjectura van der Waerden [3] dovedită în 1980 de G.P.Egorychev [4] și independent de D. Falikman [5] (depusă spre publicare în 1979); pentru aceste rezultate, ambii oameni de știință au primit premiul Fulkerson în 1982 . [3] $n$ $n!/n^{n}$

Note

↑ Probleme și teoreme ale algebrei liniare, 1996 , p. 223.
↑ 1 2 Probleme și teoreme ale algebrei liniare, 1996 , p. 225.
↑ 1 2 Mink, 1982 , p. 211.
↑ Egorychev G.P. Rezolvarea problemei Van der Waerden pentru permanenți // Institutul de Fizică. L. V. Kirensky SO AS URSS , preprint IFSO-13M. — Krasnoyarsk, 1980.
↑ Falikman D. I. Dovada conjecturii lui Van der Waerden despre permanenta unei matrice dublu stocastice // Note matematice . - 1981. - T. 29 , nr 6 . - S. 931-938 .

Literatură

Mink H. Permanente. — M .: Mir, 1982. — 211 p.
Prasolov VV Probleme și teoreme ale algebrei liniare. — M .: Nauka, 1996. — 304 p. - ISBN 5-02-014727-3 .