Theoreme des facteurs invariants

Theoreme des facteurs invariants

Théorème des facteurs invariants

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.

Sommaire

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 :

A=\begin{pmatrix}
2 & 4 & 3\\
1 & 5 & 0\\
3 & 8 & 2\\
\end{pmatrix}=\begin{pmatrix}L_1\\L_2\\L_3\end{pmatrix}.

on multiplie à gauche successivement par les matrices :

T_1=\begin{pmatrix}
1 & 0 & 0\\
-1/2 & 1 & 0\\
0 & 0 & 1\\
\end{pmatrix},T_2=\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
-3/2 & 0 & 1\\
\end{pmatrix}.

La première multiplication matricielle revient à remplacer la deuxième ligne de la matrice A par L_2-\frac{1}{2}L_1 ; puis la seconde multiplication revient à remplacer la troisième ligne par L_3-\frac{3}{2}L_1. On obtient ainsi une égalité matricielle :

T_2T_1A=\begin{pmatrix}&L_1&\\0&*&*\\0&*&*\\ \end{pmatrix}.

c'est-à-dire qu'on a annulé les coefficients sous-diagonaux de la première colonne de A, par multiplication par des matrices Ti de transvection, en se servant de la ligne L1 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.

Échelonnement des matrices à coefficients dans un anneau euclidien

Quelle obstruction rencontre-t-on dans le cas d'une matrice à coefficients dans un anneau euclidien? La principale est que la non nullité d'un coefficient n'assure pas qu'on puisse s'en servir comme pivot pour des opérations de transvection : dans l'exemple précédent, on s'est servi de 2 comme pivot, et on a été amenés à faire des calculs avec son inverse ; ce faisant, on est sorti du cadre initial d'une matrice à coefficients entiers.

Échelonnement des matrices lignes et colonnes

Il existe un palliatif. Regardons pour une matrice de taille 2\times 1 à coefficients dans un anneau euclidien :

A=\begin{pmatrix}a\\b\\ \end{pmatrix}

Dans le cas où a et b sont non nuls, soit p un plus grand diviseur commun de a et b. On considère alors la matrice :

T=\begin{pmatrix}\alpha&\beta\\-\frac{b}{p}&\frac{a}{p}\\ \end{pmatrix}

avec la relation det(T)=\alpha \frac{a}{p}+\beta \frac{b}{p}=1. Le fait de se placer dans un anneau principal assure l'existence des coefficients α et β (voir théorème de Bachet-Bézout), et le fait de se placer dans un anneau euclidien donne l'algorithme d'Euclide pour les calculer. On constate l'égalité :

TA=\begin{pmatrix}p\\0\\ \end{pmatrix}

on s'est ainsi ramené à une matrice colonne avec un coefficient nul, par une opération sur les lignes de la matrice A ; on peut voir cette opération comme une généralisation de la transvection. Remarquons que la matrice de transvection généralisée T est inversible puisque de déterminant (égal à 1) inversible dans l'anneau considéré. Dans la cas où b est nul, on prend T = Id, dans le cas où a est nul, on prend T=\begin{pmatrix}0&-1\\-1&0\\ \end{pmatrix}. On voit en particulier que les matrices de transvection généralisées qu'on considère ne comprennent pas les matrices de permutation qui apparaissaient dans la décomposition LU ; c'est dû au choix restrictif de se limiter à des matrices de déterminant 1 ; leur absence est toutefois facilement palliée, comme on l'a vu ci-dessus.

Pour traiter le cas d'une matrice colonne de taille quelconque, il suffit d'effectuer d'abord une opération entre la première et la deuxième ligne, pour annuler le deuxième coefficient, puis entre la première et la troisième pour annuler le troisième, etc. Ainsi, pour A=\begin{pmatrix}a_1\\a_2\\ \vdots\\a_n\\ \end{pmatrix}, il existe T produit de matrices de transvection généralisées telle que TA=\begin{pmatrix}p\\0\\ \vdots\\0\\ \end{pmatrix}, où p est le pgcd des coefficients ai.

Le cas d'une matrice ligne s'en déduit par transposition.

Matrices de transvection généralisées, et opérations élémentaires

On s'intéresse maintenant à des matrices de taille n\times m, éventuellement rectangulaires, toujours à coefficients dans un anneau euclidien. Les matrices de transvection généralisées codant les opérations sur les lignes seront donc des matrices carrées de taille n, et celles codant les opérations sur les colonnes des matrices carrées de taille m. Pour faire une opération entre les rangées i et j, il faut donc considérer les matrices :

