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.

Cliquer ici pour voir (ou cacher) le corrigé