X Maths PC 2000

Thème de l'épreuve Évaluation des valeurs propres de la matrice d'adjacence d'un graphe
Principaux outils utilisés polynômes, algèbre linéaire et bilinéaire, combinatoire

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(PDF non trouvé ! |/net/www/doc-solus.fr/www//prepa/sci/adc/pdf/rapports.pdf/2000/PC_MATHS_X_1_2000.rapport.pdf|)

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2000 FILIÈRE PC

PREMIÈRE COMPOSITION DE MATHÉMATIQUES

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

***

On se propose d'étudier une famille de polynômes (polynômes de Krawtchouk) et 
une famille de
matrices (matrices d'adjacence du schéma d'association de Hamming) dont les 
propriétés sont
liées, et applicables àla théorie des codes détecteurs et correcteurs d'erreurs 
dans la transmission
de l'information. (Ces applications ne sont pas abordées dans le problème.)

Les deuæ premières parties sont indépendantes.

***

Dans tout le problème, N désigne un entier naturel non nul.

On prend par convention O! = 1. Si n et le sont des entiers naturels, on pose

Première partie

1. Pour tout k EUR Z, on définit le polynôme 901EUR de la variable X par

1 . .
ËÎ H (X--z) Slk>0
'09'5k--1
"(X): 1 sik=0
0 sik<0.

Évaluer (pk (j) pour chaque entier naturel j.

2. Pour tout entier n tel que 0 S n S N, on définit le polynôme Pn de la 
variable X par

N

Pn(X) = Z(--1)kflPk(X)fin--k(N -- X)-
k=0

a) Calculer P0, P1 et P2.
b) Calculer le degré et le coefficient dominant du polynôme Pn.

c) Montrer que, pour chaque entier j tel que 0 5 j S N,

. " j N --j
... = 2<--1>k(k)(n_k) .

k=0

3. Pour tout entier j tel que 0 5 j 5 N, on considère la fonction fj de la 
variable réelle u,
définie par

N
W) = 2 BMW .
n=0
Montrer que fj(u) = (1 -- u)j(1 + u)N_Ï . \

4. On considère la fonction F de deux variables réelles u et v, définie par

N
F(u,v) = 2 = 2 (N)P(j)Q(J') .

j=0 3

3.) Montrer que < | > est un produit scalaire sur RN [X ]

b) Montrer que (Pn)05ng N est une base orthogonale de R N [X ] muni de ce 
produit scalaire.

2

6. Montrer que, pour tout entier ... tel que 1 5 m 5 N -- 1,
(m + 1)Pm+1(X) -- (N -- 2X)P...(X) + (N -- m+ 1)Pm_1(X) = () .

du '

[On calculera de deux manières différentes le coefficient de um dans (l -- u2)

Deuxième partie

On pose E = {l, 2, . . . , N } et l'on désigne par 'P(E) l'ensemble des parties 
de E. Pour chaque
partie I de E, on note CardI le cardinal de I. Si I et J sont des parties de E, 
on pose

d(I, J) = Card(I A J) ,

où I A J est l'ensemble des points de la réunion I U J qui n'appartiennent pas 
à l'intersection
I D J.

7.a) À quelle condition a--t-on d(I , J ) = 0? À quelle condition a--t-on d(I , 
J) = 1 ?
b) Montrer que d(I A J, I) = Card J.

8. Soient I et J deux parties de E. On pose d(I , J ) = k. Calculer le nombre 
fy'-° de parties A
de E telles que d(I,A) = 1 et d(J, A) = j.

Troisième part ie

On utilise dans cette partie les notations et les résultats des deux premières 
parties.

On suppose 'P(E) muni d'un ordre total _-5. On a donc P(E) = {11,12,.... ,12N} 
où
115125...512N.

Pour tout entier naturel n, on définit une matrice carrée réelle à 2N lignes

An : ((An)pq)lsp52N par

15q52N
1 si d(I ,I ) = n
(An)pq : {O . p q
s1non.

On note ] la matrice identité à 2N lignes.
9.a) Que vaut An pour n > N ? Expliciter A0.

b) Montrer que pour tout entier m tel que 1 5 m 5 N -- 1,
A1Am = (N -- m + 1)A...-1 + (m + 1)Am+1 .

