Centrale Mathématiques 1 PSI 2016Sujet, corrigé et rapport du jury

Dans tout ce problème, n est un entier supérieur ou égal à 2 et l'on note :

Par exemple :

Ce problème aborde l'étude de matrices à coefficients dans {0, 1} à travers plusieurs thématiques indépendantes les unes des autres. Les deux premières parties étudient quelques propriétés algébriques et topologiques des ensembles X_n et y_n définis ci-dessus. La partie III étudie le cas particulier des matrices de permutation. La partie IV étudie deux modalités de génération aléatoire de matrices à coefficients dans {0, 1}.

I.A.1) Justifier que X_n est un ensemble fini et déterminer son cardinal.
I.A.2) Démontrer que pour tout M ∈ y_n, det(M) ⩽ n ! et qu'il n'y a pas égalité.
I.A.3) Démontrer que y_n est une partie convexe et compacte de M_n(ℝ).
I.A.4) Soit M ∈ y_n et λ une valeur propre complexe de M. Démontrer que |λ| ⩽ n et donner un exemple explicite où l'on a l'égalité.

I.B.1) Faire la liste des éléments de X_2^′. Préciser (en justifiant) ceux qui sont diagonalisables sur ℝ.
I.B.2) Démontrer que X_2^′ engendre l'espace vectoriel M_2. Est-ce que, pour n ⩾ 2, X_n^′ engendre l'espace vectoriel M_n(ℝ) ?

Pour tout (M, N) ∈ (M_n(ℝ))^2, on note

II.A.1) Démontrer que l'on définit ainsi un produit scalaire sur M_n(ℝ). Expliciter ( M|N ) en fonction des coefficients de M et N.
On notera ‖M‖ la norme euclidienne associée.
II.A.2) On fixe A ∈ M_n(ℝ), prouver qu'il existe une matrice M ∈ y_n telle que:

II.A.3) Justifier l'unicité de la matrice M ci-dessus et expliciter ses coefficients en fonction de ceux de A.
II.B - Maximisation du déterminant sur X_n et y_n
II.B.1) Justifier que le déterminant possède un maximum sur X_n (noté x_n ) et un maximum sur y_n (noté y_n ).
II.B.2) Démontrer que la suite (y_k)_(k ⩾ 2) est croissante.
II.B.3) Soit J ∈ X_n la matrice dont tous les coefficients valent 1 . On pose M = J − I_n.

Calculer det(M) et en déduire que lim_(k → + ∞)y_k = + ∞.
II.B.4) Soient N = (n_(i, j))_(i, j) ∈ y_n. Fixons 1 ⩽ i, j ⩽ n et supposons que n_(i, j) ∈ ]0, 1[.

Démontrer qu'en remplaçant n_(i, j) soit par 0 , soit par 1 , on peut obtenir une matrice N^′ de y_n telle que det(N) ⩽ det(N^′).
En déduire que x_n = y_n.

On munit ℝ^n de sa structure euclidienne canonique et on note ( e_1, …, e_n ) sa base canonique.
On note S_n l'ensemble des bijections de l'ensemble {1, …, n} dans lui-même (appelées permutations).
Pour tout σ ∈ S_n, on note P_σ la matrice de P_n dont le coefficient ligne i, colonne j vaut 1 si i = σ(j) et 0 sinon. On dit que P_σ est la matrice de permutation associée à σ.
On note u_σ l'endomorphisme de ℝ^n canoniquement associé à P_σ.
III.A - Description de P_n
III.A.1) Donner deux définitions d'une isométrie vectorielle de ℝ^n et démontrer leur équivalence.
III.A.2) Démontrer que si M ∈ O_n(ℝ), alors son déterminant vaut 1 ou -1 . Que penser de la réciproque ?
III.A.3) Démontrer que P_n = X_n ∩ O_n(ℝ) et déterminer son cardinal.
III.B - Quelques propriétés des éléments de P_n
III.B.1) Soient σ et σ^′ deux éléments de S_n.

Démontrer que P_σ P_(σ^′) = P_(σ ∘ σ^′).
Justifier que l'application {ℤ → S_n; k ↦ σ^k n'est pas injective.
En déduire qu'il existe un entier N ⩾ 1 tel que σ^N = Id_({1, …, n}), où Id_({1, …, n}) désigne l'application identité sur l'ensemble {1, …, n}.
III.B.2) Démontrer que tous les éléments de P_n sont diagonalisables sur ℂ.
III.B.3) Déterminer les vecteurs propres communs à tous les éléments de P_n dans les cas n = 2 et n = 3.
III.B.4) On se propose de démontrer que les seuls sous-espaces vectoriels de ℝ^n stables par tous les u_σ, σ ∈ S_n sont {0_(ℝ^n)}, ℝ^n, la droite D engendrée par e_1 + e_2 + ⋯ + e_n et l'hyperplan H orthogonal à D.
a) Vérifier que ces quatre sous-espaces vectoriels sont stables par tous les u_σ.
b) Soit V un sous-espace vectoriel de ℝ^n, non contenu dans D et stable par tous les u_σ. Démontrer qu'il existe un couple (i, j) ∈ {1, …, n}^2 avec i ≠ j tel que e_i − e_j ∈ V, puis que les n − 1 vecteurs e_k − e_j(k ∈ {1, …, n}, k ≠ j) appartiennent à V.
c) Conclure.

