Matrice doublement stochastique

Matrice doublement stochastique (Redirigé à partir du théorème de Birkhoff – Von Neumann) Aller à la navigation Aller à la recherche En mathématiques, notamment en probabilité et combinatoire, une matrice doublement stochastique (aussi appelée matrice bistochastique), est une matrice carrée {style d'affichage X=(X_{ij})} de nombres réels non négatifs, dont chacune des lignes et des colonnes totalise 1,[1] c'est à dire., {somme de style d'affichage _{je}X_{ij}=somme _{j}X_{ij}=1,} Ainsi, une matrice doublement stochastique est à la fois stochastique à gauche et stochastique à droite.[1][2] En effet, toute matrice qui est à la fois stochastique à gauche et à droite doit être carrée: si chaque ligne totalise un, alors la somme de toutes les entrées de la matrice doit être égale au nombre de lignes, et puisque la même chose vaut pour les colonnes, le nombre de lignes et de colonnes doit être égal.[1] Contenu 1 Polytope de Birkhoff 2 Théorème de Birkhoff-von Neumann 3 Autres propriétés 4 Preuve du théorème de Birkhoff-von Neumann 4.1 Généralisations 5 Voir également 6 Références 7 Liens externes Birkhoff polytope Article principal: Birkhoff polytope The class of {displaystyle ntimes n} matrices doublement stochastiques est un polytope convexe connu sous le nom de polytope de Birkhoff {style d'affichage B_{n}} . Utilisation des entrées de la matrice comme coordonnées cartésiennes, il réside dans un {style d'affichage (n-1)^{2}} -sous-espace affine dimensionnel de {displaystyle n^{2}} -espace euclidien dimensionnel défini par {style d'affichage 2n-1} contraintes linéaires indépendantes spécifiant que la somme des lignes et des colonnes est égale à un. (Il y a {style d'affichage 2n-1} contraintes plutôt que {style d'affichage 2n} car l'une de ces contraintes dépend, car la somme des sommes des lignes doit être égale à la somme des sommes des colonnes.) En outre, les entrées sont toutes contraintes d'être non négatives et inférieures ou égales à un.

Birkhoff–von Neumann theorem The Birkhoff–von Neumann theorem (souvent connu simplement sous le nom de théorème de Birkhoff[3][4][5]) indique que le polytope {style d'affichage B_{n}} est l'enveloppe convexe de l'ensemble des {displaystyle ntimes n} matrices de permutation, et de plus que les sommets de {style d'affichage B_{n}} sont précisément les matrices de permutation. Autrement dit, si {style d'affichage X} est une matrice doublement stochastique, alors il existe {style d'affichage thêta _{1},ldots ,thêta _{k}geq 0, somme _{je=1}^{k}thêta _{je}=1} et matrices de permutation {style d'affichage P_{1},ldots ,P_{k}} tel que {style d'affichage X=thêta _{1}P_{1}+cdots + thêta _{k}P_{k}.} (Une telle décomposition de X est connue sous le nom de "combinaison convexe".) Une preuve du théorème basé sur le théorème du mariage de Hall est donnée ci-dessous.

Cette représentation est connue sous le nom de décomposition de Birkhoff-von Neumann, et peut ne pas être unique. Il est souvent décrit comme une généralisation à valeur réelle du théorème de Kőnig, où la correspondance est établie par des matrices d'adjacence de graphes.

Autres propriétés Le produit de deux matrices doublement stochastiques est doublement stochastique. Cependant, l'inverse d'une matrice doublement stochastique non singulière n'a pas besoin d'être doublement stochastique (En effet, l'inverse est doublement stochastique ssi il a des entrées non négatives). La distribution stationnaire d'une chaîne de Markov finie apériodique irréductible est uniforme si et seulement si sa matrice de transition est doublement stochastique. Le théorème de Sinkhorn stipule que toute matrice avec des entrées strictement positives peut être rendue doublement stochastique par pré- et post-multiplication par des matrices diagonales. Pour {displaystyle n=2} , toutes les matrices bistochastiques sont unistochastiques et orthostochastiques, mais pour les plus grands {displaystyle n} ce n'est pas le cas. La conjecture de Van der Waerden selon laquelle le minimum permanent parmi toutes les matrices doublement stochastiques n × n est {displaystyle n!/n^{n}} , atteint par la matrice pour laquelle toutes les entrées sont égales à {displaystyle 1/n} .[6] Les preuves de cette conjecture ont été publiées dans 1980 par B. Gyires[7] et en 1981 par G. P. Egorychev[8] et D. je. Falikman;[9] pour ce travail, Egorychev et Falikman ont remporté le prix Fulkerson en 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. Ainsi si l'on prend λ le plus petit xij correspondant à un pij non nul, 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. En conséquence, nous pouvons successivement réduire le nombre de cellules non nulles dans X en supprimant les multiples scalaires des matrices de permutation jusqu'à ce que nous arrivions à la matrice nulle, à quel point nous aurons construit une combinaison convexe de matrices de permutation égales au X d'origine.[3] Par exemple si {style d'affichage X={frac {1}{12}}{commencer{pmatrice}7&0&5\2&6&4\3&6&3end{pmatrice}}} alors {style d'affichage P={commencer{pmatrice}0&0&1\1&0&0\0&1&0end{pmatrice}}} , {style d'affichage lambda ={frac {2}{12}}} , et {style d'affichage X-lambda P={frac {1}{12}}{commencer{pmatrice}7&0&3\0&6&4\3&4&3end{pmatrice}}} .

Preuve: Construire un graphe biparti dans lequel les lignes de X sont répertoriées dans une partie et les colonnes dans l'autre, and in which row i is connected to column j iff xij ≠ 0. Soit A un ensemble quelconque de lignes, et définir A' comme l'ensemble des colonnes jointes aux lignes de A dans le graphique. Nous voulons exprimer les tailles |UN| et |UN'| des deux ensembles en termes de xij.

Pour tout i dans A, la somme sur j dans A' de xij est 1, since all columns j for which xij ≠ 0 are included in A', et X est doublement stochastique; Par conséquent |UN| is the sum over all i ∈ A, j ∈ A' of xij.

Entre-temps |UN'| est la somme sur tout je (que ce soit en A ou non) and all j in A' of xij ; et c'est ≥ la somme correspondante dans laquelle les i sont limités aux lignes de A. Ainsi |UN'| ≥ |UN|.

Il s'ensuit que les conditions du théorème de mariage de Hall sont satisfaites, et que l'on peut donc trouver un ensemble d'arêtes dans le graphe qui joignent chaque ligne de X à exactement une (distinct) colonne. Ces arêtes définissent une matrice de permutation dont les cellules non nulles correspondent à des cellules non nulles dans 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 entier positif), les sommes des colonnes sont égales à 1, et toutes les cellules sont non négatives (la somme des sommes des lignes étant égale au nombre de colonnes). Toute matrice sous cette forme peut être exprimée comme une combinaison convexe de matrices sous la même forme composée de 0 et de 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 ; appliquer le théorème de Birkhoff à la matrice carrée résultante; and at the end to additively recombine the ri rows into a single i th row.

De la même manière il est possible de répliquer aussi bien des colonnes que des lignes, mais le résultat de la recombinaison n'est pas nécessairement limité aux 0 et aux 1. Une autre généralisation (avec une preuve beaucoup plus difficile) has been put forward by R. M. Caron et al.[4] Voir aussi Matrice stochastique Matrice unistochastique Références ^ Aller à: a b c Gagniuc, Paul A.. (2017). Chaînes de Markov: De la théorie à la mise en œuvre et à l'expérimentation. Etats-Unis, New Jersey: John Wiley & Sons. pp. 9–11. ISBN 978-1-119-38755-8. ^ Maréchal, Olkin (1979). Inégalités: Théorie de la majorisation et ses applications. pp. 8. ISBN 978-0-12-473750-1. ^ Sauter à: a b Théorème de Birkhoff, notes de Gabor Hetyei. ^ Sauter à: un b R. M. Caron et al., 'Non carré "Doublement stochastique" Matrices, 1996. ^ W. B. Jurkat et H. J. Frisson, "Rangs des termes et permanents des matrices non négatives" (1967). ^ van der Waerden, B. L. (1926), "tâche 45", Jbr. Deutsch. Club de maths., 35: 117. ^ Gyires, B. (1980), "La source commune de plusieurs inégalités concernant les matrices doublement stochastiques", Publications mathématiques Institut mathématique de l'Université de Debrecen, 27 (3–4): 291–304, M 0604006. ^ Egorychev, g. P. (1980), Solution problemy van-der-Vardena dlya permanentov (en russe), Krasnoïarsk: Décalages. Nauk SSSR sibérien. département. Inst.. Je l'ai fait., p. 12, M 0602332. Egorychev, g. P. (1981), "Preuve de la conjecture de van der Waerden pour les permanents", Akademiya Nauk SSSR (en russe), 22 (6): 65–71, 225, M 0638007. Egorychev, g. P. (1981), "La solution du problème de van der Waerden pour les permanents", Avancées en mathématiques, 42 (3): 299–305, est ce que je:10.1016/0001-8708(81)90044-X, M 0642395. ^ Falikman, ré. je. (1981), "Preuve de la conjecture de van der Waerden sur le permanent d'une matrice doublement stochastique", Akademiya Nauk Soyuza SSR (en russe), 29 (6): 931–938, 957, M 0625097. ^ Prix Fulkerson, Société d'optimisation mathématique, récupéré 2012-08-19. Brualdi, Richard A.. (2006). Classes matricielles combinatoires. Encyclopédie des mathématiques et de ses applications. Volume. 108. Cambridge: la presse de l'Universite de Cambridge. 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 (équation différentielle linéaire)GeneratorGramHessianHouseholderJacobianMomentPayoffPickRandomRotationSeifertShearSimilaritySymplecticTotally positiveTransformation Used in statistics CenteringCorrelationCovarianceDesignDoubly stochasticFisher informationHatPrecisionStochasticTransition Used in graph theory AdjacencyBiadjacencyDegreeEdmondsIncidenceLaplacianSeidel adjacencyTutte Used in science and engineering Cabibbo–Kobayashi–MaskawaDensityFundamental (vision par ordinateur)Associatif flouGammaGell-MannHamiltonienIrrégulierChevauchementSTransition d'étatSubstitutionZ (chimie) Related terms Jordan normal formLinear independenceMatrix exponentialMatrix representation of conic sectionsPerfect matrixPseudoinverseRow echelon formWronskian Mathematics portalList of matricesCategory:Catégories de matrices: Matrices