Théorème de Frobenius-König et matrices bistochastiques

Soit $n \in \mathbb{N}^*$ et $A = (a_{i,j}) \in \mathcal{M}_{n}(\mathbb{R})$ .

Pour toute permutation $\sigma \in \mathfrak{S}_{n}$ , on définit le serpent de $A$ associé à $\sigma$ comme l'ensemble des coefficients :

S_{\sigma} = \left\{ a_{1, \sigma(1)}, a_{2, \sigma(2)}, \dots, a_{n, \sigma(n)} \right\}

Montrer l'équivalence entre les deux assertions suivantes :
1. Chaque serpent de la matrice $A$ contient au moins un élément nul.
2. Il existe un bloc de zéros dans $A$ de taille $r \times s$ (obtenu par intersection de $r$ lignes et $s$ colonnes) tel que $r + s = n + 1$ .
On suppose dans cette question que la matrice $A$ $A$ est bistochastique, c'est-à-dire que :
- $\forall (i,j) \in \llbracket 1, n \rrbracket^2, \ a_{i,j} \ge 0$ .
- $\forall i \in \llbracket 1, n \rrbracket, \ \sum_{j=1}^n a_{i,j} = 1$ .
- $\forall j \in \llbracket 1, n \rrbracket, \ \sum_{i=1}^n a_{i,j} = 1$ .
Démontrer qu'il existe nécessairement un serpent de $A$ $A$ ne contenant aucun coefficient nul.

1.

Pour $(ii) \implies (i)$ , raisonner par l'absurde ou par un argument de dénombrement sur les colonnes disponibles pour les $r$ lignes du bloc nul.

2.

Pour $(i) \implies (ii)$ , utiliser le théorème de König sur les couvertures de matrices : le nombre maximal d'éléments non nuls "indépendants" (n'appartenant pas à une même ligne ou colonne) est égal au nombre minimal de lignes et colonnes nécessaires pour couvrir tous les éléments non nuls.

3.

Pour la question 2, supposer que tous les serpents contiennent un zéro et utiliser le résultat de la question 1. Sommer les coefficients sur les lignes du bloc nul et comparer avec la somme sur les colonnes correspondantes.

Idées clés

•

Dénombrement et principe des tiroirs pour la condition suffisante.

•

Théorème de König pour la condition nécessaire (lien entre couplage et couverture).

•

Propriété de conservation de la somme pour les matrices bistochastiques.

Résolution.

Étude de l'équivalence.
$(ii) \implies (i)$ : Supposons qu'il existe un bloc de zéros de taille $r \times s$ avec $r+s = n+1$ . Quitte à permuter les lignes et les colonnes (ce qui ne change pas la nature des serpents, seulement leur indexation), on peut supposer que :
$\forall i \in \llbracket 1, r \rrbracket, \ \forall j \in \llbracket 1, s \rrbracket, \ a_{i,j} = 0$
Soit $\sigma \in \mathfrak{S}_n$ une permutation quelconque. Pour que le serpent $S_\sigma$ ne contienne aucun zéro, il faudrait que pour chaque ligne $i \in \llbracket 1, r \rrbracket$ , l'indice de colonne choisi $\sigma(i)$ soit strictement supérieur à $s$ . Or, l'ensemble des valeurs possibles pour ces colonnes est $\llbracket s+1, n \rrbracket$ . Le nombre de valeurs disponibles est donc :
$(n - (s+1) + 1) = n - s$
D'après l'hypothèse $r+s = n+1$ , nous avons :
$\boxed{r = n - s + 1}$
On doit donc placer $r$ valeurs distinctes $(\sigma(1), \dots, \sigma(r))$ dans un ensemble de taille $r-1$ . D'après le principe des tiroirs, cela est impossible. Par conséquent, il existe au moins un $i \in \llbracket 1, r \rrbracket$ tel que $\sigma(i) \in \llbracket 1, s \rrbracket$ , d'où $a_{i, \sigma(i)} = 0$ .
$\boxed{\text{Tous les serpents contiennent au moins un zéro.}}$
$(i) \implies (ii)$ : Cette implication repose sur le théorème de König. Appelons "système d'éléments indépendants" un ensemble d'indices $(i, \sigma(i))$ où les coefficients sont non nuls. L'assertion $(i)$ signifie que le nombre maximal $m$ d'éléments non nuls indépendants est strictement inférieur à $n$ . Soit $m \le n-1$ ce maximum. D'après le théorème de König, il existe une couverture de tous les éléments non nuls par $k$ lignes et $l$ colonnes telle que $k+l = m$ . Considérons les $n-k$ lignes et les $n-l$ colonnes qui n'ont pas été sélectionnées pour cette couverture. Par définition de la couverture, l'intersection de ces lignes et de ces colonnes ne contient que des zéros. On a ainsi un bloc nul de taille $r \times s$ avec $r = n-k$ et $s = n-l$ . Calculons la somme :
$r + s = (n-k) + (n-l) = 2n - (k+l) = 2n - m$
Comme $m \le n-1$ , on en déduit :
$\boxed{r + s \ge 2n - (n-1) = n+1}$
Si $r+s > n+1$ , il suffit de réduire $r$ ou $s$ pour obtenir exactement $n+1$ .
Cas des matrices bistochastiques.
Supposons par l'absurde que tous les serpents de $A$ contiennent au moins un zéro. D'après la question 1, il existe un bloc de zéros de taille $r \times s$ avec $r+s = n+1$ . Notons $I \subset \llbracket 1, n \rrbracket$ l'ensemble des $r$ indices de lignes et $J \subset \llbracket 1, n \rrbracket$ l'ensemble des $s$ indices de colonnes formant ce bloc nul. On a donc :
$\forall i \in I, \ \forall j \in J, \ a_{i,j} = 0$
Calculons la somme de tous les coefficients des lignes de $I$ :
$\sum_{i \in I} \sum_{j=1}^n a_{i,j} = \sum_{i \in I} 1 = r$
Comme les coefficients pour $j \in J$ sont nuls, cette somme se réduit à :
$\sum_{i \in I} \sum_{j \notin J} a_{i,j} = r$
Or, comme tous les coefficients de la matrice sont positifs, la somme sur les lignes $I$ et les colonnes hors de $J$ est inférieure ou égale à la somme de tous les coefficients présents dans les colonnes $J^c = \llbracket 1, n \rrbracket \setminus J$ :
$\sum_{i \in I} \sum_{j \notin J} a_{i,j} \le \sum_{j \notin J} \left( \sum_{i=1}^n a_{i,j} \right)$
La matrice étant bistochastique, la somme de chaque colonne vaut 1 :
$\sum_{j \notin J} 1 = \text{card}(J^c) = n - s$
On obtient donc l'inégalité :
$\boxed{r \le n - s}$
Ce qui est équivalent à $r + s \le n$ . Ceci contredit l'hypothèse $r+s = n+1$ issue de la question 1. L'hypothèse de départ est donc fausse :
$\boxed{\text{Il existe un serpent ne contenant aucun zéro.}}$

Dans la question 1, il ne faut pas oublier de préciser que la permutation des lignes et colonnes ne change pas l'existence d'un serpent sans zéro, car un serpent correspond simplement à un choix de $n$ cases "indépendantes".