Doublement stochastique (matrice)

Imaginez trois destinations et trois parts de ressource. Une matrice indique quelle fraction de chaque ressource va vers chaque destination. Elle est doublement stochastique lorsque chaque ressource distribue exactement tout son contenu et que chaque destination reçoit exactement une unité au total. Ses nombres sont donc compris entre 0 et 1, et chaque ligne comme chaque colonne totalise 1. La matrice décrit un mélange parfaitement équilibré de plusieurs façons de faire correspondre les lignes aux colonnes. Elle peut ainsi représenter des probabilités, un partage ou un transport sans perte ni surplus.

Une matrice doublement stochastique est une matrice carrée réelle A = (a_ij) de taille n, dont chaque coefficient est positif ou nul. Le coefficient a_ij désigne la contribution de la ligne i à la colonne j. Pour chaque ligne i et chaque colonne j, les sommes vérifient les conditions suivantes.

La première égalité impose une somme de ligne égale à 1, et la seconde impose une somme de colonne égale à 1. Le terme « bistochastique » est un synonyme courant. Le théorème de Birkhoff-von Neumann relie ces matrices aux matrices de permutation : toute matrice doublement stochastique de taille finie est une combinaison convexe de telles matrices. Les coefficients de cette combinaison sont positifs ou nuls et leur somme vaut 1. Cette structure explique leur présence en probabilités, en optimisation combinatoire, en transport optimal et dans l'étude de chaînes de Markov réversibles.

Une matrice doublement stochastique comporte cinq éléments liés. Sa forme carrée possède autant de lignes que de colonnes. La ligne i rassemble les destinations possibles depuis la source i, tandis que la colonne j rassemble les contributions reçues par la destination j. Le coefficient a_ij est positif ou nul et mesure la part envoyée de i vers j. La condition sur les lignes garantit que chaque source distribue une unité au total. La condition sur les colonnes garantit que chaque destination reçoit une unité au total. Ces deux conditions dépendent l'une de l'autre pour l'équilibre global, mais aucune ne remplace l'autre. Les coefficients et leur organisation suffisent à vérifier la propriété, à calculer les sommes et à interpréter la matrice comme un mélange de correspondances déterministes.

Dans une matrice de permutation, chaque ligne et chaque colonne contient exactement un 1, les autres coefficients étant nuls. Une matrice doublement stochastique peut combiner plusieurs de ces organisations, avec des poids qui totalisent 1.

Considérons la matrice A qui répartit trois unités entre trois destinations. Les données sont les suivantes : ligne 1 = (1/2, 1/3, 1/6), ligne 2 = (1/6, 1/2, 1/3) et ligne 3 = (1/3, 1/6, 1/2).

On additionne d'abord la première ligne : 1/2 + 1/3 + 1/6 = 1.
On additionne ensuite la deuxième ligne : 1/6 + 1/2 + 1/3 = 1.
La troisième ligne donne également 1 : 1/3 + 1/6 + 1/2 = 1.
Les colonnes donnent respectivement 1/2 + 1/6 + 1/3 = 1, 1/3 + 1/2 + 1/6 = 1 et 1/6 + 1/3 + 1/2 = 1.
Tous les coefficients sont positifs ou nuls : A est donc doublement stochastique.

Le contrôle par décomposition donne le même résultat. Si P₀, P₁ et P₂ sont les trois permutations cycliques de taille 3, alors A = 1/2 P₀ + 1/3 P₁ + 1/6 P₂. Les poids sont positifs et 1/2 + 1/3 + 1/6 = 1.

En probabilités, chaque ligne peut répartir une probabilité totale de 1 entre plusieurs états, tandis que les colonnes imposent la même normalisation du côté des états reçus. On vérifie alors séparément les deux familles de sommes.

En optimisation combinatoire, la décomposition en matrices de permutation transforme un partage fractionnaire en mélange de correspondances complètes. Une matrice de permutation convient lorsque l'affectation doit être unique ; la matrice doublement stochastique convient lorsque plusieurs affectations sont pondérées.

En transport optimal, les coefficients représentent des quantités réparties entre sources et destinations normalisées. Si les masses de départ ou d'arrivée ne valent pas toutes 1, on utilise plutôt une matrice de transport dont les marges correspondent aux masses données.

Pour étudier une chaîne de Markov réversible, on ne conclut pas à la réversibilité à partir des seules sommes. Il faut aussi vérifier la relation d'équilibre détaillée avec la distribution stationnaire choisie.

Une matrice stochastique par lignes n'exige que des coefficients positifs ou nuls et une somme de ligne égale à 1. Elle peut avoir des colonnes dont les sommes diffèrent de 1. La matrice A de l'exemple ne crée pas cette distinction, car elle vérifie aussi la condition sur les colonnes.

Une matrice de permutation n'est pas une matrice doublement stochastique quelconque : elle ne contient que des 0 et des 1, avec un seul 1 par ligne et par colonne. Toute matrice de permutation est doublement stochastique, mais l'inverse est faux dès qu'un coefficient est strictement compris entre 0 et 1, comme 1/2 dans A.

Une matrice de transport peut avoir des marges de lignes et de colonnes différentes de 1. Elle devient doublement stochastique seulement dans le cas carré où toutes ces marges valent 1 et où les coefficients restent positifs ou nuls.

Le mot « positive » est parfois employé au sens strict, mais la définition donnée ici autorise les zéros. Une matrice contenant un coefficient nul peut donc être doublement stochastique ; les seules exigences sont a_ij ≥ 0 et les sommes égales à 1.

La condition double porte sur deux directions. Une ligne qui totalise 1 ne suffit pas : la matrice stochastique par lignes [[1, 0], [1, 0]] respecte cette condition, mais ses colonnes totalisent 2 et 0. Elle n'est donc pas doublement stochastique.

La propriété concerne une matrice carrée. Une matrice rectangulaire ne peut pas avoir simultanément toutes ses sommes de lignes et de colonnes égales à 1 : la somme totale serait à la fois le nombre de lignes et le nombre de colonnes. Il faut alors parler de matrice de transport ou préciser les marges considérées.

Enfin, la décomposition de Birkhoff-von Neumann est une existence de combinaison convexe, pas une décomposition unique en général. Le nombre et les poids des matrices de permutation retenues peuvent varier selon la décomposition choisie.

Le théorème de Birkhoff-von Neumann ouvre vers une lecture géométrique : les matrices doublement stochastiques forment l'enveloppe convexe des matrices de permutation. Cette perspective permet de passer d'un partage fractionnaire à des affectations déterministes pondérées, puis d'étudier les liens avec l'optimisation combinatoire et le transport optimal.