WikiPrépaLivrets

Mines Mathématiques 1 MP 2016Sujet, corrigé et rapport du jury

Pas encore noté
Faisable en Sup
Logo concours Mines

Explorer les annales

BanqueMinesAnnée2016FilièreMPMatièreMathématiques
Annales Mines MP MathématiquesMines MP 2016MP MathématiquesMathématiques 2016

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Corrigé 2
Corrigé 3
Rapport du juryLire en ligneLaTeXWord

Présentation du sujet

Difficulté moyenne
Autour de l'inégalité de Hoffman-Wielandt : matrices bistochastiques et théorème de Birkhoff-Von Neumann
Afficher ou masquer la section

Le problème étudie les matrices bistochastiques et leurs liens avec les matrices de permutation. Une partie A indépendante diagonalise une matrice de permutation circulaire et l'applique à une marche aléatoire. La partie B démontre le théorème de Birkhoff-Von Neumann, puis la partie C en déduit l'inégalité de Hoffman-Wielandt sur les valeurs propres de deux matrices symétriques et une application probabiliste.

  1. 1Partie A : un exempleDiagonalisation de la matrice de permutation circulaire J et étude de la loi limite d'une marche aléatoire sur les entiers modulo n.
  2. 2Partie B : théorème de Birkhoff-Von NeumannConvexité et compacité de l'ensemble des matrices bistochastiques, structure du groupe des matrices de permutation, éléments extrémaux et décomposition d'une matrice bistochastique en combinaison convexe de matrices de permutation.
  3. 3Partie C : inégalité de Hoffman-WielandtInvariance de la norme euclidienne par les matrices orthogonales, théorème spectral et comparaison des valeurs propres de deux matrices symétriques, puis distance entre deux lois uniformes.

Difficulté moyenne. Les premières questions classiques sont en général bien traitées, mais le jury juge le problème un peu long et note que peu de candidats sont arrivés aux questions 17 et 18.

Ce qu'a observé le jury

6 erreurs relevées
Valeurs propres réelles oubliées · Matrice de transition devinée · Compacité mal justifiée
Afficher ou masquer la section

Le problème s'ouvre sur deux questions classiques de diagonalisation, en général bien traitées. La suite exige davantage de rigueur, notamment pour la compacité, les récurrences et l'usage du théorème spectral. La dernière question, délicate, n'a pratiquement été abordée par personne de manière significative.

Les erreurs les plus sanctionnées

  1. 1
    Valeurs propres réelles oubliéesQ1

    Montrer que les valeurs propres sont des racines de l'unité ne suffit pas ; le cas des racines réelles, avec une discussion selon la parité de n, était souvent omis.

  2. 2
    Matrice de transition devinéeQ3, Q4

    La formule des probabilités totales est souvent oubliée et certaines matrices A sont données au hasard. Faute de voir la relation entre J et sa transposée, beaucoup n'ont pas trouvé les valeurs propres de A.

    « un problème de mathématiques ne se réduit pas à des devinettes »
  3. 3
    Compacité mal justifiéeQ6

    Il fallait rappeler l'équivalence des normes en dimension finie, choisir une norme et préciser la caractérisation des fermés utilisée.

  4. 4
    Diagonalisabilité des matrices de permutationQ7

    Cette question ouverte a mis en échec une forte proportion de candidats ; la structure de sous-groupe demandait aussi une justification précise par produit matriciel.

  5. 5
    Raisonnement incomplet sur les zérosQ12

    Beaucoup n'ont pas justifié que λ0 est différent de 1, ou ont montré qu'un zéro apparaît sans vérifier qu'aucun autre zéro ne disparaît.

  6. 6
    Arguments topologiques superflusQ14

    Il suffisait de remarquer que l'ensemble des matrices de permutation est fini ; de nombreuses copies se sont compliqué la tâche.

    « Nous conseillons aux futurs candidats de ne pas se précipiter sans réfléchir sur des arguments topologiques dans une situation aussi simple. »

Ce qui a été bien réussi

  • Les deux premières questions de diagonalisation ont en général été bien traitées, y compris par un calcul direct des vecteurs propres.
  • La question 8, inhabituelle, a mis en valeur l'adaptation et l'imagination des meilleurs candidats.
  • Les questions 10 et 11 ont été traitées correctement dans les meilleures copies.
  • La question 15, très classique, a rapporté des points à de nombreux candidats.

Conseils du jury

  • Répondre à toutes les questions faciles : des oublis de réponse sont fréquents.
  • Ne pas se laisser décourager par une question surprenante, qui n'est pas forcément difficile.
  • Donner une réponse précise lorsqu'on invoque le théorème spectral, en explicitant la matrice de passage.
  • Écrire au stylo à bille noir et utiliser des brouillons pour rendre une copie lisible.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

CONCOURS 2016

PREMIÈRE ÉPREUVE DE MATHÉMATIQUES

