Corrigé ENS Ulm 2025 Maths D MP — Partie 3 (Q29 à Q32) : Polytope de Birkhoff : dimension, sommets = matrices de permutation (Birkhoff-von Neumann)

Sujet officiel du concours ENS Ulm, session 2025, épreuve Maths D MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Une matrice $M \in M_{n} (R)$ est bistochastique si ses coefficients sont $\geq 0$ et si toutes ses sommes de lignes et de colonnes valent $1$ ; $B_{n}$ désigne leur ensemble, $S_{n}$ le groupe symétrique. Pour $σ \in S_{n}$ , $P^{σ}$ est la matrice de coefficients $P_{ij}^{σ} = 1$ si $j = σ (i)$ , $0$ sinon.

Q29. $B_{n}$ est un polytope ; déterminer sa dimension.
Q30. Chaque $P^{σ}$ est un sommet de $B_{n}$ .
Q31. Si $M \in B_{n} ∖ M_{n} (Z)$ , il existe des couples $(r_{1}, s_{1}), \dots, (r_{k}, s_{k})$ , $k \geq 2$ , avec $0 < M_{r_{i}, s_{i}} < 1$ , $0 < M_{r_{i}, s_{i + 1}} < 1$ et $(r_{k}, s_{k}) = (r_{1}, s_{1})$ ; on peut de plus supposer distincts les couples $(r_{1}, s_{1}), (r_{1}, s_{2}), (r_{2}, s_{2}), \dots, (r_{k - 1}, s_{k - 1}), (r_{k - 1}, s_{k})$ .
Q32. En déduire, pour un tel $M$ , une matrice $Q \neq = 0$ et $ϵ > 0$ avec $M + tQ \in B_{n}$ pour $t \in [- ϵ, ϵ]$ ; conclure que tout sommet de $B_{n}$ est un $P^{σ}$ .

Corrigé

On identifie $M_{n} (R)$ à $R^{n^{2}}$ ; les applications $M \mapsto M_{ij}$ , $M \mapsto \sum_{k} M_{ik}$ , $M \mapsto \sum_{k} M_{k j}$ sont des formes linéaires.

Q29. Polytope. L'ensemble $B_{n}$ est défini par les inégalités linéaires $- M_{ij} \leq 0$ , $\sum_{k} M_{ik} \leq 1$ , $- \sum_{k} M_{ik} \leq - 1$ , $\sum_{k} M_{k j} \leq 1$ , $- \sum_{k} M_{k j} \leq - 1$ (en nombre fini). Il est fermé, non vide ( $I_{n} \in B_{n}$ ) et borné ( $0 \leq M_{ij} \leq \sum_{k} M_{ik} = 1$ ) : compact. C'est un polytope.

Dimension. Soit $W$ le sous-espace vectoriel des matrices dont toutes les sommes de lignes et de colonnes sont nulles. Pour $M, M^{'} \in B_{n}$ , $M - M^{'} \in W$ , donc $B_{n} \subset W$ . Réciproquement, soit $J$ la matrice dont tous les coefficients valent $\frac{1}{n}$ : $J \in B_{n}$ . Si $E \in W$ vérifie $∣ E_{ij} ∣ \leq \frac{1}{n}$ pour tous $i, j$ , alors $J + E$ est à coefficients $\geq 0$ et de sommes de lignes et colonnes égales à $1$ , donc $J + E \in B_{n}$ et $E = (J + E) - J \in B_{n}$ . Tout $E \in W$ est un multiple d'un tel élément, donc $W = B_{n}$ .

Calculons $dim W$ (pour $n \geq 2$ ). L'application $Φ : W \to M_{n - 1} (R)$ qui à $M$ associe son bloc $(M_{ij})_{i, j \leq n - 1}$ est linéaire et injective : si ce bloc est nul, la nullité des sommes des lignes $i \leq n - 1$ donne $M_{in} = 0$ , celle des colonnes $j \leq n - 1$ donne $M_{nj} = 0$ , puis la dernière ligne donne $M_{nn} = 0$ . Elle est surjective : pour $N \in M_{n - 1} (R)$ , on pose $M_{ij} = N_{ij}$ ( $i, j < n$ ), $M_{in} = - \sum_{j < n} N_{ij}$ , $M_{nj} = - \sum_{i < n} N_{ij}$ , $M_{nn} = \sum_{i, j < n} N_{ij}$ ; les lignes $i < n$ et colonnes $j < n$ sont de somme nulle, et la dernière ligne a pour somme $- \sum_{i, j < n} N_{ij} + \sum_{i, j < n} N_{ij} = 0$ , de même la dernière colonne. Donc $dim W = (n - 1)^{2}$ . Pour $n = 1$ , $B_{1} = {(1)}$ est de dimension $0$ . Dans tous les cas

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →