CCP Maths 2 MP 2000

Thème de l'épreuve Étude de familles de matrices
Principaux outils utilisés algèbre linéaire et bilinéaire

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Énoncé obtenu par reconnaissance optique des caractères


SESSION 2000

A

CONCOURS COMMUNS IP0lYÎECHNIOIIES

ÉPREUVE SPÉCIFIQUE-FILIÈRE MP

MATHÉMATIQUES z

DURÉE : 4 heures

Les calculatrices programmables et alphanumériques sont autorisées, sous 
réserve des conditions
définies dans la circulaire n°99-018 du 01.02.99.

Préambule

Dans ce problème, on se propose d'étudier des familles de matrices que l'on 
rencontre lors de la
résolution numérique de problèmes relatifs à des équations aux dérivées 
partielles de type
elliptique par des méthodes de différences finies.

Matrices irréductibles - Matrices à diagonales faiblement ou fortement 
dominantes.

Notations :
Dans tout le problème, on suppose que N est un entier supérieur ou égal à 2.
MN (R) est l'ensemble des matrices carrées réelles à N lignes et N colonnes, 
MN_p (R)

l'ensemble des matrices réelles à N lignes et P colonnes.

IN est la matrice unité de MN (R). SN (R) est l'ensemble des matrices 
symétriques à N lignes et

Ncolonnes. Si Ae MN (R), (Ae 5N(R) @ 'A = A).

SiA appartient à MN (R) on pourra écrire A = ("g") i: 1,...,N j= 1,...,N .

aij étant l'élément de la i--ème ligne et de la j-ème colonne de A.

2
u,v l--> u v de (RN) dans R dési ne le roduit scalaire euclidien canonique de 
RN. On
N g P

identifiera RN et M,... (R) et pour A & MN (R), v & MN,1 (R) on écrira par 
exemple (Avlv)N le
produit scalaire des éléments de RN correspondants: on a donc, en raison de 
l'identification

(Avlv)N : 'vAv.

WN est l'ensemble des N premiers entiers strictement positifs.

Rappel : une matrice réelle symétrique est dite positive (définie positive) si 
ses valeurs propres
sont positives (strictement positives).

Tournez la page S.V.P.

Définition 1 :

Soient (el,e2,...,eN) la base canonique de RN et O' une permutation de 
l'ensemble {1,2,...,N}.
On appellera matrice de permutation PÔ associée à 6, la matrice Pc de MN (R) 
telle que

Pcei : eo(i)- Alors P5 = (51.6...) où ô,-j est le symbole de Kronecker.

Définition 2 :

Soit A 6 MN (R). On dit qu'une matrice A = ("i/') est irréductible si pour tout 
couple (S, T) de
parties de WN telles que S (\ T= @ et S U T : WN, il existe un élément aij # 0 
avec t' e S et
j e T.

Dans le cas contraire on dira que A est réductible.

Définition 3 :

A & MN (R) A : (a,-j) est à diagonale faiblement dominante si :

N
1) pour tout indice i & WN, la,-il Z Zlaijl
J'=l
j=ti
N
2) pour au moins un indice i e WN, lah-' > 2'"Ül

j=1
j;=i

Définition 4 :

N
A & MN (R) est à diagonale fortement dominante si, pour tout indice i e WN, 
|ail--l > Elu,"

j=l
j1=i

_
Question 1-1

a) Soient o et 6' deux permutations de l'ensemble WN.
a.1) Montrer que P6 Po, : PGO, .

a.2) Montrer que PC est inversible et que P: : PG_. .

a.3) Montrer que Pg1 : [PC.

b) Soit AeMN (R) et POEMN (R) la matrice associée à la permutation 6. On définit

B : pc--1A po : (bij). Exprimer b,, à l'aide de o.

0) Montrer que Ae MN (R) est irréductible si et seulement s'il n'existe pas de 
matrice de

permutation Po telle que PO-- 1APÔ soit de la forme:

_1 F 0
POAPG=G H

où F et H sont des matrices appartenant respectivement à MP (R) et MN_p (R) et 
0 une
matrice dont tous les éléments sont nuls.

Question 1-2

F 0
G H
MN_p(R) et sont inversibles. Résoudre le système linéaire CX =U où X & MN,] (R) 
est la

matrice des inconnues et U & MN,} (R) est donnée. On utilisera pour cela une 
décomposition

a) Soit C 6 MN (R) telle que C =( ) où F et H appartiennent respectivement à M 
F (R) et

U1 X1
convenable de X et de U en blocs U = , X = .
U2 X2

