Matrice doppiamente stocastica

Matrice doppiamente stocastica (Reindirizzato da teorema di Birkhoff-Von Neumann) Vai alla navigazione Vai alla ricerca In matematica, soprattutto in probabilità e combinatoria, una matrice doppiamente stocastica (detta anche matrice bistocastica), è una matrice quadrata {stile di visualizzazione X=(X_{ij})} di numeri reali non negativi, ciascuna delle cui righe e colonne viene sommata 1,[1] cioè., {somma dello stile di visualizzazione _{io}X_{ij}=somma _{j}X_{ij}=1,} così, una matrice doppiamente stocastica è sia stocastica sinistra che stocastica destra.[1][2] Infatti, qualsiasi matrice che sia stocastica sia sinistra che destra deve essere quadrata: se ogni riga somma a uno, la somma di tutte le voci nella matrice deve essere uguale al numero di righe, e poiché lo stesso vale per le colonne, il numero di righe e colonne deve essere uguale.[1] Contenuti 1 Politopo Birkhoff 2 Teorema di Birkhoff-von Neumann 3 Altre proprietà 4 Dimostrazione del teorema di Birkhoff-von Neumann 4.1 generalizzazioni 5 Guarda anche 6 Riferimenti 7 Collegamenti esterni Politopo Birkhoff Articolo principale: Birkhoff polytope The class of {tempi di visualizzazione n} matrici doppiamente stocastiche è un politopo convesso noto come politopo di Birkhoff {stile di visualizzazione B_{n}} . Utilizzo delle voci della matrice come coordinate cartesiane, si trova in un {stile di visualizzazione (n-1)^{2}} -sottospazio affine dimensionale di {stile di visualizzazione n^{2}} -spazio euclideo dimensionale definito da {stile di visualizzazione 2n-1} vincoli lineari indipendenti che specificano che la somma di riga e colonna è uguale a uno. (Ci sono {stile di visualizzazione 2n-1} vincoli piuttosto che {stile di visualizzazione 2n} perché uno di questi vincoli è dipendente, poiché la somma delle somme delle righe deve essere uguale alla somma delle somme delle colonne.) Inoltre, le voci sono tutte vincolate ad essere non negative e minori o uguali a uno.

Birkhoff–von Neumann theorem The Birkhoff–von Neumann theorem (spesso noto semplicemente come teorema di Birkhoff[3][4][5]) afferma che il politopo {stile di visualizzazione B_{n}} è lo scafo convesso dell'insieme di {tempi di visualizzazione n} matrici di permutazione, ed inoltre che i vertici di {stile di visualizzazione B_{n}} sono precisamente le matrici di permutazione. In altre parole, Se {stile di visualizzazione X} è una matrice doppiamente stocastica, allora esistono {stile di visualizzazione theta _{1},ldot ,theta _{K}geq 0,somma _{io=1}^{K}theta _{io}=1} e matrici di permutazione {stile di visualizzazione P_{1},ldot ,P_{K}} tale che {stile di visualizzazione X=teta _{1}P_{1}+cdot + theta _{K}P_{K}.} (Tale scomposizione di X è nota come "combinazione convessa".) Di seguito viene fornita una dimostrazione del teorema basato sul teorema del matrimonio di Hall.

Questa rappresentazione è nota come decomposizione Birkhoff–von Neumann, e potrebbe non essere unico. Viene spesso descritta come una generalizzazione a valore reale del teorema di Kőnig, dove la corrispondenza è stabilita attraverso matrici di adiacenza di grafici.

