Ce document dans d'autres formats: feuille de travail, source RST.
Références: - Wikipedia: Théorème des facteurs invariants
On souhaite maintenant faire de l'algèbre linéaire sur l'anneau $\ZZ$. On va donc travailler avec des $\ZZ$-modules. Peut-on procéder comme sur un corps?
Exercices
Correction
Exercice
Considérons la matrice suivante:
M = matrix([[14,19,-10], [10,14,-7]]); M
Correction
Oublions les deux dernières colonnes pour le moment:
v = M[:,0]; v
Dans ce cas, le sous-module engendré par les deux lignes est juste un idéal de $\ZZ$, nommément $14\ZZ + 10\ZZ = 2\ZZ$ :
a = 14; b = 10
gcd(a,b)
On veut donc renvoyer la forme échelon $\begin{matrix}2\\0\end{matrix}$, et en obtenir les coefficients par combinaisons linéaires de $a$ et de $b$. Calculons les coefficients de Bezout:
r, u, v = xgcd(a,b)
r, u, v
On a alors:
a*u+b*v
a*(-b/r) + b*(a/r)
Posons:
T = matrix([[u,v], [-b/r,a/r]]); T
On peut mettre $M$ sous forme échelon en la multipliant par $T$ :
T * M
La matrice $T$ étant de déterminant $1$ :
det(T)
cette opération est inversible: les lignes de la forme échelon de $M$ engendrent bien le même sous-module que les lignes de $M$.
Cette forme échelon n'est pas encore réduite; on peut la réduire avec une étape de plus, et on obtient:
sage: M.echelon_form() [ 2 1 -2] [ 0 3 1]
Remarque clef
Soit $\begin{pmatrix}a\\b\end{pmatrix}$ un vecteur de $\ZZ^2$, et $r, u,v$ les résultats du pgcd étendu de $a$ et $b$ : $r = a\wedge b = ua+bv$. Posons:
$$M := \begin{pmatrix} u & v \\ -\frac br & \frac ar \\ \end{pmatrix}$$alors: $M\begin{pmatrix}a\\b\end{pmatrix} = \begin{pmatrix}r\\0\end{pmatrix}$ et $M\in GL(\ZZ)$ ($\det(M)=1$)!
Théorème: forme de Hermite
Soit $M$ une matrice à coefficient dans $\ZZ$. Alors il existe une matrice $T$ inversible telle que $TM$ est sous forme échelon.
Comme pour un corps, il existe une forme réduite canonique, dite forme de Hermite (les pivots y sont entiers positifs, et les coefficients dans la colonne d'un pivot $r$ sont réduits modulo $r$.
Moralité
La majeure partie de ce que l'on a vu précédemment va s'appliquer mutatis-mutandis en utilisant la forme de Hermite comme forme échelon réduite. L'algèbre linéaire sur $\ZZ$ n'est pas foncièrement plus compliquée ou coûteuse que sur un corps.
Il y a juste quelques points techniques à traiter. Elles apparaîtront en fait déjà en dimension $1$.
Corollaire
Tout sous-module $F$ d'un $\ZZ$-module libre $E$ de dimension finie $n$ est libre de dimension finie $\leq n$.
Début de la démonstration
Si $F$ admet un système générateur fini, le mettre sous forme échelon. Alors $F=\ZZ v_1 \oplus \cdots \oplus \ZZ v_k$, où $v_1,\vdots,v_k$ sont les lignes de la forme échelon.
Mais sinon?
Exercice
Exemple
V = ZZ^6
I = V.zero_submodule(); I
I = I + V.submodule([V.random_element(prob=.3)]); I # random
Exercice: Une équation
Déterminer l'ensemble des solutions entières de chacune des équations suivantes:
Exercice: noyau
Correction
Soit $T$ inversible telle que $TM$ est sous forme échelon. Soit $k$ son rang. Alors les $n-k$ dernières colonnes de $T$ forment une base de $K$.
Corollaire
Le noyau d'un $\ZZ$-morphisme entre deux modules libres est libre.
L'ensemble des solutions entières d'un système d'équations à coefficients entiers est un module libre.
Exercice: Torsion
M = sage: diagonal_matrix([2,6,12,0])
On s'intéresse aux groupes (additifs) $G$ abélien engendrés par un nombre fini d'éléments.
Exercice
Correction
Y'en a t'il d'autres?$G$ est isomorphe à $\ZZ^n / F$.Exercice
Soit $M$ une matrice $n\times m$ vue comme famille génératrice d'un sous $\ZZ$-module de $\ZZ^m$. Soient $S$ et $T$ matrices inversibles de dimensions appropriées.
Montrer que le sous-module correspondant à $S M T$ est isomorphe à $F$.
Théorème
Correspondance:
Problème
On a vu que la forme échelon (ligne) donne une forme normale pour les matrices modulo l'action à gauche de $GL_n(\ZZ)$.
Équivalent pour les matrices modulo la double action de $GL_n(\ZZ)$ et $GL_m(\ZZ)$?
Exemple
A = matrix([[ 4134, 11016, 52074, 159720, -462804, 1027050,-1807692],
[-18014,-47944,-226778,-695548, 2015364,-4472474, 7872162],
[-11584,-30896,-145972,-447728, 1297368,-2879104, 5067330],
[ 7516, 20072, 94768, 290684, -842328, 1869292,-3289908],
[-19264,-51392,-242776,-744644, 2157744,-4788448, 8427786]]); A
```
```{.python .input}
_.echelon_form()
_.transpose().echelon_form().transpose()
_echelon_form()
_.transpose().echelon_form().transpose()
Note: statistiquement, la procédure termine en deux voire une étapes. Pour trouver l'exemple ci-dessus, on a essayé plein d'exemples aléatoires avec les fonctions du fichier suivant.
Forme normale de Smith
Soit $M$ une matrice $n\times m$ à coefficients dans $\ZZ$.
Alors $M$ est équivalente à une matrice diagonale dont les coefficients non nuls $d_1,\dots,d_k$ se divisent successivement.
Démonstration
Corollaire: classification des groupes abéliens
Tout groupe abélien est isomorphe de façon canonique à un produit direct
$$\ZZ/d_1\ZZ \times \cdots \times \ZZ/d_k\ZZ \times \ZZ \times\cdots\times\ZZ$$où les $d_1,\dots,d_k$ se divisent successivement.
Pour les détails et aller plus loin, voir https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_facteurs_invariants
Tout ce que l'on vient de dire se généralise immédiatement pour un anneau principal quelconque comme $A=\QQ[x]$; à condition bien entendu que $A$ soit constructif, et en particulier, qu'il y ait un algorithme pour calculer le PGCD étendu.
Soit $A$ un anneau. Par exemple un anneau de polynômes multivariés $A=\QQ[x,y]$. Qu'est-ce qui subsiste de tout ce que l'on a vu?
Un $A$-sous-module de $A^1$ est juste un idéal de $A$.
Exemple: $\langle x^2y, xy^2\rangle$
Calcul avec les idéaux et sous-modules: bases de Gröbner
Combinatoire sous-jacente: idéaux monomiaux!
Explorons un exemple:
pretty_print_default()
A = QQ['a']
a = A.gen()
M = matrix(A, random_matrix(ZZ, 3, 8)); M[0,0] = a; M
N = copy(M)
M[1] = M[0,0] * M[1] - M[1,0] * M[0]
M[2] = M[0,0] * M[2] - M[2,0] * M[0]
M
M[2] = M[1,1] * M[2] - M[2,1] * M[1]
M
Revenons sur notre exemple:
M
On constate que $a$ divise la troisième ligne; on peut donc diviser de manière exacte par $a$ :
M[2] = M[2] / a
M
De plus, le coefficient M[3,3] est le déterminant de la matrice d'origine:
N[:,:3]
N[:,:3].det()
Ce phénomène est général et peut être utilisé récursivement:
Algorithme de Gauß-Bareiss
On procède comme pour Gauß sans fractions, y compris pour traiter les lignes avec un coefficient nul dans la colonne du pivot. Cependant, avant de traiter les colonnes $\geq i+2$ on divise tout le quadrant inférieur composé des lignes et colonnes $\geq i+2$, par $M[i,i]$.
Le fonctionnement de l'algorithme repose sur la propriété suivante:
Proposition
Soit $M$ une matrice sur un anneau intègre. Après avoir traité les $i$ premières colonnes, $M_{i,i}$ est le déterminant du $i$-ème mineur dominant de la matrice d'origine (correspondant aux $i$ premières lignes et colonnes). De plus après avoir traité la colonne $i+1$, ce déterminant divise toutes les coefficients $M_{i',j'}$ avec $i',j'\geq i+2$.
Exercice
Vérifier la proposition dans le cas d'une matrice triangulaire supérieure.
Remarque
Pour simplifier, on a supposé ci-dessus que la matrice était carrée et que tous les mineurs dominants étaient non nuls. Modulo les détails techniques usuels (forme échelon réduite plutôt que uni triangulaire supérieure), l'algorithme se généralise à des matrices quelconques sur un anneau intègre.
Le coeur de l'algèbre linéaire est l'étude des matrices modulo des relations d'équivalences (équivalence, conjugaison, similitude), et ce sur les différents types d'anneaux.
Dans chaque cas, on introduit une notion d'ordre (plus conceptuellement de drapeau) qui permet de définir simultanément une forme normale et un algorithme d'élimination permettant de calculer cette forme normale.
Voir par exemple [Storjohan.2004]_ pour une présentation d'ensemble.
Modulo quelques difficultés supplémentaires (gestion de la torsion, etc.), La plupart des algorithmes de l'algèbre linéaire sur les corps peuvent être adaptés aux anneaux principaux sans changement majeur de complexité, la forme normale de Hermite remplaçant la forme échelon.
Sur les anneaux plus généraux, il reste possible de faire certains calcul (déterminant, ...) avec des analogues du pivot de Gauß, mais la plupart des opérations (résolution d'équation, ...) nécessitent de nouveaux outils comme les bases de Gröbner.
Exercice: algorithme de Gauß-Bareiss
Dans tout cet exercice, on pourra supposer que la matrice d'entrée est inversible, voire que ses $n$ premiers mineurs sont non nuls (pas de permutation des lignes nécessaire).
M = matrix([[2, 1, 3], [1, 4, 9], [1, 8, 27]]); M
Évaluer la complexité pratique en prenant des matrices aléatoire de taille $n=1,2,...$. Comparer avec ce que l'on obtient avec Gauß, et avec Gauß sur un corps fini.
Qu'en pensez-vous?exercice: forme de Hermite et de Smith