Corrigé ESSEC-HEC 2026 Maths approfondies ECG — Partie I (Q1 à Q6) : Matrices de permutation (produit, inverse, orthogonalité) et réordonnement décroissant d'un vecteur, tri par sélection en Python

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

Énoncé

Notations du problème : $P_{n}$ est l'ensemble des permutations (bijections) de $[[1; n]]$ ; pour $x = (x_{1}, \dots, x_{n}) \in R^{n}$ et $σ \in P_{n}$ , $x_{σ} = (x_{σ (1)}, \dots, x_{σ (n)})$ ; $δ_{i, k}$ est le symbole de Kronecker. La matrice de permutation associée à $σ$ est $P_{σ} \in M_{n} (R)$ de coefficients $(P_{σ})_{i, j} = δ_{i, σ (j)}$ , et $P_{n}$ désigne l'ensemble de ces matrices. $O_{n} = {M \in M_{n} (R) ∣ M^{t} M = I_{n}}$ , $(e_{1}, \dots, e_{n})$ est la base canonique de $R^{n}$ , et $⟨ U, V ⟩ =^{t} U V$ sur $M_{n, 1} (R)$ .

Q1. Si $ϕ_{σ}$ est l'endomorphisme de $R^{n}$ canoniquement associé à $P_{σ}$ , montrer que $ϕ_{σ} (e_{j}) = e_{σ (j)}$ pour tout $j$ .
Q2. Montrer que $P_{σ} P_{τ} = P_{σ \circ τ}$ ; en déduire que l'inverse d'une matrice de permutation en est une.
Q3. Montrer que toute $P \in P_{n}$ est orthogonale.
Q4. Montrer par récurrence sur $n$ que pour tout $(x_{1}, \dots, x_{n})$ il existe $α \in P_{n}$ avec $x_{α (1)} ⩾ \dots ⩾ x_{α (n)}$ (relation (1)).
Q5. Si $α$ et $β$ vérifient tous deux (1), montrer que $x_{α (i)} = x_{β (i)}$ pour tout $i$ .
On note ensuite $x^= (x^_{1}, \dots, x^_{n})$ , $x^_{i} = x_{α (i)}$ : les composantes de $x$ rangées dans l'ordre décroissant.
Q6. Compléter la fonction Python à trous permutevecteur(X) du sujet (tri par sélection), qui renvoie (Y, alpha) : les valeurs de X triées dans l'ordre décroissant et une permutation $α$ comme en Q4.

Corrigé

Q1. L'image par $ϕ_{σ}$ du $j$ -ème vecteur de la base canonique a pour coordonnées la $j$ -ème colonne de $P_{σ}$ . Le coefficient de cette colonne sur la ligne $i$ vaut $δ_{i, σ (j)}$ : il vaut $1$ pour $i = σ (j)$ et $0$ sinon. Donc

$ϕ_{σ} (e_{j}) = i = 1 \sum n δ_{i, σ (j)} e_{i} = e_{σ (j)}, \forall j \in [[1; n]], ϕ_{σ} (e_{j}) = e_{σ (j)} .$

Autrement dit, la $j$ -ème colonne de $P_{σ}$ est le vecteur $e_{σ (j)}$ : $P_{σ}$ contient un seul $1$ par colonne, placé sur la ligne $σ (j)$ .

Q2. Par la formule du produit matriciel, pour $(i, j) \in [[1; n]]^{2}$ ,

$(P_{σ} P_{τ})_{i, j} = k = 1 \sum n (P_{σ})_{i, k} (P_{τ})_{k, j} = k = 1 \sum n δ_{i, σ (k)} δ_{k, τ (j)} .$

Dans cette somme, seul le terme d'indice $k = τ (j)$ peut être non nul ; il vaut $δ_{i, σ (τ (j))}$ . Ainsi $(P_{σ} P_{τ})_{i, j} = δ_{i, (σ \circ τ) (j)} = (P_{σ \circ τ})_{i, j}$ , et comme $σ \circ τ \in P_{n}$ (composée de deux bijections),

$P_{σ} P_{τ} = P_{σ \circ τ} .$

(On peut aussi le lire sur Q1 : $ϕ_{σ} \circ ϕ_{τ} (e_{j}) = ϕ_{σ} (e_{τ (j)}) = e_{σ (τ (j))} = ϕ_{σ \circ τ} (e_{j})$ , et deux endomorphismes égaux sur une base sont égaux.)

Pour l'identité $id$ de $[[1; n]]$ , $(P_{id})_{i, j} = δ_{i, j}$ , donc $P_{id} = I_{n}$ . Soit $P = P_{σ} \in P_{n}$ ; la bijection réciproque $σ^{- 1}$ est encore une permutation, et

$P_{σ} P_{σ^{- 1}} = P_{σ \circ σ^{- 1}} = P_{id} = I_{n} .$

Une matrice carrée admettant un inverse à droite est inversible, d'inverse celui-ci : $P_{σ}^{- 1} = P_{σ^{- 1}} \in P_{n} .$

Q3. Soit $P = P_{σ}$ . Pour $(i, j) \in [[1; n]]^{2}$ ,

$(P^{t} P)_{i, j} = k = 1 \sum n P_{i, k} P_{j, k} = k = 1 \sum n δ_{i, σ (k)} δ_{j, σ (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 →