1
10. On pose A : 5(NJ -- A1). Montrer par récurrence sur n que, pour tout entier 
n tel que
0 S n S N,
A" = P,,(A) ,

où les polynômes Pn sont ceux définis et étudiés dans la première partie.

11. Soit i un entier tel que 0 S i S N. Montrer que, si I E P(E) est tel que 
Card] : i, alors
pour tout entier j tel que 0 5 j 5 N,

Pj(i)= Z (_1)Card(IñJ)_

JE'P(E)
Card J=j

12.a) Soient I, J, K E P(E). Montrer que

(_1)Card((mJ)nK) : (_1)Card(InK)(_1)Card(JñK) .

b) Soient I, J E P(E). Montrer que

2 (_1)Card(IñK)(_l)card(_jnK) : 2N si I : J
KGP(E) 0 sinon .

13. Pour tout entier k tel que 0 5 k 5 N, on pose

1 N
Bk = ëÏ\Ï Z Pk(n)An .
n=0

a) Montrer que

(Bk)2=Bk
BkBg=0 SiË%k.

[On pourra utiliser les résultats des questions 11. et 12.].
b) Déterminer la trace et le rang de chaque matrice Bk.
14.3) Pour chaque entier n tel que 0 S n S N, trouver les valeurs propres de la 
matrice A...

b) Déterminer la dimension des sous--espaces propres de la. matrice A1.

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Maths 1 PC 2000 -- Corrigé
Ce corrigé est proposé par Mathieu Dutour (ENS Ulm) ; il a été relu par Brice
Goglin (ENS Ulm) et David Hernandez (ENS Ulm).

Une fois de plus, l'X montre la voie : un problème original qui porte sur 
l'utilisation
de l'algèbre en informatique. Significativement, on
la notation Ckn , qui est
 abandonne

n
franco-francaise, pour la notation internationale
. Le problème n'est pas classique
k
dans l'ensemble, mais on peut se rattraper à différentes questions faciles, 
dispersées
un peu partout.
La première partie, classique, concerne un ensemble de polynômes orthogonaux
Pn . La seconde partie, très courte, porte sur des dénombrements. La troisième 
est
consacrée aux matrices d'adjacences et à leurs valeurs propres.

Indications
I.2.a C'est une question classique, où il faut montrer que deg Pn = n et 
déterminer
le coefficient dominant. On montre d'abord que deg Pn 6 n. Ensuite on
détermine le coefficient de Xn et s'il est non nul cela veut dire que Pn est de
degré n.
I.4.a Le binôme
  de Newton est évidemment très utile dans toute question où il y
n
a des
= Ckn .
k
I.4.b Ce genre de résultat peut être délicat à démontrer, même s'il semble 
relativement clair. Dans ce cas particulier, il faut montrer le résultat pour 
les
fonctions (uv)j .
II Pour ces questions d'ensemble, il peut être utile de faire des dessins.
II.8 Utiliser le fait que A diffère de I par l'ajout ou le retrait d'un seul 
élément.
III.9.b Ce genre de relation matricielle A = B, qui sort d'un contexte où elles
n'existent pas a priori, doit se montrer comme suit : déterminer l'expression
de chacun des termes Apq et Bpq , puis constater l'égalité.
III.10 C'est une récurrence entre les termes m - 1, m et m + 1 qui est utilisée 
; il
faut donc montrer HR0 et HR1 avant d'envisager de montrer HRm+1 .
III.11 Utiliser la question I.2.c.
III.13.a C'est sans conteste la question la plus difficile du problème. Il faut 
montrer
que
(Bk Bl )pq =
puis

Pk (d(Ip , Iq )) =

1
Pk (d(Ip , Iq ))
2N
P

(-1)Card (Ip Iq )J

JP(E)
Card J=k

Il faut intervertir les trois sommes qui apparaissent dans le produit (Bk Bl 
)pq .
Enfin, on peut utiliser la question III.12.b .
III.13.b Question classique qui utilise le fait que si p est un projecteur, 
alors Tr p =
rg p.
III.14.a Il s'agit à nouveau d'une question extrêmement délicate. La famille 
(Bk )06k6N
s'exprime en fonction de la famille (An )06n6N . Il faut donc inverser le 
système linéaire pour obtenir les An en fonction des Bk . Utiliser ensuite la
première partie où l'on montre que les Pk forment une famille orthonormée.
Calculer la norme hPk |Pk i.

