Géométrie des matrices bistochastiques

On note $\mathcal{M}_{n}(\mathbb{R})$ l'ensemble des matrices carrées d'ordre $n \geq 2$ . On définit l'ensemble $\mathcal{B}_{n}$ des matrices bistochastiques comme l'ensemble des matrices $A=\left(a_{i, j}\right) \in \mathcal{M}_{n}(\mathbb{R})$ vérifiant les trois conditions suivantes :

$\forall (i, j) \in \{1, \dots, n\}^2, \ a_{i, j} \geq 0$
$\forall i \in \{1, \dots, n\}, \ \sum_{j=1}^{n} a_{i, j} = 1$
$\forall j \in \{1, \dots, n\}, \ \sum_{i=1}^{n} a_{i, j} = 1$

Établir que $\mathcal{B}_{n}$ est un ensemble convexe et qu'il est stable pour le produit matriciel.
Proposer deux exemples distincts de matrices appartenant à $\mathcal{B}_{n}$ (dont un ne contenant que des coefficients strictement positifs).
Identifier l'ensemble des matrices de $\mathcal{B}_{n}$ dont tous les coefficients appartiennent à l'ensemble $\{0, 1\}$ .
On rappelle qu'un élément $M$ d'un convexe $\mathcal{C}$ est dit point extrémal si $M$ ne peut pas s'écrire sous la forme $M = t A + (1-t) B$ avec $A, B \in \mathcal{C} \setminus \{M\}$ et $t \in ]0, 1[$ . Déterminer l'ensemble des points extrémaux de $\mathcal{B}_{n}$ .

1.

Pour la stabilité par produit, introduire le vecteur colonne $U = \begin{pmatrix} 1 & \dots & 1 \end{pmatrix}^T$ et traduire les conditions de somme par les relations $AU=U$ et $A^T U = U$ .

2.

Pour la question 3, observer que chaque ligne ne peut contenir qu'un seul "1".

3.

Pour la question 4, montrer d'abord que les matrices de permutation sont extrémales. Pour la réciproque, si une matrice possède un coefficient dans $]0,1[$ , construire un "cycle" de coefficients non entiers pour définir une perturbation $\pm \varepsilon K$ .

Idées clés

•

Caractérisation vectorielle : $A \in \mathcal{B}_n \iff (A \ge 0 \text{ et } AU=U, \ A^T U = U)$ .

•

Lien avec les matrices de permutation (Théorème de Birkhoff).

•

Méthode de la perturbation pour les points non extrémaux (construction d'une chaîne d'indices).

Résolution.

