Algèbre linéaire sur ZZ

Algèbre linéaire sur ZZ

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

L'algèbre linéaire effective travaille sur des matrices. Les manipulations sur les matrices correspondent à des actions théoriques. Une bonne compréhension demande de passer sans problème du point de vue pratique au point de vue théorique et réciproquement.

Ici, nous allons travailler sur l'anneau des entiers et voir comment des problèmes concrets sur les entiers d'essence linéaire peuvent se résoudre de manière effective.

Ce document a été fait à partir de séances devant machine destinées à des étudiants de licence.

I Introduction

II Forme normale d'Hermite

III Forme normale de Smith

IV Groupes abéliens de type fini

V Des problèmes

I Introduction

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Définition

Soit A un anneau. Un A-module est un groupe abélien (M, +) muni d'une loi externe vérifiant les mêmes axiomes que ceux d'un espace vectoriel.

On prend dans la suite .

Définition

Un -module libre (de rang n) L est un -module tel qu'il existe une suite (e1, ..., en) (appelée base) de n éléments de L vérifiant : tout élément de L s'écrit comme combinaison linéaire de (e1, ..., en), de manière unique.

Nous ne réintroduirons pas tout le vocabulaire très semblable à celui des espaces vectoriels : on parlera donc librement de matrices (à coefficients dans ), de morphisme , de noyau et image d'un morphisme, du groupe (groupe des matrices inversibles dans , on montre que ce sont les matrices dont le déterminant est inversible dans , c'est-à-dire égal à ) ...

I-1 Interprétation des matrices

I-2 Changements de base

I-3 Cas de rang 2

I-1 Interprétation des matrices

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Soit L un -module libre de rang n. Fixons une base . Une matrice A de taille représente un sous- -module M de L : si v1, ... , vm sont les vecteurs représentés par les vecteurs colonnes de A dans la base , la matrice A représente le sous-module . Une matrice a aussi une interprétation en tant que matrice d'un morphisme : la matrice A représente le morphisme f de dans L donné par f( 0,..., 0, 1, 0, .., 0) = vi où le 1 est à la place i. L'image de f est alors le sous- -module M et A représente aussi le sous- -module M au sens précédent.

Dans la suite, L est un -module libre de rang n, M un sous- -module de L et A une matrice de M dans une base fixée de L.

Algèbre linéaire sur ZZ ---> I Introduction ---> I-1 Interprétation des matrices

I-2 Changements de base

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

I-2-1 Opérations à droite

I-2-2 Opérations à gauche

Algèbre linéaire sur ZZ ---> I Introduction ---> I-2 Changements de base

I-2-1 Opérations à droite

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Remarque

Multiplier A à droite par une matrice de revient à changer le système générateur de M.

Solution

Les opérations élémentaires suivantes sur les colonnes sont utilisées dans l'algorithme de Gauss sur un corps et sont encore permises dans :

  • Echanger deux colonnes ;
  • Ajouter à une colonne un multiple d'une autre colonne ;
  • Multiplier une colonne par un élément inversible .

Remarque

Faire une transformation élémentaire sur les colonnes de A revient à multiplier à droite par une matrice élémentaire. Donner cette matrice pour chacune des opérations élémentaires précédentes.

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

