Matrices bistochastiques, épisode 3

Publié le 20/01/17

On reprend les définitions et les notations de l’épisode 1.
On prouve ici la réciproque du résultat final de l’épisode 2: on va donc montrer que tout élément extrémal de {\mathcal{B}_{n}(\mathbb{R})} est une matrice de permutation P_{\sigma}.
Pour cela, soit {C=(c_{i,j})} bistochastique sans être une matrice de permutation.
On doit montrer qu’il existe {A,B} bistochastiques distinctes telles que {C\in\,]A\,;B[}.

  1. Montrer qu’il existe deux suites (i_{k})_{k\ge0} et (j_{k})_{k\ge0} de {[[0,n\!-\!1]]} telles que :{\forall\, k\in\mathbb{N},\begin{cases}i_{k}\ne j_{k+1}\\j_{k}\ne j_{k+1}\end{cases}\text{ et }\begin{cases}0\lt c_{i_{k},j_{k}}\lt 1\\0\lt c_{i_{k},j_{k+1}}\lt 1\\0\lt c_{i_{k+1},j_{k+1}}\lt 1\end{cases}}Indication: choisir {(i_{0},j_{0})}, puis {j_{1}} puis {i_{1}} et repartir de {(i_{1},j_{1})}.
  2. La suite {(j_{k})_{k\ge0}} n’étant pas injective, certaines valeurs de {j_{k}} se répètent.
    Quitte à renuméroter, on peut dire qu’il existe {m\ge1} tel que {j_{m+1}=j_{0}}.
    On définit alors la matrice {D=(d_{i,j})} par : {\forall\, k\in[[ 0,m]],\;\begin{cases}d_{i_{k},j_{k}}=1\\d_{i_{k},j_{k+1}}=-1\end{cases}\quad\text{et}\quad d_{i,j}=0\text{ sinon}}Montrer que pour {\lambda>0} assez petit, {\begin{cases}A=C-\lambda D\\B=C+\lambda D\end{cases}} sont bistochastiques.
    Conclure.

  1. La matrice C est bistochastique mais n’est pas une matrice de permutation.

    Elle possède donc au moins un coefficient {c_{i_{0},j_{0}}\in\,]0,1[}.

    Mais la somme des coefficients de la ligne {i_{0}} de {C} vaut {1}.

    Il existe donc un indice de colonne {j_{1}\ne j_{0}} tel que {0\lt c_{i_{0},j_{1}}\lt 1}.

    De même, il existe un indice de ligne {i_{1}\ne i_{0}}, tel que {0\lt c_{i_{1},j_{1}}\lt 1}.

    À partir de {c_{i_{1},j_{1}}}, on choisit d’abord {j_{2}\ne j_{1}} tel que {0\lt c_{i_{1},j_{2}}\lt 1}.

    On choisit ensuite {i_{2}\ne i_{1}} tel que {0\lt c_{i_{2},j_{2}}\lt 1}.

    Et on recommence à partir de {c_{i_{2},j_{2}}}, etc.

    Les suites {(i_{k})_{k\ge 0}} et {(j_{k})_{k\ge 0}} satisfont donc aux conditions de l’énoncé.

  2. Tous les coefficients d_{i,j} de {D} sont nuls sauf:
    – ceux d’indices {(i_{k},j_{k})} qui valent {1},
    – ceux d’indice {(i_{k},j_{k+1})} qui valent {-1}.

    Pour chaque coefficient {d_{i_{k},j_{k}}=1}, on trouve :
    – sur la même ligne un coefficient {d_{i_{k},j_{k+1}}=-1},
    – sur la même colonne un coefficient {d_{i_{k-1},j_{k}}=-1}

    NB: pour {d_{i_{0},j_{0}}=1}, c’est {d_{i_{0},j_{1}}=-1} et {d_{i_{m},j_{0}}=-1} (qui « ferme la marche »).

    La somme de chaque ligne et chaque colonne de {D} est donc nulle.

    Ainsi la somme de chaque ligne et chaque colonne de {M_{\lambda}=C+\lambda D} vaut {1}.

    Mais pour {\left|{\lambda}\right|} assez petit, tous les coefficients de {M_{\lambda}} sont \gt 0 (rappelons que {M_{\lambda}} ne diffère de {C} qu’en des positions où les {c_{i,j}} sont \gt 0).

    Il existe donc {\lambda>0} tel que {\begin{cases}A=C-\lambda D\\B=C+\lambda D\end{cases}} soient bistochastiques.

    Ainsi {C\in ]A\,;B[} (elle en est le milieu) et n’est donc pas extrémale dans {\mathcal{B}_{n}(\mathbb{R})}.

    Conclusion: les éléments extrémaux du convexe {\mathcal{B}_{n}(\mathbb{R})} sont les matrices de permutation.