Doppelt stochastische Matrix

Doppelt stochastische Matrix (Umgeleitet vom Birkhoff-Von-Neumann-Theorem) Zur Navigation springen Zur Suche springen In der Mathematik, insbesondere in Wahrscheinlichkeitsrechnung und Kombinatorik, eine doppelt stochastische Matrix (auch bistochastische Matrix genannt), ist eine quadratische Matrix {Anzeigestil X=(x_{ij})} von nichtnegativen reellen Zahlen, jede der Zeilen und Spalten summiert sich zu 1,[1] d.h., {Anzeigestil Summe _{ich}x_{ij}= Summe _{j}x_{ij}=1,} Daher, Eine doppelt stochastische Matrix ist sowohl linksstochastisch als auch rechtsstochastisch.[1][2] In der Tat, Jede Matrix, die sowohl links- als auch rechtsstochastisch ist, muss quadratisch sein: Wenn sich jede Zeile zu eins summiert, muss die Summe aller Einträge in der Matrix gleich der Anzahl der Zeilen sein, und da dasselbe für Spalten gilt, Die Anzahl der Zeilen und Spalten muss gleich sein.[1] Inhalt 1 Birkhoff-Polytop 2 Birkhoff–von Neumann theorem 3 Andere Eigenschaften 4 Beweis des Satzes von Birkhoff–von Neumann 4.1 Verallgemeinerungen 5 Siehe auch 6 Verweise 7 Externe Links Birkhoff Polytop Hauptartikel: Birkhoff-Polytop Die Klasse der {displaystyle nmal n} Doppelt stochastische Matrizen ist ein konvexes Polytop, das als Birkhoff-Polytop bekannt ist {Anzeigestil B_{n}} . Verwendung der Matrixeinträge als kartesische Koordinaten, es liegt in einem {Anzeigestil (n-1)^{2}} -Dimensionsaffiner Unterraum von {Anzeigestil n^{2}} -dimensionaler euklidischer Raum definiert durch {Anzeigestil 2n-1} unabhängige lineare Einschränkungen, die angeben, dass die Zeilen- und Spaltensummen alle gleich eins sind. (Es gibt {Anzeigestil 2n-1} Einschränkungen statt {Anzeigestil 2n} weil eine dieser Einschränkungen abhängig ist, da die Summe der Zeilensummen gleich der Summe der Spaltensummen sein muss.) Darüber hinaus, die Einträge sind alle darauf beschränkt, nicht negativ und kleiner oder gleich eins zu sein.

Satz von Birkhoff–von Neumann Der Satz von Birkhoff–von Neumann (oft einfach als Birkhoffs Theorem bekannt[3][4][5]) besagt, dass das Polytop {Anzeigestil B_{n}} ist die konvexe Hülle der Menge von {displaystyle nmal n} Permutationsmatrizen, und außerdem, dass die Eckpunkte von {Anzeigestil B_{n}} sind genau die Permutationsmatrizen. Mit anderen Worten, wenn {Anzeigestil X} ist eine doppelt stochastische Matrix, dann gibt es {displaystyle theta _{1},Punkte ,theta _{k}geq 0,summe _{i=1}^{k}theta _{ich}=1} und Permutationsmatrizen {Anzeigestil P_{1},Punkte ,P_{k}} so dass {Anzeigestil X=theta _{1}P_{1}+cdots + theta _{k}P_{k}.} (Eine solche Zerlegung von X ist als „konvexe Kombination“ bekannt.) Ein Beweis des Satzes basierend auf dem Heiratssatz von Hall ist unten angegeben.

Diese Darstellung ist als Birkhoff-von-Neumann-Zerlegung bekannt, und darf nicht eindeutig sein. Es wird oft als reellwertige Verallgemeinerung des Satzes von König beschrieben, wobei die Korrespondenz durch Adjazenzmatrizen von Graphen hergestellt wird.

