Matrices - IGM

Les vecteurs Les matrices Multiplication matricielle Type de matrices Proprietes

Matrices

Vincent Nozick

Vincent Nozick Matrices 1 / 47


Les vecteurs

Un vecteur (colonne) : x =

x1x2...xn



Vecteurs et transpose

x =

x1x2...xn

x> =(x1 x2 · · · xn

)

Autrement dit: x1x2...xn

=(x1 x2 · · · xn

)>



Addition de vecteurs

x =

x1x2...xn

y =

y1y2...yn

x+ y =

x1 + y1x2 + y2

...xn + yn

Conditions : x et y sont de meme dimension.



Produit scalaire

x =

x1x2...xn

y =

y1y2...yn

produit scalaire :

x> · y = x1y1 + x2y2 + · · ·+ xnyn=∑n

i=1 xiyi

Conditions : x et y sont de meme dimension.



Produit scalaire

Propriete geometrique :

Le produit scalaire est l’intensite (signee) de la projection d’un vecteursur un autre.



Produit scalaire

Propriete geometrique :

u · v = ‖u‖‖v‖ cosα

ou α est l’angle entre u et v (valable pour toutes dimensions).

Applications geometriques :

→ trouver l’angle entre 2 vecteurs : α = ± cos−1

(u · v‖u‖‖v‖

)

→ trouver la projection de u sur v : projv(u) =u · v‖v‖

· v

‖v‖



Produit vectoriel

x =

x1x2x3

y =

y1y2y3

z = x× y =

x2y3 − x3y2x3y1 − x1y3x1y2 − x2y1

Conditions : defini uniquement en dimension 3.



Norme de vecteurs

Proprietes :

• ‖x‖ > 0 ssi x 6= 0 et ‖x‖ = 0 ssi x = 0

• ‖kx‖ = |k|.‖x‖• ‖x+ y‖ ≤ ‖x‖+ ‖y‖

Norme L1 : ‖x‖1 =∑n

i=1 |xi| (norme de Manhattan)

Norme L2 : ‖x‖2 =√x21 + ...+ x2n (norme euclidienne)

Norme Lp : ‖x‖p =(∑n

i=1 |xi|p) 1

p

Norme L∞ : ‖x‖∞ = max(|x1|, ..., |xn|

)Vincent Nozick Matrices 9 / 47


Les matrices

Une matrice : M =

m11 m12 m13

m21 m22 m23

m31 m32 m33



Les matrices

Element d’une matrice : Mij

M =

m11 m12 m13

m21 m22 m23

m31 m32 m33

︸︷︷︸

j

i

i : lignesj : colonnes



Addition matricielle

M =

m11 m12 m13

m21 m22 m23

m31 m32 m33

N =

n11 n12 n13n21 n22 n23n31 n32 n33

A = M+ N =

m11 + n11 m12 + n12 m13 + n13m21 + n21 m22 + n22 m23 + n23m31 + n31 m32 + n32 m33 + n33

Aij = Mij + Nij → O(n2)



Multiplication matrice-vecteur

y = Mx =

m11 m12 m13

m21 m22 m23

m31 m32 m33

x1x2x3

=

m11x1 +m12x2 +m13x3m21x1 +m22x2 +m23x3m31x1 +m32x2 +m33x3

Mx =

m>1•xm>2•xm>3•x

→ produit scalaire→ produit scalaire→ produit scalaire

ou m>i• correspond a la ieme ligne de M



Multiplication vecteur-matrice

y> = x>M =(x1 x2 x3

) m11 m12 m13

m21 m22 m23

m31 m32 m33

=

m11x1 +m21x2 +m31x3m12x1 +m22x2 +m32x3m13x1 +m23x2 +m33x3

>

x>M =

x>m•1x>m•2x>m•3

> → produit scalaire→ produit scalaire→ produit scalaire

ou m•j correspond a la jeme colonne de M