T_{i,j,\alpha,\beta,\gamma,\delta}=\begin{pmatrix}
1&&&     &      &      &     &&&0\\
&\ddots&&&      &      &     &&&\\
&&1&     &      &      &     &&&\\
&&&\alpha&\dots&\dots&\beta&&&\\
&&&\vdots&1&0&\vdots&&&\\
&&&\vdots&0&1&\vdots&&&\\
&&&\gamma&\dots&\dots&\delta&&&\\
&&&      &      &      &      &1&&\\
&&&      &      &      &       &&\ddots&\\
0&&&     &      &      &       &&&1\\
\end{pmatrix}

avec αδ − βγ = 1, où les coefficients α,β apparaissent sur la ligne i, et γ,δ sur la ligne j. On remarque la relation suivante : T_{i,j,\alpha,\beta,\gamma,\delta}^{-1}=T_{i,j,\delta,-\beta,-\gamma,\alpha}.

Multiplier une matrice A, dont les lignes sont Li, à gauche par une telle matrice, c'est remplacer la ième ligne Li de A par αLi + βLj, et la jème ligne par γLi + δLj. Pour obtenir une opération sur les colonnes, il faut effectuer une multiplication à droite par une matrice de transvection généralisée.

Dans le cas où α = δ = 1, et où un des deux coefficients β ou γ est nul, on retrouve une matrice de transvection proprement dite ; dans le cas où α = δ = 0, et β = − γ = + − 1, on trouve une matrice qui va jouer le rôle de matrice de transposition ; convenons d'appeler anti-transposition l'opération correspondante.

Algorithme d'échelonnement pour les matrices de taille quelconque

Commençons à décrire l'algorithme. Pour une matrice :

A=\begin{pmatrix}
a_{1,1}&\dots&a_{1,m}\\
\vdots&&\vdots\\
a_{n,1}&\dots&a_{n,m}\end{pmatrix}

on commence par multiplier à gauche par des matrices de type T1,j, pour j allant de 2 à n ; on effectue ces opérations en considérant seulement leur effet sur le premier vecteur colonne de la matrice A. D'après ce qu'on a vu pour les opérations sur les lignes d'un vecteur colonne, on parvient ainsi à annuler tous les coefficients sous-diagonaux de la première colonne de A, et le premier coefficient de la nouvelle matrice est précisément un pgcd des coefficients de la première colonne de A :

T_1A=\begin{pmatrix}p&*&*\\0&*&*\\0&*&*\\ \end{pmatrix}

On veut ensuite multiplier par des matrices de type T2,j, pour j > 2, pour annuler tous les coefficients sous-diagonaux de la deuxième colonne ; de telles opérations ne font pas intervenir la première ligne ; tous les coefficients de la première colonne, autre que celui en position (1,1), qui seront ainsi obtenus seront donc combinaison linéaire des coefficients nuls de la première colonne : ils seront nuls. Il faut ensuite multiplier par des matrices de type T3,j, pour annuler les coefficients sous-diagonaux de la troisième colonne, etc.

On obtient en définitive une égalité avec une matrice de la forme : TA=\begin{pmatrix}
p_1&*&&&&&*\\
0&\dots&0&p_2&*&&*\\
0&&\dots&&0&p_3&*\\
&&&\dots&&&\\
\end{pmatrix} où les coefficients pi sont non nuls. La matrice obtenue est dite sous forme échelonnée en lignes, voir matrice échelonnée.

L'échelonnement en colonnes s'en déduit par transposition.

Théorème d'échelonnement