Andere Eigenschaften Das Produkt zweier doppelt stochastischer Matrizen ist doppelt stochastisch. Jedoch, die Umkehrung einer nichtsingulären doppelt stochastischen Matrix muss nicht doppelt stochastisch sein (in der Tat, die Umkehrung ist doppelt stochastisch genau dann, wenn sie nichtnegative Einträge hat). Die stationäre Verteilung einer irreduziblen aperiodischen endlichen Markov-Kette ist genau dann gleichmäßig, wenn ihre Übergangsmatrix doppelt stochastisch ist. Der Satz von Sinkhorn besagt, dass jede Matrix mit streng positiven Einträgen durch pre doppelt stochastisch gemacht werden kann- und Nachmultiplikation mit diagonalen Matrizen. Zum {Darstellungsstil n=2} , alle bistochastischen Matrizen sind unistochastisch und orthostochastisch, aber für größer {Anzeigestil n} das ist nicht der Fall. Van der Waerdens Vermutung, dass die kleinste Permanente unter allen n × n doppelt stochastischen Matrizen ist {Anzeigestil n!/n^{n}} , erreicht durch die Matrix, für die alle Einträge gleich sind {Anzeigestil 1/n} .[6] Beweise dieser Vermutung wurden veröffentlicht in 1980 von B. Gyire[7] und in 1981 von G. P. Egoritschew[8] und d. ich. Falkmann;[9] für diese Arbeit, Egorychev und Falikman gewannen den Fulkerson-Preis in 1982.[10] Beweis des Satzes von Birkhoff–von Neumann Sei X eine doppelt stochastische Matrix. Dann zeigen wir, dass es eine Permutationsmatrix P gibt, so dass xij ≠ 0 immer wenn pij ≠ 0. Wenn wir also λ das kleinste xij sein lassen, das einem pij ungleich Null entspricht, die Differenz X – λP ist ein skalares Vielfaches einer doppelt stochastischen Matrix und hat mindestens eine Nullzelle mehr als X. Dementsprechend können wir die Anzahl der Nicht-Null-Zellen in X sukzessive verringern, indem wir skalare Vielfache von Permutationsmatrizen entfernen, bis wir bei der Nullmatrix ankommen, An diesem Punkt haben wir eine konvexe Kombination von Permutationsmatrizen konstruiert, die gleich dem ursprünglichen X sind.[3] Zum Beispiel wenn {Anzeigestil X={frac {1}{12}}{Start{pMatrix}7&0&5\2&6&4\3&6&3end{pMatrix}}} dann {Anzeigestil P={Start{pMatrix}0&0&1\1&0&0\0&1&0end{pMatrix}}} , {Anzeigestil Lambda ={frac {2}{12}}} , und {Displaystyle X-Lambda P={frac {1}{12}}{Start{pMatrix}7&0&3\0&6&4\3&4&3end{pMatrix}}} .

Nachweisen: Konstruieren Sie einen zweigeteilten Graphen, in dem die Zeilen von X in einem Teil und die Spalten in dem anderen aufgelistet sind, und in der Zeile i mit Spalte j verbunden ist, wenn xij ≠ 0. Sei A eine beliebige Menge von Zeilen, und definieren Sie A' als den Satz von Spalten, die mit Zeilen in A im Diagramm verbunden sind. Wir wollen die Größen ausdrücken |EIN| und |EIN'| der beiden Mengen in Bezug auf xij.

Für jedes i in A, die Summe über j in A' von xij ist 1, da alle Spalten j für die xij ≠ 0 sind in A' enthalten, und X ist doppelt stochastisch; somit |EIN| ist die Summe über alle i ∈ A, j ∈ A' von xij.

In der Zwischenzeit |EIN'| ist die Summe über alle i (ob in A oder nicht) und alle j in A' von xij ; und dies ist ≥ die entsprechende Summe, in der die i auf Zeilen in A beschränkt sind. Somit |EIN'| ≥ |EIN|.

Daraus folgt, dass die Bedingungen des Heiratssatzes von Hall erfüllt sind, und dass wir daher im Graphen eine Menge von Kanten finden können, die jede Zeile in X zu genau einer verbinden (unterscheidbar) Säule. Diese Kanten definieren eine Permutationsmatrix, deren Nicht-Null-Zellen Nicht-Null-Zellen in X entsprechen. ∎ Verallgemeinerungen Es gibt eine einfache Verallgemeinerung auf Matrizen mit mehr Spalten und Zeilen, so dass die i-te Zeilensumme gleich ri ist (eine positive ganze Zahl), die Spaltensummen sind gleich 1, und alle Zellen sind nicht negativ (wobei die Summe der Zeilensummen gleich der Anzahl der Spalten ist). Jede Matrix in dieser Form kann als konvexe Kombination von Matrizen in der gleichen Form ausgedrückt werden, die aus Nullen und Einsen bestehen. Der Beweis besteht darin, die i-te Zeile der ursprünglichen Matrix durch ri separate Zeilen zu ersetzen, jeweils gleich der ursprünglichen Zeile dividiert durch ri ; den Satz von Birkhoff auf die resultierende quadratische Matrix anzuwenden; und am Ende die ri-Reihen additiv zu einer einzigen i-ten Reihe zu rekombinieren.