(Durée de l'épreuve : 3 heures) L'usage de l'ordinateur ou de la calculatrice est interdit.
Sujet mis à la disposition des concours : Concours Commun TPE/EIVP, Concours Mines-Télécom, Concours Centrale-Supélec (Cycle international).
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie :
MATHÉMATIQUES I - MP
L'énoncé de cette épreuve comporte 6 pages de texte.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.

Autour de l'inégalité de Hoffman-Wielandt

Dans tout le problème n désigne un entier supérieur ou égal à 2 . Soit M_n(ℝ) l'ensemble des matrices carrées d'ordre n à coefficients réels et A un sous ensemble de M_n(ℝ). On dit qu'une matrice A ∈ M_n(ℝ) est extrémale dans A si pour tous M, N dans A et tout λ ∈ ]0, 1[, on a l'implication :
A = λM + (1 − λ)N ⟹ A = M = N.
On note B_n l'ensemble des matrices bistochastiques de M_n(ℝ), c'est-à-dire l'ensemble des matrices A = (A_(i, j))_(1 ⩽ i, j ⩽ n) dont tous les coefficients sont positifs ou nuls et tels que ∑_(j = 1)^n A_(i, j) = ∑_(j = 1)^n A_(j, i) = 1 pour tout i ∈ {1, 2, …, n}.
On note enfin P_n l'ensemble des matrices de permutation M_σ ∈ M_n(ℝ) dont les coefficients sont de la forme :
(M_σ)_(i, j) = {1, si i = σ(j); 0, sinon
pour tous i, j dans {1, 2, …, n}, où σ est une permutation de {1, 2, …, n}.
La partie A n'est pas indispensable à la résolution des parties suivantes.

A Un exemple

Soit J la matrice de M_n(ℂ) définie par
J = (0, 1, 0, …, 0; 0, 0, 1, ⋱, ⋮; ⋮, ⋱, ⋱, ⋱, 0; 0, ⋱, ⋱, 1; 1, 0, …, 0, 0)
c'est-à-dire par J_(i, j) = 1 si j − i = 1 ou i − j = n − 1, et J_(i, j) = 0 sinon.
  1. Montrer que J est une matrice de permutation. Calculer les valeurs propres réelles et complexes de J, et en déduire que J est diagonalisable sur ℂ.
  2. Déterminer une base de ℂ^n de vecteurs propres de J.
Dans les trois questions suivantes n désigne un entier naturel impair ⩾ 3. Pour tout m ∈ ℕ, on note X_m une variable aléatoire à valeurs dans {0, 1, …, n − 1} telle que
  • X_0 = 0 avec probabilité 1 ;
  • si X_m = k, alors ou bien X_(m + 1) = k − 1 modulo n, ou bien X_(m + 1) = k + 1 modulo n, ceci avec équiprobabilité.
On note
U_m = (P(X_m = 0); P(X_m = 1); ⋮; P(X_m = n − 1))
  1. Déterminer U_0 et une matrice A de M_n(ℝ) telle que pour tout m ∈ ℕ, U_(m + 1) = AU_m. On exprimera A à l'aide de la matrice J.
  2. Déterminer les valeurs propres de la matrice A et un vecteur propre de ℝ^n unitaire associé à la valeur propre de module maximal.
  3. En déduire la limite de U_m lorsque m → + ∞.

B Théorème de Birkhoff-Von Neumann

  1. Montrer que l'ensemble B_n est convexe et compact. Est-il un sous espace vectoriel de M_n(ℝ) ?
  2. Montrer que P_n ⊂ B_n et que P_n est un sous-groupe multiplicatif de GL_n(ℝ). Tout élément de P_n est-il diagonalisable sur ℂ ? L'ensemble P_n est-il convexe?
  3. Montrer que toute matrice de P_n est extrémale dans B_n.
Dans toute la suite de cette partie, on considère une matrice bistochastique A = (A_(i, j))_(1 ⩽ i, j ⩽ n) qui n'est pas une matrice de permutation.
9. Montrer qu'il existe un entier r > 0 et deux familles i_1, i_2, …, i_r et j_1, j_2, …, j_r
d'indices distincts dans {1, 2, …, n} tels que pour tous k ∈ {1, 2, …, r}, A_(i_k, j_k) ∈ ]0, 1[ et A_(i_k, j_(k + 1)) ∈ ]0, 1[ avec j_(r + 1) = j_1.
10. En considérant la matrice B = (B_(i, j))_(1 ⩽ i, j ⩽ n) de M_n(ℝ) définie par :
{B_(i_k, j_k) = 1, k ∈ {1, 2, …, r}; B_(i_k, j_(k + 1)) = − 1, k ∈ {1, 2, …, r}; B_(i, j) = 0, dans les autres cas
montrer que A n'est pas un élément extrémal de B_n. En déduire l'ensemble des éléments extrémaux de B_n.
On dit qu'une matrice M = (M_(i, j))_(1 ⩽ i, j ⩽ n) de M_n(ℝ^+), à coefficients positifs ou nuls, admet un chemin strictement positif s'il existe une permutation σ de {1, 2, …, n} telle que M_(σ(1), 1)M_(σ(2), 2)⋯M_(σ(n), n) > 0.
On démontre par récurrence sur n, et on admet le résultat suivant : si M est à coefficients positifs ou nuls et si toute matrice extraite de M ayant p lignes et q colonnes avec p + q = n + 1 n'est pas la matrice nulle, alors M admet un chemin strictement positif.
11. Montrer que A admet un chemin strictement positif.
On note σ une permutation de {1, 2, …, n} telle que A_(σ(1), 1)A_(σ(2), 2)⋯A_(σ(n), n) > 0 et on pose λ_0 = min_j(A_(σ(j), j)) et A_0 = 1/(1 − λ_0)(A − λ_0 M_σ) où M_σ est la matrice de permutation associée à σ.
12. Montrer que A_0 est bien définie, et que c'est une matrice bistochastique contenant au moins un élément nul de plus que A.
13. En raisonnant par récurrence, démontrer que A s'écrit comme une combinaison linéaire d'un nombre fini de matrices de permutation M_0, M_1, …, M_s :
A = λ_0 M_0 + λ_1 M_1 + ⋯ + λ_s M_s
où les coefficients λ_i sont tous strictement positifs et de somme ∑_(i = 0)^s λ_i = 1.
14. Soit φ une forme linéaire de M_n(ℝ). Montrer que inf_(M ∈ P_n)φ(M) existe. En déduire que inf_(M ∈ B_n)φ(M) existe et est atteint en une matrice de permutation.

C Inégalité de Hoffman-Wielandt

Dans cette partie, on munit M_n(ℝ) de la norme euclidienne ‖ ⋅ ‖ associée au produit scalaire défini par ⟨A, B⟩ = tr(^t A ⋅ B). On note S_n(ℝ) le sous-ensemble de M_n(ℝ) des matrices symétriques et O_n(ℝ) celui des matrices orthogonales.
15. Montrer que pour tous A ∈ M_n(ℝ) et P, Q dans O_n(ℝ), on a ‖PAQ‖ = ‖A‖.
Dans la suite de cette partie, A et B désignent deux matrices symétriques réelles.
16. Montrer qu'il existe deux matrices diagonales réelles D_A, D_B, et une matrice orthogonale P = (P_(i, j))_(1 ⩽ i, j ⩽ n) telles que ‖A − B‖^2 = ‖D_A P − PD_B‖^2.
17. Montrer que la matrice R définie par R_(i, j) = (P_(i, j))^2 pour tous i, j dans {1, 2, …, n} est bistochastique et que
‖A − B‖^2 = ∑_(1 ⩽ i, j ⩽ n)R_(i, j)|λ_i(A) − λ_j(B)|^2
où λ_1(A), …, λ_n(A) désignent les valeurs propres de A et λ_1(B), …, λ_n(B) celles de B.
18. En déduire que
min_σ∑_(j = 1)^n|λ_(σ(j))(A) − λ_j(B)|^2 ⩽ ‖A − B‖^2
où le minimum porte sur l'ensemble de toutes les permutations de {1, 2, …, n}.
Soit ( Ω, 𝔄, P ) un espace probabilisé et V l'ensemble des variables aléatoires définies sur cet espace admettant un moment d'ordre 2. Pour tout X de V, on
note X ∼ P_X si X suit la loi P_X. Pour tout couple ( P_1, P_2 ) de lois, on pose
d^2(P_1, P_2) = inf_(X, Y ∈ V; X ∼ P_1, Y ∼ P_2)E(|X − Y|^2)
Soit (a_1, …, a_n) et (b_1, …, b_n) deux familles de réels. On note P_1 la loi uniforme sur {a_1, …, a_n} et P_2 la loi uniforme sur {b_1, …, b_n}.
19. Montrer que
d^2(P_1, P_2) = 1/n∑_(i = 1)^n|a_((i)) − b_((i))|^2
où l'on a noté a_((1)) ⩽ ⋯ ⩽ a_((n)) et b_((1)) ⩽ ⋯ ⩽ b_((n)) les suites (a_1, …, a_n) et (b_1, …, b_n) ré-ordonnées par ordre croissant. En déduire que pour toutes matrices symétriques réelles A, B de valeurs propres respectives (a_1, …, a_n) et ( b_1, …, b_n ), on a l'inégalité :
nd^2(P_1, P_2) ⩽ ‖A − B‖^2

Fin du problème

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet Mines maths 1 MP 2016 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet Mines maths 1 MP 2016 ?

Le sujet porte sur la réduction des matrices, les matrices de permutation, la topologie en dimension finie, la convexité, le théorème spectral et les matrices orthogonales, avec des applications en probabilités.

Quelles erreurs le jury a-t-il le plus relevées en Mines maths 1 MP 2016 ?

Le jury relève l'oubli des valeurs propres réelles, la formule des probabilités totales négligée, des justifications de compacité imprécises et des récurrences mal conduites sur le nombre de coefficients nuls.

La partie A du sujet Mines maths 1 MP 2016 est-elle nécessaire pour la suite ?

Non. L'énoncé précise que la partie A n'est pas indispensable à la résolution des parties suivantes.

Quelle est la question la plus difficile de Mines maths 1 MP 2016 ?

Selon le jury, la dernière question était délicate et pratiquement aucun candidat ne l'a abordée de manière significative, le problème étant un peu long.

Pas de description pour le moment