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 à 1.

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 ${\displaystyle A=(a_{ij})}$ est bistochastique si et seulement si l'égalité suivante est vérifiée :

${\displaystyle \sum _{i}a_{ij}=\sum _{j}a_{ij}=1.}$

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 ℝ^d, 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) :

Démonstration

Dans l'espace M_d(ℝ) 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 ℝ^d, B(y) = E(y). Par juxtaposition de colonnes, on en déduit que pour toute matrice N dans M_d(ℝ), 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 φ sur M_d(ℝ), φ(B) = φ(E) donc (cf. « Séparation des convexes ») B = E.

Conjecture de Van der Waerden

En 1926, Van der Waerden conjectura que le permanent d'une matrice bistochastique de dimension n était supérieure à ${\displaystyle n!/n^{n}}$, 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],[6],[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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Doubly stochastic matrix » (voir la liste des auteurs).

1. Rombaldi 2012
2. Les articles initiaux sont : Birkhoff 1946 et von Neumann 1953, cités par exemple dans Budish et al. 2010. Une preuve peut-être trouvée dans Rombaldi 2012.
3. (en) B. L. van der Waerden, « Aufgabe 45 », Jber. Deutsch. Math.-Verein., vol. 35,‎ 1926, p. 117.
4. (en) B. Gyires, « The common source of several inequalities concerning doubly stochastic matrices », Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, vol. 27, n^os 3-4,‎ 1980, p. 291–304 (MR 604006)
5. (ru) G. P. Egoryčev, « Reshenie problemy van-der-Vardena dlya permanentov », Akademiya Nauk Soyuza SSR, Krasnoyarsk, Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz.,‎ 1980, p. 12 (MR 602332).
6. (ru) G. P. Egorychev, « Proof of the van der Waerden conjecture for permanents », Akademiya Nauk SSSR, vol. 22, n^o 6,‎ 1981, p. 65–71, 225 (MR 638007)
7. G. P. Egorychev, « The solution of van der Waerden's problem for permanents », Advances in Mathematics, vol. 42, n^o 3,‎ 1981, p. 299–305 (DOI 10.1016/0001-8708(81)90044-X, MR 642395).
8. (ru) D. I. Falikman, « Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix », Akademiya Nauk Soyuza SSR, vol. 29, n^o 6,‎ 1981, p. 931–938, 957 (MR 625097).
9. Mathematical Optimization Society, « Lauréats du prix Fulkerson », 19 aout 2012
10. Voir par exemple (en) Godfrey Harold Hardy, John Edensor Littlewood et George Pólya, Inequalities, Londres, Cambridge University Press, coll. « Cambridge Mathematical Library », 1952, 2^e éd., 324 p. (ISBN 978-0-521-35880-4, lire en ligne).

Bibliographie

• Jean-Etienne Rombaldi, Matrices bistochastiques, 2012 (lire en ligne)
• (en) Garrett Birkhoff, « Three observations on linear algebra », Univ. Nac. Tucumàn. Revista A, vol. 5,‎ 1946, p. 147-151
• (en) John von Neumann, « A certain zero-sum two-person game equivalent to the optimal assignment problem », Contributions to the Theory of Games, vol. 2,‎ 1953, p. 5-12
• (en) Eric Budish, Yeon-Koo Che, Fuhito Kojima et Paul Milgrom, Implementing random assignments : A generalization of the birkhoff-von neumann theorem, 2010 (lire en ligne)