Altre proprietà Il prodotto di due matrici doppiamente stocastiche è doppiamente stocastico. Tuttavia, l'inverso di una matrice doppiamente stocastica non singolare non deve necessariamente essere doppiamente stocastica (infatti, l'inverso è doppiamente stocastico se ha voci non negative). La distribuzione stazionaria di una catena di Markov finita aperiodica irriducibile è uniforme se e solo se la sua matrice di transizione è doppiamente stocastica. Il teorema di Sinkhorn afferma che qualsiasi matrice con voci rigorosamente positive può essere resa doppiamente stocastica da pre- e post-moltiplicazione per matrici diagonali. Per {stile di visualizzazione n=2} , tutte le matrici bistocastiche sono unistocastiche e ortostocastiche, ma per più grandi {stile di visualizzazione n} Questo non è il caso. La congettura di Van der Waerden che il minimo permanente tra tutte le n × n matrici doppiamente stocastiche sia {stile di visualizzazione n!/n^{n}} , ottenuto dalla matrice per la quale tutte le voci sono uguali {stile di visualizzazione 1/n} .[6] Le prove di questa congettura sono state pubblicate in 1980 di B. Giri[7] e dentro 1981 di G. P. Egorychev[8] e d. io. Falikman;[9] per questo lavoro, Egorychev e Falikman hanno vinto il Premio Fulkerson a 1982.[10] Proof of the Birkhoff–von Neumann theorem Let X be a doubly stochastic matrix. Then we will show that there exists a permutation matrix P such that xij ≠ 0 whenever pij ≠ 0. Quindi se λ sia il più piccolo xij corrispondente a un pij diverso da zero, the difference X – λP will be a scalar multiple of a doubly stochastic matrix and will have at least one more zero cell than X. Di conseguenza possiamo ridurre successivamente il numero di celle diverse da zero in X rimuovendo multipli scalari di matrici di permutazione fino ad arrivare alla matrice zero, a quel punto avremo costruito una combinazione convessa di matrici di permutazione uguali alla X originale.[3] Per esempio se {stile di visualizzazione X={frac {1}{12}}{inizio{pmatrice}7&0&5\2&6&4\3&6&3end{pmatrice}}} poi {stile di visualizzazione P={inizio{pmatrice}0&0&1\1&0&0\0&1&0end{pmatrice}}} , {displaystyle lambda ={frac {2}{12}}} , e {displaystyle X-lambda P={frac {1}{12}}{inizio{pmatrice}7&0&3\0&6&4\3&4&3end{pmatrice}}} .

Prova: Costruisci un grafo bipartito in cui le righe di X sono elencate in una parte e le colonne nell'altra, and in which row i is connected to column j iff xij ≠ 0. Sia A un qualsiasi insieme di righe, e definire A' come l'insieme di colonne unite alle righe in A nel grafico. Vogliamo esprimere le dimensioni |UN| e |UN'| dei due insiemi in termini di xij.

Per ogni i in A, la somma su j in A' di xij è 1, since all columns j for which xij ≠ 0 are included in A', e X è doppiamente stocastico; quindi |UN| is the sum over all i ∈ A, j ∈ A' of xij.

Nel frattempo |UN'| è la somma di tutto i (indipendentemente dal fatto che in A) and all j in A' of xij ; e questa è ≥ la somma corrispondente in cui le i sono limitate alle righe di A. Quindi |UN'| ≥ |UN|.

Ne consegue che le condizioni del teorema del matrimonio di Hall sono soddisfatte, e che possiamo quindi trovare un insieme di archi nel grafico che uniscono ogni riga in X esattamente a uno (distinto) colonna. Questi bordi definiscono una matrice di permutazione le cui celle diverse da zero corrispondono a celle diverse da zero in X. ∎ Generalisations There is a simple generalisation to matrices with more columns and rows such that the i th row sum is equal to ri (un numero intero positivo), le somme delle colonne sono uguali a 1, e tutte le celle non sono negative (la somma delle somme di riga è uguale al numero di colonne). Qualsiasi matrice in questa forma può essere espressa come una combinazione convessa di matrici nella stessa forma composta da 0 e 1. The proof is to replace the i th row of the original matrix by ri separate rows, each equal to the original row divided by ri ; applicare il teorema di Birkhoff alla matrice quadrata risultante; and at the end to additively recombine the ri rows into a single i th row.

