TRAVAUX PRATIQUES
TP.VI.A. Algorithmes de Gauss-Jordan, de Hermite
et de Smith
On se propose de passer en revue quelques algorithmes classiques de manipulation des matrices à coefficients dans Z. Les résultats obtenus sont à interpréter
dans le cadre de la théorie des groupes abéliens de type fini ou, de manière équivalente, des Z-modules de type fini.
On rappelle pour commencer l’algorithme de Gauss-Jordan, qui s’applique
aux matrices à coefficients dans Q, puis on modifie cet algorithme en n’autorisant
que des opérations « réversibles » dans Z et en utilisant notamment la structure
euclidienne de Z (c’est-à-dire l’existence d’une division euclidienne des entiers).
Cela permet de répondre de manière effective à des problèmes pratiques d’algèbre
linéaire (résolution d’équations linéaires, extraction d’une base à partir d’un système générateur, comparaison de sous-espaces vectoriels, recherche d’une base du
noyau et de l’image d’une application linéaire donnée) et de voir comment ces
méthodes se transposent au cas des Z-modules. Enfin, l’algorithme de Smith est
appliqué au calcul des facteurs invariants (voir également TR.VI.C). Cela constitue une preuve algorithmique du théorème de structure des groupes abéliens de
type fini.
Algorithme de Gauss-Jordan
On dit qu’une matrice A ∈ M m,n (Q) est sous forme normale échelonnée par
ligne (abrégé FNEL) si elle s’écrit :
A
=
⎛
⎜
⎜
⎝
0 ... 0 1 ∗ ... ∗ 0 ∗ ... ∗ 0
1 ∗ ... ∗ 0
1 ...
... 0 ∗
∗
1 ∗ ... ∗
0 . . .
0
⎞
⎟
⎟
⎠ .
TP.VI.A. Algorithmes de Gauss-Jordan, de Hermite
et de Smith
On se propose de passer en revue quelques algorithmes classiques de manipulation des matrices à coefficients dans Z. Les résultats obtenus sont à interpréter
dans le cadre de la théorie des groupes abéliens de type fini ou, de manière équivalente, des Z-modules de type fini.
On rappelle pour commencer l’algorithme de Gauss-Jordan, qui s’applique
aux matrices à coefficients dans Q, puis on modifie cet algorithme en n’autorisant
que des opérations « réversibles » dans Z et en utilisant notamment la structure
euclidienne de Z (c’est-à-dire l’existence d’une division euclidienne des entiers).
Cela permet de répondre de manière effective à des problèmes pratiques d’algèbre
linéaire (résolution d’équations linéaires, extraction d’une base à partir d’un système générateur, comparaison de sous-espaces vectoriels, recherche d’une base du
noyau et de l’image d’une application linéaire donnée) et de voir comment ces
méthodes se transposent au cas des Z-modules. Enfin, l’algorithme de Smith est
appliqué au calcul des facteurs invariants (voir également TR.VI.C). Cela constitue une preuve algorithmique du théorème de structure des groupes abéliens de
type fini.
Algorithme de Gauss-Jordan
On dit qu’une matrice A ∈ M m,n (Q) est sous forme normale échelonnée par
ligne (abrégé FNEL) si elle s’écrit :
A
=
⎛
⎜
⎜
⎝
0 ... 0 1 ∗ ... ∗ 0 ∗ ... ∗ 0
1 ∗ ... ∗ 0
1 ...
... 0 ∗
∗
1 ∗ ... ∗
0 . . .
0
⎞
⎟
⎟
⎠ .