Théorème des facteurs invariants - Définition

Introduction

En mathématiques, le théorème des facteurs invariants porte sur les modules de type fini sur les anneaux principaux. Les facteurs invariants sont des obstructions à l'inversibilité des matrices qui n'apparaissent pas dans la théorie des espaces vectoriels. Leur calcul a de nombreuses applications : par exemple trouver la classe d'isomorphie d'un groupe abélien de type fini à partir d'une présentation de celui-ci. Dans un cadre précis, le théorème des facteurs invariants se particularise en théorèmes de réduction d'endomorphisme. Il permet alors notamment de calculer les invariants de similitude d'un endomorphisme sur un espace vectoriel. Le résultat du théorème des facteurs invariants est aussi connu sous le nom de forme normale de Smith.

L'approche présentée ici est effective dans le cadre d'un anneau euclidien. Le premier algorithme, dit d'échelonnement, est une généralisation du procédé d'élimination de Gauss-Jordan, de la décomposition LU : il permet de calculer des rangs et déterminants de matrices, et des noyaux et des images de morphismes de modules, ainsi que de résoudre des systèmes linéaires dans ce cadre. Le second algorithme, qui permet d'obtenir les applications annoncées est essentiellement un algorithme d'échelonnement simultané en lignes et en colonnes.

Une autre approche classique consiste à passer par la décomposition de Frobenius.

Rappel sur la décomposition LU

Une matrice A étant donnée, on souhaite la transformer en matrice triangulaire supérieure par opérations élémentaires sur les lignes (c'est-à-dire multiplication à gauche par des matrices de transvection, et des matrices de permutation). Par exemple, pour la matrice :

on multiplie à gauche successivement par les matrices :

La première multiplication matricielle revient à remplacer la deuxième ligne de la matrice A par  ; puis la seconde multiplication revient à remplacer la troisième ligne par . On obtient ainsi une égalité matricielle :

c'est-à-dire qu'on a annulé les coefficients sous-diagonaux de la première colonne de A, par multiplication par des matrices T_i de transvection, en se servant de la ligne L₁ comme pivot. En itérant le procédé, on peut annuler tous les coefficients sous-diagonaux de A, sous réserve toutefois de ne jamais tomber sur un pivot nul.

Théorème des facteurs invariants

Pour obtenir les conséquences théoriques annoncées,il faut aller plus loin ; on veut essentiellement obtenir une matrice qui soit à la fois échelonnée en lignes et en colonnes. Le théorème s'énonce ainsi :

Théorème

Soit un anneau euclidien, et . Alors, il existe des matrices et , produits de matrices de transvection généralisées, telles que TAU soit échelonnée en lignes et en colonnes ; c'est-à-dire de la forme :

avec de plus la relation de divisibilité Les coefficients p_i forment un système de facteurs invariants pour la matrice A. Les facteurs invariants sont définis de façon unique, à multiplication par inversibles près. La suite des facteurs invariants caractérise les matrices à équivalence près.

Corollaire et remarque

Notons le résultat suivant, corollaire de l'existence d'une mise sous forme diagonale :

Les matrices de peuvent s'écrire comme produit d'un nombre fini de matrices de transvection généralisées.

En effet, pour , il existe d'après le théorème U₁ et U₂ produit de matrices de transvection généralisées telles que :

Le déterminant de TAU est 1, et donc le produit des ε_i. On multiplie chaque membre à gauche par le produit de matrices de transvection généralisées

et on obtient la matrice identité au membre de droite. C'est-à-dire , ce qui est bien une écriture de A comme produit de matrices de transvection généralisées.

 

L'algorithme concerne donc les classes d'équivalence pour la relation si et seulement s'il existe telles que A = TBU. Les facteurs invariants, définis à inversibles de près, caractérisent en fait les classes pour la relation d'équivalence moins précise si et seulement s'il existe telles que A = TBU. Pour trouver les invariants pour la relation , il ne faut plus s'autoriser toutes les multiplications des facteurs invariants par des inversibles.

On rappelle que dans le cas d'un espace vectoriel, les classes d'équivalence de matrice étaient caractérisées par le rang. La situation est ici plus compliquée. Le rang apparaît notamment (comme le nombre de facteurs invariants), mais il ne suffit pas pour classifier ; en particulier, une matrice carrée de rang maximal peut ne pas être inversible : il suffit qu'un de ses facteurs invariants ne soit pas inversible.

Algorithme

Il ne suffit pas d'effectuer d'abord un échelonnement en lignes puis un échelonnement en colonnes. On peut procéder comme suit ; on va utiliser le stathme sur l'anneau  :

• On se ramène d'abord (si c'est possible! c'est-à-dire si A est non nulle) au cas où le coefficient en position (1,1) est non nul, et ce par permutations sur les lignes et les colonnes.
• On multiplie à gauche par des matrices de transvection (non généralisées), de façon à remplacer chaque coefficient a_1,j, par son reste par la division euclidienne par a_1,1.
• On multiplie à droite par des matrices de transvection (non généralisées), de façon à remplacer chaque coefficient a_i,1 par son reste par la division euclidienne par a_1,1.
• Si jamais il y a un (et s'il y en a plusieurs, il est bon de choisir celui de stathme minimal, pour améliorer la vitesse de l'algorithme) coefficient non nul sur la première ligne ou la première colonne ailleurs qu'en position (1,1), il est de stathme inférieur à celui du coefficient en position (1,1), d'après les deux étapes précédentes. On effectue une (anti)-transposition sur les lignes ou sur les colonnes suivant le cas pour le mettre en position (1,1).

On itère ces trois dernières étapes. A chaque passage, le stathme du coefficient a_1,1 diminue ; et le seul cas de stagnation est celui où tous les restes obtenus sont nuls : c'est-à-dire qu'on obtient une matrice dont la première ligne et la première colonne sont nulles, excepté le coefficient (1,1). Puisque notre stathme est à valeurs dans les entiers naturels, on finit par tomber sur ce cas.

On a donc écrit  ; par récurrence sur les dimensions des matrices considérées, on obtient l'écriture souhaitée. Il reste à voir qu'on peut avoir la relation de divisibilité annoncée. Il suffit pour cela de faire la constatation suivante. A partir de la matrice , on fait les opérations :

• Muliplier à droite par la matrice de transvection on obtient
• Multiplier à gauche par la matrice de transvection généralisée , où p₁α + p₂β = p = pgcd(p₁,p₂) pour obtenir : .
• Multiplier à droite par la matrice de transvection car ), et on obtient :

