CCINP - MP 2025 - Mathématiques 2

Éléments de correction

Exercice 1
Q1.
1 def degreMax (d : dict) -> int:
2 return max ([ len(d[s]) for s in d])

Q2.
1 def GrapheInv (d:dict) -> dict:
2 D = {s:[] for s in d}
3 for s in d:
4 for i in d[s]:
5 D[i]. append (s)
6 return D

Q3.
1 def ColorationValide (d : dict , L : list) -> bool:
2 for s in d:
3 for i in d[s]:
4 if L[i]==L[s]:
5 return False
6 return True

Q4. Le graphe étant orienté, chaque arête est parcourue exactement une fois par l’algorithme précédent et il
déclenche une comparaison pour chacune d’entre elle. Si on note M le nombre d’arêtes, la complexité
est donc constante égale à M ; est est donc en O(M) dans le pire des cas.
Si on ne considère que des graphes simples, on a au plus N(N − 1) arêtes, qui correspondent aux couples
(i, j) de sommets distincts. L’algorithme est donc en O(N 2 ), indépendamment du nombre d’arêtes.
Q5.
1 SELECT MAX( duree ) FROM LOCATIONS ;

Q6.
1 SELECT [Link] , [Link] , AVG(L. duree ) AS moyenne_duree
2 FROM FILMS F
3 JOIN LOCATIONS L ON F. codefilm = L. codefilm
4 GROUP BY [Link] , F. nomfilm
5 HAVING AVG(L. duree ) < 2
6 ORDER BY moyenne_duree DESC;

Exercice 2
Q7. On montre par récurrence double sur n ∈ N∗ que Pn est de degré n et de coefficient dominant égal à 2n−1 .
Initialisation :

1 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

 P1 = X est de degré 1 et de coefficient dominant égal à 1 = 21−1 donc la propriété est vraie pour n = 1.
P2 = 2X 2 − 1 est de degré 2 et de coefficient dominant égal à 2 = 22−1 donc la propriété est vraie pour
n = 2.
Hérédité : Soit n ≥ 2 tel que Pk est de degré k et de coefficient dominant égal à 2k−1 pour tout k ∈
Jn − 1; nK. Alors

deg(Pn+1 ) = deg(2XPn − Pn−1 ) = max deg(2XPn ), deg(Pn−1 ) = deg(Pn ) + 1 = n + 1.

En outre, si on note cd(P) le coefficient dominant d’un polynôme P, puisque deg(Pn−1 ) < deg(2XPn ), on
a:
cd(Pn+1 ) = cd(2XPn ) = 2cd(Pn ) = 2 × 2n−1 = 2n ,
d’où l’hérédité.
En conclusion :

∀n ∈ N∗ , deg(Pn ) = n et cd(Pn ) = 2n−1 .

Q8. On montre par récurrence double sur n ∈ N que, pour tout θ ∈ R, Pn (cos(θ)) = cos(nθ).
Initialisation :
Pour n = 0, on a P0 (cos(θ)) = 1 = cos(0 × θ).
Pour n = 1, on a P1 (cos(θ)) = cos(θ).
Hérédité : Soit n ≥ 1 tel que, pour tout θ ∈ R, Pk (cos(θ)) = cos(kθ), pour k ∈ Jn − 1; nK
Alors :

Pn+1 (cos(θ)) = 2 cos(θ)Pn (cos(θ)) − Pn−1 (cos(θ))

= 2 cos(θ) cos(nθ)) − cos((n − 1)θ)
cos((n + 1)θ) + cos((n − 1)θ))
=2 − cos((n − 1)θ)
2
= cos((n + 1)θ),

d’où l’hérédité.
En conclusion :

∀n ∈ N, ∀θ ∈ R, Pn (cos(θ)) = cos(nθ).

P(t)Q(t)
Q9. Soit (P, Q) ∈ R[X]2 et f : t 7→ √ . On a f ∈ C0 (]−1; 1[ , R) et
1−t 2

|P(1)Q(1)| 1
| f (t)| ∼ √ × √
t→1 2 1−t
Z 1
1
or le changement de variable affine u = 1−t montre que √ dt est de même nature que l’intégrale
Z 1 0 1Z−t
1
1 |P(1)Q(1)| 1
1/2
du, qui converge d’après le critère de Riemann. Ainsi, √ × √ dt converge et,
0 u 0 2 1−t
par comparaison pour les fonctions positives, on a :
Z 1
P(t)Q(t)
√ dt converge.
0 1 − t2

2 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

 Le même raisonnement avec le changement de variable u = 1 + t montre que