On se donne une matrice M de GL_n(ℝ) dont tous les coefficients sont des entiers naturels et telle que l'ensemble formé par tous les coefficients de toutes les puissances successives de M est fini.
Démontrer que M^(− 1) est à coefficients dans ℕ et en déduire que M est une matrice de permutation. Que dire de la réciproque?

Soit p ∈ ]0, 1[. Soient X_1, …, X_n des variables aléatoires mutuellement indépendantes, définies sur un espace probabilisé ( Ω, A, P ) et suivant une même loi de Bernoulli de paramètre p.
IV.A.1) Calculer la probabilité que X_1, …, X_n soient égales.
IV.A.2) Quelle est la loi de S = X_1 + … + X_n ? On attend une démonstration du résultat annoncé.
IV.A.3) Soient i et j dans {1, …, n}. Donner la loi de la variable aléatoire X_(i, j) = X_i × X_j
IV.A.4) Si ω ∈ Ω, on introduit la matrice colonne

et la matrice M(ω) = U(ω)^t(U(ω)). L'application M : {Ω → M_n(ℝ); ω ↦ M(ω) est ainsi une variable aléatoire.
a) Si ω ∈ Ω, justifier que M(ω) ∈ X_n.
b) Si ω ∈ Ω, justifier que tr(M(ω)) ∈ {0, …, n}, que M(ω) est diagonalisable sur ℝ et que rg(M(ω)) ⩽ 1.
c) Si ω ∈ Ω, justifier que M(ω) est une matrice de projection orthogonale si et seulement si S(ω) ∈ {0, 1}.
IV.A.5) Donner la loi, l'espérance et la variance des variables aléatoires tr(M) et rg(M).
IV.A.6) Exprimer M^k en fonction de S et M.

Quelle est la probabilité pour que la suite de matrices (M^k)_(k ∈ ℕ) soit convergente ?
Montrer que, dans ce cas, la limite est une matrice de projection.
IV.A.7) Quelle est la probabilité que M admette deux valeurs propres distinctes?

Soit p ∈ ]0, 1[. On part de la matrice nulle de M_n(ℝ), notée M_0. Pour tout k ∈ ℕ, on construit la matrice M_(k + 1) à partir de la matrice M_k de la manière suivante

Les M_k sont donc des variables aléatoires à valeurs dans X_n et l'on considère qu'elles sont définies sur un espace probabilisé commun ( Ω, A, P ). Voici un exemple de réalisation de cette évolution pour n = 2

Pour k ⩾ 1, le nombre de modifications réalisées lors de la k-ième vague est noté N_k. Dans l'exemple ci-dessus : N_1 = 2, N_2 = 0, N_3 = 1, N_4 = 1, N_5 = 0.
On s'intéresse au plus petit indice k pour lequel la matrice M_k ne comporte que des 1 ; on dit alors qu'elle est totalement remplie. Dans l'exemple précédent, ce premier indice vaut 4.
On note q = 1 − p et m = n^2.
IV.B.1) Dans toute cette question on utilise le langage Python. M désigne une matrice carrée d'ordre n. Ses lignes et ses colonnes sont numérotées de 0 à n − 1. L'expression M[i, j] permet d'accéder à l'élément situé à l'intersection de la ligne i et de la colonne j et len( M ) donne l'ordre de la matrice M .
a) Écrire une fonction Somme(M) qui renvoie la somme des coefficients de la matrice M.
b) Écrire une fonction Bernoulli(p) qui renvoie 1 avec la probabilité p et 0 avec la probabilité 1 − p. On pourra utiliser l'expression random() qui renvoie un réel de l'intervalle [ 0,1 [ selon la loi uniforme.
c) À l'aide de la fonction Bernoulli(p), écrire une fonction Modifie(M,p) qui modifie aléatoirement la matrice M suivant le principe décrit au IV.B ci-dessus.
d) Écrire une fonction Simulation(n,p) qui renvoie le plus petit entier k tel que M_k est totalement remplie à partir d'un remplissage aléatoire de la matrice nulle d'ordre n (qui peut être obtenue par zeros((n, n)) ). Il n'est pas demandé de mémoriser les M_k.
IV.B.2) Donner la loi de N_1, puis la loi conditionnelle de N_2 sachant ( N_1 = i ) pour i dans un ensemble à préciser. N_1 et N_2 sont-elles indépendantes?
IV.B.3) Soient i et j dans {1, …, n}. Le plus petit entier k ⩾ 1 tel que le coefficient ligne i, colonne j de M_k vaut 1 est noté T_(i, j) (dans l'exemple ci-dessus : T_(1, 1) = 1 et T_(1, 2) = 3 ). Donner la loi de T_(i, j).
IV.B.4) Pour un entier k ⩾ 1, donner la valeur de P(T_(i, j) ⩾ k)
IV.B.5) Soient r ⩾ 1 un entier et S_r = N_1 + ⋯ + N_r. Que représente S_r ? Donner sa loi (on pourra utiliser la question précédente).
IV.B.6) On note N le plus petit indice k pour lequel la matrice M_k est totalement remplie.
a) Proposer une démarche pour approcher l'espérance de N à l'aide d'une simulation informatique utilisant les fonctions précédentes.
b) Donner une expression de la valeur exacte de cette espérance faisant intervenir q et m.