Produit exterieur

Produit scalaire : x>y = u

Produit externe : xy> = A

x1x2...xn

(y1, y2, · · · , ym) =

x1y1 x1y2 · · · x1ymx2y1 x2y2 · · · x2ym

......

......

xny1 xny2 · · · xnym

Aij = xiyj



Multiplication matricielle

A = MN =

m11 m12 m13

m21 m22 m23

m31 m32 m33

n11 n12 n13n21 n22 n23n31 n32 n33

=

m>1•n•1 m>1•n•2 m>1•n•3m>2•n•1 m>2•n•2 m>2•n•3m>3•n•1 m>3•n•2 m>3•n•3

ou m>i• correspond a la ieme ligne de M

et n•j correspond a la jeme colonne de N



Multiplication matricielle

Pour chacune des m× n case de A :1 produit scalaire de l elements.

complexite : O(lmn) ∼ O(n3)



Strassen

Introduction :

• multiplication matricielle standard : O(n3)• avec la methode de Strassen : O(nlog2 7) = O(n2.81)• methode recursive.

• efficace seulement sur les grosses matrices.



Strassen

Methode :

r s

t u

=

a b

c d

×

e f

g h



Strassen

ae+bg af+bh

ce+dg cf+dh

=

a b

c d

×

e f

g h

8 produits de sous matrices4 additions de sous matrices



Strassen

r sae+bg af+bh

t uce+dg cf+dh

=

a b

c d

×

e f

g h

on definit :P1 = af − ahP2 = ah+ bhP3 = ce+ deP4 = dg − deP5 = ae+ ah+ de+ dhP6 = bg+ bh− dg− dhP7 = ae+ af − ce− cf

tel que :r = P5 + P4 − P2 + P6

s = P1 + P2

t = P3 + P4

u = P1 + P5 − P3 − P7



Strassen

P1 = af − ahP2 = ah+ bhP3 = ce+ deP4 = dg − deP5 = ae+ ah+ de+ dhP6 = bg+ bh− dg− dhP7 = ae+ af − ce− cf

P1 = a(f − h)P2 = (a+ b)hP3 = (c+ d)eP4 = d(g − e)P5 = (a+ d)(e+ h)P6 = (b− d)(g + h)P7 = (a− c)(e+ f)



Strassen

P1 = a(f − h)P2 = (a+ b)hP3 = (c+ d)eP4 = d(g − e)P5 = (a+ d)(e+ h)P6 = (b− d)(g + h)P7 = (a− c)(e+ f)

r = P5+P4−P2+P6

s = P1 + P2

t = P3 + P4

u = P1+P5−P3−P7

→ 7 produits de sous matrices→ 18 additions de sous matrices

ce qui comporte moins d’operations que 8produits de sous matrices 4 additions desous matrices



Strassen

Remarques :

• efficace sur les grosses matrices, mais pas sur les petites.

• pas tres stable numeriquement.

• gestion specifique de la memoire.



Verification du produit matriciel

Methode :

Soit C = AB

Le produit de la matrice A avec le vecteur somme-des-lignes b de lamatrice B doit etre egal au vecteur somme-des-lignes c de la matriceC.

Ab = c

Si Ab 6= c, alors il y a une erreur de calcul.La reciproque n’est pas forcement vraie.




Exemple :

C = AB[2 154 22

]=

[1 32 4

] [2 30 4

]

c =

(2 + 154 + 22

)=

(1726

)b =

(2 + 30 + 4

)=

(54

)




Exemple :

c =

(1726

)b =

(54

)

Ab =

[1 32 4

](54

)=

(1726

)(

1726

)=

(1726

)⇒ Le calcul est probablement exact



Differents types de matrices

• matrices carrees

• matrices triangulaires

• matrices diagonales

• matrices creuses

• ...



Matrices diagonales

m11 0 0 · · · 00 m22 0 · · · 00 0 m33 · · · 0...

