Matrice unimodulaire
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
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
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
La matrice suivante est totalement unimodulaire :
Condition suffisante pour être totalement unimodulaire
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
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
- 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.
