Matrice bistochastique
En mathématiques, une matrice bistochastique ou doublement stochastique est une matrice carrée à coefficients réels positifs dont les sommes des éléments de chaque ligne et chaque colonne sont égales à Modèle:Math.
Ces matrices sont utilisées en théorie des probabilités et en combinatoire.
Définition
Formellement, pour une matrice carrée réelle à coefficients positifs est bistochastique si et seulement si l'égalité suivante est vérifiée :
Les matrices bistochastiques sont aussi les matrices stochastiques dont la transposée est stochastique[1].
Propriétés
Polytope de Birkhoff et théorème de Birkhoff-von Neumann
L'ensemble des matrices bistochastiques de taille d est un polytope convexe dans l'ensemble des matrices carrées de taille d à coefficients réels, appelé polytope de Birkhoff. Les matrices de permutations sont clairement des points extrémaux de ce convexe. Le théorème de Birkhoff-von Neumann[2] établit que ce sont les seuls, ou encore (cf. théorème de Krein-Milman) que ce polytope est l'enveloppe convexe de l'ensemble des matrices de permutation.
Il en résulte que pour tout vecteur y de ℝModèle:Exp, l'ensemble des images de y par les matrices bistochastiques est égal à l'enveloppe convexe de l'ensemble des vecteurs obtenus en permutant les coordonnées de y. Inversement, on peut déduire le théorème de Birkhoff-von Neumann de cette égalité (qui constitue l'équivalence entre deux caractérisations de la majorisation, et peut se démontrer directement) :
Modèle:Démonstration/début Dans l'espace MModèle:Ind(ℝ) des matrices réelles carrées de taille d, notons B l'ensemble des matrices bistochastiques et E l'enveloppe convexe de l'ensemble des matrices de permutation. Par hypothèse, pour tout vecteur y de ℝModèle:Exp, B(y) = E(y). Par juxtaposition de colonnes, on en déduit que pour toute matrice N dans MModèle:Ind(ℝ), les ensembles de matrices BN et EN sont égaux, donc ont même image par l'application trace. Autrement dit : pour toute forme linéaire Modèle:Math sur MModèle:Ind(ℝ), Modèle:Math(B) = Modèle:Math(E) donc (cf. « Séparation des convexes ») B = E. Modèle:Démonstration/fin
Conjecture de Van der Waerden
En 1926, Van der Waerden conjectura que le permanent d'une matrice bistochastique de dimension n était supérieure à , valeur atteinte par la matrice ne contenant que des 1/n[3]. Des preuves de ce résultat ont été publiées, en 1980 par B. Gyires[4], et en 1981 par G. P. Egorychev[5]Modèle:,[6]Modèle:,[7] et D. I. Falikman[8]. Egorychev et Falikman ont remporté le prix Fulkerson en 1982 pour ces preuves[9].
Applications et utilisations
Les matrices bistochastiques apparaissent notamment dans l'inégalité de Muirhead, une généralisation de l'inégalité arithmético-géométrique[10] et dans les chaînes de Markov ayant une certaine symétrie.
Notes et références
Modèle:Traduction/Référence Modèle:Références
Bibliographie
- ↑ Modèle:Harvsp
- ↑ Les articles initiaux sont : Modèle:Harvsp et Modèle:Harvsp, cités par exemple dans Modèle:Harvsp. Une preuve peut-être trouvée dans Modèle:Harvsp.
- ↑ Modèle:Article.
- ↑ Modèle:Article
- ↑ Modèle:Article.
- ↑ Modèle:Article
- ↑ Modèle:Article.
- ↑ Modèle:Article.
- ↑ Modèle:Lien web
- ↑ Voir par exemple Modèle:Ouvrage.