Centre Des Classes Préparatoires Lm6e Benguerir: Devoir Libre N 3 Novembre 2023

Centre Des Classes Préparatoires Lm6e Benguerir
Devoir libre N◦ 3
Novembre 2023
Classes : MPSI 4
Problème 1 : Les matrices de permutation

Soit n ∈ N∗ . On note alors Sn l’ensemble des bijections de {1, . . . n} dans lui-même.
( Pour σ ∈ ℑn , on note Mσ
1 si i = σ(j)
la matrice de Mn (R) définie par ∀(i, j) ∈ {1, . . . n}2 , [Mσ ]i,j = δi,σ(j) = Une telle matrice
0 sinon
est alors appelée une matrice de permutation.
PARTIE 1 : Généralités
1. Déterminer Mid .
2. Montrer que pour tout (σ, τ ) ∈ Sn2 , Mσ◦τ = Mσ Mτ . En déduire que pour tout σ ∈ Sn , Mσ est inversible,
et déterminer son inverse.
3. En utilisant la trace, montrer que pour tous σ, τ ∈ ℑn , σ ◦ τ et τ ◦ σ ont le même nombre de points fixes.
4. Soit M ∈ Mn (R). Montrer que M est une matrice de permutation si et seulement si sur chaque ligne et
chaque colonne de M se trouvent exactement un coefficient égal à 1 et n − 1 coefficients nuls.
PARTIE 2 : Une caractérisation des matrices de permutation

On souhaite montrer dans cette partie le résultat suivant : si M ∈ GLn (R) est à coefficients dans N, alors il y
a équivalence entre :
i) M est une matrice de permutation
ii) l’ensemble de tous les coefficients de toutes les matrices M k , k ∈ N est fini.
1. Montrer que i) ⇒ ii).
2. On suppose à présent que M est une matrice inversible, à coefficients dans N, qui satisfait ii).
(a) Prouver que M k , k ∈ N est fini et en déduire que l’application k 7→ M k n’est pas injective sur N.

(b) Prouver alors que M −1 est à coefficients dans N.

(c) En considérant les coefficients de M M −1 = In , montrer que M est une matrice de permutation.
PARTIE 3 : Points extrémaux de l’ensemble des matrices bistochastiques.