Si b1, ..., bm est un autre système générateur de M, la matrice B correspondante est avec V la matrice des bj exprimés dans le système générateur (a1, ... , am) de M :
représenté par (la base de L n'a pas changée).

La matrice V est à coefficients dans . Comme les vecteurs ai peuvent aussi s'exprimer comme combinaison entière des bi, son inverse est aussi à coefficients dans , autrement dit, le déterminant de la matrice V est égal à : .

Attention, ici on a pris un système générateur ayant même nombre d'éléments.

I-2-2 Opérations à gauche

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Remarque

Multiplier A à gauche par une matrice de revient à changer de base de référence de L.

Les opérations élémentaires suivantes sur les lignes sont utilisées dans l'algorithme de Gauss sur un corps et sont encore permises dans :

  • Echanger deux lignes
  • Ajouter à une ligne un multiple d'une autre ligne
  • Multiplier une ligne par un élément inversible de A.

Remarque

Faire une transformation élémentaire sur les lignes de A revient à multiplier à gauche par une matrice élémentaire. Donner cette matrice pour chacune des opérations élémentaires précédentes.

On note M[i] la colonne i de la matrice. On suppose que l'on dispose de fonctions permettant de manipuler directement de telles colonnes, comme: échanger deux colonnes ou faire une combinaison de colonnes. Commenter l'algorithme suivant, le corriger au besoin, dire exactement ce qu'on obtient :


Algorithme de Gauss


Input: une matrice M de taille
Output: une forme échelonnée en colonnes pour M
j := 0
pour i = 1 à n faire
      si il existe p > j tel que alors
             Choisir p tel que .
             j := j + 1;
             Echange M[j] et M[p] ;
            
            pour k = j+1 à m faire
                   M[k] := M[k] - M[k][i] M[j]



retourner M

Par exemple, que donne l'algorithme sur les matrices

L'algorithme donne une forme échelonnée en colonnes : les seules opérations que l'on fait sont faites sur les colonnes : il y a un pivot par colonne (si r est le rang de M, on peut donc définir une application strictement croissante telle que les pivots soient en position (i,f(i)). A quel moment trouve-on les pivots dans l'algorithme précédent ?

Cet algorithme demande de diviser par des coefficients, il nécessite d'être sur un corps.

I-3 Cas de rang 2

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Les opérations suivantes permettent de faire des "réductions de matrices", c'est-à-dire de transformer une matrice en une matrice plus simple en conservant certaines propriétés :

I-3-1 dans un corps

I-3-2 dans

I-3-1 dans un corps

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Ainsi, on peut transformer par des opérations élémentaires sur des colonnes (resp. sur des lignes) un vecteur ligne (resp. colonne) non nul en le vecteur (1,0) (resp. ).

Exercice

Le groupe GL2(K) agit à droite sur l'ensemble des matrices M2(K). Réinterpréter l'algorithme de Gauss comme permettant de trouver un système de représentants de l'ensemble quotient M2(K)/GL2(K). Faire de même avec . Quelle interprétation peut-on donner de ces ensembles quotient.

Solution

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

, , , .

, , .

On vérifie que ces matrices ne sont pas équivalentes.

I-3-2 dans

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Dans un anneau, on ne peut diviser par b que si b est inversible, par exemple dans , égal à . Pour remplacer cette opération, on peut utiliser la division euclidienne de a par b : a = b q + r avec (elle n'existe pas dans tous les anneaux, mais nous travaillerons dans ) :

En itérant comme dans l'algorithme d'Euclide, on obtient

Cette opération permet de transformer en ; de même en multipliant par une matrice convenable à droite, on peut transformer en :

ou
avec a u + b v = pgcd(a,b), s = -b/pgcd(a,b), t = a/pgcd(a,b). On rajoute cette opération aux opérations élémentaires lorsqu'on travaille sur .

Exercice

Donner un système de représentants de l'ensemble quotient .

Comment peut-on traduire ces énoncés en termes de sous-modules ? Faire de même avec , . Préciser comment réduire une matrice de en un représentant parmi ceux trouvés. Quelle interprétation peut-on donner de ces ensembles quotients ?

Solution

Donnons une idée des opérations à faire

  • Si c et d sont non nuls,
    • si ,
      avec si a1 est non nul.
    • si ,
  • Si c = 0 et d non nul,
  • Si c et d sont nuls et a et b non nuls,
  • Si a, c et d sont nuls et b non nuls, etc ...

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

Formes possibles : ; avec a strictement positif ; avec d strictement positif ; avec a et d strictement positifs et .

Vérifiez qu'elles ne sont pas équivalentes modulo la multiplication à droite par une matrice de . Si on avait travaillé sur un corps, qu'aurait-on obtenu ? Les sous- -modules de la deuxième et troisième forme sont de rang 1, ceux de la quatrième forme sont de rang 2. Les pivots (voir paragraphe suivant) sont a (resp. d, resp. ( a, d)).

II Forme normale d'Hermite

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

II-1 Définitions

II-2 Propriétés de la forme normale d'Hermite

II-3 Hermite et Hermite

II-4 Application de la forme d'Hermite

Algèbre linéaire sur ZZ ---> II Forme normale d'Hermite

II-1 Définitions

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Définition

La matrice est une forme normale de Hermite (supérieure échelonnée en colonnes) (HNF) si est une matrice telle qu'il existe une fonction strictement croissante
vérifiant
  1. et si i > f(j),
  2. si k > j.

Remarque

Les qj sont appelés pivots . Il y a un pivot (non nul) par colonne (non nulle).

Par exemple, la matrice suivante a 8 lignes et 7 colonnes, les deux premières colonnes sont nulles et les cinq dernières sont non nulles (par convention, dans ce qui suit, times représente un élément de l'anneau, représente un élément soumis à une condition : laquelle ?) :

Les autres entrées times peuvent être nulles, positives ou négatives.
  • f(j) est la ligne du pivot qj > 0. La fonction f donne le rang et la position des pivots : ici, f(1) = 1, f(2) = 4, f(3) = 5, f(4) = 6, f(5) = 8.
  • La matrice extraite à partir des lignes des pivots
    est non singulière et triangulaire supérieure
  • Tous les coefficients à droite du pivot qj sont réduits modulo qj (en particulier ils sont positifs ou nuls).

Exercice

Donner tous les formes normales d'Hermite HNF de taille (3, 2), de taille (2, 3).

Solution

Exercice

Si une matrice de rang n est HNF, elle est triangulaire supérieure avec des coefficients diagonaux strictement positifs. La fonction pivot est alors l'identité.

Solution

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

2,3 : un -module dans , équivalent à (0,v1,v2). On est ramené au cas des matrices de taille (2, 2). ; avec q strictement positif ; avec q strictement positif ; avec q1 et q2 strictement positifs et .

3,2 : un sous- -module de engendré par deux vecteurs.

Convention : aucune condition sur les times, une condition sur les par rapport au pivot de la même ligne, les qi sont des pivots (positifs ou nuls)

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

La même chose avec des pivots égaux à 1 et des égaux à 0

II-2 Propriétés de la forme normale d'Hermite

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

On admet le résultat suivant (voir cependant l'algorithme qui suit) :

Théorème [Forme normale d'Hermite]

Si A est une matrice à coefficients dans non singulière, il existe une matrice V unimodulaire (à coefficients dans de déterminant 1) et une unique matrice B qui est HNF telles que .

Voici des conséquences.

Théorème

Soit L un -module libre de rang n. Une fois fixée une base de L, tout sous-module de L a une base canonique : celle donnée par sa matrice HNF.

Théorème

Le groupe linéaire opère à droite sur et l'ensemble des matrices HNF de taille forme un système de représentants de .

Algèbre linéaire sur ZZ ---> II Forme normale d'Hermite ---> II-2 Propriétés de la forme normale d'Hermite

II-3 Hermite et Hermite

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Pour calculer la forme normale d'Hermite, on utilise un algorithme du type de l'algorithme de Gauss en rajoutant l'opération élémentaire d'Euclide . Il n'est pas demandé de l'implémenter. Le principe est le même que celui de l'algorithme de Gauss donné. On utilisera la commande mathnf dans Pari/GP (la commande mupad linalg::hermiteForm ne fonctionne que pour des matrices carrées inversibles, ce qui limite son utilisation.)


Algorithme naïf pour HNF



Input:
Output:
Soit
pour i = m, , 1 faire
      siil existe j < R - 1 tel que alors
             Choisir j tel que
             Ecrire
            

      si alors
            



pour i = m, , 1 faire
      si alors
            
            pour j = n, . . . , n - R + 2 faire
                  
                  

            


La forme d'Hermite d'une matrice dont on vient de parler est obtenue par manipulation sur les colonnes et est supérieure . On aurait pu manipuler les lignes ou obtenir une matrice inférieure . Il y a ainsi quatre définitions possibles:

  • matrice échelonnée en colonnes et supérieure
  • matrice échelonnée en colonnes et inférieure
  • matrice échelonnée en lignes et supérieure
  • matrice échelonnée en lignes et inférieure .

Exercice

Donner pour chacune d'elle la définition formelle. Comment peut-on passer facilement d'une forme à l'autre ? Il y a deux involutions intéressantes qui échangent les lignes et les colonnes qui sont la transposition et la multiplication (à droite et à gauche) par les matrices carrées antidiagonales d'antidiagonale formée de 1.

Il suffit d'avoir un algorithme pour l'une des définitions. L'une ou l'autre des définitions est plus ou moins adaptée ensuite selon le problème qu'on se pose. Donner les formules permettant de passer d'une des formes aux trois autres et les comparer sur des exemples significatifs . Quel est le résultat sur la matrice

Obtient-on les mêmes pivots ? Le nombre de pivots est-il le même ? Faire d'autres essais.

Solution

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

Définition

La matrice est une forme normale d'Hermite supérieure échelonnée en colonnes si est une matrice telle qu'il existe une fonction strictement croissante
vérifiant
  1. et si i > f(j),
  2. si k > j.

Définition

La matrice est une forme normale d'Hermite supérieure échelonnée en lignes si est une matrice telle qu'il existe une fonction strictement croissante
vérifiant
  1. et si j > f(i),
  2. si k > i.

Définition

La matrice est une forme normale d'Hermite inférieure échelonnée en colonnes si est une matrice telle qu'il existe une fonction strictement croissante
vérifiant
  1. et si i < f(j),
  2. si k < j.

Définition

La matrice est une forme normale d'Hermite inférieure échelonnée en lignes si est une matrice telle qu'il existe une fonction strictement croissante
vérifiant
  1. et si j < f(i),
  2. si k < i.

Si A est une matrice , on note w(A)=Wn A Wm (ou en abrégé W A W). Pour passer d'une forme à l'autre,

Il reste à se persuader que la transposée d'une matrice échelonnée en lignes est échelonnée en colonnes, etc. Par exemple

, ,

Regardons sur un exemple : 

gp > hnf1(A) = H = mathnf(A,1) ; [A * H[2],  H[2]];


gp > ww (n) = matrix(n,n,i,j, if(i+j == n + 1,1)) ;
gp > ww(3)
%1 = [0 0 1]
     [0 1 0]
     [1 0 0]


gp > {hnf2(A) =  r = matsize(A) ; W1 = ww(r[1]) ; W2 = ww(r[2]) ; 
     B = W2 * A~ * W1 ; H = mathnf(B,1) ; U = H[2] ; H = B * U ;
     [W1 * H~* W2,  W1 * U~* W1]}
     
gp > hnf3(A) = H = hnf1(A~) ; [H[1]~ , H[2]~] ;


gp > hnf4(A) = H = hnf2(A~) ; [H[1]~ , H[2]~] ;


gp > {A = [-2, -2, -1, -3, -3, -3;
           -2, -3, -3, -2, 1, 0;
           -2, 0, -1, -2, 1, -2;
           -3, -1, -1, -3, 0, -3;
            -1, 0, 1, -3, -2, -1]} ;


gp > hnf1(A)[1]
%3 = [0 2 1 0 1 1]
     [0 0 2 1 1 1]
     [0 0 0 1 0 0]
     [0 0 0 0 1 0]
     [0 0 0 0 0 1]


gp > hnf2(A)[1]
%4 = [1 0 0 4 3 2]
     [0 1 0 4 2 -2]
     [0 0 1 1 1 1]
     [0 0 0 7 0 -5]
     [0 0 0 0 4 4]


gp > hnf3(A)[1]
%5 = [16 26 0 0 0 0]
     [15 25 1 0 0 0]
     [10 15 0 2 0 0]
      [5  9 0 0 1 0]
     [12 18 0 1 0 1]
     
gp > hnf4(A)[1]
%6 = [1 0 0 0 0 0]
     [0 1 0 0 0 0]
     [0 0 1 0 0 0]
     [0 0 0 1 0 0]
     [2 3 1 3 4 0]
Les pivots sont (2, 2, 1, 1, 1) pour la première forme, (1, 1, 1, 7, 4) pour la seconde forme, (26, 1, 1, 2, 1, 1) pour la troisième et (1, 1, 1, 1, 4) pour la quatrième. Ils varient donc selon la forme d'Hermite choisie 
hnf1(A) = H = mathnf(A,1) ; [A * H[2],  H[2]];
ww (n) = matrix(n,n,i,j, if(i+j == n + 1,1)) ;
ww(3)
{hnf2(A) =  r = matsize(A) ; W1 = ww(r[1]) ; W2 = ww(r[2]) ; 
     B = W2 * A~ * W1 ; H = mathnf(B,1) ; U = H[2] ; H = B * U ;
     [W1 * H~* W2,  W1 * U~* W1]}
hnf3(A) = H = hnf1(A~) ; [H[1]~ , H[2]~] ;
hnf4(A) = H = hnf2(A~) ; [H[1]~ , H[2]~] ;
{A = [-2, -2, -1, -3, -3, -3;
   -2, -3, -3, -2, 1, 0;
   -2, 0, -1, -2, 1, -2;
   -3, -1, -1, -3, 0, -3;
   -1, 0, 1, -3, -2, -1]} ;
hnf1(A)[1]
hnf2(A)[1]
hnf3(A)[1]
hnf4(A)[1]

II-4 Application de la forme d'Hermite

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Nous allons maintenant voir comment utiliser la forme d'Hermite pour résoudre des problèmes. Pour chacun, expliquez comment on peut lire la solution sur une forme d'Hermite. S'il y a lieu, l'appliquer aux problèmes concrets.

Algorithme

Trouver le noyau d'un homomorphisme de -modules
donné par sa matrice A.

Solution

Algorithme

Trouver l'image d'un homomorphisme de -modules
donné par sa matrice A.

Solution

Algorithme

Montrer qu'un sous- -module d'un -module libre est libre. Trouver une base du -module engendré dans par certains vecteurs.

Exercice

Des exemples traités : exemple , exemple

Image I

Image II

Questions diverses

Algorithme

Trouver la somme dans des deux sous-modules donnés par les matrices A et B.

Solution

Algorithme

Vérifier que deux sous- -modules M et M' de donnés par des matrices A ( m colonnes) et B ( m' colonnes) sont égaux.

Solution

Algorithme

Soient deux sous- -modules M et M' de donnés par des matrices A ( m colonnes) et B ( m' colonnes). Vérifier que M' est contenu dans M.

Solution

Algorithme

Trouver l'intersection dans des deux sous-modules M et N donnés par les matrices A ( m colonnes) et B ( m' colonnes).

Solution

Algèbre linéaire sur ZZ ---> II Forme normale d'Hermite ---> II-4 Application de la forme d'Hermite

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution


Noyau d'un homorphisme


Input: matrice représentant l'homomorphisme
Output: matrice représentant le noyau
calculer la matrice HNF par colonnes de la matrice A :
prendre les colonnes de la matrice V correspondant à une colonne de zéros dans H.

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution


Image d'un homomorphisme


Input: matrice représentant l'homomorphisme
Output: matrice représentant l'image
calculer la matrice HNF par colonnes de la matrice A : .
prendre les colonnes de la matrice H.

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution


Somme de deux sous-modules


Input: matrices représentant les sous-modules
Output: matrice représentant la somme
calculer la matrice HNF par colonnes de la matrice : .
prendre les colonnes (non nulles) de la matrice H

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution


Egalité de deux sous-modules


Input: Matrices représentant les sous-modules.
Output: Booléen disant si les deux sous-modules sont égaux.
calculer les matrices HNF de M et M'
vérifier qu'elles sont égales.

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution


Inclusion de deux sous-modules


Input: Matrices représentant les sous-modules
Output: Booléen indiquant si le premier sous-module est inclus dans l'autre.
calculer M + M' ;
vérifier que M + M' = M.

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution


Intersection de deux sous-modules


Input: Matrices représentant les sous-modules
Output: Matrice représentant l'intersection
calculer le noyau N de la matrice en utilisant la matrice HNF par colonnes :
prendre les n premières lignes N1 du noyau N
calculer A N1 et et le mettre sous forme HNF.
On cherche X et Y tel que A X = B Y, donc (X, -Y) est dans le noyau de

III Forme normale de Smith

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

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

Algèbre linéaire sur ZZ ---> III Forme normale de Smith

III-1 Définitions

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

On va maintenant se permettre aussi des multiplications à gauche.

Définition

Une matrice ou est dans une forme normale de Smith (SNF) si D est diagonale, de diagonale d1, ... , dn formée d'entiers positifs telle que (en terme d'idéaux, telle que ).

III-2 Forme normale de Smith d'une matrice

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Le théorème suivant est admis.

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

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

Théorème

Soit A une matrice entière . Il existe des matrices U et V unimodulaires et une unique matrice S de Smith telles que
avec U carrée d'ordre n, V carrée d'ordre m, D diagonale de diagonale (d1 , ... , dr) avec , di > 0.

Théorème [Traduction]

L'ensemble des matrices SNF forment un système de représentants de
(pour la multiplication à gauche et à droite).
Algèbre linéaire sur ZZ ---> III Forme normale de Smith ---> III-2 Forme normale de Smith d'une matrice

III-3 Comment calculer la forme de Smith

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

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 , 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.

Partons de la matrice . Soit d1 le pgcd de b et d. Si d1 = d, c'est-à-dire si d divise b, on multiplie à gauche par la matrice :

Si d1 est différent de d (on a donc ), en utilisant b u + d v = d1, s = -b/d1, t = d/d1 on obtient
(on remplace donc la colonne par ). Si d1 divise c1, on multiplie à droite par pour obtenir une matrice diagonale . Sinon, soit d2 le pgcd de d1 et c1 :
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 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 diagonale : . On veut maintenant obtenir la matrice avec d le pgcd de a et b et (le déterminant de ces matrices est inchangée au signe près, on a alors nécessairement ). Pour cela, soient u et v tels que a u + b v = d, on a
Ces matrices sont composées d'opérations élémentaires comme le montrent les produits suivants :
et

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 pour laquelle le nombre d'opérations à faire pour obtenir sa matrice de Smith est grand.
Algèbre linéaire sur ZZ ---> III Forme normale de Smith ---> III-3 Comment calculer la forme de Smith

III-4 Résolution de quelques problèmes

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Algorithme

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

Solution

Exercice

Un exemple : exemple , exemple , exemple Relations entre vecteurs

Algorithme

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

Solution

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 . L'appliquer sur des exemples.

Exercice

Des exemples traités : exemple

Interprétation de la forme de Smith

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

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

Il s'agit de calculer l'ensemble des solutions entières d'un système
A X = B
Si B est nul, c'est aussi le noyau de l'application linéaire de -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 A V = S la forme normale de Smith. Résoudre en entiers A X = B est équivalent à résoudre S Y = C en entiers avec C = U B, le lien étant donné par X = V Y et. Le système S Y = C est de la forme :

Lorsqu'une solution existe, ce qui se vérifie facilement sur C, il est maintenant facile de finir la résolution.

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

On se ramène à la résolution d'un système linéaire diophantien en introduisant des inconnues supplémentaires
A X + DM Y = C
où DM est la matrice diagonale de diagonale M. On calcule la matrice SNF de la matrice .

IV Groupes abéliens de type fini

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

IV-1 Définitions

IV-2 Module des relations

Algèbre linéaire sur ZZ ---> IV Groupes abéliens de type fini

IV-1 Définitions

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Définition

Un groupe abélien de type fini est un -module de type fini, c'est-à-dire ayant un nombre fini de générateurs. Un groupe abélien libre est isomorphe à pour un entier d où d est par définition son rang .

Théorème

Soit un homomorphisme de groupes abéliens libres de type fini. Il existe des bases de L1 et de L2 telles que la matrice de f dans ces bases soit sous forme normale de Smith.

Remarque

Si A est la matrice de f dans des bases données de L1 et de L2, la nouvelle base de L1 est donnée par la matrice V, la nouvelle base de L2 est donnée par la matrice :

Théorème

Soit M un sous-module d'un -module L libre de type fini et de rang maximal. Il existe une base de L et des entiers positifs d1, ..., dr tels que et tels que d1 e1, ..., dr er soient une base de M. Les entiers d1, ..., dr caractérisent .

Exercice

Des exemples : exemple , exemple

Bases associées

Diviseurs élémentaires I

Diviseurs élémentaires II

IV-2 Module des relations

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Soit M un groupe abélien de type fini et v1, ..., vs des générateurs . Pour décrire M, introduisons l'application

qui envoie ei sur vi.

Le noyau de f est un sous- -module de engendré par certains vecteurs r1, ..., rt. Il est appelé module des relations de M. Soit A la matrice formée par les vecteurs r1, ..., rt. C'est une matrice de qu'on appelle une matrice des relations de M (relativement au système générateur ( r1, ..., rt)). En effet, on a

ce qui donne une relation entre les éléments vi de M.

La matrice A définit un homomorphisme . Son image est par définition égale au noyau de f. Alors, .

Théorème

Soit M un -module de type fini, il existe des entiers positifs d1, ..., dm tels que et un entier r positif ou nul tels que

Analyser la structure de M revient donc à étudier le groupe et à en trouver les invariants. Ce qui se fait en utilisant la forme normale de Smith de A.

Exercice

Quelques exemples traités : exemple , exemple , exemple

Relations

Groupes abéliens

Groupes en arithmétique

Exercice

Quotient

Sous-module des rationnels

Nombre de sous-groupe d'ordre p

Isomorphismes

V Des problèmes

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Voici quelques problèmes qu'on aimerait résoudre. Ces problèmes ont pour inconnues des entiers, ce qui les distingue des problèmes sur .

V-1 Les boeufs d'Archimède

V-2 Identité de Bézout

V-3 Un système modulo des entiers divers

V-4 Un système linéaire : condition de compatibilité

V-5 Le groupe multiplicatif dans les rationnels

V-6 Carreleur cherche aide

V-7 Base

V-8 Groupe abélien

V-9 Groupe abélien défini par générateurs et relations (1)

V-10 Groupe abélien défini par générateurs et relations (2)

V-11 Groupe abélien défini par générateurs et relations (3)

Algèbre linéaire sur ZZ ---> V Des problèmes

V-1 Les boeufs d'Archimède

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Le soleil (c'était alors un dieu) possédait un troupeau de taureaux et de vaches, dont une partie était blanche, une partie noire, une partie tachetée, et la quatrième brune. Parmi les taureaux, le nombre de ceux qui étaient blancs dépassait le nombre des bruns de la moitié plus un tiers du nombre des taureaux noirs. Le nombre des taureaux noirs dépassait le nombre des taureaux bruns d'un quart plus un cinquième du nombre des taureaux tachetés. Enfin le nombre des taureaux tachetés dépassait celui des bruns d'un sixième plus un septième du nombre des taureaux blancs. Parmi les vaches, le nombre des blanches était égal au tiers augmenté du quart du nombre total des bovins noirs. Le nombre des vaches noires, au quart augmenté du cinquième du nombre total des bovins tachetés. Le nombre des vaches tachetées, au cinquième augmenté du sixième du nombre total des bovins bruns. Enfin le nombre des vaches brunes était égal à un sixième plus un septième du nombre total des bovins blancs.
Peut-on déterminer le troupeau du soleil ? Le plus petit possible ?

Un renseignement supplémentaire : il est possible de mettre les taureaux blancs et les taureaux noirs ensemble en carré et de mettre les taureaux bruns et les taureaux tachetés en triangle.
Ce célèbre problème est généralement attribué à Archimède. Il a été découvert dans un manuscrit grec conservé dans une bibliothèque du nord de l'Allemagne en 1773. Le texte propose de compter les troupeaux du dieu du soleil. La deuxième partie n'est pas faisable avec les méthodes dont on parle aujourd'hui. [remarquer aussi que les seuls rationnels utilisés sont ce qu'on appelle des fractions égyptiennes, c'est-à-dire de la forme 1/n.

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-1 Les boeufs d'Archimède

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

Le texte propose de compter les troupeaux du dieu du soleil, et en substance, il s'énonce de la façon suivante : il s'y trouve des taureaux et vaches de 4 couleurs différentes, blancs, noirs, tachetés et marrons. Pour les taureaux, le nombre de blancs est plus grand que le nombre des marrons de 1/2 + 1/3 du nombre des noirs ; le nombre des noirs plus grand que les marrons de 1/4 + 1/5 du nombre des tachetés ; le nombre des tachetés plus grand que le nombre des marrons de 1/6 + 1/7 du nombre des blancs. Pour les vaches, le nombre des blanches est 1/3 + 1/4 du nombre total de têtes de bétail noires ; le nombre des noires, 1/4 + 1/5 du nombre total de têtes de bétail tachetées ; le nombre de tachetées, 1/5 + 1/6 du nombre total de têtes de bétail marrons ; le nombre des marrons, 1/6 + 1/7 du nombre total de têtes de bétail blanches. Ce problème se retranscrit simplement en le système suivant de 7 équations à 8 inconnues : 

  b = m + 5/6 * n
  n = m + 9/20*t
  t = m + 13/42*b
  B = 7/12(n + N)
  N = 9/20(t + T)
  T = 11/30(m + M)
  M = 13/42(b + B)
qui conduit à la solution, z étant un paramètre entier quelconque, 

{ A =
  [-6, 5, 6, 0, 0, 0, 0, 0;
  0, -20, 20, 9, 0, 0, 0, 0;
  13, 0, 42, -42, 0, 0, 0, 0;
  0, 7, 0, 0, -12, 7, 0, 0;
  0, 0, 0, 9, 0, -20, 0, 9;
  0, 0, 11, 0, 0, 0, 11, -30;
  13, 0, 0, 0, 13, 0, -42, 0]
} 
%1 = 
  [-6, 5, 6, 0, 0, 0, 0, 0;
   0, -20, 20, 9, 0, 0, 0, 0;
   13, 0, 42, -42, 0, 0, 0, 0;
   0, 7, 0, 0, -12, 7, 0, 0;
   0, 0, 0, 9, 0, -20, 0, 9;
   0, 0, 11, 0, 0, 0, 11, -30;
   13, 0, 0, 0, 13, 0, -42, 0]


gp>  H = mathnf(A, 1)[1]
%2 = 
 [45, 39, 6, 32, 10, 0, 3;
   0, 1, 0, 0, 0, 0, 0;
   0, 0, 7, 4, 0, 0, 1;
   0, 0, 0, 1, 0, 0, 0;
   0, 0, 0, 0, 1, 0, 0;
   0, 0, 0, 0, 0, 1, 0;
   0, 0, 0, 0, 0, 0, 1]


gp>  U = mathnf(A, 1)[2]
%3 = 
  [10366482 -5152434 377822331012 -39871691734469
   -231909102725990 314125208121690 2649594446226 328544517685]
  [7460514 -3708081 271909871649 -28694721544752
   -166899542932178 226068546006716 1906850989602 236445784965]
  [4149387 -2062359 151230771311 -15959423780508
   -92826150282503 125734753116095 1060551954891 131506363548]
  [7358060 -3657160 268175778529 -28300661698320
   -164607539221500 222963984201380 1880664521580 233198714260]
  [7206360 -3581760 262646839434 -27717191275459
   -161213850708508 218367169768860 1841891148174 228390891960]
  [4893246 -2432079 178341853095 -18820463498892
   -109467058282407 148275173597044 1250676692982 155081458395]
  [5439213 -2703441 198240457519 -20920368550692
   -121680914158297 164819069347075 1390221731600 172384769652]
  [3515820 -1747460 128139450571 -13522590521440
   -78652590294960 106536401569829 898617018380 111426748840]


gp>  U[,1]
%4 = [10366482, 7460514, 4149387, 7358060, 7206360, 
         4893246, 5439213, 3515820]~
Le premier vecteur est une base du noyau. 
  b = 10366482z,
  n = 7460514z,
  m = 4149387z,
  t = 7358060z,
  B = 7206360z,
  N = 4893246z,
  M = 5439213z,
  T = 3515820z.


{ A =
  [-6, 5, 6, 0, 0, 0, 0, 0;
  0, -20, 20, 9, 0, 0, 0, 0;
  13, 0, 42, -42, 0, 0, 0, 0;
  0, 7, 0, 0, -12, 7, 0, 0;
  0, 0, 0, 9, 0, -20, 0, 9;
  0, 0, 11, 0, 0, 0, 11, -30;
  13, 0, 0, 0, 13, 0, -42, 0]
}
H = mathnf(A, 1)[1]
U = mathnf(A, 1)[2]
U[,1]

De plus, la somme du nombre de taureaux blancs et du nombre de taureaux noirs est un carré. La somme du nombre de taureaux roux et du nombre de taureaux tachetés est un triangulaire.Cela conduit à une équation de Pell-Fermat (un triangulaire est un nombre de la forme n(n+1)).

V-2 Identité de Bézout

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Trouver des entiers e1, ..., e5 tels que

12e1 + 43e2 + 189e3 + 19e4 + 289e5 = 220.0

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-2 Identité de Bézout

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

On cherche la réduction HNF de la matrice (12, 43, 189, 19, 289) : 
gp>  mathnf(Mat([12, 43, 189, 19, 289]), 1) 
%1 = [Mat(1), 
 [-289, 1032, 4536, 456, -24;
  0, 1, 0, 0, 0;
  0, 0, 1, 0, 0;
  0, 0, 0, 1, 0;
  12, -43, -189, -19, 1]]


gp>  U = mathnf(A, 1)[2]
%2 = [-289, 1032, 4536, 456, -24;
      0, 1, 0, 0, 0;
      0, 0, 1, 0, 0;
      0, 0, 0, 1, 0;
      12, -43, -189, -19, 1]


gp>  A*U[2]
%3 =  [0, 0, 0, 0, 1]


gp>  mathnf(A, 1) 
%4 = [[12; 43; 189; 19; 289], Mat(1)]
On lit sur ces résultats que le noyau est de rang 4 et possède comme bases les 4 premières colonnes de U. 1 est l'image du vecteur (-24, 0, 0, 0, 1). Donc une solution est

De manière générale, pour résoudre le système linéaire M X = B, on écrit M U = (0 | H) sous forme d'Hermite, On doit résoudre

On résoud donc d'abord le système (0 | H) Y = B qui est simple car "triangulaire" : ici on trouve Y = (y1, y2, y3, y4, 220), puis on applique U : X = U Y : 
gp>  Y = [y1, y2, y3, y4, 220]~ ; 


gp>  U*Y
%6 = [-289*y1 + 1032*y2 + 4536*y3 + 456*y4 - 5280]
     [y2]
     [y3]
     [y4]
     [12*y1 + -43*y2 -189*y3 - 19*y4 + 220)]

Il peut bien sûr y avoir des conditions de compatibilités, ce qu'il n'y a pas ici. 

  A = Mat([12, 43, 189, 19, 289])
  HU = mathnf(A, 1)
  H1 = HU[1] ; U = HU[2]
  H = A*U
  Z = 220*H1[1,1]
  Y = [y1,y2,y3,y4,Z]~
  U*Y

V-3 Un système modulo des entiers divers

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

On cherche un polynôme P du troisième degré à coefficients entiers tel que que

ou plus généralement

Existe-t-il pour toutes valeurs des bi ? quelles conditions faut-il mettre sur les bi ? comment trouver toutes les solutions ? Le polynôme 7x3 - 67x2 + 52x + 43 est-il solution ? (répondre en exploitant les calculs précédents).

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-3 Un système modulo des entiers divers

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

On introduit des variables entières supplémentaires : on obtient un système du type
AX + diag(M) Y = B
La matrice A est une matrice de Vandermonde ; le programme suivant retourne la matrice A1 = (A | diag(M)) si on l'applique aux vecteurs a = (53, 19, 2, 47) et m = (85, 68, 561, 64). 

gp>  { vandm(a,m)= M = matrix(#a,#a,i,j,a[i]^(j-1));
     M = concat(M,matdiagonal(m)); } ;


gp>  A1 = vandm([53, 19, 2, 47],[85, 68, 561, 64]) ; 


gp>  VM = mathnf(M, 1) 
%2 = [[17, 0, 1, 0; 0, 68, 52, 17; 0, 0, 1, 0; 0, 0, 0, 1], 
 [-179520, -2116395503, -89442813409, -4183688174927, 
                         -71808, 0, 111400576, 40293825;
  0, 1, 0, 0, 0, 0, 0, 0;
  0, 0, 1, 0, 0, 0, 0, 0;
  0, 0, 0, 1, 0, 0, 0, 0;
  2112, 24898770, 1052268360, 49219859130, 845, 0, -1310595, -474045;
  2640, 31123463, 1315335486, 61524826001, 1056, 1, -1638243, -592556;
  320, 3772541, 159434605, 7457554679, 128, 0, -198575, -71825;
  2805, 33068679, 1397543925, 65370126111, 1122, 0, -1740634, -629591]]


gp>  H = VM[1]
%3 = [17, 0, 1, 0
      0, 68, 52, 17;
      0, 0, 1, 0;
      0, 0, 0, 1]


gp>  VM[2]
%4 = [-179520, -2116395503, -89442813409, -4183688174927,
                              -71808, 0, 111400576, 40293825;
  0, 1, 0, 0, 0, 0, 0, 0;
  0, 0, 1, 0, 0, 0, 0, 0;
  0, 0, 0, 1, 0, 0, 0, 0;
  2112, 24898770, 1052268360, 49219859130, 845, 0, -1310595, -474045;
  2640, 31123463, 1315335486, 61524826001, 1056, 1, -1638243, -592556;
  320, 3772541, 159434605, 7457554679, 128, 0, -198575, -71825;
  2805, 33068679, 1397543925, 65370126111, 1122, 0, -1740634, -629591]

On voit que le noyau de A1 est de rang 4. Seule la projection sur les quatre première lignes (projection sur le sous-module engendré par les quatre premiers vecteurs de la base canonique nous intéresse). On cherche une solution à l'équation (A|M) X = B. 


gp>  H^(-1)*[20, 37, 496, 61]~
%5 = [-28, -394, 496, 61]~

On résoud ensuite H X = B, puis on calcule U X. On remarque que malheureusement, les coefficients sont très grands. Trouver une petite solution est un autre problème très intéressant que l'on résoud par des méthodes LLL.

Pour vérifier que 7x3 - 67x2 + 52x + 43 est solution, on peut bien sûr faire la vérification directe. On peut aussi vérifier que la différence de cette "solution" avec la solution particulière trouvée est bien dans la projection du noyau. 

gp> Y0 = concat([0, 0, 0, 0], Y~)~
%6 = [0, 0, 0, 0, -28, -394, 496, 61]~


gp>  S0 = vecextract(V*Y0,"1..4")
%7 = [57714619645, 0, 0, 0]~


gp> K0 = S0-[43, 52, -67, 7]~
%8 = [57714619602, -52, 67, -7]~


gp>  mathnf(concat(K,K0)) == mathnf(K)
%9 = 1

Pour traiter le cas où le second membre n'est pas connu, on peut utiliser la forme d'Hermite, mais il est plus facile d'utiliser la forme de Smith : U A V = S. Résoudre U A V = B revient à résoudre successivement S Y = B 

gp>  matsnf(A)
%10 = [68, 17, 1, 1]


gp>  matsnf(A, 1)
%11 = [[-52, 1, 0, -17;
         -1, 0, 1, 0;
          1, 0, 0, 0;
          0, 0, 0, 1], 
  [8930, -7238, -29469, -18887424, 0, -6293129, 6072323, 12689988;
   -5125, 4149, 12001, 11510400, 0, 3835709, -3724697, -7733550;
   340, -273, -759, -768768, 0, -256187, 248943, 516516;
   -5, 4, 11, 11328, 0, 3775, -3669, -7611;
   612, -486, -1320, -1390272, 0, -463304, 450417, 934089;
   0, -7, 0, 240, 1, 80, -85, -161;
   0, 0, 15, -2048, 0, -684, 732, 1376; 0, 0, 0, 3, 0, 1, -1, -2], 
  [0, 0, 0, 0, 68, 0, 0, 0;
   0, 0, 0, 0, 0, 17, 0, 0;
   0, 0, 0, 0, 0, 0, 1, 0;
   0, 0, 0, 0, 0, 0, 0, 1]]


gp>  U = matsnf(A, 1)[1]
%12 = [-52, 1, 0, -17;
       -1, 0, 1, 0;
       1, 0, 0, 0;
       0, 0, 0, 1]


gp>  B=[b1,b2,b3,b4]~;


gp>  B1 = U*B
%14 = [b3, 52*b3 + (17*b4 + b1), b2 + b3, b4]~


gp>  U = matsnf(A, 1)[2]
%15 =[8930, -7238, -29469, -18887424, 0, -6293129, 6072323, 12689988;
       -5125, 4149, 12001, 11510400, 0, 3835709, -3724697, -7733550;
       340, -273, -759, -768768, 0, -256187, 248943, 516516;
       -5, 4, 11, 11328, 0, 3775, -3669, -7611;
       612, -486, -1320, -1390272, 0, -463304, 450417, 934089;
       0, -7, 0, 240, 1, 80, -85, -161;
       0, 0, 15, -2048, 0, -684, 732, 1376;
       0, 0, 0, 3, 0, 1, -1, -2]


gp>  U = matsnf(A, 1)[3]
%16 = [0, 0, 0, 0, 68, 0, 0, 0;
       0, 0, 0, 0, 0, 17, 0, 0;
       0, 0, 0, 0, 0, 0, 1, 0;
       0, 0, 0, 0, 0, 0, 0, 1]
La condition pour qu'il existe une solution est donc que 68 divise b3 et que 17 divise 52b3 + 17b4 + b1, cette dernière condition étant équivalente à ce que 17 divise b1 + b3. 

{ vandm(a,m) = M = matrix(#a,#a,i,j,a[i]^(j-1));
   M = concat(M,matdiagonal(m)); M }
  A1 = vandm([53, 19, 2, 47],[85, 68, 561, 64]) ;
  VM = mathnf(A1, 1)
  H = VM[1]
  V = VM[2]
  K = vecextract(V,"1..4","1..4")
  B = [20, 37, 496, 61]
  Y = H^(-1)*B~
  Y1 = concat([y1,y2,y3,y4], Y~)~
  Y1 = vecextract(V*Y1,"1..4")
  Y0 = concat([0, 0, 0, 0], Y~)~
  S0 = vecextract(V*Y0,"1..4")
  K0 = S0-[43, 52, -67, 7]~
  mathnf(concat(K,K0)) == mathnf(K)


  UVS = matsnf(A1, 1) ;
  U = UVS[1]
  V = UVS[2]
  S = UVS[3]
  B = [b1,b2,b3,b4]~
  B1 = U*B

V-4 Un système linéaire : condition de compatibilité

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Résoudre dans le système linéaire

selon les valeurs (entières) de a, b, c, d.

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-4 Un système linéaire : condition de compatibilité

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

gp>  {A =
  [4, -17, -22, -9;
  0, -30, 45, -18;
  20, -75,  95, -39;
  7, -25,  33, -14]
} ;


gp>  U = matsnf(A, 1)[1]; S = matsnf(A, 1)[3]
%2 = [29040, 0, 0, 0
      0, 1, 0, 0;
      0, 0, 1, 0;
      0, 0, 0, 1]


gp>  B=[b1,b2,b3,b4]; U*B
%2 = [133*b2 + (265*b3 + (1760*b4 - 62*b1)), 
        15*b2 + (12*b3 - 7*b1), b3, b4]~
La condition pour qu'il existe une solution est donc que 29040 divise 133b2 + 265b3 + 1760b4 - 62b1. Si l'on veut obtenir une condition paramétrée, c'est-à-dire une expression des bi en fonction de paramètres entiers quelconques, il ne reste plus qu'à résoudre
... ce qui ramène à un problème du type le précédent ! 
gp>  B = Mat([-62, 133, 265, 1760, 29040])
%3 = [-62, 133, 265, 1760, 29040]


gp>  mathnf(Mat(B))
%4 = [1]


gp>  mathnf(Mat(B), 1)
%5 = [Mat(1), 
   [14520, -809837, 106496610, 707298240, -401874;
     0, 2, -265, -1760, 1;
     0, 0, 1, 0, 0;
     0, 0, 0, 1, 0;
     31, -1729, 227370, 1510080, -858]]


gp>  mathnf(Mat(B), 1)[2]
%6 = [14520, -809837, 106496610, 707298240, -401874;
      0, 2, -265, -1760, 1;
      0, 0, 1, 0, 0;
      0, 0, 0, 1, 0;
      31, -1729, 227370, 1510080, -858]


gp>  B*mathnf(Mat(B), 1)[2]
%7 = [0, 0, 0, 0, 1]


gp>  C = vecextract(mathnf(Mat(B), 1)[2],"1..3","1..4")
%8 = [14520, -809837, 106496610, 707298240;
      0, 2, -265, -1760;
      0, 0, 1, 0]


gp>  [z1,z2,z3]*C
%9 = [14520*z1, -809837*z1 + 2*z2, 106496610*z1 + (-265*z2 + z3),
        707298240*z1 - 1760*z2]

On trouve donc que pour tous paramètres entiers z1, z2, z3, le système A X = B a une solution entière si et seulement si B est de la forme

avec z1, z2 et z3 entiers. 

{A = [4, -17, -22, -9;
      0, -30, 45, -18;
      20, -75,  95, -39;
      7, -25,  33, -14]
} ;
U = matsnf(A, 1)[1]; S = matsnf(A, 1)[3]
B=[b1,b2,b3,b4]; U*B
B = Mat([-62, 133, 265, 1760, 29040])
mathnf(Mat(B))
mathnf(Mat(B), 1)
mathnf(Mat(B), 1)[2]
B*mathnf(Mat(B), 1)[2]
C = vecextract(mathnf(Mat(B), 1)[2],"1..3","1..4")
[z1,z2,z3]*C

V-5 Le groupe multiplicatif dans les rationnels

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

On regarde tous les rationnels de la forme . Obtient-on tous les rationnels engendrés multiplicativement par 2, 3, 5 ? Sinon, quelle est "la différence" (à définir proprement) ? Généraliser.

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-5 Le groupe multiplicatif dans les rationnels

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

V-6 Carreleur cherche aide

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Un carreleur doit carreler un mur. Il a commencé par mettre des repères-clous régulièrement sur son mur (il est un peu bizarre), il a choisi des vecteurs v1 et v2 à coefficients entiers et il a mis ses repères aux points de coordonnées n v1 + m v2 avec m et n entiers (il est un peu mathématicien). Il voudrait que chaque carreau ait son extrémité en bas à gauche coincée sur un clou et que chaque clou soit le coin en bas à gauche d'un carreau. Quelle taille de carreaux doit-il commander ? Combien de solutions y a-t-il ? Même problème dans le cas de maçonnerie dans l'espace ! Résoudre pour les vecteurs v1=(3,2) et v2 = (5,10), puis dans l'espace pour v1=(-1,-3,0), v2=(-5,-12,0), v3=(2,7,-2).

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-6 Carreleur cherche aide

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

On note e1 = (1, 0), e2 = (0, 1). La base ( e1, e2) donne les directions horizontale et verticale du mur. Soit M le -module libre engendré par v1 et v2.

Trouvons d'abord quelques solutions. Prenons une base de M donnée par la normalisation de Hermite. On a donc w1 = a e1 w2 = b e1 + c e2 avec . On se persuade facilement avec un dessin que l'on peut paver le plan comme indiqué avec des briques de dimension .

On aurait pu échanger le rôle de e1 et e2 ce qui revient à multiplier la matrice de départ à gauche par une matrice de permutation par et à appliquer ensuite la normalisation de Hermite.

On a donc obtenu deux solutions. Réciproquement, on doit montrer que ce sont les deux seules solutions.

Démonstration

On se persuade d'abord qu'il existe deux briques ayant un côté commun, par exemple, le côté vertical et on met l'origine sur le coin commun en bas. On note w1 le vecteur perpendiculaire (donc horizontal) porté par le côté horizontal de la brique de droite. C'est un multiple de e1 qui appartient à M : w1 = a e1. Soit maintenant w2 un vecteur reliant l'origine (coin en bas à gauche d'une des briques choisies) à un autre coin sur la face verticale opposée (un dessin rend les choses claires). On a alors w2 = b e1 + c e2 avec . Les coefficients a, b et c sont entiers. Et il doit être clair que w1 et w2 est encore une base de M. En tout cas, la matrice associée à w1, w2 est de la forme avec .
Fin de la démonstration

gp> A = [\A] ; 
gp> H = mathnf(A) ; W=[0,1;1,0] ; V = W * mathnf(W*A)*W  ;
gp> H
\%3 = [\H]
gp> V
\%4 = [\V]

De manière générale, en dimension n, il y a n! solutions obtenues en prenant les diagonales des formes normales de Hermite de PpA où Pp est une matrice de permutation associée à une permutation p. On a alors PpAU = H, donc AUPp = Hp avec . La matrice Hp vérifie que son (i, j)-ième coefficient est nul dès que p(i) < p(j). Donnons un exemple en dimension 3. 

gp> { carreleur(A) = n=#A ; L=listcreate(n!) ;
       for(k = 1, n!, v = numtoperm(3,k); 
          w = matrix(n, n, i, j, if(i == v[j], 1)); 
          H = mathnf(w*A) ; B = w^(-1)*H*w ;
          V=vector(n, i, B[i, i]) ;
          listput( L, V) ;
       );
     Vec(L)}
     
gp>  A = [5, 2, 1; -4, 2, 4; 0, 3, -6]
%1 = [5, 2, 1;
      -4, 2,4;
       0, 3, -6]


gp> carreleur(A)
%3 = [[1, 12, 15], [3, 2, 30], [15, 2, 6], [5, 12, 3], 
    [15, 4, 3], [1, 6, 30]]


A = [\A] ; 
H = mathnf(A) ; W=[0,1;1,0] ; V = W * mathnf(W*A)*W  ;
H
V
{
   carreleur(A) = n=#A ; L=listcreate(n!) ;
       for(k = 1, n!, v = numtoperm(3,k); 
          w = matrix(n, n, i, j, if(i == v[j], 1)); 
          H = mathnf(w*A) ; B = w^(-1)*H*w ;
          V=vector(n, i, B[i, i]) ;   
       );
     Vec(L)
}
A = [5, 2, 1; -4, 2, 4; 0, 3, -6] 
carreleur(A)

Référence : Bricklaying and the Hermite Normal Form, William J. Gilbert, American Mathematical Monthly , Vol. 100, 3, March 1993, pp. 242-245

V-7 Base

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Trouver une base du -module engendré dans par les vecteurs

-2e1 - 2e2 - 2e3 - 3e4 - e5,

-2e1 - 3e2 - e4,

-e1 - 3e2 - e3- e4 + e5,

-3e1 - 2e2 - 2e3 - 3e4 - 3e5,

-3e1 + e2 + e3 - 2e5,

-3e1 - 2e3 - 3e4 - e5.

Solution

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

gp> {A = mattranspose([-2, -2, -2, -3, -1;
  -2, -3, 0, -1, 0 ;
  -1, -3, -1, -1, 1;
  -3, -2, -2, -3, -3 ;
  -3, 1, 1, 0, -2 ;
  -3, 0, -2, -3, -1])
} ;


gp>  mathnf(A, 1)
%2 = [2, 1, 0, 1, 1;
      0, 2, 1, 1, 1;
      0, 0, 1, 0, 0;
      0, 0, 0, 1, 0;
      0, 0, 0, 0, 1]
Une base du -module est 2e1, e1 + 2e2, e2 + e3, e1 + e2 + e4, e1 + e2 + e5. 
gp>  mathnf(A, 1)[2]
%3 = [-13, -2, 10, -1, 3, -1;
       8, 2, -6, 2, -3, 1;
      -5, -2, 3, -2, 2, -1;
       5, 1, -4, 0, -1, 0;
      -7, -2, 5, -1, 2, -1;
       7, 1, -5, 1, -2, 1]
La première colonne est un élément du noyau et donne donc une relation entre les vecteurs de départ
-13f1 + 8f2 -5f3 + 5f4 -7f5 +7f6 = 0
Si on veut aller plus loin, soit L le -module engendré 
gp>  matsnf(A)
%4 =[4, 1, 1, 1, 1]
Donc est un groupe abélien fini isomorphe à . 
gp>  U = matsnf(A, 1)[1]
%5 = [-2, 1, -1, -3, -3;
       0, 0, 1, 0, 0;
       0, 0, 0, 1, 0;
       0, 0, 0, 0, 1;
       1, 0, 0, 0, 0]


gp>  matsnf(A, 1)[2]
%6 = [-13, -4, 12, 28, 24, 23;
        8, 2, -6, -19, -15, -14;
       -5, -2, 3, 12, 9, 8;
        5, 1, -5, -11, -10, -9;
   -7, -2, 6, 16, 13, 12;
   7, 3, -6, -15, -12, -12]


gp>  matsnf(A, 1)[3]
%7 = [0, 4, 0, 0, 0, 0;
      0, 0, 1, 0, 0, 0;
      0, 0, 0, 1, 0, 0;
      0, 0, 0, 0, 1, 0;
      0, 0, 0, 0, 0, 1]


gp>  matsnf(A, 1)[1]^(-1)
%8 = [0, 0, 0, 0, 1;
      1, 1, 3, 3, 2;
      0, 1, 0, 0, 0;
      0, 0, 1, 0, 0;
      0, 0, 0, 1, 0]


gp>  A*matsnf(A, 1)[2] 
 %9 = [0, 0, 0, 0, 0, 1;
       0, 4, 1, 3, 3, 2;
       0, 0, 1, 0, 0, 0;
       0, 0, 0, 1, 0, 0;
       0, 0, 0, 0, 1, 0]

Une base adaptée de est donnée par la matrice U1 inverse de U (il s'agit donc des vecteurs e2, e2 + e3, 3e2 + e4, 3e2 + e5, e1 + 2e2), la nouvelle base de L (exprimée dans la base des fi) est donnée par V :

(les vecteurs de A V sont bien proportionnels aux vecteurs correspondants de U1). 
{A = mattranspose([-2, -2, -2, -3, -1;
  -2, -3, 0, -1, 0 ;
  -1, -3, -1, -1, 1;
  -3, -2, -2, -3, -3 ;
  -3, 1, 1, 0, -2 ;
  -3, 0, -2, -3, -1])
}
mathnf(A, 1)
mathnf(A, 1)[2]
matsnf(A)
U = matsnf(A, 1)[1]
matsnf(A, 1)[2]
matsnf(A, 1)[3]
matsnf(A, 1)[1]^(-1)
A*matsnf(A, 1)[2]

V-8 Groupe abélien

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Soit . Déterminer une base du sous- -module de engendré par les vecteurs colonnes de A. Si f est l'application -linéaire dont la matrice dans les bases canoniques de et est A, donner une base du noyau de f. Donner la structure du groupe abélien .

Solution

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

gp>  {A= = [10, 10, -9, -8;
   -16, -6, 22, 20;
   6, -1, -4, -6;
   8, 12, -5, -4;
   12, 8, -13, -12]};


gp>  V = mathnf(A, 1)[1]
%2 = [0, 2, 1;
      6, 4, 4;
     15, 0, 13;
      0, 4, 1;
      0, 0, 1]


gp>  mathnf(A, 1)[2]
%3 = [-4, 3, 1, -1;
       2, -1, 0, 1;
       4, 4, 0, 7;
      -7, -2, 1, -8]


gp>  matsnf(A)
%4 = [0, 0, 6, 1, 1]


gp>  matsnf(A, 1)[1]
%5 = [-2, 0, 0, 1, 1;
     -22, -5, 2, 16, 0;
     -15, -5, 0, 11, 0;
       0, 0, 1, 0, 0;
      11, 3, -1, -8, 0]


gp>  matsnf(A, 1)[2]
%6 = [4, 5, 1, -5;
     -2, 4, 1, 6;
     -4, 2, 1, 9;
      7, 3, 0, -12]
Que lit-on sur les calculs précédents. Le noyau de f est engendré par (-4, 2, 4, -7). Une base de L est donnée par la matrice V. Le groupe abélien est isomorphe à . Un isomorphisme explicite est donné par = où s1 est l'image de e5, s2 est l'image de 7e1 + e2 + 10e4 + 4e5 et s2 est l'image de 8e1 + 11e4 + 5e5. Les deux derniers vecteurs de l'inverse U1 de U appartiennent à L : comme le remontre le calcul suivant (deux sous- -modules sont égaux si les formes normales d'Hermite d'un de leurs systèmes générateurs le sont.) 

gp>  U1 = matsnf(A, 1)[1]^(-1)
%7 = [0, 7, 8, 11, 25;
      0, 1, 0, 0, 2;
      0, 0, 0, 1, 0;
      0, 10, 11, 15, 35;
      1, 4, 5, 7, 15]


gp>  mathnf(A) == mathnf(concat (A, U1[,4]))
%8 = 1


gp>  mathnf(A) == mathnf(concat (A, U1[,5]))
%9 = 1
Dans Pari/GP, le résultat d'un test est 1 s'il est vrai et 0 s'il est faux. 

{A= = [10, 10, -9, -8;
   -16, -6, 22, 20;
   6, -1, -4, -6;
   8, 12, -5, -4;
   12, 8, -13, -12]}
V = mathnf(A, 1)[1]
mathnf(A, 1)[2]
matsnf(A)
matsnf(A, 1)[1]
matsnf(A, 1)[2]
U = matsnf(A, 1)[1]
U1 = U^(-1):
mathnf(A) == mathnf(concat (A, U1[,4]))
mathnf(A) == mathnf(concat (A, U1[,5]))

V-9 Groupe abélien défini par générateurs et relations (1)

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Un groupe abélien G a trois générateurs u, v, w soumis aux relations

8u + 9v = 2u - 20v + 22w = 27v - 24w = 0
Décrire le module des relations. Donner la structure du groupe G.

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-9 Groupe abélien défini par générateurs et relations (1)

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

Les relations sont données par la matrice 
gp> { A = [8, 2, 0;
   9, -20, 27;
   0, 22, -24]
} ;


gp> matsnf(A)
time = 0 ms.
%2 = [240, 2, 1]
gp> matsnf(A, 1)[3]
%3 = [240 0 0]
     [0 2 0]
     [0 0 1]
La matrice SNF est
Le groupe G est donc isomorphe à . 

{ A = [8, 2, 0;
   9, -20, 27;
   0, 22, -24] };
matsnf(A)
matsnf(A, 1)[3]

V-10 Groupe abélien défini par générateurs et relations (2)

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Soit H un groupe abélien engendré par trois éléments h1, h2, h3 soumis aux relations

3h1 + h2 + h3 = 0, 25h1 + 8h2 + 10h3 = 0, 46h1 + 20h2 + 11h3 = 0
Montrer que H est fini. Trouver sa structure (en fait ) et trouver explicitement un isomorphisme de H dans et de dans H (préciser les images de h1, h2, h3 ou l'image de 1 pour la réciproque).

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-10 Groupe abélien défini par générateurs et relations (2)

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

On définit une application f de dans H par
On définit ensuite une application A
par
On a alors
On calcule alors la forme normale de Smith. On trouve 
gp> { A = 
    [3, 25, 46;
     1, 8, 20;
     1, 10, 11]} ; 


gp>  U = matsnf(A, 1)[1]
%2 = [1, -12, -10;
      0, 1, 0;
      0, 0, 1]


gp>  V = matsnf(A, 1)[2]
%3 = [112, 61, 52;
       -9, -5, -4;
       -2, -1, -1]


gp>  D = matsnf(A, 1)[3]
%4 = [19, 0, 0;
       0, 1, 0;
       0, 0, 1]


gp>  U^(-1)
 %5 = [1, 12, 10;
       0, 1, 0;
       0, 0, 1]
L'interprétation de ces calculs indique que H est isomorphe à . La nouvelle base (a1,a2,a3) de L2 est donnée par les colonnes de l'inverse de U et (19a1,a2,a3) est une base du noyau de f. On a donc e1 = a1, e2= -12a1+a2, e3= -10a1 +a3. Ainsi, l'isomorphisme de H sur est donné par
L'image de h2 est alors -12, celle de h3 est -10. 

{ A = [3, 25, 46;
   1, 8, 20;
   1, 10, 11]
 } ; 
U = matsnf(A, 1)[1]
V = matsnf(A, 1)[2]
D = matsnf(A, 1)[3]
U^(-1)

V-11 Groupe abélien défini par générateurs et relations (3)

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Le -module M est engendré par des éléments u1, u2, u3 soumis aux relations

3u1 + 2u2 - 2u3 = 0, - 4u1 - u2 + 4u3 = 0.0
Monter que M est un -module libre. Trouver une base de M.

Solution

Algèbre linéaire sur ZZ ---> V Des problèmes ---> V-11 Groupe abélien défini par générateurs et relations (3)

Solution

I Introduction picto

II Forme normale d'Hermite picto

III Forme normale de Smith picto

IV Groupes abéliens de type fini picto

V Des problèmes picto

Index

Solution

Une matrice des relations est 
gp> {A = 
  [3, -4;
   2, -1;
  -2, 4];
 }


gp>  matsnf(A)
%2 = [0, 1, 1]
Comme M est isomorphe à , il est libre.

Par Version interactive
Dernière modif. 2012-05-09 20:22:34
Description: document donnant un point de vue algorithmique sur les groupes abéliens de type fini.

Keywords: module,hermite,smith, forme normale, matrice, Gauss,groupe, group, wims, mathematics, mathematical, math, maths, interactive mathematics, interactive math, interactive maths, mathematic, online, calculator, graphing, exercise, exercice, puzzle, calculus, K-12, algebra, mathématique, interactive, interactive mathematics, interactive mathematical, interactive math, interactive maths, mathematical education, enseignement mathématique, mathematics teaching, teaching mathematics, algebra, geometry, calculus, function, curve, surface, graphing, virtual class, virtual classes, virtual classroom, virtual classrooms, interactive documents, interactive document