Corrigé ESSEC-HEC 2026 Maths approfondies ECG — Partie II (Q7.a à Q10) : Matrices bistochastiques et orthostochastiques, théorème de Birkhoff-Von Neumann pour n = 2 et n = 3, algorithme de Sinkhorn en Python

Sujet officiel du concours ESSEC-HEC, session 2026, épreuve Maths approfondies ECG. Corrigé rédigé par Ibrahim Alame.

Énoncé

$S \in M_{n} (R)$ est bistochastique si ses coefficients sont positifs et si chaque ligne et chaque colonne a pour somme $1$ ; elle est orthostochastique s'il existe $Q \in O_{n}$ avec $S_{i, j} = (Q_{i, j})^{2}$ pour tous $i, j$ . Théorème de Birkhoff-Von Neumann (à établir ici pour $n \in {2, 3}$ ) : toute matrice bistochastique est combinaison convexe $a_{1} P_{1} + \dots + a_{k} P_{k}$ de matrices de permutation ( $a_{i} ⩾ 0$ , $\sum a_{i} = 1$ ).

Q7.a. Montrer que toute matrice orthostochastique et toute matrice de permutation sont bistochastiques.
Q7.b. Donner, pour $n = 3$ , une matrice bistochastique non orthostochastique.
Q8.a. ( $n = 2$ ) Trouver toutes les matrices de permutation de $M_{2} (R)$ .
Q8.b. En déduire : $S \in M_{2} (R)$ est bistochastique si et seulement si $S = α I_{2} + (1 - α) P$ avec $α \in [0, 1]$ et $P$ de permutation.
Q9. ( $n = 3$ , $S$ bistochastique.) (a) Nombre de permutations de ${1, 2, 3}$ ? (b) Montrer que les cinq matrices $P_{1}, \dots, P_{5}$ du sujet sont de permutation et donner les $σ$ associées. (c) Montrer que $S$ s'écrit sous la forme (2) (troisième ligne et troisième colonne complétées par $1$ moins les sommes partielles), exprimer $S_{3, 3}$ en fonction des $S_{i, j}$ , $i, j ⩽ 2$ , et donner des conditions nécessaires sur ces coefficients. (d) Avec $β_{0} = min_{1 ⩽ i ⩽ 3} S_{i, i}$ , montrer qu'il existe $β_{1}, \dots, β_{5} ⩾ 0$ tels que $S = β_{0} I_{3} + \sum_{i = 1}^{5} β_{i} P_{i}$ . (e) Conclure.
Q10. Écrire bistochastique(n,iter) : partir d'une matrice $A^{(0)}$ de coefficients uniformes sur $] 0, 1 [$ , puis, pour $0 ⩽ k < iter$ , diviser chaque ligne de $A^{(2 k)}$ par sa somme (on obtient $A^{(2 k + 1)}$ ), puis chaque colonne de $A^{(2 k + 1)}$ par sa somme (on obtient $A^{(2 k + 2)}$ ) ; renvoyer la dernière matrice.

Corrigé

Q7.a. Matrice orthostochastique. Soit $S$ avec $S_{i, j} = (Q_{i, j})^{2}$ , $Q \in O_{n}$ . D'abord $S_{i, j} ⩾ 0$ . Ensuite, pour tout $i$ ,

$j = 1 \sum n S_{i, j} = j = 1 \sum n Q_{i, j} Q_{i, j} = (Q^{t} Q)_{i, i} = (I_{n})_{i, i} = 1.$

Pour les colonnes il faut $^{t} Q Q = I_{n}$ : de $Q^{t} Q = I_{n}$ , la matrice carrée $Q$ est inversible d'inverse $^{t} Q$ , donc $^{t} Q Q = I_{n}$ . Alors, pour tout $j$ , $\sum_{i = 1}^{n} S_{i, j} = \sum_{i = 1}^{n} Q_{i, j} Q_{i, j} = (^{t} Q Q)_{j, j} = 1$ . Donc $S$ est bistochastique.

Matrice de permutation. Soit $P \in P_{n}$ : $P$ est orthogonale (Q3) et ses coefficients valent $0$ ou $1$ , donc $P_{i, j} = (P_{i, j})^{2}$ : $P$ est orthostochastique (avec $Q = P$ ), donc bistochastique. $Orthostochastique \Rightarrow bistochastique, et P_{n} \subset {bistochastiques} .$

Q7.b. Prenons

$S = \frac{1}{2} 101110011 .$

Ses coefficients sont positifs et chaque ligne, chaque colonne contient exactement deux coefficients $\frac{1}{2}$ : $S$ est bistochastique. Supposons $S_{i, j} = (Q_{i, j})^{2}$ avec $Q \in O_{3}$ . Alors $Q_{1, 3} = Q_{2, 1} = 0$ et $∣ Q_{1, 2} ∣ = ∣ Q_{2, 2} ∣ = \frac{1}{2}$ . Mais $Q^{t} Q = I_{3}$ impose, au coefficient $(1, 2)$ ,

$0 = k = 1 \sum 3 Q_{1, k} Q_{2, k} = Q_{1, 1} \cdot 0 + Q_{1, 2} Q_{2, 2} + 0 \cdot Q_{2, 3} = Q_{1, 2} Q_{2, 2} = \pm \frac{1}{2},$

contradiction. $S est bistochastique mais pas orthostochastique.$

Q8.a. $P_{2}$ contient deux permutations : l'identité et la transposition $τ = (2, 1)$ . Par Q1, la colonne $j$ de $P_{σ}$ est $e_{σ (j)}$ , donc

$P_{id} = I_{2}, P_{τ} = J = (0110), P_{2} = {I_{2}, J} .$

Q8.b. ( $\Rightarrow$ ) Soit $S$ bistochastique. Les relations $S_{1, 1} + S_{1, 2} = 1$ , $S_{1, 1} + S_{2, 1} = 1$ , $S_{2, 1} + S_{2, 2} = 1$ donnent, avec $a = S_{1, 1}$ : $S_{1, 2} = S_{2, 1} = 1 - a$ et $S_{2, 2} = a$ . La positivité impose $a ⩾ 0$ et $1 - a ⩾ 0$ , donc $a \in [0, 1]$ , et

$S = (a 1 - a 1 - a a) = a I_{2} + (1 - a) J .$

On prend $α = a$ et $P = J$ .

( $\Leftarrow$ ) Si $S = α I_{2} + (1 - α) P$ avec $α \in [0, 1]$ : pour $P = I_{2}$ , $S = I_{2}$ est bistochastique ; pour $P = J$ , $S = (α 1 - α 1 - α α)$ a des coefficients positifs et des sommes de lignes et de colonnes égales à $1$ . $S bistochastique ⟺ \exists α \in [0, 1], \exists P \in P_{2}, S = α I_{2} + (1 - α) P .$ C'est le théorème de Birkhoff-Von Neumann pour $n = 2$ .

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 →