Matrice unimodulaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Exemple de 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 :

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 :

\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[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.

Notes et références[modifier | modifier le code]

  1. Cours d'algèbre matricielle
  2. Le terme a été proposé par Claude Berge, cf (en) A. J. Hoffman (en) 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[modifier | modifier le code]