Corrigé ESSEC-HEC 2025 Maths appliquées ECG — Partie 3 — Opérations élémentaires (Q16 à Q18) : Opérations sur une ligne ou une colonne en Python, invariance de (K) et de l'ergodicité, symétrisation d'un couple de coefficients et connexité du graphe

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

Énoncé

Notations de la partie 1 (cette partie est indépendante de la partie 2). Soit $α \in] 0, 1]$ et $M = (m_{i, j}) \in S T_{r}$ . Deux opérations élémentaires produisent $M^{'} = (m_{i, j}^{'}) \in S T_{r}$ :

sur la ligne $k$ : $m_{k, j}^{'} = α m_{k, j}$ pour $j \neq = k$ et $m_{k, k}^{'} = 1 - α + α m_{k, k}$ , les autres coefficients étant inchangés ;
sur la colonne $k$ : pour $i \neq = k$ , $m_{i, k}^{'} = α m_{i, k}$ et $m_{i, i}^{'} = m_{i, i} + (1 - α) m_{i, k}$ , les autres coefficients étant inchangés.

Hors diagonale, seule la ligne $k$ (resp. la colonne $k$ ) est modifiée.

Q16. Écrire opLigne(M,k,alph) réalisant l'opération sur la ligne $k$ de la matrice numpy M ( $α$ est alph). La fonction analogue opCol(M,k,alph) n'est pas demandée.
Q17. (a) Montrer que $M$ vérifie $(K)$ si et seulement si $M^{'}$ la vérifie. (b) Montrer que $m_{i, j} > 0$ entraîne $m_{i, j}^{'} > 0$ . (c) Montrer que si $M$ est ergodique, $M^{'}$ l'est aussi.
Pour $I \subset [[1, r]]$ non vide, $G_{M} (I)$ est le graphe non orienté de sommets $I$ dont les arêtes sont les ${i, j}$ tels que $i \neq = j$ , $m_{i, j} \neq = 0$ et $m_{j, i} = m_{i, j}$ .
Q18. On suppose $G_{M} (I)$ connexe, et $ℓ \in I$ , $k \in / I$ tels que $m_{ℓ, k}$ et $m_{k, ℓ}$ soient non nuls. 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 note $M^{'}$ le résultat. Montrer que ${k, ℓ}$ est une arête de $G_{M^{'}} (I \cup {k})$ et que ce graphe est connexe.

Corrigé

Q16. Les indices mathématiques vont de $1$ à $r$ , ceux de Python de $0$ à $r - 1$ : $m_{i, j}$ est M[i-1][j-1]. La matrice est modifiée sur place (un tableau numpy est mutable), ce qu'exige le script de Q21.b, qui appelle la fonction sans récupérer de résultat ; on la renvoie aussi, par commodité.


def opLigne(M, k, alph):
    r = np.shape(M)[0]
    for j in range(r):
        if j != k - 1:
            M[k-1][j] = alph * M[k-1][j]
    M[k-1][k-1] = 1 - alph + alph * M[k-1][k-1]
    return M

Pour l'algorithme de Q21, on écrit aussi opCol ; le coefficient diagonal se met à jour avec l'ancienne valeur de $m_{i, k}$ , donc avant de la multiplier par $α$ :


def opCol(M, k, alph):
    r = np.shape(M)[0]
    for i in range(r):
        if i != k - 1:
            M[i][i] = M[i][i] + (1 - alph) * M[i][k-1]
            M[i][k-1] = alph * M[i][k-1]
    return M

Exécutées en fractions exactes sur la matrice d'exemple du sujet, de lignes $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ , $(\frac{1}{3}, 0, \frac{2}{3})$ , $(\frac{1}{6}, \frac{2}{3}, \frac{1}{6})$ , avec $k = 1$ et $α = \frac{1}{2}$ , elles ont renvoyé les lignes $(\frac{2}{3}, \frac{1}{6}, \frac{1}{6})$ , $(\frac{1}{3}, 0, \frac{2}{3})$ , $(\frac{1}{6}, \frac{2}{3}, \frac{1}{6})$ pour opLigne, et $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ , $(\frac{1}{6}, \frac{1}{6}, \frac{2}{3})$ , $(\frac{1}{12}, \frac{2}{3}, \frac{1}{4})$ pour opCol : ce sont les deux matrices $M^{'}$ données par le sujet.

Q17.a. D'après le résultat admis en partie 1, appliqué à $M$ et à $M^{'}$ (toutes deux dans $S T_{r}$ ), il suffit de comparer $(K)$ sur les circuits $(i_{0}, \dots, i_{n}, i_{0})$ où $n ⩾ 2$ et $i_{0}, \dots, i_{n}$ sont deux à deux distincts. Fixons un tel circuit et notons

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 →