b) On suppose que A & MN (R) est réductible. Proposer une méthode de résolution 
du système
AX : U .

Question 1-3

On veut montrer que A & .'MN (R) est irréductible si et seulement si la 
propriété (P) suivante est
vérifiée :
(P) pour tout couple (i, j) d'indices distincts de WN , "tj # 0 ou alors il 
existe un entier s

et des indices i],i2,...,is tels que le produit aülaili7 ...a--

, - soit non nul.
.r--l'x

a...-

a) Etablir que la condition est suffisante.

b) On suppose maintenant que Ae MN (R) est irréductible. Pour chaque indice 
ieWN, on
définit X ,- comme l'ensemble des indices j de WN tels que :

l) j;fii
2) soit a,-]- #0

soit il existe il ,...,is tels que le produit aiilail,--2 "'aiç_1içaiçj soit 
différent de 0.

Montrer que X ,- : WN \{i} et en déduire que la condition est nécessaire.
Tournez la page S.V.P.

Question 1-4

Le concept d'irréductibilité peut être illustré graphiquement.
Soit AG MN(R), A=(aij) et {Fj- l i GW} un ensemble de N points distincts du 
plan. Pour

. . 2 \ . .
chaque couple (1,1) EUR (WN) tel que aÿ- # 0, on trace une fleche allant du 
pornt P,- vers le pomt
Pj. Si ail» et a ji sont non nuls, il y aura une flèche du point B-- vers le 
point Pj et une autre de

Pj vers P,-- . Si a,--,-- $ 0 on pourra tracer une boucle allant de P,- vers 
lui--même.

Pj

Pi
#0

i

au

CZÙ'$O et afi$0

On associe ainsi à chaque matrice ce que l'on appelle un graphe orienté.
En étudiant les graphes associés aux deux matrices suivantes :

1 0 1
1 1 1
0 1 0
0 0 1
0 0 1
donner une interprétation graphique du caractère réductible ou irréductible de 
chacune d'elles.

Deuxième partie

Question 2-1
Soit AEMN(R) à diagonale fortement dominante; soit UGMN,1(R) tel que AU :O

"1
U = E ; soit i, un indice tel que lu,--i: max{lull,...,\uN'}. En considérant la 
i-ème ligne du

"N
produit AU montrer que l'on a nécessairement U = 0. Que peut-on en déduire pour 
det A '?

Question 2-2

On suppose que A EUR M N (R) est irréductible et à diagonale faiblement 
dominante.

a) Montrer qu'alors pour tout indice i & WN , \aHI > O.

b) Montrer que det A # 0. Pour cela, on raisonnera comme dans la question 2--1 
et on montrera
d'abord que si AU : 0, tous les éléments de la matrice colonne U sont 
nécessairement égaux

en valeur absolue.

Question 2-3

a) Si A EUR SN (R) est une matrice dont les éléments diagonaux sont ?. 0 et si, 
de plus, elle est à
diagonale faiblement dominante, montrer que toutes les valeurs propres de A 
sont 2 0 .

b) Si, de plus, A est irréductible ou inversible, on montrera que toutes les 
valeurs propres de A sont
strictement positives.

Troisième partie

Définition 5 :
Une matrice A & SN (R) est une L-matrice si :
l) pour tout indice i & WN , on a a,,- > 0

2 . .
2) pour tout couple d'indices (i, j) EUR (WN) tels que 1 $ ] , on a aij < 0

Définition 6 :
Une matrice A & 5N (R) est une S-matrice si :
1) A est définie positive,

2 . .
2) pour tout couple d'indices (i,j) & (WN) tels que 1 $ ] , on a % < 0

Définition 7 :
Une matrice A & SN (R) est une M-matrice si :

2 . .
l) pour tout couple d'indices (i,j) & (WN) tels que 1 $ ] , on a aij < 0 ,
2) A est inversible,
3) tous les éléments de A_1 sont 20.

Question 3-1

a) Soit A & SN (R) définie positive, montrer qu'alors a,--, > 0 pour tout 
indice i & WN . En déduire
que A EUR 5 N (R) est une S-matrice si et seulement si A est une L-matrice 
définie positive.

b) Montrer que toute M--matrice est une L-matrice.

Tournez la page S.V.P.

c) Montrer que si A & SN (R) est une L-matrice
l) irréductible,
2) à diagonale faiblement dominante,
alors A est une S-matrice.

Question 3-2

Le spectre de Q est, par définition, l'ensemble des valeurs propres réelles ou 
complexes de Q.

Sp(Q) = {À & C/ det(Q -- 7JN ): O} . On appelle alors rayon spectral de Q, S 
(Q) : max(lM).
ÀeSp Q

