Algèbre T1
– Étape 1 : Après permutation éventuelle de deux lignes, on se ramène au cas
où δ i 0 ,j 0 (A) = δ(A i 0 ,j 0 ).
– Étape 2 : On fait L i ← L i − q i L i 0 pour tout i > i 0 , où q i désigne le quotient
de la division euclidienne de A i,j 0 par A i 0 ,j 0 . Si tous les A i,j 0 sont nuls pour
i > i 0 , alors on ajuste le signe de p i 0 = A i 0 ,j 0 (par L i 0 ← (−1)L i 0 au besoin)
et l’on passe à l’étape 3, sinon on recommence l’étape 1 (noter que δ i 0 ,j 0 (A)
a diminué, ce qui assure que l’algorithme ne boucle pas).
– Étape 3 : On s’occupe des + au-dessus du pivot par des opérations
L i ← L i − q i L i 0 puis l’on remplace i 0 par i 0 + 1 (tant que i 0 < n), on
actualise le plus petit entier j 0 tel que δ i 0 ,j 0 (A) = 0 (si un tel entier n’existe
pas, c’est terminé) et on recommence l’étape 1.
Concernant les écritures A = P −1 A , où A est sous FNH et P ∈ GL m (Z), il y
a unicité de la matrice A , mais pas de la matrice P (avec les notations de la
définition de la FNH, démontrer que si
⎛
⎝
p 1 +
+
p 2
+
. . .
pr
⎞
⎠ = P r
⎛
⎜
⎝
p
1 +
+
p
2
+
. . .
p
r
⎞
⎟
⎠, où
P r ∈ GL r (Z), alors P r = Id r et les deux matrices sont égales).
☞ Quelques commandes Maple utiles :
iquo ; les opérations élémentaires sur les lignes sont disponibles via les commandes Swaprow, AddRow et MultiplyRow du module LinearAlgebra de la librairie Student (faire with(Student[LinearAlgebra])) ; HermiteForm de la librairie
LinearAlgebra est l’implémentation de l’algorithme de Hermite.
5. Dérouler l’algorithme sur la matrice A =
10 −5 10
−16 8 −6
−2 1 −1
8 −4 12
en effectuant une
succession de commandes Swaprow,AddRow et MultiplyRow. Enfin, tester la
commande HermiteForm.
6. On demande de déterminer une base du sous-groupe H de Z 5 engendré par
les vecteurs colonnes de la matrice C =
10 10 −9 −8
−16 −6 22 20
6 −1 −4 −6
8 12 −5 −4
12 8 −13 −12
. Soit I l’ensemble
des indices des colonnes de C = HermiteForm(A) contenant un pivot ; démontrer que (C i ) i∈I est un système libre maximal. Est-ce une base de H ?
Déterminer enfin une base échelonnée (canonique) de H en utilisant l’algorithme de Hermite appliqué à t C.
7. Soit φ : Z 4 → Z 5 le morphisme de groupes abéliens (c’est donc une application Z-linéaire) dont la matrice dans les bases canoniques est C ; donner
également une base de Ker φ.
164
– Étape 1 : Après permutation éventuelle de deux lignes, on se ramène au cas
où δ i 0 ,j 0 (A) = δ(A i 0 ,j 0 ).
– Étape 2 : On fait L i ← L i − q i L i 0 pour tout i > i 0 , où q i désigne le quotient
de la division euclidienne de A i,j 0 par A i 0 ,j 0 . Si tous les A i,j 0 sont nuls pour
i > i 0 , alors on ajuste le signe de p i 0 = A i 0 ,j 0 (par L i 0 ← (−1)L i 0 au besoin)
et l’on passe à l’étape 3, sinon on recommence l’étape 1 (noter que δ i 0 ,j 0 (A)
a diminué, ce qui assure que l’algorithme ne boucle pas).
– Étape 3 : On s’occupe des + au-dessus du pivot par des opérations
L i ← L i − q i L i 0 puis l’on remplace i 0 par i 0 + 1 (tant que i 0 < n), on
actualise le plus petit entier j 0 tel que δ i 0 ,j 0 (A) = 0 (si un tel entier n’existe
pas, c’est terminé) et on recommence l’étape 1.
Concernant les écritures A = P −1 A , où A est sous FNH et P ∈ GL m (Z), il y
a unicité de la matrice A , mais pas de la matrice P (avec les notations de la
définition de la FNH, démontrer que si
⎛
⎝
p 1 +
+
p 2
+
. . .
pr
⎞
⎠ = P r
⎛
⎜
⎝
p
1 +
+
p
2
+
. . .
p
r
⎞
⎟
⎠, où
P r ∈ GL r (Z), alors P r = Id r et les deux matrices sont égales).
☞ Quelques commandes Maple utiles :
iquo ; les opérations élémentaires sur les lignes sont disponibles via les commandes Swaprow, AddRow et MultiplyRow du module LinearAlgebra de la librairie Student (faire with(Student[LinearAlgebra])) ; HermiteForm de la librairie
LinearAlgebra est l’implémentation de l’algorithme de Hermite.
5. Dérouler l’algorithme sur la matrice A =
10 −5 10
−16 8 −6
−2 1 −1
8 −4 12
en effectuant une
succession de commandes Swaprow,AddRow et MultiplyRow. Enfin, tester la
commande HermiteForm.
6. On demande de déterminer une base du sous-groupe H de Z 5 engendré par
les vecteurs colonnes de la matrice C =
10 10 −9 −8
−16 −6 22 20
6 −1 −4 −6
8 12 −5 −4
12 8 −13 −12
. Soit I l’ensemble
des indices des colonnes de C = HermiteForm(A) contenant un pivot ; démontrer que (C i ) i∈I est un système libre maximal. Est-ce une base de H ?
Déterminer enfin une base échelonnée (canonique) de H en utilisant l’algorithme de Hermite appliqué à t C.
7. Soit φ : Z 4 → Z 5 le morphisme de groupes abéliens (c’est donc une application Z-linéaire) dont la matrice dans les bases canoniques est C ; donner
également une base de Ker φ.
164