*Groupe de travail transport (Guido - Quentin 04/11/2021) suite de l'exposé de Quentin
[1] V N. Sachov "Combinatorial methods in discrete mathematics" Enciclopedia Mathematics Cambridge V.
Soit $X$ un ensemble et soit $X_1$,$X_2$,......$X_n$ une famille finie de parties de non vides de $X$.
Notons que l' égalité $X_i =X_J$ pour $i\neq j$ est possible. Notons cette famille $(X_i : i\in I)$ où $I=\{1,2,...,n\}$. Une transversal , ou système de representants de la famille est un ensemble de éléments $\{x_i: i\in I\}$ tels que $x_i\in X_i$ pour chaque $i\in I$ et $x_i\neq x_j$ si $i\neq j$.
Une famille $(X_i : i\in I)$ où $I=\{1,2,...,n\}$ de parties d'un ensemble $X$ admet une transversal si et seulement si $$: | X_{i_1}\cup X_{i_2}\cup ,.....\cup X_{i_k}|\geqslant k$$ quelque soit $1\leq k \leq n$ et $1\leq i_1 < .......< i_k\leq n$.
La condition famille finie est essentiel : par exemple $\mathbb N =X$ et la famille $\{1,2,3,......\}$, $\{1\}$, $\{2\}$, $\{3\}$,...., vérifie la condition de Hall mais n'admet pas de transversal.
On dira qu'une sous-famille stricte $X_{i_{1}},......X_{i_{k}}$ de la famille $(X_i:i\in I)$ avec $1\leq k <n$, est critique si $$| X_{i_1}\cup X_{i_2}\cup ,.....\cup X_{i_k}|= k.$$
Pour démontrer que la condition est suffisante on fait un raisonnement par induction sur $n$
Pour $n=1$ le résultat est vraie. Supposons que le résultat est vraie pour toute famille d' au plus $n-1$ sous-ensembles X . Soit $(X_i : i\in I)$ où $I=\{1,2,...,n\}$ une famille de parties d'un ensemble $X$ verifiant la condition de Hall.
Deux cas:
Dans la démonstration on ne considère pas comme sous-famille critique le cas où intervienent tous les éléments de la famille c'est à dire le cas où pour $k=n$ on a $$| X_{1}\cup X_{2}\cup ,.....\cup X_{n}|= n.$$ Si l'on veut analiser ce cas particulier on examine les deux cas possibles de la démonstration.
Nous noterons $\mathbb B_n$ l’ensemble des matrices bistochastiques de taille $n\times n$. C'est une partie convexe de l'espace vectoriel réeel de matrices carrées réels de taille $n\times n$.
Soit $A=(a_{ij})$ non négative de taille $n\times n$ telle que $$\sum _{j=1}^{n} a_{ij}=t, i=1...n $$ $$\sum _{i=1}^{n} a_{ij}=t, j=1...n $$ où t est une constante non négative. Alors il existe un entier $s$ et des réels non négatifs $\alpha_1$,$\alpha_2$, ...., $\alpha_s$ tels que $$\alpha_1+\alpha_2+......+\alpha_s=t$$ et $$A=\alpha_1 \mathbb P _1+...........+\alpha_s \mathbb P _s$$ où $\mathbb P _1$, ....., $\mathbb P _S$ sont matrices de permutation de taille $n\times n$.
On va faire une recurrence sur le nombre $\omega$ de éléments non nuls de la matrice $A$.
Si la matrice $A$ est la matrice nulle alors $t=0$ et on peut representer la matrice $A$ comme une somme à coefficient nuls de matrices de permutation.
Si la matrice $A$ a des coefficients posifs alors $t>0$ et il est clair que $n\leq \omega$.
Lorsque $n= \omega$ nécesairement $A=t\mathbb P$ est un multiple d'une matrice de permutation. En effet chacune des $n$ lignes (et chaque colonne) doit avoir au moins un coefficient non nul.
Supposons maintenant que le resultat est vraie pour toutes le matrices $A$ vérifiant les conditions du théorème et ayant au plus $\omega-1$ coefficients positifs.
Considérons la famille d'ensembles $\{Q_i:1\leq i \leq n\}$ où $Q_i=\{j:a_{ij}>0\}$ pour $i=1, ....n.$
Cette famille satisfait la condition de P. Hall: en effet si pour un $1\leq k \leq n$, $1\leq \beta _1 <........<\beta _k\leq n$ on a $$|Q_{\beta_1} \cup .......\cup Q_{\beta_k}|<k$$ alors les coefficients positifs de $A$ dans les lignes d'indice $\beta_1$, ...., $\beta_k$ sont places en au plus dans $k-1$ colonnes. Si l'on fait la somme des ces coefficients le long de m lignes on obtient $k\times t$ ,
mais si l'ont fait la même somme le long de colonnes on peut obtenir au plus $(k-1)\times t$. C'est une contradiction.
D'après le théorème de Hall, il existe une tranversal $\{r_i:1\leq i \leq n \}$ de la famille $\{Q_i:1\leq i \leq n\}$. On obtient alors une matrice de permutation $\mathbb P _1 =(p_{ij})$ en définissant $p(ij)=1$ si $j=r_i$ et zéro ailleurs.
Par définition de $Q_1$,...., $Q_n$ on a $a_{ir_i}>0$ pour $i=1,..., n$ soit $$\mu_1=min\{a_{ir_i}:1\leq i \leq n\}>0 $$
La matrice $A_1=(a_{i,j}^1)=A-\mu_1 \mathbb P _1$ satisfait au conditions du théorème, elle est non négative et $$\sum _{j=1}^{n} a_{ij}^1=t-\mu _1, i=1...n $$
$$\sum _{i=1}^{n} a_{ij}^1=t-\mu _1, j=1...n $$
et a au plus $\omega -1$ coefficients non nuls.
Par la hypothèse de recurrence $$A_1=\alpha_2 \mathbb P _2+...........+\alpha_s \mathbb P _s$$ où $\mathbb P _2$, ....., $\mathbb P _s$ sont matrices de permutation de taille $n\times n$ avec $\alpha _2 +... +\alpha_s=t-\mu _1$ . Donc $$A=\ \mu_1\mathbb P _1+\alpha_2 \mathbb P _2+...........+\alpha_s \mathbb P _s.$$ Le theoréme est démontré.
$\mathbb B _n$, est l'enveloppe convexe des $n!$ matrices permutations. En plus les points extrêmaux de $\mathbb B _n$ sont les matrices de permutation.
Une analyse plus pousée de la dimension de l'espace des solutions définissant $\mathbb B_n$ montre que les matrices bi stochastiques sont contenues dans un espace affine de dimension $(n-1)^2$ et que alors dans la décomposition de $A$ le nombre $s$ de matrices de permutation necesaires est inférieur où égale à $(n-1)^2 +1$.
Soit $A=\begin{bmatrix}
0 & 0 & 2 & 0 & 1\\
0 & 0 & 0 & 2 & 1\\
2 & 0 & 1 & 0 & 0\\
0 & 2 & 0 & 1 & 0\\
1 & 1 & 0 & 0 & 1
\end{bmatrix}$
Ici on a $t=3$ et $Q_1= \{3,5\}$, $Q_2= \{4,5\}$, $ Q_3= \{1,3\}$, $ Q_4=\{2,4\}$ et $Q_5= \{1,2,5\}.$
Une transversal de la famille est $(3,4,1,2,5)$ et la matrice de permutation est $P_1=\begin{bmatrix}
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0\\
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1
\end{bmatrix}$ et
$ \mu_1=min\{a_{13},a_{24},a_{31},a_{42},a_{55}\}=a_{55}=1$
$A_1=A-1\times P_1=\begin{bmatrix}
0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 1 & 0\\
1 & 1 & 0 & 0 & 0
\end{bmatrix}$ Ici on a $t=2$ et $Q_1= \{3,5\}$, $Q_2= \{4,5\}$, $ Q_3= \{1,3\}$, $ Q_4=\{2,4\}$ et $Q_5= \{1,2\}.$
Une transversal de la famille est $(5,4,3,2,1)$ et la matrice de permutation est $P_2=\begin{bmatrix}
0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0
\end{bmatrix}$ et
$A_2=A_1-1\times P_2=\begin{bmatrix}
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0\\
0 & 1 & 0 & 0 & 0
\end{bmatrix}=P_3$
Finallement $$A=P_1+P_2+P_3$$
Soient $m$ et $n$ deux nombres entiers naturels, considerons deux vecteurs non négatifs $p=(p_1,.......,p_n)$ et $q=(q_1,q_2,.....,q_m)$ On note $\mathbb U(p,q)$ l'ensemble des matrices $A=(a_{ij})$ non négatives de taille $n\times m$ verifiant : $$\sum _{j=1}^{n} a_{ij}=p_i, i=1...n $$
$$\sum _{i=1}^{n} a_{ij}=q_j, j=1...m $$.
$\mathbb U(p,q)$ est un compact convexe de $\mathcal M (n,m)$ appelée le polytope de transport associée à $p$ et$q$.
Si l'on considère la mesure $\pi_A$ sur $F=I_n\times I_m$ donnée par $p_i{(i,j)}=a_{ij}$ alors la masse totale F est égale à $\sum_{i=1}^{n} p_i$ et aussi à $\sum_{j=1}^{m} q_j$. Par conséquent une condition nécesaire pour que $p$ et $q$ soient des mesures marginales associées à la mesure $\pi_A$ est que $$\sum_{j=1}^{m} q_j=\sum_{i=1}^{n} p_i .$$ Par ailleurs si cette condition est vérifiée $\mathbb U(p,q)$ est non vide.
Comment décrire les points extremales du convexe $\mathbb U(p,q)$
Exercice (de Nicolas le jeune)
Soit $p=(3,3)$ et $q=(2,2,2)$ Démontrer que il y a 6 matrices extrêmales dans $\mathbb U(p,q)$ et sa dimension est $2$