Matrices bistochastiques, épisode 2

Publié le 19/01/17

On reprend ici les définitions et les notations de l’épisode 1.
On établit des propriétés usuelles des matrices bistochastiques ou de permutation.

    1. Soit \sigma et s dans {{\mathcal S}_{n}}.
      Préciser {P_{\,\text{Id}}}, {P_{s}\,P_{\sigma}}, {{P_{\sigma}}^{-1}}, {{(P_{\sigma})}^{\top}} et {P_{\sigma}^{\,m}} pour tout {m} de {\mathbb{Z}}.
    2. Soit {A} dans {\mathcal{M}_{n}(\mathbb{R})}, et soit {P_{\sigma}} une matrice de permutation d’ordre {n}.
      Décrire le passage de {A} à chacune des matrices {P_{\sigma}^{-1}A}, {AP_{\sigma}}, et {P_{\sigma}^{-1}AP_{\sigma}}.
    1. Montrer que {\mathcal{B}_{n}(\mathbb{R})} est compact et stable pour le produit des matrices.
    2. Soit {A,B} dans {\mathcal{B}_{n}(\mathbb{R})}, et {\lambda} dans {[0,1]}.
      Montrer que {C=\lambda A+(1\!-\!\lambda)B} est dans {\mathcal{B}_{n}(\mathbb{R})}.
      L’ensemble {\mathcal{B}_{n}(\mathbb{R})} est donc convexe.
    3. Soit {A}, {B} distinctes dans {\mathcal{B}_{n}(\mathbb{R})}, et soit {P_{\sigma}\in\mathcal{M}_{n}(\mathbb{R})}.
      On suppose que {P_{\sigma}} est élément du segment [A\,;B].
      Montrer que nécessairement {P=A} ou {P=B}.
      Ainsi {]A\,;B[} ne contient aucune matrice de permutation.
      On dit que les matrices de permutation sont extrémales dans {\mathcal{B}_{n}(\mathbb{R})}.

    1. On se place dans {\mathbb{R}^{n}}, muni de la base canonique {\mathcal{B}=(e_{i})_{1\le i\le n}}.

      Soit \varphi_{\sigma}\in\text{GL}(\mathbb{R}^{n}) défini par : {\forall\, j\in[[ 1,n]],\;\varphi_{\sigma}(e_{j})=e_{\sigma(j)}}.

      Alors {P_{\sigma}} est la matrice de {\varphi_{\sigma}} dans {\mathcal{B}}.

      Pour {1\le j\le n}, on a {(\varphi_{s}\varphi_{\sigma})(e_{j})=\varphi_{s}(e_{\sigma(j)})=e_{s\sigma(j)}}.

      Ainsi {\varphi_{s}\varphi_{\sigma}=\varphi_{s\sigma}}. De plus {\varphi_{\,\text{Id}}=\text{Id}_{\mathbb{K}^{n}}}.

      On a alors immédiatement: {\varphi_{\sigma}^{-1}=\varphi_{\sigma^{-1}}}, et {(\varphi_{\sigma})^{m}=\varphi_{\sigma^{m}}}.

      Les propriétés de {\sigma\mapsto \varphi_{\sigma}} donnent :
      P_{\text{Id}}=I_{n},\;P_{s}\,P_{\sigma}=P_{s\sigma},\;P_{\sigma}^{-1}=P_{\sigma^{-1}},\;P_{\sigma}^{m}=P_{\sigma^{m}}Enfin dans {\mathbb{R}^{n}} muni de son produit scalaire canonique, {\varphi_{\sigma}} est une isométrie.

      Sa matrice {P_{\sigma}} dans la base orthonormée {\mathcal{B}} est donc orthogonale.

      On en déduit : (P_{\sigma})^{\top}=P_{\sigma}^{-1}=P_{\sigma^{-1}}.

    2. Ici {i} et {j} désignent deux indices quelconques de ligne et de colonne.

      {\begin{array}{rl}\text{D'une part : }\big(P_{\sigma}^{-1}A\big)_{i,j}&=\big({(P_{\sigma})}^{\top}A\big)_{i,j}=\displaystyle\sum_{k=1}^{n}\big(P_{\sigma}\big)_{k,i}\,a_{k,j}\\&=\displaystyle\sum_{k=1}^{n}\delta_{k,\sigma(i)}\,a_{k,j}=a_{\sigma(i),j}\end{array}}

      {\begin{array}{rl}\text{D'autre part : }\big(AP_{\sigma}\big)_{i,j}&=\displaystyle\sum_{k=1}^{n}a_{i,k}\big(P_{\sigma}\big)_{k,j}\\&=\displaystyle\sum_{k=1}^{n}a_{i,k}\,\delta_{k,\sigma(j)}=a_{i,\sigma(j)}\phantom{\biggl(}\end{array}}

      En combinant les deux résultats précédents : {\bigl(P_{\sigma}^{-1}AP_{\sigma}\bigr)_{i,j}=a_{\sigma(i),\sigma(j)}}.

      Passer de {A} à {P_{\sigma}^{-1}A} (resp. de {A} à {AP_{\sigma}}) c’est donc renuméroter les lignes (resp. les colonnes) de {A} par {\text{L}_{i}\leftarrow\text{L}_{\sigma(i)}} (resp. {\text{C}_{i}\leftarrow\text{C}_{\sigma(i)}}).

      Passer de {A} à {B=P_{\sigma}^{-1}AP_{\sigma}} (conjugaison par {P_{\sigma}}), c’est renuméroter les lignes et les colonnes : le coefficient d’indice {(\sigma(i),\sigma(j))} de {A} passe en position {(i,j)} dans {B}.

    1. Soit {A=(a_{i,j})} dans {\mathcal{M}_{n}(\mathbb{R})}. Soit {e=(1,1,\ldots,1)\in\,\mathbb{R}^{n}}.

      Dire {A\in\,\mathcal{B}_{n}(\mathbb{R})} c’est dire : les a_{i,j} sont \ge 0 et Ae=A^{\top}e=e.

      Dès lors, si {A} et {B} sont dans \mathcal{B}_{n}(\mathbb{R}), alors les coefficients de AB sont \ge0 et on a (AB)e=(AB)^{\top}e=e, donc {AB\in\,\mathcal{B}_{n}(\mathbb{R})}.

      De même soit {(A_{k})_{k\ge0}} une suite de {\mathcal{B}_{n}(\mathbb{R})}, convergente ver {A=(a_{i,j})}.

      À la limite, on a encore {a_{i,j}\ge0} et {A_{k}e=A_{k}^{\top}e=e}, donc {A\in\mathcal{B}_{n}(\mathbb{R})}.

      Ainsi l’ensemble {\mathcal{B}_{n}(\mathbb{R})} est une partie fermée de {\mathcal{M}_{n}(\mathbb{R})}.

      Enfin {\mathcal{B}_{n}(\mathbb{R})} est borné : si on utilise par exemple {\left\|{A}\right\|=\max\left|{a_{i,j}}\right|}, toute matrice bistochastique vérifie {\left\|A\right\|\le1}.

      Conclusion: {\mathcal{B}_{n}(\mathbb{R})} est un compact de {\mathcal{M}_{n}(\mathbb{R})}.

    2. La matrice {C} est évidemment à coefficients dans {\mathbb{R}^{+}}.

      On a {Ce=(\lambda A+\mu B)e=\lambda Ae+\mu Be=\lambda e+\mu e=e}.

      De même {{C}^{\top}e=e}. Donc {C\in\mathcal{B}_{n}(\mathbb{R})}.

    3. Par l’absurde, on suppose que {P\notin\{A,B\}}.

      Ainsi il existe {\lambda\in\,]0,1[} tel que {P_{\sigma}=\lambda A+(1-\lambda)B}.

      Fixons un indice de colonne {j\in[[ 1,n]]}.

      Pour tout {i} de {[[ 1,n]]}, on a {\lambda a_{i,j}+(1-\lambda) b_{i,j}=(P_{\sigma})_{i,j}=\delta_{i,\sigma(j)}}.

      En particulier, pour tous indices i,j tels que {\forall\, i\ne\sigma(j)} :{\lambda a_{i,j}+(1-\lambda) b_{i,j}=0\text{ donc }a_{i,j}=b_{i,j}=0\text{ car }0\lt \lambda\lt 1}{A,B} étant bistochastiques, on en déduit {a_{\sigma(j)j}=b_{\sigma(j)j}=1=(P_{\sigma})_{\sigma(j)j}}.

      Ainsi {A,B,P} ont même {j}-ème colonne, pour tout {j\in[[ 1,n]]}.

      Il en résulte {A=P=B}, ce qui est contradictoire.