Matrices totalement unimodulaires
Une matrice carrée ou rectangulaire \( M \) est dite totalement unimodulaire si toute sous-matrice carrée non singulière (c’est-à-dire de déterminant non nul) est une matrice unimodulaire.
Une sous-matrice carrée est unimodulaire lorsque son déterminant est exactement égal à $+1$ ou à $-1$.
Cette définition inclut également les éléments non nuls de \( M \), que l’on peut considérer comme des sous-matrices \( 1 \times 1 \) dont le déterminant correspond simplement à la valeur de l’entrée.
Remarque : Les éléments nuls ne sont pas pris en compte, car les sous-matrices \( 1 \times 1 \) correspondantes sont singulières : $$ \det(0) = 0 $$
Exemple pratique
Considérons la matrice rectangulaire suivante :
$$ \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \end{pmatrix} $$
Cette matrice est totalement unimodulaire, car toutes ses sous-matrices carrées non singulières ont un déterminant égal à ±1 :
$$ \det \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix} = 1 $$
$$ \det \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} = -1 $$
$$ \det \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = 1 $$
Les éléments non nuls de la matrice sont eux aussi considérés comme des sous-matrices \( 1 \times 1 \) :
$$ \det(1) = 1 \qquad \det(-1) = -1 $$
Remarque : Les éléments nuls ne sont pas pris en compte, car leur déterminant est nul et ne satisfait donc pas la condition de non-singularité.
Propriétés fondamentales
Les matrices totalement unimodulaires possèdent plusieurs caractéristiques remarquables :
- Condition nécessaire (mais non suffisante) : toutes les entrées non nulles doivent être égales à $1$ ou à $-1$.
Remarque : Si une matrice contient un élément différent de ±1, la sous-matrice \( 1 \times 1 \) correspondante a un déterminant qui ne satisfait pas la condition. Cependant, la réciproque n’est pas vraie : une matrice formée uniquement de $0$, $1$ et $-1$ n’est pas forcément totalement unimodulaire. Par exemple : $$ \begin{pmatrix} 1 & -1 & 0 \\ 1 & 1 & 0 \end{pmatrix} $$ n’est pas totalement unimodulaire, car elle contient une sous-matrice carrée dont le déterminant vaut $$ \det \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} = 2 $$
- Différence avec les matrices unimodulaires : une matrice unimodulaire n’est pas toujours totalement unimodulaire.
Exemple : La matrice $$ \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} $$ est unimodulaire car $$ \det \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} = 3 - 2 = 1 $$ Mais elle n’est pas totalement unimodulaire, car certaines de ses sous-matrices \( 1 \times 1 \) ne vérifient pas la condition : $$ \det(3) = 3 \qquad \det(2) = 2 $$
- Stabilité par ajout de lignes ou de colonnes unitaires : si une matrice \( M_{m,n} \) est totalement unimodulaire, alors l’ajout de colonnes ou de lignes correspondant à la matrice identité \( I \) (ou à son opposé) conserve la propriété de total unimodularité.
Exemple : Soit $$ M_{2,3} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \end{pmatrix} $$ une matrice totalement unimodulaire. En lui ajoutant horizontalement \( I_2 \) ou \( -I_2 \) : $$ [ M_{2,3} \ I_2 ] = \begin{pmatrix} 1 & -1 & 0 & \color{red}1 & \color{red}0 \\ 1 & 0 & 1 & \color{red}0 & \color{red}1 \end{pmatrix} $$ $$ [ M_{2,3} \ -I_2 ] = \begin{pmatrix} 1 & -1 & 0 & \color{red}-1 & \color{red}0 \\ 1 & 0 & 1 & \color{red}0 & \color{red}-1 \end{pmatrix} $$ De même, en ajoutant verticalement \( I_3 \) ou \( -I_3 \) : $$ \begin{bmatrix} M_{2,3} \\ I_3 \end{bmatrix} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \\ \color{red}1 & \color{red}0 & \color{red}0 \\ \color{red}0 & \color{red}1 & \color{red}0 \\ \color{red}0 & \color{red}0 & \color{red}1 \end{pmatrix} $$ $$ \begin{bmatrix} M_{2,3} \\ -I_3 \end{bmatrix} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \\ \color{red}-1 & \color{red}0 & \color{red}0 \\ \color{red}0 & \color{red}-1 & \color{red}0 \\ \color{red}0 & \color{red}0 & \color{red}-1 \end{pmatrix} $$
Ces propriétés confèrent aux matrices totalement unimodulaires une importance majeure en algèbre linéaire et en optimisation, en particulier dans la programmation entière, la théorie des réseaux et l’étude des matroïdes.