I

Les polynômes Pn

I.1 Si j > k, alors
k (j) =

j(j - 1) . . . (j - (k - 1))
j!
=
=
k!
k!(j - k)!

j
k

et si 0 6 j < k, alors k (j) = 0. On a donc dans tous les cas la relation
 
j
 j  N,
k (j) =
k
I.2.a On a 0 (X) = 1, 1 (X) = X et 2 (X) =

X(X - 1)
d'où l'on tire
2

P0 (X) = 0 (X)0 (N - X) = 1
P1 (X) = 0 (X)1 (N - X) - 1 (X)0 (N - X) = N - 2X
ce qui donne

P0 (X) = 1

et

P1 (X) = N - 2X

P2 (X) = 0 (X)2 (N - X) - 1 (X)1 (N - X) + 2 (X)0 ((N - X)
X(X - 1)
(N - X)(N - X - 1)
- X(N - X) +
2
2
X2 - X(2N - 1) + N(N - 1) - 2XN + 2X2 + X2 - X
=
2
=

P2 (X) =

4X2 - X(4N) + N(N - 1)
2

I.2.b Le degré de k est k, le degré de n-k est n-k, donc le degré de k (X)n-k 
(N-
X) est n. Le degré d'une somme étant inférieur au maximum des degrés, deg Pn 6 
n.
Calculons le coefficient du terme de degré n. S'il n'est pas nul, alors le 
degré est
1
égal à n. Le coefficient de Xk dans k est ; le coefficient de Xn-k dans n-k (N 
- X)
k!
(-1)n-k
est
; par suite, le coefficient de Xn dans Pn est :
(n - k)!
k=N
P

(-1)k

k=0

k=N
P
k=0

Ce qui donne

(-1)k

k=N
P 1
1 (-1)n-k
1
= (-1)n
k! (n - k)!
k=0 k! (n - k)!
 
n k=N
(-1) P n
=
n! k=0 k

1 (-1)n-k
(-1)n n
=
2
k! (n - k)!
n!
(-1)n 2n
n!

I.2.c On utilise la question I.1 et on obtient

j
N-j
Pn (j) =
(-1) k (j)n-k (N - j) =
(-1)
k
n-k
k=0
k=0
k=N
P

k=N
P

k

k

I.3 On utilise la formule du binôme de Newton sur la fonction
(
R - R
fj :
u 7- (1 - u)j (1 + u)N-j
 
j
Le coefficient de uk dans (1 - u)j est (-1)k
. Le coefficient de un-k dans
k

N-j
(1 + u)N-j est
, donc le coefficient de un dans (1 - u)j (1 + u)N-j est la
n-k
somme sur tous les k possibles.

k=N
P
N-j
k j
Ainsi,
(-1)
= Pn (j)
k
n-k
k=0
Pour l'origine des polynômes de Krawtchouk et des analogues, on peut se
référer à l'ouvrage Sphere Packings, lattices and Groups de J.H. Conway et
N.J.A. Sloane, Édition Springer (p. 255), qui aborde également les questions
de codes.
I.4.a On utilise le résultat précédent :
 
N
P
N
F(u, v) =
fj (u)fj (v)
j=0 j
 
N
P
N
=
(1 - u)j (1 + u)N-j (1 - v)j (1 + v)N-j
j=0 j
 
N
P
N
=
[(1 - u)(1 - v)]j [(1 + u)(1 + v)]N-j
j
j=0
= [(1 - u)(1 - v) + (1 + u)(1 + v)]N

= (2 + 2uv)N
F(u, v) = 2N (1 + uv)N
ce qui donne la formule attendue, avec
 = 2N

et

=N

I.4.b Si on prend un terme Qj = (uv)j alors, en différentiant :
 a+b Qj
 a uj  b v j
j!
j!
=
=
uj-a
v j-b
a
b
u v
ua v b
(j - a)!
(j - b)!
Cette quantité ne peut être non nulle en 0 que si j - a = 0 et j - b = 0, 
auquel cas
elle vaut (a!)2 . La fonction F s'exprime comme un polynôme en uv :
 
j=N
P N
F(u, v) = 2N
(uv)j
j
j=0