......

. . ....

0 0 0 · · · mnn



Matrices triangulaire (superieure)

U =

m11 m12 m13 · · · m1n

0 m22 m23 · · · m2n

0 0 m33 · · · m3n...

......

. . ....

0 0 0 · · · mnn



Matrices triangulaire (inferieure)

L =

m11 0 0 · · · 0m21 m22 0 0 0m31 m32 m33 · · · 0

......

.... . .

...mn1 mn2 mn3 · · · mnn



Matrice transposee

Soit M> la transposee de M, on a :

M>ij = Mji

Remarque : (AB)> = B>A>



Matrice symetrique

Mij = Mji ∀i, j

autrement dit : M = M>

(→ M est carree)



Matrice antisymetrique

Mij = −Mji ∀i, j

autrement dit : M = −M>(→ M est carree et Mii = 0)



Matrice hermitienne

Mij = Mji ∀i, j

exemple : matrice Hamiltonienne en mecanique quantique



Matrices identite

Id =

1 0 0 · · · 00 1 0 · · · 00 0 1 · · · 0...

......

. . ....

0 0 0 · · · 1

→ matrice carree→ matrice diagonale

matrice : Id.M = M

vecteur : Id.x = x

matrice : M.Id = M

vecteur : x>.Id = x>



Matrice de permutation

P =

0 1 0 0 00 0 0 1 01 0 0 0 00 0 0 0 10 0 1 0 0

→ un 1 par ligne→ un 1 par colonne→ 0 pour le reste

P est une matrice orthogonaleP permute les elements d’une matrice ou d’un vecteur



Matrice inverse

Soit M une matrice carree, on a :

M−1M = MM−1 = Id

Si M−1 n’existe pas, M est dite singuliere,sinon M est reguliere.



Matrice inverse

Proprietes :

•(M−1)−1

= M

•(M>)−1

=(M−1)>

= M−>

• (AB)−1 = B−1A−1

• [diag(mi)]−1 = [diag( 1

mi)]



Matrice orthogonale

M−1 = M>

exemple : une matrice de rotation



Produit vectoriel

Produit vectoriel :

u =(u1, u2, u3

)>v =

(v1, v2, v3

)>z = u× v =

u2v3 − u3v2u3v1 − u1v3u1v2 − u2v1

Forme matricielle :

[u]× =

0 −u3 u2u3 0 −u1−u2 u1 0

avec

z = [u]×v (produit matrice-vecteur)



Matrice de Householder

Hu = Idn − 2uu>

‖u‖2

→ matrice de reflexion par rapport a l’hyperplan de normale u.



Matrice creuse

Matrice qui contient beaucoup de 0.

M =

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 00 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 6 00 0 1 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 00 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 00 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 00 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 6 0 0 0 0 0 0 7 0 0 0 00 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 70 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 00 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0



Rang d’une matrice

Definition :

Le rang d’une matrice est le nombre maximal de vecteurs lignes(ou colonnes) lineairement independants.




Exemple :

1 1 0 00 0 1 11 1 1 11 1 2 2

⇒ rang 2

→ L3 = L1 + L2

→ L4 = L1 + 2L2

→ L1 et L2 sont independants

⇒ matrice de rang 2




Exemple :

1 1 0 00 0 1 11 1 1 11 1 2 2

⇒ rang 2

→ L3 = L1 + L2

→ L4 = L1 + 2L2






Exemple :

1 1 0 00 0 1 11 1 1 11 1 2 2

⇒ rang 2

→ L3 = L1 + L2

→ L4 = L1 + 2L2





Trace d’une matrice

Definition :

La trace d’une matrice carree est la somme des elements de sadiagonale.

Tr(M) =

n∑i=1

aii



Noyau d’une matrice

Definition :

Le noyau (kernel / right null space) d’une matrice M est l’ensembledes vecteurs x tels que :

Mx = 0


Documents

Matrices - IGM