Algèbre linéaire sur ZZ

Algèbre linéaire sur ZZ


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

Algèbre linéaire sur ZZ → I Introduction

Définition

Soit A un anneau. Un A-module est un groupe abélien (M,+) muni d'une loi externe A×M→M vérifiant les mêmes axiomes que ceux d'un espace vectoriel.
On prend dans la suite A=ℤ.

Définition

Un ℤ-module libre (de rang n) L est un ℤ-module tel qu'il existe une suite (e 1,...,e n) (appelée base) de n éléments de L vérifiant : tout élément de L s'écrit comme combinaison linéaire de (e 1,...,e n), 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 GL m(ℤ) (groupe des matrices inversibles dans ℤ, on montre que ce sont les matrices dont le déterminant est inversible dans ℤ, c'est-à-dire égal à ±1) ...

I-1 Interprétation des matrices

I-2 Changements de base

I-3 Cas de rang 2

Algèbre linéaire sur ZZ → I Introduction

I-1 Interprétation des matrices

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

Soit L un ℤ-module libre de rang n. Fixons une base ℬ. Une matrice A de taille n×m représente un sous- ℤ-module M de L : si v 1, ... , v m sont les vecteurs représentés par les vecteurs colonnes de A dans la base ℬ, la matrice A représente le sous-module ℤv 1+...+ℤv m. Une matrice a aussi une interprétation en tant que matrice d'un morphisme : la matrice A représente le morphisme f de ℤ m dans L donné par f(0,...,0,1,0,..,0)=v i 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

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

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

Algèbre linéaire sur ZZ → I Introduction → I-2 Changements de base → I-2-1 Opérations à droite

Remarque

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

Solution
Si b 1, ..., b m est un autre système générateur de M, la matrice B correspondante est AV avec V la matrice des b j exprimés dans le système générateur (a 1,...,a m) de M :
b j=v 1ja 1+...+v mja m
représenté par AV j (la base ℬ de L n'a pas changée).
La matrice V est à coefficients dans ℤ. Comme les vecteurs a i peuvent aussi s'exprimer comme combinaison entière des b i, son inverse est aussi à coefficients dans ℤ, autrement dit, le déterminant de la matrice V est égal à ±1 : V∈GL m(ℤ).
Attention, ici on a pris un système générateur ayant même nombre d'éléments.

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.
Algèbre linéaire sur ZZ → I Introduction → I-2 Changements de base → 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-2 Opérations à gauche

Remarque

Multiplier A à gauche par une matrice de GL n(ℤ) 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 n×m
Output: une forme échelonnée en colonnes pour M
j:=0
pour i=1 à n faire
      si il existe p>j tel que M[p][i]≠0 alors
             Choisir p tel que M[p][i]≠0.
             j:=j+1;
             Echange M[j] et M[p] ;
             M[j]←M[j]/M[j][i]
            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
(1 0 0 2 1 0 3 1 0 4 1 1)(1 1 4 0 1 3 0 1 2 0 0 1)(1 2 3 4 0 1 1 1 0 0 0 1)(1 0 0 0 1 1 1 0 4 3 2 1)
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 f:{1,..,r}→{1..,n} 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.
Algèbre linéaire sur ZZ → I Introduction → I-2 Changements de base → I-2-2 Opérations à gauche

I-3 Cas de rang 2

Algèbre linéaire sur ZZ → I Introduction → I-3 Cas de rang 2

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 ℤ

Algèbre linéaire sur ZZ → I Introduction → I-3 Cas de rang 2

I-3-1 dans un corps

Algèbre linéaire sur ZZ → I Introduction → I-3 Cas de rang 2 → I-3-1 dans un corps

(a b)(0 1 1 −a/b)=(b 0)
(0 1 1 −a/b)(a b)=(b 0)

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. (1 0)).

Exercice

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

Solution
(0 0 0 0), (1 0 0 0), (1 × 0 1), (1 0 0 1).
(0 0), (1 0), (× 1).
On vérifie que ces matrices ne sont pas équivalentes.

I-3-2 dans ℤ

Algèbre linéaire sur ZZ → I Introduction → I-3 Cas de rang 2 → I-3-2 dans ℤ

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

En itérant comme dans l'algorithme d'Euclide, on obtient
(a b)(0 1 1 −q 1)(0 1 1 −q 2)...=(pgcd(a,b) 0)

Cette opération permet de transformer (a b) en (pgcd(a,b) 0) ; de même en multipliant par une matrice convenable à droite, on peut transformer (a b) en (pgcd(a,b) 0) :
(a b)(u s v t)=(pgcd(a,b) 0)
ou
(u v s t)(a b)=(pgcd(a,b) 0)
avec au+bv=pgcd(a,b), s=−bpgcd(a,b), t=apgcd(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 M 2(ℤ)/GL 2(ℤ).
Comment peut-on traduire ces énoncés en termes de sous-modules ? Faire de même avec M 2(ℤ)/GL 2(ℤ), M 2,1(ℤ)/GL 2(ℤ). Préciser comment réduire une matrice de M 2(ℤ) en un représentant parmi ceux trouvés. Quelle interprétation peut-on donner de ces ensembles quotients ?

Solution
Formes possibles : (0 0 0 0); (0 a 0 0) avec a strictement positif ; (0 b 0 d) avec d strictement positif ; (a b 0 d) avec a et d strictement positifs et 0≤b<a.
Vérifiez qu'elles ne sont pas équivalentes modulo la multiplication à droite par une matrice de GL 2(ℤ). 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)).

Donnons une idée des opérations à faire
  • Si c et d sont non nuls,
    (a b c d)→euclide(a 1 × 0 pgcd(c,d))→chang.signe(∣a 1∣ × 0 pgcd(c,d))
    • si ∣a 1∣≠0,
      →div.eucl(∣a 1∣ b 0 pgcd(c,d))=(q 1 * 0 q 2)
      avec 0≤b<∣a∣ si a 1 est non nul.
    • si ∣a 1∣=0,
      =(0 × 0 q 1)
  • Si c=0 et d non nul,
    (a b 0 d)→chang.signe(∣a∣ b 0 ∣d∣)→div.eucl(∣a∣ b 1 0 ∣d∣)=(q 1 * 0 q 2)
  • Si c et d sont nuls et a et b non nuls,
    (a b 0 0)→euclide(0 pgcd(a,b) 0 0)=(0 q 1 0 0).
  • Si a, c et d sont nuls et b non nuls, etc ...

II Forme normale d'Hermite

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

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

Algèbre linéaire sur ZZ → II Forme normale d'Hermite → II-1 Définitions

Définition

La matrice (0∣H) est une forme normale de Hermite (supérieure échelonnée en colonnes) (HNF) si H=(H ij) est une matrice n×r telle qu'il existe une fonction strictement croissante
f:{1,…,r}→{1,…,n}
vérifiant
  1. q j:=H f(j),j>0 et H i,j=0 si i>f(j),
  2. 0≤H f(j),k<q j si k>j.

Remarque

Les q j 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 ?) :
(0 0 q 1 ⋆ ⋆ ⋆ ⋆ 0 0 ∣ × × × × ∣ × × × × ∣ q 2 ⋆ ⋆ ⋆ ∣ q 3 ⋆ ⋆ ∣ q 4 ⋆ ∣ × 0 0 ∣ q 5 )
Les autres entrées times peuvent être nulles, positives ou négatives.
  • f(j) est la ligne du pivot q j>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
    (H f(i),j) i,j≤r=(q 1 ⋆ ⋆ ⋆ ⋆ q 2 ⋆ ⋆ ⋆ q 3 ⋆ ⋆ q 4 ⋆ q 5 )
    est non singulière et triangulaire supérieure
  • Tous les coefficients à droite du pivot q j sont réduits modulo q j (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
2,3 : un ℤ-module dans ℤ 2, équivalent à (0,v 1,v 2). On est ramené au cas des matrices de taille (2,2). (0 0 0 0 0 0); (0 0 q 0 0 0) avec q strictement positif ; (0 0 × 0 0 q) avec q strictement positif ; (0 q 1 ⋆ 0 0 q 2) avec q 1 et q 2 strictement positifs et 0≤⋆<q 1.
3,2 : un sous- ℤ-module de ℤ 3 engendré par deux vecteurs.
Convention : aucune condition sur les times, une condition sur les ⋆ par rapport au pivot de la même ligne, les q i sont des pivots (positifs ou nuls)
(0 × 0 q 1 0 0) (0 q 1 0 0 0 0) (q 1 ⋆ 0 q 2 0 0) (q 1 ⋆ 0 × 0 q 2)

Exercice

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

Solution
La même chose avec des pivots égaux à 1 et des ⋆ égaux à 0
(0 0 vline 1 0 0 0 0 0 0 vline × × × × vline × × × × vline 1 0 0 0 vline 1 0 0 vline 1 0 vline × 0 0 vline 1 )

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

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

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

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


Si A est une matrice n×n à 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 B=AV.
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 Gl m(ℤ) opère à droite sur M n×m et l'ensemble des matrices HNF de taille n×m forme un système de représentants de M n×m(ℤ)/Gl m(ℤ).
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

Algèbre linéaire sur ZZ → II Forme normale d'Hermite → II-3 Hermite et Hermite

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: A=(A[i,j])∈M m×n(ℤ)
Output:
Soit R←n+1
pour i=m,,1 faire
      siil existe j<R−1 tel que A[i,j]≠0 alors
             Choisir j tel que A[i,j]≠0
             Ecrire (A[i,j]A[i,R−1])(u s v t)=(0d)
             (A[,j]A[,R−1])←A[,j](A[,R−1])(u s v t)

      si A[i,R−1]≠0 alors
             R←R−1


R←n
pour i=m,,1 faire
      si A[i,R]≠0 alors
             A[i,]←A[i,]×sign(A[i,R])
            pour j = n, . . . , n - R + 2 faire
                   q←floor(A[i,j]/A[i,R])
                   A[,j]←A[,j]−qA[,R]

             R←R−1



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
(−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)
Obtient-on les mêmes pivots ? Le nombre de pivots est-il le même ? Faire d'autres essais.
Solution

Définition

La matrice (0∣H) est une forme normale d'Hermite supérieure échelonnée en colonnes si H=(H ij) est une matrice n×r telle qu'il existe une fonction strictement croissante
f:{1,…,r}→{1,…,n}
vérifiant
  1. q j:=H f(j),j>0 et H i,j=0 si i>f(j),
  2. 0≤H f(j),k<q j si k>j.

Définition

La matrice (H 0) est une forme normale d'Hermite supérieure échelonnée en lignes si H=(H ij) est une matrice r×m telle qu'il existe une fonction strictement croissante
f:{1,…,r}→{1,…,n}
vérifiant
  1. q i:=H i,f(i)>0 et H i,j=0 si j>f(i),
  2. 0≤H k,f(i)<q i si k>i.

Définition

La matrice (H∣0) est une forme normale d'Hermite inférieure échelonnée en colonnes si H=(H ij) est une matrice n×r telle qu'il existe une fonction strictement croissante
f:{1,…,r}→{1,…,n}
vérifiant
  1. q j:=H f(j),j>0 et H i,j=0 si i<f(j),
  2. 0≤H f(j),k<q j si k<j.

Définition

La matrice (0 H) est une forme normale d'Hermite inférieure échelonnée en lignes si H=(H ij) est une matrice r×m telle qu'il existe une fonction strictement croissante
f:{1,…,r}→{1,…,n}
vérifiant
  1. q i:=H i,f(i)>0 et H i,j=0 si j<f(i),
  2. 0≤H k,f(i)<q j si k<i.

Si A est une matrice (n×m), on note w(A)=W nAW m (ou en abrégé WAW). Pour passer d'une forme à l'autre,
  • triangulaire supérieure, échelonnée en colonnes
    AU=hermite 1(A),
  • triangulaire supérieure, échelonnée en lignes
    VA=hermite 2(A)=transposew(hermite 1(wtranspose(A))) :
    WA tW×U=H 1
    d'où
    U tWAW=H 1 t,
    WU tW×A=WH 1 tW.
  • triangulaire inférieure, échelonnée en colonnes
    AU=hermite 3(A)=w(hermite 1(wA))
    WAW×U=H 1
    d'où
    AWUW=WH 1W.
  • triangulaire inférieure, échelonnée en lignes
    VA=hermite 4(A)=transpose(hermite 1(transposeA))
    A t×U=H 1,
    d'où
    U tA=H 1 t.
Il reste à se persuader que la transposée d'une matrice échelonnée en lignes est échelonnée en colonnes, etc. Par exemple
A=(3 2 1 0 0 5 0 0 0), WAW=(0 0 0 5 0 0 2 1 3) A t=(3 0 0 1 0 0 2 5 0), WA tW=(0 5 2 0 0 1 0 0 3)
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]
Algèbre linéaire sur ZZ → II 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-4 Application de la forme d'Hermite

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
f:ℤ m→ℤ n
donné par sa matrice A.

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 : AV=(0∣H)
prendre les colonnes de la matrice V correspondant à une colonne de zéros dans H.

Algorithme

Trouver l'image d'un homomorphisme de ℤ-modules
f:ℤ m→ℤ n
donné par sa matrice A.

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 : AV=(0∣H).
prendre les colonnes de la matrice H.

Algorithme

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

Exercice

Des exemples traités : exemple , exemple

Image I
Image II
Questions diverses

Algorithme

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

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 (A∣B) : (A∣B)V=(0∣H).
prendre les colonnes (non nulles) de la matrice H

Algorithme

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

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.

Algorithme

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

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.

Algorithme

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

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 (A∣B) en utilisant la matrice HNF par colonnes :
prendre les n premières lignes N 1 du noyau N
calculer AN 1 et et le mettre sous forme HNF.
On cherche X et Y tel que AX=BY, donc (X,−Y) est dans le noyau de (A∣B)
Algèbre linéaire sur ZZ → II Forme normale d'Hermite → II-4 Application de la forme d'Hermite

III Forme normale de Smith

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

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

Algèbre linéaire sur ZZ → III Forme normale de Smith → III-1 Définitions

On va maintenant se permettre aussi des multiplications à gauche.

Définition

Une matrice (0∣D) ou (0 D) est dans une forme normale de Smith (SNF) si D est diagonale, de diagonale d 1,...,d n formée d'entiers positifs telle que d n∣…∣d 1 (en terme d'idéaux, telle que (d 1)⊂(d 2)⊂...).