Ebenso ist es möglich, sowohl Spalten als auch Zeilen zu replizieren, aber das Ergebnis der Rekombination ist nicht notwendigerweise auf Nullen und Einsen beschränkt. Eine andere Verallgemeinerung (mit einem deutlich schwierigeren Beweis) wurde von R. M. Carronet al.[4] Siehe auch Stochastische Matrix Unistochastische Matrix Referenzen ^ Hochspringen zu: a b c Gagniuc, Paul A. (2017). Markov-Ketten: Von der Theorie zur Umsetzung und zum Experiment. Vereinigte Staaten von Amerika, NJ: John Wiley & Sons. pp. 9–11. ISBN 978-1-119-38755-8. ^ Marschall, Olkin (1979). Ungleichheiten: Theorie der Majorisierung und ihre Anwendungen. pp. 8. ISBN 978-0-12-473750-1. ^ Nach oben springen: a b Satz von Birkhoff, Notizen von Gabor Hetyei. ^ Nach oben springen: ein b R. M. Carronet al., „Nicht quadratisch "Doppelt stochastisch" Matrizen, 1996. ^W. B. Jurkat und H. J. Schauer, "Termränge und Dauerwerte von nichtnegativen Matrizen" (1967). ^ van der Waerden, B. L. (1926), "Aufgabe 45", Jbr. Deutsch. Math.-Verein., 35: 117. ^ Gyire, B. (1980), "Die gemeinsame Quelle mehrerer Ungleichungen in Bezug auf doppelt stochastische Matrizen", Mathematische Veröffentlichungen Mathematisches Institut der Universität Debrecen, 27 (3–4): 291–304, HERR 0604006. ^ Egoritschew, G. P. (1980), Lösung problematisch van-der-Vardena dlya permanentov (auf Russisch), Krasnojarsk: Verzögerungen. Nauk SSSR Sibirisch. Abteilung. Inst. Ich tat., p. 12, HERR 0602332. Egoritschew, G. P. (1981), "Beweis der Van-der-Waerden-Vermutung für Dauerhafte", Akademie Nauk SSSR (auf Russisch), 22 (6): 65–71, 225, HERR 0638007. Egoritschew, G. P. (1981), "Die Lösung von van der Waerdens Problem für bleibende Karten", Fortschritte in der Mathematik, 42 (3): 299–305, doi:10.1016/0001-8708(81)90044-X, HERR 0642395. ^ Falkmann, D. ich. (1981), "Beweis der Van-der-Waerden-Vermutung über die Dauer einer doppelt stochastischen Matrix", Akademie Nauk Sojuza SSR (auf Russisch), 29 (6): 931–938, 957, HERR 0625097. ^ Fulkerson-Preis, Gesellschaft für mathematische Optimierung, abgerufen 2012-08-19. Brualdi, Richard A. (2006). Kombinatorische Matrixklassen. Enzyklopädie der Mathematik und ihrer Anwendungen. Vol. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001. External links PlanetMath page on Birkhoff–von Neumann theorem PlanetMath page on proof of Birkhoff–von Neumann theorem hide vte Matrix classes Explicitly constrained entries AlternantAnti-diagonalAnti-HermitianAnti-symmetricArrowheadBandBidiagonalBisymmetricBlock-diagonalBlockBlock tridiagonalBooleanCauchyCentrosymmetricConferenceComplex HadamardCopositiveDiagonally dominantDiagonalDiscrete Fourier TransformElementaryEquivalentFrobeniusGeneralized permutationHadamardHankelHermitianHessenbergHollowIntegerLogicalMatrix unitMetzlerMooreNonnegativePentadiagonalPermutationPersymmetricPolynomialQuaternionicSignatureSkew-HermitianSkew-symmetricSkylineSparseSylvesterSymmetricToeplitzTriangularTridiagonalVandermondeWalshZ Constant ExchangeHilbertIdentityLehmerOf onesPascalPauliRedhefferShiftZero Bedingungen für Eigenwerte oder Eigenvektoren CompanionConvergentDefectiveDefiniteDiagonalisableHurwitzPositiv-definiteStieltjes Erfüllende Bedingungen für Produkte oder Inverse CongruentIdempotent or Projec tionInvertibleInvolutoryNilpotentNormalOrthogonalUnimodularUnipotentUnitaryTotally unimodularWägen Mit spezifischen Anwendungen AdjugateAlternating signAugmentedBézoutCarlemanCartanCirculantCofactorCommutationConfusionCoxeterDistanceDuplication and EliminationEuclidean distanceFundamental (lineare Differentialgleichung)GeneratorGrammHessischHaushaltJacobianMomentPayoffPickRandomRotationSeifertShearÄhnlichkeitSymplektischTotal positivTransformation Verwendet in der Statistik ZentrierenKorrelationKovarianzDesignDoppelt stochastischFisherinformationHutPräzisionStochastischTransition Verwendet in der Graphentheorie AdjacencyBiaadjacencyDegreeEdmondsIncidenceLaplaceianSeidel adjacencyTutte Verwendet in Wissenschaft und Technik Cabibbo–Kobayashiity–Fundamental (Computer Vision)Fuzzy-AssoziativGammaGell-MannHamiltonianIrregularOverlapSZustandsübergangSubstitutionZ (Chemie) Verwandte Begriffe Jordanische NormalformLineare UnabhängigkeitMatrixexponentielleMatrixdarstellung von KegelschnittenPerfekte MatrixPseudoinverseZeilenstufenformWronskian Mathematics portalListe der MatrizenKategorie:Matrizen-Kategorien: Matrizen