Corrigé ESSEC-HEC 2025 Maths appliquées ECG — Partie 3 — Algorithme de réversibilité (Q19.a à Q21.b) : Symétrisation en r − 1 opérations d'une matrice ergodique vérifiant (K), réciproque, et fonction Python estRev qui teste la réversibilité

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

Énoncé

Notations de Q16 à Q18 : opérations élémentaires sur une ligne ou une colonne $k$ , de paramètre $α \in] 0, 1]$ ; graphe $G_{M} (I)$ d'arêtes ${i, j}$ , $i \neq = j$ , $m_{i, j} = m_{j, i} \neq = 0$ ; propriété $(K)$ ; Q8 (chemins de poids strictement positif). Désormais $M \in S T_{r}$ est ergodique.

Q19. On suppose que $M$ vérifie $(K)$ .
(a) À l'aide de Q8, montrer que pour tout $I \subset [[1, r]]$ non vide et différent de $[[1, r]]$ , il existe $ℓ \in I$ et $k \in / I$ tels que $m_{ℓ, k}$ et $m_{k, ℓ}$ soient non nuls.
(b) Partant de $I = {1}$ , en déduire un algorithme de $r - 1$ opérations élémentaires transformant $M$ en une matrice $M^{*}$ ergodique, vérifiant $(K)$ , avec $G_{M^{*}} ([[1, r]])$ connexe. En déduire que $M^{*}$ est symétrique.
Q20. Réciproquement, si une suite d'opérations élémentaires transforme $M \in S T_{r}$ en une matrice symétrique $M^{*}$ , montrer que $M$ vérifie $(K)$ .
Q21. (a) Écrire NonNul(M,I,J) qui renvoie un couple $(i, j)$ avec $i \in I$ , $j \in J$ et M[i-1][j-1] non nul s'il en existe, $(0, 0)$ sinon. (b) Compléter les quatre trous de la fonction estRev(M) du sujet (boucle while len(I) < ..., return ... en cas d'échec, I.append(...), J.remove(...)) pour qu'elle renvoie True si $M$ ergodique vérifie $(K)$ et False sinon.

Corrigé

Q19.a. Démontrons un peu plus : il existe $ℓ \in I$ et $k \in / I$ avec $m_{ℓ, k} > 0$ et, pour tout tel couple, on a aussi $m_{k, ℓ} > 0$ .

Existence de $m_{ℓ, k} > 0$ . Soit $i \in I$ et $j \in / I$ (possible car $I \neq = \emptyset$ et $I \neq = [[1, r]]$ ). Par ergodicité, $m_{i, j}^{(σ)} > 0$ , et Q8 fournit $(i_{0}, \dots, i_{σ})$ avec $i_{0} = i$ , $i_{σ} = j$ et $θ_{M} (i_{0}, \dots, i_{σ}) > 0$ , donc tous les facteurs $m_{i_{h - 1}, i_{h}}$ sont strictement positifs. Le chemin part de $I$ et finit hors de $I$ : soit $t ⩾ 1$ le plus petit indice tel que $i_{t} \in / I$ . Alors $ℓ = i_{t - 1} \in I$ , $k = i_{t} \in / I$ et $m_{ℓ, k} > 0$ .

Retour. Soit $ℓ \in I$ , $k \in / I$ avec $m_{ℓ, k} > 0$ . Par ergodicité, $m_{k, ℓ}^{(σ)} > 0$ ; Q8 fournit $(j_{0}, \dots, j_{σ})$ avec $j_{0} = k$ , $j_{σ} = ℓ$ et $θ_{M} (j_{0}, \dots, j_{σ}) > 0$ . Le chemin fermé $(ℓ, j_{0}, j_{1}, \dots, j_{σ - 1}, ℓ)$ a pour poids, par Q5, $m_{ℓ, k} θ_{M} (j_{0}, \dots, j_{σ}) > 0$ . La propriété $(K)$ , appliquée avec $n = σ$ à la suite $(ℓ, j_{0}, \dots, j_{σ - 1})$ , puis Q5, donnent

$0 < θ_{M} (ℓ, j_{0}, \dots, j_{σ - 1}, ℓ) = θ_{M} (ℓ, j_{σ - 1}, \dots, j_{0}, ℓ) = θ_{M} (j_{σ}, j_{σ - 1}, \dots, j_{0}) m_{k, ℓ},$

d'où $m_{k, ℓ} > 0$ . Les deux résultats donnent $\exists ℓ \in I, \exists k \in / I, m_{ℓ, k} \neq = 0 et m_{k, ℓ} \neq = 0.$

(Variante : par Q9, $M$ ergodique vérifiant $(K)$ est $μ$ -réversible pour une certaine $μ$ , et Q1.a donne $m_{k, ℓ} \neq = 0$ .)

Q19.b. Algorithme. On pose $M_{0} = M$ et $I_{0} = {1}$ ; $G_{M_{0}} (I_{0})$ , réduit à un sommet, est connexe. Pour $t = 0, 1, \dots, r - 2$ :

on choisit $ℓ \in I_{t}$ et $k \in / I_{t}$ avec $m_{ℓ, k} \neq = 0$ et $m_{k, ℓ} \neq = 0$ , coefficients de $M_{t}$ ;
si $m_{ℓ, k} ⩽ m_{k, ℓ}$ , on applique l'opération sur la ligne $k$ avec $α = m_{ℓ, k} / m_{k, ℓ}$ , sinon l'opération sur la colonne $k$ avec $α = m_{k, ℓ} / m_{ℓ, k}$ : on obtient $M_{t + 1}$ ;
on pose $I_{t + 1} = I_{t} \cup {k}$ .

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 →