Travaux pratiques
Algorithme de Smith
On dit qu’une matrice A ∈ M m,n (Z) est sous forme normale de Smith (abrégé
FNS) si elle s’écrit :
A
=
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
d 1
d 2
. . .
dr
0
. . .
0
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
où les coefficients diagonaux d i > 0 vérifient d i | d i+1 et les autres coefficients sont
nuls.
L’algorithme de Smith permet de mettre une matrice A ∈ M m,n (Z) donnée
sous FNS en un nombre fini d’étapes ; chaque étape est une opération élémentaire
sur les lignes ou les colonnes. Le voici :
On note δ(A) la valeur minimale de δ sur les coefficients non nuls de A (par
convention, δ(0) = 0). Si δ(A) = 0, c’est terminé, sinon on procède comme suit :
– Étape 1 : On se ramène au cas où δ(A) = δ(A 1,1 ).
– Étape 2 : S’il existe sur la première ligne un élément A 1,j non multiple de
A 1,1 , on le remplace par le reste r de sa division euclidienne par A 1,1 (en
opérant sur les colonnes). On refait les étapes 1 et 2 jusqu’à ce que tous les
termes de la première ligne soient multiples de A 1,1 (pourquoi ce moment
arrive-t-il ?). On applique alors le même procédé à la première colonne et
l’on obtient finalement une matrice dont tous les termes de la première
ligne et première colonne sont multiples de A 1,1 . Finalement, par opération
élémentaire toujours, on se ramène au cas où A 1,j = A i,1 = 0 pour i = 1 et
j = 1.
– Étape 3 : On a obtenu une matrice constituée de deux blocs, le coefficient
A 1,1 et un bloc B ∈ M m−1,n−1 (Z). Si l’un des coefficients de B n’est pas
multiple de A 1,1 , on additionne la ligne de ce coefficient à la première, puis
l’on remplace l’élément en question (sur la première ligne) par le reste de sa
division euclidienne par m 1,1 . On refait alors les étapes 1, 2 et 3. Il arrive
un moment où tous les coefficients de B sont multiples de A 1,1 (pourquoi ?).
– On réapplique alors l’algorithme à B ; etc.
Cela démontre algorithmiquement :
165
Algorithme de Smith
On dit qu’une matrice A ∈ M m,n (Z) est sous forme normale de Smith (abrégé
FNS) si elle s’écrit :
A
=
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
d 1
d 2
. . .
dr
0
. . .
0
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
où les coefficients diagonaux d i > 0 vérifient d i | d i+1 et les autres coefficients sont
nuls.
L’algorithme de Smith permet de mettre une matrice A ∈ M m,n (Z) donnée
sous FNS en un nombre fini d’étapes ; chaque étape est une opération élémentaire
sur les lignes ou les colonnes. Le voici :
On note δ(A) la valeur minimale de δ sur les coefficients non nuls de A (par
convention, δ(0) = 0). Si δ(A) = 0, c’est terminé, sinon on procède comme suit :
– Étape 1 : On se ramène au cas où δ(A) = δ(A 1,1 ).
– Étape 2 : S’il existe sur la première ligne un élément A 1,j non multiple de
A 1,1 , on le remplace par le reste r de sa division euclidienne par A 1,1 (en
opérant sur les colonnes). On refait les étapes 1 et 2 jusqu’à ce que tous les
termes de la première ligne soient multiples de A 1,1 (pourquoi ce moment
arrive-t-il ?). On applique alors le même procédé à la première colonne et
l’on obtient finalement une matrice dont tous les termes de la première
ligne et première colonne sont multiples de A 1,1 . Finalement, par opération
élémentaire toujours, on se ramène au cas où A 1,j = A i,1 = 0 pour i = 1 et
j = 1.
– Étape 3 : On a obtenu une matrice constituée de deux blocs, le coefficient
A 1,1 et un bloc B ∈ M m−1,n−1 (Z). Si l’un des coefficients de B n’est pas
multiple de A 1,1 , on additionne la ligne de ce coefficient à la première, puis
l’on remplace l’élément en question (sur la première ligne) par le reste de sa
division euclidienne par m 1,1 . On refait alors les étapes 1, 2 et 3. Il arrive
un moment où tous les coefficients de B sont multiples de A 1,1 (pourquoi ?).
– On réapplique alors l’algorithme à B ; etc.
Cela démontre algorithmiquement :
165