Z 0
P(t)Q(t)
√ dt converge.
−1 1 − t2
En conclusion :

Z 1
P(t)Q(t)
√ dt converge (absolument).
−1 1 − t2

Q10. ⟨−, −⟩ est symétrique par commutativité du produit dans R, et bilinéaire par bilinéarité de la multiplication
et linéarité de l’intégrale.
Montrons que ⟨−, −⟩ est définie positive. Soit P ∈ Rk [X], on a :
1
P(t)2
Z
⟨P, P⟩ = √ dt ≥ 0
−1 1 − t 2
| {z }
≥0

P(t)2 P(t)2
et, t 7→ √ étant continue positive sur ]−1; 1[, on a égalité si, et seulement si, √ = 0, pour
1 − t2 1 − t2
tout t ∈ ]−1; 1[. Mais dans ce cas, P s’annule sur tout l’intervalle ]−1; 1[ donc admet une infinité de
racines, et donc P est le polynôme nul.
En conclusion :

⟨−, −⟩ définit un produit scalaire sur Rk [X].

Q11. Soit (m, n) ∈ N2 .

On a : Z π Z π
1
cos(nθ) cos(mθ) dθ = cos((n + m) + θ) + cos((n − m)θ) dθ.
0 2 0
— Si m , n, on a m + n , 0 et n − m , 0 donc
Z π #π
sin((n + m)θ) sin((n − m)θ)
"
cos((n + m)θ) + cos((n − m)θ) dθ. = + = 0.
0 n+m n−m 0

— Si m = n.
— Si m = n = 0, alors Z π Z π
cos(nθ) cos(mθ) dθ = dθ = π.
0 0

— Si m = n > 0, alors
Z π #π
1 π 1 sin((n + m)θ) π
Z "
cos(nθ) cos(mθ) dθ = cos((n + m) + θ) + 1 dθ = +θ = .
0 2 0 2 n+m 0 2

En conclusion :

3 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

 π si m = n = 0







Z π
 π



∀(m, n) ∈ N2 , cos(nθ) cos(mθ) dθ =  si m = n > 0

0



 2




 0 sinon.


Q12. Soit (m, n) ∈ N2 . On a Z 1

Pm (t)Pn (t)
⟨Pm , Pn ⟩ = √ dt.
−1 1 − t2
L’application θ 7→ cos(θ) étant une bijection C1 décroissante de [0, π] vers [−1, 1], on peut effectuer le
changement de variable t = cos θ et il vient :
Z π
⟨Pm , Pn ⟩ = Pm (cos θ)Pn (cos θ) dθ
0

et, d’après Q8 et Q11, on a donc :

π si m = n = 0







Z π
 π



⟨Pm , Pn ⟩ = cos(mθ) cos(nθ) dθ =  si m = n > 0

0



 2




 0 sinon.


Puisque deg(P j ) = j pour tout j, la famille (P j )0≤ j≤k est orthogonale dans Rk [X] pour le produit scalaire
défini à la question Q10.
On a p √
∥P0 ∥ = ⟨P0 , P0 ⟩ = π
donc on pose

1 1
E0 = √ P0 = √ .
π π

Pour tout n ∈ N∗ , on a :
π
r
p
∥Pn ∥ = ⟨Pn , Pn ⟩ =
2
donc on pose

r
2
En = Pn .
π

Alors (E0 , . . . , Ek ) est une famille orthonormale de Rk [X]. Elle est donc libre et, par dimension, c’est une
base.
En conclusion :

(E0 , . . . , Ek ) est une base orthonormale de Rk [X].

4 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

 Remarque
Les polynômes Pn étudiés dans cet exercice sont classiques et s’appellent polynômes de Tchebychev de
première espèce. Ils jouent un rôle dans de nombreuses branches des mathématiques, voir par exemple
[Link]

Problème : Matrices de rang 1

Partie I - Exemples
Q13. On observe que
      
  X1   X1   X1 
M = X1 
  ..  , X2 
  ..  , . . . , Xn 
  .. 
. . . 
      
Xn Xn Xn
 
 X1 (ω) 
de sorte que, pour tout ω ∈ Ω, les colonnes de M(ω) sont dans Vect 
 .. 
 .  et donc rg(M(ω)) ≤ 1.

Xn (ω)
Puisque le rang est à valeurs dans N, on a Y(ω) = rg(M(ω)) ∈ {0, 1} et donc :

Y(Ω) ⊂ {0, 1} .

 
 X1 (ω) 
Par ailleurs, Y(ω) = 0 si, et seulement si 
 .. 
 .  est le vecteur nul et donc, les Xi étant des vaiid de loi

Xn (ω)
B(p), on a :  n
\

 Y n
P (Y = 0) = P  [Xi = 0] = P (Xi = 0) = (1 − p)n
i=1 i=1

donc

P (Y = 1) = 1 − (1 − p)n .

En conclusion, on a :

Y ∼ B 1 − (1 − p)n .

n
X n
X
Q14. On a tr(M) = Xi2 mais chaque Xi est de Bernoulli donc Xi2 = Xi de sorte que tr(M) = Xi . Les Xi
i=1 i=1
étant des variables aléatoires indépendantes de loi B(p), on sait alors que :

tr(M) ∼ B(n, p).

5 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

Q15. On a
M 2 = (UU ⊤ )(UU ⊤ ) = U(U ⊤ U)U ⊤
n
X
mais U ⊤U = Xi2 = tr(M) donc
i=1

M 2 = tr(M)UU ⊤ = tr(M)M.

On a donc bien :

M 2 = tr(M)M.

Ainsi, l’événement «M est une matrice de projection» se réalise si, et seulement si, [tr(M) = 1] ⊔ [M = 0]
se réalise. Or, d’après Q15
P (tr(M) = 1) = npqn−1 .
D’autre part, d’après Q13,
P (M = 0) = qn .

Ainsi, si on note Pn (R) l’ensemble des matrices de projection, on a :

P (M ∈ Pn (R)) = (np + q)qn−1 .

Q16. L’événement «M est une matrice de projection» se réalise encore si, et seulement si, [tr(M) = 1]⊔[M = 0]
n
X
se réalise et on a toujours la relation tr(M) = Xi2 . Les Xi étant ici de Poisson, les Xi2 sont à valeurs
i=1
n
X
dans N de sorte que Xi2 = 1 si, et seulement si, exactement l’une des Xi prend la valeur 1, les autres
i=1
prenant la valeur 0. D’autre part, [M = 0] se réalise si, et seulement si chacune des Xi est nulle.
D’une part,
 n 
X 2
P (tr(M) = 1) = P  Xi = 1


i=1
  
  
G n \ n 
= P  [Xi = 1] ∩  [X j = 0]
 i=1  j=1 
j,i
 
 
Xn  Yn  
= (Xi = 1) P X j = 0 

P
| {z }
i=1 
 j=1 | {z }
=λe−λ =e
−λ
j,i

= nλe −nλ
.

D’autre part
 n 
\
P (M = 0) = P  [Xi = 0]


i=1

6 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

 n
Y
= P (Xi = 0)
i=1
Yn
= e−λ
i=1
=e −nλ

Ainsi, si on note Pn (R) l’ensemble des matrices de projection, on a : En conclusion :

P (M ∈ Pn (R)) = (nλ + 1)e−nλ

Q17. On a clairement

rg(J) = 1 et tr(J) = n.

1  n 
   

 1  n 
Si on pose V =  , on a JV =  ..  = nV de sorte que n ∈ Sp(J) et V ∈ En (J).
..
   
 .
  . 
   
1 n
Par ailleurs, si on note (e1 , . . . , en ) la base canonique de Rn , on a J(e1 − ei ) = 0 pour tout i ∈ J2; nK donc

Vect(e1 − e2 , . . . , e1 − en ) ⊂ ker(J) = E0 (J)

et, par dimension, on a donc :

E0 (J) = Vect(e1 − e2 , . . . , e1 − en ).
Ainsi, si on pose
 
 1 1 1 ··· 1 
 1 −1 0 ··· 0 
.
 
.
P =  −1 . . ..
 
1 0 
.. .. .. ..
 

 . . . . 0 

1 0 · · · 0 −1
alors

P−1 JP = diag(n, 0, 0, . . . , 0)
| {z }
n−1 fois

Q18. Considérons la matrice  

 0 1 0 
M =  0 0 0  .
 
 
0 0 0
Alors rg(M) = 1. Par ailleurs, M 2 = 03 et M , 03 donc le polynôme minimal µ M de M est X 2 , scindé
mais pas à racines simples, de sorte que M n’est pas diagonalisable.

7 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

Partie II - Résultats généraux
c1
 
 
 c2 
Q19. Notons C =  ..
 
 la première colonne non nulle de A. Puisque A est de rang 1, toutes ses colonnes sont
 . 
 
cn
dans Vect(C) donc, il existe a1 , a2 , . . . , an réels tels que

A = (a1C|a2C|a3C| · · · |anC)

et donc
c1
 
 
 c2   
A =  ..  × a1 a2 · · · an .
 
 . 
 
cn
Ainsi, on pose :

 
L= a1 a2 · · · an .

Q20. On a
c1
 
 
   c2  X n
LC = ..  = ai ci .

a1 a2 · · · an × 
 .  1=2
 
cn
On observe alors que
n
X n
X n
X
tr(A) = [A]i,i = [aiC]i,1 = ai ci
i=1 i=1 i=1
de sorte que

LC = tr(A).

Alors, par associativité du produit matriciel, il suit de Q19 que :

A2 = (CL)(CL) = C(LC)L = tr(A)CL = tr(A)A.

On a donc bien :

A2 = tr(A)A.

Q21. On sait que rg(A) = 1 donc, d’après le théorème du rang, dim E0 (A) = dim ker(A) = n − 1. Il s’ensuit
que la multiplicité algébrique de 0 est supérieure ou égale à n − 1 et donc que X n−1 divise χA . Puisque
deg(χA ) = n, il existe un réel α tel que

χA = X n−1 (X − α) = X n − αX n−1 .

Par ailleurs, on sait que le coefficient en degré n − 1 de χA est égal à −tr(A) donc α = tr(A) et :

8 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

 χA = X n−1 (X − tr(A)).

D’autre part, il suit de Q20 que X 2 − tr(A)X annule A donc µA divise X(X − tr(A)). Puisque A est de rang
1, elle est non nulle et donc µA , X. D’autre part, puisque A est de rang 1 et que n ≥ 2, A , tr(A)In donc
µA , (X − tr(A)). Il s’ensuit que :

µA = X(X − tr(A)).

Q22. D’après Q21, on a µA = X(X − tr(A)). Ainsi, on a les équivalences suivantes :

A diagonalisable ⇔ µA scindé à racines simples

⇔ X(X − tr(A)) scindé à racines simples
⇔ tr(A) , 0.

On a donc bien :

A diagonalisable ⇔ tr(A) , 0.

Q23. Si im(u) ∩ ker(u) , {0}, alors im(u) ∩ ker(u) est un sous-espace vectoriel non trivial de im(u), mais im(u)
est de dimension 1 donc im(u) ∩ ker(u) = im(u), c’est-à-dire

im(u) ⊂ ker(u).

Soit alors e2 un vecteur non nul de im(u) et e1 ∈ Rn tel que u(e1 ) = e2 . La famille (e1 , e2 ) est libre car
e2 est dans ker(u) et e1 ne l’est pas. Soit G le supplémentaire de Re2 dans im(u) et soit BG = (e3 , . . . , en )
une base de G. Alors B = (e1 , e2 , . . . , en ) est une base de Rn et

 
 0 0 02,n−2 
MatB (u) =  1 0
 
 
0n−2,2 0n−2

Q24. Si im(u) ∩ ker(u) = {0} alors, d’après le théorème du rang, on a :

Rn = im(u) ⊕ ker(u).

Considérons une base B = (e1 , e2 , . . . , en ) adaptée à cette décomposition. Puisque u(e1 ) ∈ im(u) =
Vect(e1 ), il existe un réel α non nul tel que u(e1 ) = αe1 de sorte que

α
!
01,n−1
MatB (u) =
0n−1,1 0n−1

On observe que dans ce cas tr(u) = α , 0.

9 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.

Q25. Soient M et N deux matrices de rang 1 et notons u et v les endomorphismes canoniquement associés.
Si M et N sont semblables, alors on sait que tr(M) = tr(N).
Réciproquement, supposons tr(M) = tr(N).
— Si tr(M) = 0, alors il suit de Q24 que l’on ne peut avoir im(u) ∩ ker(u) = {0}. Alors im(u) ∩ ker(u) ,
{0} et donc M est semblable à la forme normale trouvée en Q23. Le même raisonnement s’applique
à N. Par transitivité de la relation de similitude, M et N sont semblables.
— Si tr(M) , 0, alors il suit de Q23 que l’on ne peut avoir im(u) ∩ ker(u) , {0}. Alors im(u) ∩ ker(u) =
{0} et donc M est semblable à la forme normale trouvée en Q24. Le même raisonnement s’applique
à N. Par transitivité de la relation de similitude, M et N sont semblables.
En conclusion :

Deux matrices de rang 1 sont semblables si, et seulement si, elles ont même trace.

*** Fin du sujet ***

10 Partagé sur [Link] – Licence CC BY-NC-SA 4.0.