a) Si Q & MN (R), montrer que la série EQ" est convergente si et seulement si S 
(Q) < 1 .
k20

On admettra l'équivalence : Q" Î;----> 0 «: S (Q) < 1.

Dans toute la suite de la question 3-2, on considère une L-matrice A d'ordre N 
et D la matrice
diagonale ayant la même diagonale que A, donc définie par :

2
Pour tout couple d'indices (i , j) & (WN) tels que i # j, on a d,-]- = 0

Pour tout indice i & WN , on a dû : a,--,--

Soit C = (cg) appartenant à MN(R), telle que A=D--C et soit 8: D_1C (on 
justifiera

l'existence de D_l).
On suppose que S (B) < 1.

--1
b) Justifier le fait que IN -- B est inversible et montrer que tous les 
éléments de (IN -- B) sont
positifs ou nuls.

c) Montrer que A est inversible et que A est une M--matrice.

Question 3-3

Si D est une matrice diagonale à coefficients diagonaux strictement positifs, 
on définit DV2 et
' 1

il" et pour
V dii

D--l/2 matrices diagonales dont les éléments diagonaux sont respectivement d

tout indice i & WN .

Soit A une M--matrice.
A
On définit D, C, B comme à la question précédente et Ae£MN (R) par

A A A
A = D'V2AD"'/2 = IN - D"V2CD--V2 et B 6 MN (R) par B = Dl/2BD"V2.

A
a) Montrer que A est une M--matrice et que :

A--l A---l A A2 Am A--1Am+l
(A) =(lN--B] =IN+B+(B) +....+(BJ +(lN--B) (B) pour t0Ut entier '"

strictement positif.

/\

A "1
b) Soit G... G MN (R) définie par: G... : IN +B+....+(B) . Montrer que tous les 
éléments de

G... sont positifs et majorés indépendamment de m.

c) En déduire que S(B) < 1.

Question 3-4

Soit A & SN (R) une S--matrice.
On utilise les mêmes notations qu'en 3-2 et 3-3.

. . _ --l _
a) Montrer que A est 1nversrble et que A l : (IN -- B) D ' .
b) On veut maintenant montrer que S ( B) < 1 ce qui suffira pour établir que 
toute S--matrice est une

M--matrice.

A
bl) Montrer que A est définie positive.
b2) En supposant S (B) 2 l, montrer que l'on est conduit à une contradiction et 
que
donc toute S-matrice est une M--matrice. On admettra que si Q & MN (R) a tous

ses éléments positifs ou nuls, alors, il existe 11 & Sp(Q) tel que u = S (Q)

Fin de l'énoncé.

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



CCP Maths 2 MP 2000 -- Corrigé
Ce corrigé est proposé par Brice Goglin (ENS Lyon) ; il a été relu par Guilhem
Bichot (Mines de Paris) et Francesco Colonna-Romano (ENS Ulm).

Le but du problème est d'étudier certaines familles de matrices.
Dans une première partie, on s'intéresse à la réductibilité des matrices. 
Ensuite,
on étudie cette propriété sur des matrices à diagonale faiblement ou fortement 
dominante. Dans la troisième partie, on étudie trois familles de matrices qui 
satisfont
certaines conditions sur leurs coefficients.
Cette épreuve n'est pas très difficile, et parfois assez calculatoire. Les 
seules compétences requises sont quelques connaissances en algèbre linéaire et 
bilinéaire des
espaces vectoriels réels de dimension finie, et quelques notions sur l'étude 
des séries
géométriques de matrices.
Les parties sont assez largement indépendantes.

Indications
1-1.a.3 Remarquer que les permutations sont des bijections et en déduire que 
i-1 (j) =
(i)j .
1-1.c Partitionner WN en {1, . . . , P} et {P + 1, . . . , N}.
1-3.a Prendre (i, j)  S × T, et remarquer que les indices i, i1 , . . . , is , 
j sont dans S
puis dans T.
1-3.b Prendre S = {i} et T = WN - {i}. Choisir i1 tel que aii1 6= 0 et faire 
passer
i1 de T à S. Réitérer le processus et remarquer que j va forcément passer de
T à S à une des N - 1 étapes.
2-1 Expliciter la nullité du ie terme du produit AU.
3-1.b Écrire la nullité du terme (i, j) du produit AA-1 pour i 6= j.
3-2.a Remarquer que Q - IN est inversible et étudier la convergence de la suite
n
P
(Q - IN )
Qk .
k=0