Soit \mathcal{A} un anneau principal, et A une matrice de M_{n,m}(\mathcal{A}). Alors, il existe une matrice T\in Sl(\mathcal{A}) (c'est-à-dire inversible et de déterminant 1), produit de matrices de transvection généralisées, telle que la matrice TA\in M_{n,m}(\mathcal{A}) soit sous forme échelonnée en lignes. Si, de plus, l'anneau \mathcal{A} est euclidien, on dispose d'un algorithme pour calculer la matrice T, dont la complexité est polynômiale en la taille de la matrice A et la taille de ses coefficients.

Conséquences

L'algorithme d'échelonnement est suffisant pour bon nombre de calculs : le rang de la matrice A est égal au nombre de lignes non nulles de sa forme échelonnée ; le déterminant, dans le cas d'une matrice carrée de rang maximal, sera le produit des coefficients pi de la matrice échelonnée.

On peut aussi en déduire des équations et paramétrisations des noyaux et images des matrices, vues comme applications linéaires ; par exemple, pour A\in M_{n,m}(\mathcal{A}), vue comme application linéaire de \mathcal{A}^m dans \mathcal{A}^n, et T\in Sl_m(\mathcal{A}) telle que AT soit échelonnée en colonnes, les éléments du noyau de AT sont de la forme \begin{pmatrix}0\\\vdots\\0\\ a_{r+1} \\ \vdots \\ a_m \end{pmatrix}, où les r premières lignes sont nulles, pour r le rang de A, et donc le nombre de colonnes non nulles de AT ; et donc les éléments du noyau de A sont engendrés par les mr derniers vecteurs colonnes de T − 1.

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 \mathcal{A} un anneau euclidien, et A\in M_{n,m}(\mathcal{A}). Alors, il existe des matrices T\in Sl_n(\mathcal{A}) et U\in Sl_m(\mathcal{A}), 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 :

\begin{pmatrix}p_1&0&&\\0&\ddots&&\\&&p_r&\\&&&0\\ \end{pmatrix}

avec de plus la relation de divisibilité p_1\mid p_2\mid\dots\mid p_r Les coefficients pi 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 Sl_n(\mathcal{A}) peuvent s'écrire comme produit d'un nombre fini de matrices de transvection généralisées.


L'algorithme concerne donc les classes d'équivalence pour la relation A\sim_1 B si et seulement s'il existe U,T\in Sl(\mathcal{A}) telles que A = TBU. Les facteurs invariants, définis à inversibles de \mathcal{A} près, caractérisent en fait les classes pour la relation d'équivalence moins précise A\sim_2 B si et seulement s'il existe U,T\in Gl(\mathcal{A}) telles que A = TBU. Pour trouver les invariants pour la relation \sim_1, 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 \mathcal{A} :

  • 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 a1,j, j\geq 2 par son reste par la division euclidienne par a1,1.
  • On multiplie à droite par des matrices de transvection (non généralisées), de façon à remplacer chaque coefficient ai,1 par son reste par la division euclidienne par a1,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 a1,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 T_1AU_1=\begin{pmatrix}a_{1,1}&0\\0&A_1\\ \end{pmatrix} ; 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 \begin{pmatrix}p_1&0\\0&p_2\\ \end{pmatrix}, on fait les opérations :

  • Muliplier à droite par la matrice de transvection \begin{pmatrix}1&0\\1&1\\ \end{pmatrix} on obtient \begin{pmatrix}p_1&0\\p_2&p_2\\ \end{pmatrix}
  • Multiplier à gauche par la matrice de transvection généralisée \begin{pmatrix}\alpha&\beta\\-\frac{p_2}{p}&\frac{p_1}{p}\\ \end{pmatrix}, où p1α + p2β = p = pgcd(p1,p2) pour obtenir :\begin{pmatrix}p&\beta p_2\\0&\frac{p_1p_2}{p}\\ \end{pmatrix}.
  • Multiplier à droite par la matrice de transvection \begin{pmatrix}1&-\beta\frac{p_2}{p}\\0&1\\ \end{pmatrix}(\beta\frac{p_2}{p}\in\mathcal{A} car p\mid p_2), et on obtient :

\begin{pmatrix}p&0\\0&\frac{p_1p_2}{p}\\ \end{pmatrix}, et p\mid\frac{p_1p_2}{p}.

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 à p_1\mid p_2, puis p_1\mid p_3, en conservant la relation précédente, jusqu'à avoir p_1\mid p_i pour tout i ; puis on s'occupe de p2, etc.

\mathcal{A}-modules de type fini

Soit \mathcal{A} un anneau euclidien, et M un \mathcal{A}-module de type fini ; alors, il existe un unique ensemble \left\{(r,t),d_1,\dots,d_t\right\} tel que r\in\mathbb{N} 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 d_1\mid d_2\mid\dots\mid d_t soient des éléments de \mathcal{A} définis à inversibles près, et tel que :

M\simeq \mathcal{A}^r\oplus\mathcal{A}/d_1\mathcal{A}\oplus\dots\oplus\mathcal{A}/d_t\mathcal{A}


Ce théorème s'applique en particulier aux \mathbb{Z}-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.

Application aux invariants de similitude

Soit \mathbb{K} un corps commutatif, E, un \mathbb{K}-espace vectoriel de dimension finie, et u\in\mathcal{L}(E) un endomorphisme de E.

Cette donnée de u est en fait équivalente à la donnée d'une structure de \mathbb{K}[X]-module sur E : si P est un polynôme de \mathbb{K}[X], et x un élément de E, alors P agit sur x par :

P.x = P(u)(x)

L'anneau \mathbb{K}[X] étant euclidien, le théorème des facteurs invariants assure l'existence d'un isomorphisme de \mathbb{K}[X]-modules :

E\simeq \mathbb{K}[X]/(P_1)\oplus\dots\oplus\mathbb{K}[X]/(P_t)

avec P_1\mid\dots\mid P_t. On remarque qu'il ne peut y avoir de partie \mathbb{K}[X]-libre, puisque l'espace E est de \mathbb{K}-dimension finie. Notons pour chaque i : di = deg(Pi). Soit (x_1,\dots,x_t) la \mathbb{K}[X]-base de E déduite par l'isomorphisme précédent de la \mathbb{K}[X]-base canonique du module de droite : xi correspond à (0,\dots,1,\dots,0), où le coefficient 1 apparaît sur la ième composante. Alors, la famille :

(x_1,u(x_1),\dots,u^{d_1-1}(x_1),x_2,\dots,u^{d_2-1}(x_2),\dots,x_t,\dots,u^{d_t-1}(x_t))

constitue une \mathbb{K}-base de E. La matrice de l'endomorphisme u dans cette base est :

\begin{pmatrix}\mathcal{C}_{P_1}&&\\&\ddots&\\&&\mathcal{C}_{P_t}\\\end{pmatrix}

où chaque \mathcal{C}_{P_i} est la matrice compagnon du polynôme Pi. La particularisation du théorème des facteurs invariants dans ce cadre est parfois appelé théorème de Frobenius.

Cette décomposition permet de trouver des polynômes annulateurs de l'endomorphisme u ; en effet, pour tout i, Pi(u)(xi) = 0 ; et donc, par la relation de divisibilité : Pt(u) = 0. Par ailleurs, la famille (x_t,\dots,u^{d_t-1}(x_t)) étant \mathbb{K}-libre, aucun polynôme de degré inférieur à dt ne peut annuler u. Ainsi, le polynôme Pt est le polynôme minimal de u ; et le polynôme P_1\dots P_t est son polynôme caractéristique.

Théorème

La suite P_1,\dots,P_t (avec relations de divisibilité, polynômes choisis unitaires) caractérise la classe de similitude d'un endomorphisme (ou d'une matrice). On l'appelle suite des invariants de similitude de l'endomorphisme (ou d'une matrice).

Calcul des invariants de similitude

En pratique, la suite des invariants de similitude d'une matrice A\in M_n(\mathbb{K}) se calcule en remarquant qu'elle se déduit de la suite des facteurs invariants de la matrice A-X.Id\in M_n(\mathbb{K}[X]), en enlevant de celle-ci les facteurs invariants inversibles (c'est-à-dire les polynômes constants).


Réduction de Jordan

Article détaillé : Réduction de Jordan.

Références

  • Rémi Goblot, Algèbre linéaire [détail des éditions]
  • Patrice Naudin, Claude Quitté Algorithmique algébrique [détail des éditions]
  • Page personnelle de Grégory Vial

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Th%C3%A9or%C3%A8me des facteurs invariants ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Theoreme des facteurs invariants de Wikipédia en français (auteurs)

См. также в других словарях:

  • Théorème des facteurs invariants — 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… …   Wikipédia en Français

  • Invariants De Similitude — En algèbre linéaire, un système complet d invariants pour la relation de similitude entre les matrices carrées de même taille à coefficients dans un corps est connu : ces invariants sont classiquement appelés invariants de similitude. Ils… …   Wikipédia en Français

  • Théorème de structure des groupes abéliens de type fini — Le théorème de structure des groupes abéliens de type fini fournit une classification très explicite des groupes abéliens de type fini à isomorphisme près. Entre autres informations, il indique que tout groupe abélien de type fini est un produit… …   Wikipédia en Français

  • Invariants de similitude — En algèbre linéaire, un invariant de similitude est une quantité qu on peut associer à toute matrice carrée (à coefficients dans un corps commutatif fixé K), telle que pour deux matrices semblables cette quantité soit toujours la même. Exemples d …   Wikipédia en Français

  • Théorème de Kronecker — Cet article concerne la structure des groupes abéliens finis. Pour d autres notions ou résultats portant le nom de Kronecker, voir Leopold Kronecker. Leopold Kronecker En a …   Wikipédia en Français

  • Theoreme de Kronecker — Théorème de Kronecker Leopold Kronecker En mathématiques et plus particulièrement en algèbre, le théorème de Kronecker traite des groupes abéliens finis. Le théorème de Kronecker est aussi appelé théorème fondamental des groupes abéliens finis.… …   Wikipédia en Français

  • Théorème de kronecker — Leopold Kronecker En mathématiques et plus particulièrement en algèbre, le théorème de Kronecker traite des groupes abéliens finis. Le théorème de Kronecker est aussi appelé théorème fondamental des groupes abéliens finis. Il stipule que tout… …   Wikipédia en Français

  • Théorème de Gauss-Wantzel — Pour les articles homonymes, voir Théorème de Gauss et Théorème de Wantzel. En géométrie, le théorème de Gauss Wantzel énonce une condition nécessaire et suffisante pour qu un polygone régulier soit constructible à la règle et au compas. Sommaire …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»