Une matrice A = (ai,j )1⩽i,j⩽n ∈ Mn (R) est dite bistochastique si tous ses coefficients sont positifs, et que
la somme des coefficients de chaque ligne et chaque colonne de A est égale à 1 . On note En l’ensemble
des matrices bistochastiques de Mn (R). On dit qu’une matrice M ∈ En est un point extrémal de En si
∀(A, B) ∈ En2 , M = A+B
2 ⇒ A = B = M.
1. Montrer que En est un ensemble convexe, c’est-à-dire que ∀(A, B) ∈ En2 , ∀λ ∈ [0, 1], λA + (1 − λ)B ∈ En .
2. Prouver que pour σ ∈ ℑn , Mσ est un point extrémal de En .
3. On souhaite à présent prouver la réciproque, à savoir que tout point extrémal de En pst une matrice de
permutation. On raisonne par l’absurde, et on suppose que M = (mi,j )1⩽i,j⩽n est un point extrémal de
En qui n’est pas une matrice de permutation.
(a) Justifier qu’il existe (i0 , j0 ) ∈ {1, . . . , n}2 tel que mi0 ,j0 ∈] 0, 1[.
1
(b) On définit deux suites (ik ) et (jk ) de la manière suivante :
• si k est pair, alors ik+1 = min {i ∈ {1, . . . , n}\{ik }/ mi,jk ∈]0, 1[} et jk+1 = jk
• si k est impair, alors ik+1 = ik et jk+1 = min {j ∈ {1, . . . , n}\ {jk } / mik ,j ∈] 0, 1[}
Justifier que ces deux suites sont bien définies et qu’il existe deux entiers p < q tels que (ip , jp ) =
(iq , jq ).
Considérons alors une suite finie (u0 , v0 ) , (u1 , v1 ) , . . . , (uN , vN ) de couples de {1, . . . , n}2 avec N ⩾ 2
et telle
• pour tous 0 ⩽ p < q ⩽ N − 1, (up , vp ) ̸= (uq , vq )
• (u0 , v0 ) = (uN , vN )
• ∀k ∈ {0, . . . , N }, muk ,vk ∈]0, 1[
• ∀k ∈ {0, . . . , N −2}, (uk = uk+1 ̸= uk+2 et vk+1 = vk+2 ) ou (vk = vk+1 ̸= vk+2 et uk+1 = uk+2 )
et de longueur minimale parmi les telles suites.
(c) Prouver que N est pair.
(d) On note alors P la matrice de Mn (R) telle que
si ∀k ∈ {0, . . . , N − 1}, (i, j) ̸= (uk , vk )


 0
∀(i, j) ∈ {1, . . . , n}2 , [P ]i,j = +1 si ∃k ∈ {0, . . . , N − 1}, (i, j) = (uk , vk ) et k ≡ 0 (mod2)
−1 si ∃k ∈ {0, . . . , N − 1}, (i, j) = (uk , vk ) et k ≡ 1 (mod2)

Prouver que la somme des coefficients de chaque ligne et chaque colonne de P est nulle.
(e) En considérant les matrices A = M − εP et B = M + εP pour ε suffisamment petit, aboutir à une
contradiction.
(f) Conclure
Problème 2 : Nombres réels

On dit que deux réels x et y sont incommensurables, si x
y / Q ou
∈ y
x / Q. Dans tout le problème x désigne un
∈
réel irrationnel. On définie la suite (Fn )n≥0 par :
Fn = nx − E(nx), pour tout n ∈ N∗ .
E(nx) est la partie entière de nx et Fn sa la partie fractionnelle. On considère l’ensemble A = {Fn : n ∈ N∗ }.

On se propose de montrer que A est dense dans [0, 1], puis donner quelques applications.
Partie I : A n’a pas de minimum

1. Montrer que A ⊂]0, 1[ et en déduire que inf A existe.
2. Soit n ∈ N∗ . Montrer que F1n ∈
/ Q.

3. Montrer que si k = E F1n , alors Fn(k+1) = (k + 1)Fn − 1.
4. En déduire que A n’admet pas de plus petit élément.
Partie II : La borne inférieure de A est nulle

On note α = inf A.
5. Vérifier que, pour tout n ∈ N∗ , la borne inférieure de An = {Fm : m > n} est égale à α.
6. Montrer que pour tout ε > 0, il existe n, m ∈ N, (m > n), tel que : 0 < Fn − Fm < ε.

7. Posons γ = Fn − Fm . Montrer que γ1 ∈ / N. On note ℓ = E γ1 .
8. Montrer que Fℓ(m−n) = 1 − ℓγ.

9. En déduire que que la borne inférieure de A est nulle.
Partie III : A est dense dans [0, 1]
2
Soient ε > 0 et a, b deux réels [0, 1] tels que 0 < a < b et ε < b − a.
10. Justifier l’existence d’un entier n tel que Fn < ε. On considère l’ensemble Γ = {k ∈ N : a < kFn < b}.
11. Montrer que Γ admet un plus petit élément qu’on note p.
12. Montrer que Fpn = pFn .

13. En déduire que A est dense dans [0, 1].
Partie IV : Applications
Considérons maintenant z ∈ R et y ∈ R+∗ incommensurables. On alors x = z
y / Q et on note Ay,z
∈
l’ensemble
Ay,z = {yFn = nz − yE(nx) : n ∈ N} .
14. Montrer que l’ensemble Ay,z est dense dans [0, y].
15. (a) Montrer que A2π,1 = n − 2πE 2π n

: n ∈ N est dense dans [0, 2π].

(b) En déduire que S = {sin(n) : n ∈ N} et C = {cos(n) : n ∈ N} sont denses dans [−1, 1].

Centre Des Classes Préparatoires Lm6e Benguerir: Devoir Libre N 3 Novembre 2023

Transféré par

Droits d'auteur :

Formats disponibles

Centre Des Classes Préparatoires Lm6e Benguerir: Devoir Libre N 3 Novembre 2023

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Centre Des Classes Préparatoires Lm6e Benguerir: Devoir Libre N 3 Novembre 2023

Transféré par

Droits d'auteur :

Formats disponibles

Centre Des Classes Préparatoires Lm6e Benguerir

Problème 1 : Les matrices de permutation

PARTIE 2 : Une caractérisation des matrices de permutation

(b) Prouver alors que M −1 est à coefficients dans N.

PARTIE 3 : Points extrémaux de l’ensemble des matrices bistochastiques.

si ∀k ∈ {0, . . . , N − 1}, (i, j) ̸= (uk , vk )

Problème 2 : Nombres réels

Fn = nx − E(nx), pour tout n ∈ N∗ .

E(nx) est la partie entière de nx et Fn sa la partie fractionnelle. On considère l’ensemble A = {Fn : n ∈ N∗ }.

Partie I : A n’a pas de minimum

4. En déduire que A n’admet pas de plus petit élément.

Partie II : La borne inférieure de A est nulle

8. Montrer que Fℓ(m−n) = 1 − ℓγ.

Partie III : A est dense dans [0, 1]

12. Montrer que Fpn = pFn .

15. (a) Montrer que A2π,1 = n − 2πE 2π n

Vous aimerez peut-être aussi