, et .

Ainsi, par multiplication à droite et à gauche par des transvections généralisées, on peut remplacer une matrice diagonale par une matrice diagonale avec relations de divisibilité. Dans le cas général de notre matrice doublement échelonnée, on se ramène successivement à , puis , en conservant la relation précédente, jusqu'à avoir pour tout i ; puis on s'occupe de p₂, etc.

-modules de type fini

Soit un anneau euclidien, et M un -module de type fini ; alors, il existe un unique ensemble tel que soit le rang de la partie libre du module M, t soit le cardinal d'un système minimal de générateurs de la partie de torsion, et soient des éléments de définis à inversibles près, et tel que :

Pour déduire ce théorème des facteurs invariants sur les modules de celui sur les matrices, choisissons un système générateur fini du module M à n éléments ; il existe alors une surjection de dans M ; le noyau N de cette surjection est un sous- -module de tel que  ; la noethérianité de l'anneau assure que ce noyau est à nouveau de type fini. Il admet un système de m générateurs ; et le module se surjecte donc dessus. On obtient ainsi par composition un morphisme entre et . Soit A la matrice de ce morphisme, dans la base canonique ; on trouve donc . Il suffit alors d'écrire A = TEU pour des matrices T,U inversibles, et une matrice E doublement échelonnée ; on obtient et donc , pour avec inversibles.

 

Ce théorème s'applique en particulier aux -modules de type fini, c'est-à-dire aux groupes abéliens de type fini. On dispose d'une part d'un théorème de classification, et d'autre part d'un algorithme pour calculer la classe d'un groupe dont on connaît un système de générateurs ainsi qu'une famille de relations entre ces générateurs, qui engendre l'ensemble des relations.