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 GL_n(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 :

${\displaystyle \mathbf {A} ={\begin{pmatrix}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\\\end{pmatrix}}}$

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

1. F. Chaplais, Cours d'algèbre matricielle.
2. 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, 2010, p. 49-50.

Articles connexes

• Théorème de König
• Optimisation combinatoire