CCINP Maths 2 MP 2000

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é.