III-2 Forme normale de Smith d'une matrice

Algèbre linéaire sur ZZ → III Forme normale de Smith → III-2 Forme normale de Smith d'une matrice
Le théorème suivant est admis.

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


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

Théorème

Soit A une matrice entière n×m. Il existe des matrices U et V unimodulaires et une unique matrice S de Smith telles que
UAV=S=(0 ∣ 0 0 ∣ D)
avec U carrée d'ordre n, V carrée d'ordre m, D diagonale de diagonale (d 1,...,d r) avec d r∣...∣d 1, d i>0.

Théorème [Traduction]

L'ensemble des matrices SNF n×m forment un système de représentants de
GL n(ℤ)\M n×m(ℤ)/GL m(ℤ)
(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

Algèbre linéaire sur ZZ → III Forme normale de Smith → III-3 Comment calculer la forme de Smith

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 2×2, 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 (a b c d). Soit d 1 le pgcd de b et d. Si d 1=d, c'est-à-dire si d divise b, on multiplie à gauche par la matrice (1 −b/d 0 1) :
(1 −b/d 0 1)(a b c d)=(a 1 0 c d)
Si d 1 est différent de d (on a donc d 1≤∣d∣/2), en utilisant bu+dv=d 1, s=−bd 1, t=dd 1 on obtient
(t s u v)(a b c d)=(a 1 0 c 1 d 1)
(on remplace donc la colonne (b d) par (0 d 1)=(0 pgcd(b,d))). Si d 1 divise c 1, on multiplie à droite par (1 0 −c 1/d 1 1) pour obtenir une matrice diagonale (* 0 0 d 1). Sinon, soit d 2 le pgcd de d 1 et c 1 :
(a 1 0 c 1 d 1)(t′ u′ s′ v′)=(* * 0 d 2)
On a peut-être perdu le zéro sur la première ligne ... Mais on a quand même gagné un peu car d 2 divise strictement d (en fait d 2≤∣d∣/2 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 : (a 0 0 b). On veut maintenant obtenir la matrice (c 0 0 d) avec d le pgcd de a et b et d∣c (le déterminant de ces matrices est inchangée au signe près, on a alors nécessairement c=±ab/d). Pour cela, soient u et v tels que au+bv=d, on a
(b/d −au/d 1 v)(a 0 0 b)(bv/d u −a/d 1)=(ab/d 0 0 d)
Ces matrices sont composées d'opérations élémentaires comme le montrent les produits suivants :
(bv/d u −a/d 1)=(1 u 0 1)(1 0 −a/d 1)
et
(b/d −au/d 1 v)=(1 b/d 0 1)(0 −1 1 0)(1 v 0 1)

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 2×2 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

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

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
Il s'agit de calculer l'ensemble des solutions entières d'un système
AX=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 UAV=S la forme normale de Smith. Résoudre en entiers AX=B est équivalent à résoudre SY=C en entiers avec C=UB, le lien étant donné par X=VY et. Le système SY=C est de la forme :
{d 1y n−t+1 = c n−t+1 ... = ... d ty n = c n
Lorsqu'une solution existe, ce qui se vérifie facilement sur C, il est maintenant facile de finir la résolution.

Exercice

Un exemple : exemple , exemple , exemple Relations entre vecteurs

Algorithme

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

Solution
On se ramène à la résolution d'un système linéaire diophantien en introduisant des inconnues supplémentaires
AX+D MY=C
où D M est la matrice diagonale de diagonale M. On calcule la matrice SNF de la matrice (A∣D M).

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 X≡BmodM. 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

IV Groupes abéliens de type fini

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

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

Algèbre linéaire sur ZZ → IV Groupes abéliens de type fini → IV-1 Définitions

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 à ℤ d pour un entier d où d est par définition son rang .

Théorème

Soit f:L 1→L 2 un homomorphisme de groupes abéliens libres de type fini. Il existe des bases de L 1 et de L 2 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 L 1 et de L 2, la nouvelle base de L 1 est donnée par la matrice V, la nouvelle base de L 2 est donnée par la matrice U −1 :

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 d 1, ..., d r tels que d r∣...∣d 1 et tels que d 1e 1,...,d re r soient une base de M. Les entiers d 1, ..., d r caractérisent M⊂L.

Exercice

Des exemples : exemple , exemple

Bases associées
Diviseurs élémentaires I
Diviseurs élémentaires II

IV-2 Module des relations

Algèbre linéaire sur ZZ → IV Groupes abéliens de type fini → IV-2 Module des relations

Soit M un groupe abélien de type fini et v 1, ..., v s des générateurs . Pour décrire M, introduisons l'application
f:ℤ s→G
qui envoie e i sur v i.
Le noyau de f est un sous- ℤ-module de ℤ s engendré par certains vecteurs r 1,...,r t. Il est appelé module des relations de M. Soit A la matrice formée par les vecteurs r 1,...,r t. C'est une matrice de M s,t(ℤ) qu'on appelle une matrice des relations de M (relativement au système générateur ( r 1,...,r t)). En effet, on a
f(r j)=∑ i=1 sa ijf(e i)=∑ i=1 sa ijv i=0,
ce qui donne une relation entre les éléments v i de M.
La matrice A définit un homomorphisme g:ℤ t→ℤ s. Son image est par définition égale au noyau de f. Alors, ℤ s/Aℤ t=ℤ s/g(ℤ t)≃M.

Théorème

Soit M un ℤ-module de type fini, il existe des entiers positifs d 1, ..., d m tels que d m∣...∣d 1 et un entier r positif ou nul tels que
M≃ℤ r⊕ℤ/d 1⊕...⊕ℤ/d m.

Analyser la structure de M revient donc à étudier le groupe ℤ s/Aℤ t 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

Algèbre linéaire sur ZZ → V Des problèmes
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

Algèbre linéaire sur ZZ → V Des problèmes → V-1 Les boeufs d'Archimède
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 1n.
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)).
Algèbre linéaire sur ZZ → V Des problèmes → V-1 Les boeufs d'Archimède

V-2 Identité de Bézout

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

Trouver des entiers e 1, ..., e 5 tels que
12e 1+43e 2+189e 3+19e 4+289e 5=220.

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
v=(−24×220,0,0,0,220)=(−5280,0,0,0,220)

De manière générale, pour résoudre le système linéaire MX=B, on écrit MU=(0∣H) sous forme d'Hermite, On doit résoudre
MU(U −1X)=B.
On résoud donc d'abord le système (0∣H)Y=B qui est simple car "triangulaire" : ici on trouve Y=(y 1,y 2,y 3,y 4,220), puis on applique U : X=UY : 
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
Algèbre linéaire sur ZZ → V Des problèmes → V-2 Identité de Bézout

V-3 Un système modulo des entiers divers

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

On cherche un polynôme P du troisième degré à coefficients entiers tel que que
{P(53) ≡20mod85 P(19) ≡37mod68 P(2) ≡496mod561 P(47) ≡61mod64
ou plus généralement
{P(53) ≡b 1mod85 P(19) ≡b 2mod68 P(2) ≡b 3mod561 P(47) ≡b 4mod64

Existe-t-il pour toutes valeurs des b i ? quelles conditions faut-il mettre sur les b i ? comment trouver toutes les solutions ? Le polynôme 7x 3−67x 2+52x+43 est-il solution ? (répondre en exploitant les calculs précédents).
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 A 1=(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 A 1 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 HX=B, puis on calcule UX. 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 7x 3−67x 2+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 : UAV=S. Résoudre UAV=B revient à résoudre successivement SY=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 b 3 et que 17 divise 52b 3+17b 4+b 1, cette dernière condition étant équivalente à ce que 17 divise b 1+b 3. 
{ 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
Algèbre linéaire sur ZZ → V Des problèmes → V-3 Un système modulo des entiers divers

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

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

Résoudre dans ℤ le système linéaire
4x 1 − 17x 2 − 22x 3 − 9x 4 = a − 30x 2 + 45x 3 − 18x 4 = b 20x 1 − 75x 2 + 95x 3 − 39x 4 = c 7x 1 − 25x 2 + 33x 3 − 14x 4 = d
selon les valeurs (entières) de a, b, c, d.
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 133b 2+265b 3+1760b 4−62b 1. Si l'on veut obtenir une condition paramétrée, c'est-à-dire une expression des b i en fonction de paramètres entiers quelconques, il ne reste plus qu'à résoudre
133b 2+265b 3+1760b 4−62b 1≡0mod29040
... 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 z 1, z 2, z 3, le système AX=B a une solution entière si et seulement si B est de la forme
(14520z 1 −809837z 1+2z 2 106496610z 1−265z 2+z 3 707298240z 1−1760z 2)
avec z 1, z 2 et z 3 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
Algèbre linéaire sur ZZ → V Des problèmes → V-4 Un système linéaire : condition de compatibilité

V-5 Le groupe multiplicatif dans les rationnels

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

On regarde tous les rationnels de la forme 3 a 1×5 a 2×12 a 3. 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

V-6 Carreleur cherche aide

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

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 v 1 et v 2 à coefficients entiers et il a mis ses repères aux points de coordonnées nv 1+mv 2 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 v 1=(3,2) et v 2=(5,10), puis dans l'espace pour v 1=(−1,−3,0), v 2=(−5,−12,0), v 3=(2,7,−2).
Solution
On note e 1=(1,0), e 2=(0,1). La base ( e 1, e 2) donne les directions horizontale et verticale du mur. Soit M le ℤ-module libre engendré par v 1 et v 2.
Trouvons d'abord quelques solutions. Prenons une base de M donnée par la normalisation de Hermite. On a donc w 1=ae 1 w 2=be 1+ce 2 avec 0≤b<a. On se persuade facilement avec un dessin que l'on peut paver le plan comme indiqué avec des briques de dimension a×c.
On aurait pu échanger le rôle de e 1 et e 2 ce qui revient à multiplier la matrice de départ à gauche par une matrice de permutation par (0 1 1 0) 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 w 1 le vecteur perpendiculaire (donc horizontal) porté par le côté horizontal de la brique de droite. C'est un multiple de e 1 qui appartient à M : w 1=ae 1. Soit maintenant w 2 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 w 2=be 1+ce 2 avec 0≤b<a. Les coefficients a, b et c sont entiers. Et il doit être clair que w 1 et w 2 est encore une base de M. En tout cas, la matrice associée à w 1, w 2 est de la forme (a b 0 c) avec 0≤b<a.
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 P pA où P p est une matrice de permutation associée à une permutation p. On a alors P pAU=H, donc AUP p=H p avec H p=P p −1HP p. La matrice H p 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
Algèbre linéaire sur ZZ → V Des problèmes → V-6 Carreleur cherche aide

V-7 Base

Algèbre linéaire sur ZZ → V Des problèmes → V-7 Base
Trouver une base du ℤ-module engendré dans ℤ 5 par les vecteurs
−2e 1−2e 2−2e 3−3e 4−e 5,
−2e 1−3e 2−e 4,
−e 1−3e 2−e 3−e 4+e 5,
−3e 1−2e 2−2e 3−3e 4−3e 5,
−3e 1+e 2+e 3−2e 5,
−3e 1−2e 3−3e 4−e 5.
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 2e 1, e 1+2e 2, e 2+e 3, e 1+e 2+e 4, e 1+e 2+e 5. 
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
−13f 1+8f 2−5f 3+5f 4−7f 5+7f 6=0
Si on veut aller plus loin, soit L le ℤ-module engendré 
gp>  matsnf(A)
%4 =[4, 1, 1, 1, 1]
Donc ℤ 5/L est un groupe abélien fini isomorphe à ℤ/4ℤ. 
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 ℤ 5 est donnée par la matrice U 1 inverse de U (il s'agit donc des vecteurs e 2, e 2+e 3, 3e 2+e 4, 3e 2+e 5, e 1+2e 2), la nouvelle base de L (exprimée dans la base des f i) est donnée par V :
AV=U −1D
(les vecteurs de AV sont bien proportionnels aux vecteurs correspondants de U 1). 
{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

Algèbre linéaire sur ZZ → V Des problèmes → V-8 Groupe abélien

Soit A=(10 10 −9 −8 −16 −6 22 20 6 −1 −4 −6 8 12 −5 −4 12 8 −13 −12). Déterminer une base du sous- ℤ-module de ℤ 5 engendré par les vecteurs colonnes de A. Si f est l'application ℤ-linéaire dont la matrice dans les bases canoniques de ℤ 4 et ℤ 5 est A, donner une base du noyau de f. Donner la structure du groupe abélien ℤ 5/f(ℤ 4).
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 ℤ 5/f(ℤ 4) est isomorphe à ℤ 2⊕ℤ/6ℤ. Un isomorphisme explicite est donné par ℤ 2⊕ℤ/6ℤ = ℤs 1⊕ℤs 2⊕ℤ/6ℤs 3 où s 1 est l'image de e 5, s 2 est l'image de 7e 1+e 2+10e 4+4e 5 et s 2 est l'image de 8e 1+11e 4+5e 5. Les deux derniers vecteurs de l'inverse U 1 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]))

Algèbre linéaire sur ZZ → V Des problèmes → V-8 Groupe abélien

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

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

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
Les relations sont données par la matrice
(8 2 0 9 −20 27 0 22 −24).
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
(240 0 0 0 2 0 0 0 1).
Le groupe G est donc isomorphe à ℤ/240ℤ×ℤ/2ℤ. 
{ A = [8, 2, 0;
   9, -20, 27;
   0, 22, -24] };
matsnf(A)
matsnf(A, 1)[3]
Algèbre linéaire sur ZZ → V Des problèmes → 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)

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

Soit H un groupe abélien engendré par trois éléments h 1, h 2, h 3 soumis aux relations
3h 1+h 2+h 3=0, 25h 1+8h 2+10h 3=0, 46h 1+20h 2+11h 3=0
Montrer que H est fini. Trouver sa structure (en fait ℤ/nℤ) et trouver explicitement un isomorphisme de H dans ℤ/nℤ et de ℤ/nℤ dans H (préciser les images de h 1, h 2, h 3 ou l'image de 1 pour la réciproque).
Solution
On définit une application f de ℤ 3 dans H par
e 1=(1,0,0)→h 1...
On définit ensuite une application A
L 1=ℤ 3→L 2=ℤ 3
par
e 1↦3e 1+e 2+e 3.
On a alors
ℤ 3/Aℤ 3=H.
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 à ℤ/19ℤ. La nouvelle base (a 1,a 2,a 3) de L 2 est donnée par les colonnes de l'inverse de U et (19a 1,a 2,a 3) est une base du noyau de f. On a donc e 1=a 1, e 2=−12a 1+a 2, e 3=−10a 1+a 3. Ainsi, l'isomorphisme de H sur ℤ/19ℤ est donné par
h 1→1.
L'image de h 2 est alors −12, celle de h 3 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)
Algèbre linéaire sur ZZ → V Des problèmes → 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-11 Groupe abélien défini par générateurs et relations (3)

Le ℤ-module M est engendré par des éléments u 1, u 2, u 3 soumis aux relations
3u 1+2u 2−2u 3=0,−4u 1−u 2+4u 3=0.
Monter que M est un ℤ-module libre. Trouver une base de M.
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 à ℤ 3/Aℤ 2=ℤ, il est libre.

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

document donnant un point de vue algorithmique sur les groupes abéliens de type fini.
: module,forme d'Hermite,forme de Smith, forme normale, algorithme de Gauss,groupe, interactive mathematics, interactive math, server side interactivity

The most recent version
Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.