Algèbre linéaire sur

III Forme normale de Smith

Algèbre linéaire sur → III Forme normale de Smith

III-1 Définitions

III-2 Forme normale de Smith d'une matrice

III-3 Comment calculer la forme de Smith

III-4 Résolution de quelques problèmes

III-1 Définitions

Algèbre linéaire sur → III Forme normale de Smith → III-1 Définitions

On va maintenant se permettre aussi des multiplications à gauche.

Définition
0
Une matrice (0 ∣ D) ou ( ) est dans une forme normale de Smith (SNF) si D est
D

diagonale, de diagonale d1, . . . , dn formée d'entiers positifs telle que dn ∣ … ∣ d1 (en

terme d'idéaux, telle que (d1) ⊂ (d2) ⊂. . .).

III-2 Forme normale de Smith d'une matrice

Algèbre linéaire sur → III Forme normale de Smith → III-2 Forme normale de Smith d'une matrice

Le théorème suivant est admis.

Théorème [Forme normale de Smith pour les matrices carrées]

Si A est une matrice n × n à coefficients dans Z non singulière, il existe des matrices
U et V unimodulaires (à coefficients dans Z de déterminant 1) tels que U A V soit une
matrice diagonale à coefficients dans Z, de diagonale d1, . . . , dn tels que dn ∣. . . ∣ d1.

Théorème
Soit A une matrice entière n × m. Il existe des matrices U et V unimodulaires et une
unique matrice S de Smith telles que
 0 ∣ 0
UA V = S = ( )
0 ∣ D

avec U carrée d'ordre n, V carrée d'ordre m, D diagonale de diagonale (d1, . . . , dr)

avec dr ∣. . . ∣ d1, di>0.

Théorème [Traduction]
L'ensemble des matrices SNF n × m forment un système de représentants de
GLn (Z)\Mn×m (Z)/ GLm (Z)

(pour la multiplication à gauche et à droite).

III-3 Comment calculer la forme de Smith

Algèbre linéaire sur → III Forme normale de Smith → III-3 Comment calculer la forme de Smith

Une première méthode est ... d'utiliser les très bons calculateurs qui existent (Pari/GP, ..).
Nous n'implémenterons pas les algorithmes ici. Regardons simplement le cas des matrices
2 × 2, qui montre bien les difficultés. Pensez à réinterpréter les multiplications par des
matrices comme des opérations sur les lignes ou les colonnes pour comprendre ce qu'on
fait.

a b
Partons de la matrice ( ). Soit d1 le pgcd de b et d. Si d1 = d, c'est-à-dire si d divise
c d

1 −b/d
b, on multiplie à gauche par la matrice ( ) :
0 1

1 −b/d a b a1 0
( )( ) = ( )
0 1 c d c d

b
s =−
Si d1 est différent de d (on a donc d1 ≤∣ d ∣ /2), en utilisant bu + dv = d1,
d1
,

d
t = on obtient
d1

t s a b a1 0
( )( ) = ( )
u v c d c1 d1

b 0 0
(on remplace donc la colonne ( ) par ( ) = ( )). Si d1 divise c1, on
d d1 pgcd(b, d)

1 0 * 0
multiplie à droite par ( ) pour obtenir une matrice diagonale ( ).
−c1/d1 1 0 d1

Sinon, soit d2 le pgcd de d1 et c1 :

a1 0 t′ u′ * *
( )( ) = ( )
c1 d1 s′ v′ 0 d2
 On a peut-être perdu le zéro sur la première ligne ... Mais on a quand même gagné un peu
car d2 divise strictement d (en fait d2 ≤∣ d ∣ /2 au moins). En recommençant ces
opérations autant de fois qu'il le faut, on obtient au bout d'un certain temps une matrice
a 0 c 0
diagonale : ( ). On veut maintenant obtenir la matrice ( ) avec d le pgcd de a
0 b 0 d

et b et d ∣ c (le déterminant de ces matrices est inchangée au signe près, on a alors

nécessairement c = ±ab/d). Pour cela, soient u et v tels que au + bv = d, on a

b/d −au /d a 0 bv/d u ab/d 0

( )( )( ) = ( )
1 v 0 b −a/d 1 0 d

Ces matrices sont composées d'opérations élémentaires comme le montrent les produits
suivants :
bv/d u 1 u 1 0
( ) = ( )( )
−a/d 1 0 1 −a/d 1

et
b/d −au/d 1 b/d 0 −1 1 v
( ) = ( )( )( )
1 v 0 1 1 0 0 1

En pratique, on commence par amener par des permutations de lignes ou de colonnes

l'élément de plus petite valeur absolue en bas à droite et on refait cette opération avant de
recommencer.

Exercice
Trouver une matrice 2 × 2 pour laquelle le nombre d'opérations à faire pour obtenir
sa matrice de Smith est grand.

III-4 Résolution de quelques problèmes

Algèbre linéaire sur → III Forme normale de Smith → III-4 Résolution de quelques problèmes

Algorithme
Calculer l'ensemble des solutions entières du système diophantien AX = B avec A et
B des matrices à coefficients dans Z. Ici, X est un vecteur colonne.

Solution
Il s'agit de calculer l'ensemble des solutions entières d'un système
AX = B.

Si B est nul, c'est aussi le noyau de l'application linéaire de Z-modules donnée par A
dans la base canonique.
Utilisons la forme normale de Smith (pour le noyau, la forme normale d'Hermite
suffirait).
Soit U AV = S la forme normale de Smith. Résoudre en entiers AX = B est
 équivalent à résoudre SY =
X = V Y et. Le système SY

de finir la résolution.

Exercice
C

⎪
⎨
⎩
en entiers avec C =
= C est de la forme :

⎧ d1yn−t+1

...

dtyn
=

=
U B,

cn−t+1

...

cn
le lien étant donné par

Lorsqu'une solution existe, ce qui se vérifie facilement sur C , il est maintenant facile

Un exemple : exemple , exemple , exemple Relations entre vecteurs

Algorithme
Calculer l'ensemble des solutions entières du système modulaire

Solution

matrice (A ∣ DM ).
AX ≡ B mod M

avec A, B et M des matrices à coefficients dans Z. Ici, X est un vecteur colonne.

On se ramène à la résolution d'un système linéaire diophantien en introduisant des

inconnues supplémentaires
AX + DM Y = C

où DM est la matrice diagonale de diagonale M . On calcule la matrice SNF de la

Dans le cas où A est la matrice identité et où M est une matrice colonne dont les
coefficients sont premiers deux à deux, l'existence et l'unicité d'une solution est donnée
par le lemme chinois. Donnez une méthode pour trouver toutes les solutions de la
congruence vectorielle X ≡ B mod M . L'appliquer sur des exemples.

Exercice
Des exemples traités : exemple

Interprétation de la forme de Smith