3-2.b Déterminer le signe des coefficients de B et de ses puissances, puis 
appliquer
la question 3-2.a à la série des puissances de B.
3-3.c Utiliser la caractérisation obtenue à la question 3-2.a.
b est symétrique, positive puis définie positive.
3-4.b.1 Montrer que A

3-4.b.2 Utiliser une valeur propre de IN - B négative et un vecteur propre 
associé.

Première partie

1-1.a.1 Soient  et   deux permutations de l'ensemble WN . Soient i et j deux
éléments de WN . Évaluons l'élément x situé sur la ie ligne et la j e colonne 
de la
matrice produit P P .
On a

N
P

x=

(P )ik (P )kj

k=1

Par définition de P , on a (P )ik = i(k) .
Donc

x=

N
P

i(k) k (j)

k=1

Le terme k (j) est non nul si et seulement si k =   (j). Il vaut alors 1. La 
somme
citée ci-dessus ne comporte donc que le terme correspondant au cas k =   (j).
D'où

x = i( (j)) = (P )ij

Or, ce terme (P )ij est exactement la valeur de l'élément situé sur la ligne i 
et
sur la colonne de j dans la matrice P .
On a donc

P P = P

1-1.a.2 Les permutations de WN sont, bien entendu, des bijections et sont donc
inversibles. On peut donc appliquer la formule précédente à une permutation et à
son inverse.
On obtient

P P-1 = P-1 = PId

La matrice PId de la permutation identité est en fait la matrice des symboles de
Kronecker. C'est donc la matrice identité IN .
Donc

P P-1 = IN

Comme les matrices considérées ici sont carrées, on peut en déduire
-1

(P )

= P-1

1-1.a.3 Les permutations étant des bijections, on a i = j si et seulement si 
(i) =
(j). Les symboles de Kronecker ij valent donc également (i)(j) . Si on applique
cette remarque avec  -1 (j) à la place de j, on déduit
i-1 (j) = (i)j
(i)j est en fait le terme situé sur la ligne i et la colonne j dans la 
transposée de
la matrice P .
Les termes de la transposée de P sont donc les i-1 (j) , c'est-à-dire les termes
de P-1 .
Donc

t

P -1 = P-1 = P
P est une matrice orthogonale.

1-1.b Soient i et j deux indices.

On a

bij =

N
P

P-1

k=1

(AP )kj

N
P

A(i)k (P )kj

ik

est le symbole de Kronecker i-1 (k) . Il ne reste donc dans la
Le terme P-1

ik
somme que le terme vérifiant i =  -1 (k), c'est-à-dire k = (i).
Donc

bij = (AP )(i)j =

k=1

De la même façon, il ne reste dans cette somme que le terme tel que k = (j).
D'où

bij = A(i)(j)
Comme on vient de le voir, les matrices P sont orthogonales. Ce sont donc
des matrices de changement de base orthonormée. En fait, il s'agit d'une
permutation des vecteurs de base de l'espace. On comprend donc d'où vient
la formule que l'on vient d'obtenir.

1-1.c Supposons qu'il existe une matrice de permutation P telle que

F O
-1
P AP =
G H
avec F  MP (R), H  MN-P (R) et O nulle.

Alors pour tout couple (i, j) vérifiant 1 6 i 6 P et P < j 6 N, on a P-1
 AP ij =
0.
D'après la question précédente, on en déduit pour 1 6 i 6 P et P < j 6 N
A(i)(j) = 0
Considérons l'ensemble S des images des entiers 1, . . . , P par  et T celui de
l'image de P + 1, . . . , N par . Les ensembles 1, . . . , P et P + 1, . . . , 
N forment une
partition de WN . Or,  réalise une bijection de WN , S et T forment donc une 
partition
de WN .
On a donc obtenu deux ensembles S et T d'intersection vide et d'union WN , tels
que pour tout couple (i, j) de S × T, Aij = 0. A est donc réductible.
On constate que ce raisonnement utilise des équivalences à chaque étape. Pour
construire la permutation , il suffit de faire correspondre S à un ensemble {1, 
. . . , P}
et T à {P + 1, . . . , N}.
On a ainsi montré l'équivalence demandée.

F O
-1
A est irréductible   telle que P AP =
G H
1-2.a Notons U1 le vecteur constitué des P premières composantes de U et U2 
celui
composé des N - P dernières composantes. Notons de la même façon X1 et X2 .

F O
X1
FX1
On a
=
G H
X2
GX1 + HX2
Résoudre le système CX = U revient donc à résoudre les deux systèmes FX1 = U1
et GX1 + HX2 = U2 .
On a donc

X1 = F-1 U1