Matrice unimodulaire
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En algèbre linéaire, une matrice unimodulaire sur l'anneau des entiers relatifs est une matrice carrée à coefficients entiers dont le déterminant vaut +1 ou –1. Plus généralement[1], une matrice unimodulaire sur un anneau commutatif A est une matrice inversible à coefficients dans A, dont l'inverse est aussi à coefficients dans A. Le groupe général linéaire GLn(A) des matrices unimodulaires de taille n sur l'anneau A est donc constitué des matrices dont le déterminant est inversible dans A.
Propriétés des matrices unimodulaires[modifier | modifier le code]
Les matrices unimodulaires d'ordre n forment un groupe pour le produit, c'est-à-dire que les matrices suivantes sont unimodulaires :
- la matrice unité ;
- l'inverse d'une matrice unimodulaire ;
- le produit de deux matrices unimodulaires.
De plus, le produit de Kronecker de deux matrices unimodulaires est unimodulaire.
Matrice totalement unimodulaire[modifier | modifier le code]
Une matrice totalement unimodulaire (TUM)[2] est une matrice (non nécessairement carrée) à coefficients entiers dont chaque sous-matrice carrée de déterminant non nul est unimodulaire. On déduit de cette définition que les éléments d'une TUM peuvent uniquement être –1, 0 ou +1.
Exemple de matrice totalement unimodulaire[modifier | modifier le code]
La matrice suivante est totalement unimodulaire :
Condition suffisante pour être totalement unimodulaire[modifier | modifier le code]
Une condition suffisante mais pas nécessaire pour qu'une matrice A soit totalement unimodulaire :
Soit A une matrice rectangulaire dont les lignes sont partitionnées en 2 ensembles disjoints B et C avec les propriétés suivantes :
- chaque colonne de A contient au plus 2 éléments non nuls ;
- chaque élément de A vaut –1, 0 ou +1 ;
- si 2 éléments d'une colonne de A ont le même signe, alors la ligne de l'un est dans B, l'autre dans C ;
- si 2 éléments d'une colonne de A ont des signes opposés, alors les lignes des 2 éléments sont dans B ou toutes les 2 dans C ;
alors les déterminants des sous-matrices de A sont –1, 0 ou +1.
Matrices unimodulaires classiques[modifier | modifier le code]
Les matrices issues des modélisations par programme linéaire du problème de flot maximum et du problème du flot de coût minimum, sont unimodulaires.
Notes et références[modifier | modifier le code]
- F. Chaplais, Cours d'algèbre matricielle.
- Le terme a été proposé par Claude Berge, cf. (en) A. J. Hoffman et J. Kruskal, « Introduction to Integral Boundary Points of Convex Polyhedra », dans M. Jünger et al. (eds.), 50 Years of Integer Programming, 1958-2008, Springer-Verlag, , p. 49-50.