Allo stesso modo è possibile replicare sia le colonne che le righe, ma il risultato della ricombinazione non è necessariamente limitato a 0 e 1. Una generalizzazione diversa (con una prova significativamente più difficile) has been put forward by R. M. Carron et al.[4] Vedi anche Matrice stocastica Matrice unistocastica Riferimenti ^ Vai a: a b c Gagniuc, Paolo A. (2017). Markov Catene: Dalla teoria all'attuazione e alla sperimentazione. Stati Uniti d'America, NJ: John Wiley & Sons. pp. 9–11. ISBN 978-1-119-38755-8. ^ Maresciallo, Olkin (1979). Disuguaglianze: Teoria della maggioranza e sue applicazioni. pp. 8. ISBN 978-0-12-473750-1. ^ Salta su: a b Teorema di Birkhoff, note di Gabor Hetyei. ^ Salta su: a b R. M. Carron et al., 'Nonsquare "Doppiamente Stocastico" matrici', 1996. ^ W. B. Jurkat e H. J. Brivido, "Gradi a termine e permanenti di matrici non negative" (1967). ^ van der Waerden, B. l. (1926), "compito 45", Jbr. Tedesco. Club di matematica., 35: 117. ^ Giri, B. (1980), "La fonte comune di numerose disuguaglianze riguardanti matrici doppiamente stocastiche", Pubblicazioni matematiche Istituto di matematica dell'Università di Debrecen, 27 (3–4): 291–304, SIG 0604006. ^ Egorychev, G. P. (1980), Soluzione problematica van-der-Vardena dlya permanentov (in russo), Krasnojarsk: Ritardo. Nauk SSSR siberiano. Dipartimento. Inst. L'ho fatto., p. 12, SIG 0602332. Egorychev, G. P. (1981), "Dimostrazione della congettura di van der Waerden per i permanenti", Akademiya Nauk SSSR (in russo), 22 (6): 65–71, 225, SIG 0638007. Egorychev, G. P. (1981), "La soluzione del problema di van der Waerden per i permanenti", Progressi in matematica, 42 (3): 299–305, doi:10.1016/0001-8708(81)90044-X, SIG 0642395. ^ Falikman, D. io. (1981), "Dimostrazione della congettura di van der Waerden sul permanente di una matrice doppiamente stocastica", Akademiya Nauk Soyuza SSR (in russo), 29 (6): 931–938, 957, SIG 0625097. ^ Premio Fulkerson, Società di ottimizzazione matematica, recuperato 2012-08-19. Brualdi, Riccardo A. (2006). Classi di matrici combinatorie. Enciclopedia della matematica e sue applicazioni. 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 Conditions on eigenvalues or eigenvectors CompanionConvergentDefectiveDefiniteDiagonalizableHurwitzPositive-definiteStieltjes Satisfying conditions on products or inverses CongruentIdempotent or ProjectionInvertibleInvolutoryNilpotentNormalOrthogonalUnimodularUnipotentUnitaryTotally unimodularWeighing With specific applications AdjugateAlternating signAugmentedBézoutCarlemanCartanCirculantCofactorCommutationConfusionCoxeterDistanceDuplication and eliminationEuclidean distanceFundamental (equazione differenziale lineare)GeneratorGramHessianHouseholderJacobianMomentPayoffPickRandomRotationSeifertShearSimilaritySymplecticTotally positiveTransformation Used in statistics CenteringCorrelationCovarianceDesignDoubly stochasticFisher informationHatPrecisionStochasticTransition Used in graph theory AdjacencyBiadjacencyDegreeEdmondsIncidenceLaplacianSeidel adjacencyTutte Used in science and engineering Cabibbo–Kobayashi–MaskawaDensityFundamental (visione computerizzata)Associativo FuzzyGammaGell-MannHamiltonianoIrregolareSovrapStransizione di statoSostituzioneZ (chimica) Related terms Jordan normal formLinear independenceMatrix exponentialMatrix representation of conic sectionsPerfect matrixPseudoinverseRow echelon formWronskian Mathematics portalList of matricesCategory:Categorie di matrici: Matrici