Convexité : Soient $A, B \in \mathcal{B}_n$ et $\lambda \in [0, 1]$ . Posons $M = \lambda A + (1-\lambda) B$ . Les coefficients de $M$ sont $m_{i,j} = \lambda a_{i,j} + (1-\lambda) b_{i,j}$ . Comme $a_{i,j}, b_{i,j} \ge 0$ et $\lambda, 1-\lambda \ge 0$ , on a $m_{i,j} \ge 0$ . De plus, pour toute ligne $i$ : $\sum_{j=1}^n m_{i,j} = \lambda \sum_{j=1}^n a_{i,j} + (1-\lambda) \sum_{j=1}^n b_{i,j} = \lambda(1) + (1-\lambda)(1) = 1$ Le calcul est identique pour les colonnes. Ainsi $M \in \mathcal{B}_n$ . Stabilité par produit : Soit $U \in \mathcal{M}_{n,1}(\mathbb{R})$ le vecteur dont toutes les composantes valent $1$ . Une matrice $A \ge 0$ appartient à $\mathcal{B}_n$ si et seulement si $AU=U$ et $A^T U = U$ . Soient $A, B \in \mathcal{B}_n$ . Alors $AB$ est à coefficients positifs (somme de produits de termes positifs). On a : $(AB)U = A(BU) = AU = U$ Et pour la transposée : $(AB)^T U = B^T (A^T U) = B^T U = U$ $\boxed{ \mathcal{B}_n \text{ est stable par produit.} }$
Exemples :
- Les matrices de permutation : si $\sigma \in \mathcal{S}_n$ , la matrice $P_\sigma = (\delta_{i, \sigma(j)})$ est bistochastique.
- La matrice $J_n = \left(\frac{1}{n}\right)_{1 \le i,j \le n}$ dont tous les coefficients valent $1/n$ est bistochastique.
Soit $A \in \mathcal{B}_n$ telle que $a_{i,j} \in \{0, 1\}$ . Pour chaque ligne $i$ , la condition $\sum_{j=1}^n a_{i,j} = 1$ avec $a_{i,j} \in \{0, 1\}$ impose qu'il existe un unique indice $j$ , noté $\sigma(i)$ , tel que $a_{i, \sigma(i)} = 1$ . L'application $\sigma : \{1, \dots, n\} \to \{1, \dots, n\}$ ainsi définie est injective. En effet, si $\sigma(i) = \sigma(k) = j$ , alors la colonne $j$ contient au moins deux fois le chiffre $1$ , ce qui contredit $\sum_{i=1}^n a_{i,j} = 1$ . Étant injective sur un ensemble fini, $\sigma$ est une bijection (permutation). $\boxed{ \text{Ces matrices sont exactement les matrices de permutation } P_\sigma. }$
Caractérisation des points extrémaux. Sens 1 : Les matrices de permutation sont des points extrémaux. Soit $P$ une matrice de permutation. Supposons $P = t A + (1-t) B$ avec $t \in ]0, 1[$ et $A, B \in \mathcal{B}_n$ . Si $p_{i,j} = 0$ , alors $0 = t a_{i,j} + (1-t) b_{i,j}$ . Comme $a_{i,j}, b_{i,j} \ge 0$ , on a nécessairement $a_{i,j} = b_{i,j} = 0$ . Si $p_{i,j} = 1$ , alors $1 = t a_{i,j} + (1-t) b_{i,j}$ . Comme $a_{i,j}, b_{i,j} \le 1$ , la seule possibilité est $a_{i,j} = b_{i,j} = 1$ . D'où $A = B = P$ . $P$ est donc extrémale.
Sens 2 : Une matrice extrémale est de permutation. Par l'absurde, soit $A \in \mathcal{B}_n$ une matrice extrémale qui n'est pas de permutation. D'après la question 3, $A$ possède au moins un coefficient $a_{i_1, j_1} \in ]0, 1[$ . Comme la somme de la ligne $i_1$ vaut 1, il existe $j_2 \neq j_1$ tel que $a_{i_1, j_2} \in ]0, 1[$ . Comme la somme de la colonne $j_2$ vaut 1, il existe $i_2 \neq i_1$ tel que $a_{i_2, j_2} \in ]0, 1[$ . En itérant, on construit une suite de coefficients dans $]0, 1[$ . Comme le nombre de coefficients est fini, on finit par créer un cycle d'indices. Soit $K$ la matrice ayant des $1$ et des $-1$ alternés sur ce cycle et $0$ ailleurs. Par construction, les sommes en ligne et en colonne de $K$ sont nulles. Pour $\varepsilon > 0$ assez petit, $A + \varepsilon K$ et $A - \varepsilon K$ sont dans $\mathcal{B}_n$ (coefficients restent dans $[0, 1]$ ). Alors $A = \frac{1}{2}(A + \varepsilon K) + \frac{1}{2}(A - \varepsilon K)$ , ce qui contredit le caractère extrémal de $A$ .
$\boxed{ \text{Les points extrémaux de } \mathcal{B}_n \text{ sont les matrices de permutation.} }$

Attention à la définition de point extrémal : il faut bien vérifier que si une combinaison convexe est égale au point, alors les deux matrices de départ sont égales à ce point. Ne pas confondre avec la notion de point frontière.