Matrices bistochastiques, épisode 6

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5.
Soit {A} une matrice positive magique de somme {\mu>0}.
On sait que {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}} (avec {\alpha_k>0}, {\displaystyle\sum_{k=1}^{m}\alpha_k=\mu}, les {P_k} matrices de permutations).
On va montrer que m peut être rendu inférieur ou égal à {(n\!-\!1)^2\!+\!1}.

Pour cela, on suppose {m>(n\!-\!1)^{2}\!+\!1}: l’objectif est de réduire le nombre de matrices {P_{k}} (tout en gardant les propriétés : les {\alpha_{k}>0} et de somme {\mu}).

  1. Montrer que les matrices 0-magiques forment un EV de dimension {(n-1)^{2}}.
  2. Montrer qu’il existe des \beta_{k} non tous nuls, tels que : {\displaystyle\sum_{k=1}^{m}\beta_{k}P_{k}=0\quad\text{et}\quad\displaystyle\sum_{k=1}^{m}\beta_{k}=0}Indication: considérer les matrices {P_{k}-P_{1}}, avec {2\le k\le m}.

  3. Justifier la possibilité de choisir {j\in\{1,\ldots,m\}} tel que : {\dfrac{\alpha_{j}}{\beta_{j}}=\min\biggl\{\dfrac{\alpha_{k}}{\beta_{k}},\;1\le k\le m,\;\beta_{k}>0\biggr\}}Quitte à tout renuméroter, on suppose {j=m}.
  4. Montrer que {A=\displaystyle\sum_{k=1}^{m-1}\delta_{k}P_{k}}, où {\delta_{k}=\alpha_{k}-\alpha_{m}\dfrac{\beta_{k}}{\beta_{m}}}.

    Indiquer le signe des {\delta_{k}}, et leur somme.

    Énoncer le résultat obtenu (en en donner la version bistochastique).

Cliquer ici pour voir (ou cacher) le corrigé

  1. Soit {E_{n}} l’ensemble des matrices 0-magiques d’ordre {n}.

    C’est de manière évidente un sous-espace vectoriel de {\mathcal{M}_{n}(\mathbb{R})}.

    L’application {\varphi\colon E_{n}\rightarrow\mathcal{M}_{n-1}(\mathbb{R})} qui à {A\in E_{n}} associe la sous-matrice {A'\in\mathcal{M}_{n-1}(\mathbb{R})} formée des {n} premières lignes et des {n-1} premières colonnes de {A} est linéaire.

    Elle est aussi bijective : la matrice {A} étant magique de somme nulle, la connaissance des {a_{i,j}} avec {1\le i,j\le n-1} détermine en effet les {a_{i,n}} (avec {1\le i\le n-1}), les {a_{n,j}} (avec {1\le j\le n-1}) puis finalement {a_{n,n}} de manière unique.

    Les matrices 0-magiques forment donc un SEV dimension {(n-1)^{2}} de {\mathcal{M}_{n}(\mathbb{R})}.

  2. Les {m-1>(n-1)^{2}} matrices {P_{k}-P_{1}}, avec {2\le k\le m}, sont 0-magiques.

    Elles sont donc liées: il existe des {\beta_{k}} non tous nuls tels que {\displaystyle\sum_{k=2}^{m}\beta_{k}(P_{k}-P_{1})=0}.

    Si on pose {\beta_{1}=-\displaystyle\sum_{k=2}^{m}\beta_{k}}, on a ainsi {\displaystyle\sum_{k=1}^{m}\beta_{k}P_{k}=0} et {\displaystyle\sum_{k=1}^{m}\beta_{k}=0}.

  3. On sait que les {\beta_{k}} sont non tous nuls, et que {\displaystyle\sum_{k=1}^{m}\beta_{k}=0}.

    Sans rien changer à la généralité du problème, et quitte à remplacer tous les {\beta_{k}} par leur opposé, on peut supposer que l’un au moins des {\beta_{k}} est strictement positif.

    Ainsi {\biggl\{\dfrac{\alpha_{k}}{\beta_{k}},\;1\le k\le m,\;\beta_{k}>0\biggr\}} est non vide.

    On peut donc choisir {j} réalisant le minimum demandé.

    Quitte à renuméroter, on suppose maintenant {j=m}.

    Autrement dit, on suppose {\beta_{m}>0}, et {\dfrac{\alpha_{m}}{\beta_{m}}\le \dfrac{\alpha_{k}}{\beta_{k}}} à chaque fois que {\beta_{k}>0}.

  4. On trouve : {\begin{array}{rl}\displaystyle\sum_{k=1}^{m-1}\delta_{k}P_{k}&=\displaystyle\sum_{k=1}^{m-1}\alpha_{k}P_{k}-\dfrac{\alpha_{m}}{\beta_{m}}\displaystyle\sum_{k=1}^{m-1}\beta_{k}P_{k}\\\\&=\displaystyle\sum_{k=1}^{m-1}\alpha_{k}P_{k}+\dfrac{\alpha_{m}}{\beta_{m}}(\beta_{m}P_{m})\\\\&=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}=A\end{array}}Soit {k} dans {[[ 1,m]]}.

    Si {\beta_{k}\le 0}, alors {\delta_{k}=\alpha_{k}-\alpha_{m}\dfrac{\beta_{k}}{\beta_{m}}\ge \alpha_{k}>0} (rappel: {\alpha_{n}>0} et {\beta_{m}>0}).

    Si {\beta_{k}>0}, alors : {\delta_{k}=\alpha_{k}-\alpha_{m}\dfrac{\beta_{k}}{\beta_{m}}=\beta_{k}\biggl(\dfrac{\alpha_{k}}{\beta_{k}}-\dfrac{\alpha_{m}}{\beta_{m}}\biggr)\ge 0}.

    Dans tous les cas, on a donc {\delta_{k}\ge0}. Enfin : {\begin{array}{rl}\displaystyle\sum_{k=1}^{m-1}\delta_{k}&=\displaystyle\sum_{k=1}^{m-1}\alpha_{k}-\dfrac{\alpha_{m}}{\beta_{m}}\displaystyle\sum_{k=1}^{m-1}\beta_{k}\\\\&=\displaystyle\sum_{k=1}^{m-1}\alpha_{k}-\dfrac{\alpha_{m}}{\beta_{m}}(-\beta_{m})=\displaystyle\sum_{k=1}^{m}\alpha_{k}=\mu\end{array}}En conclusion:
    On est parti de l’égalité : {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}} ({m>(n-1)^{2}+1}, {\alpha_{k}>0}).
    On es arrivé à {A=\displaystyle\sum_{k=1}^{m-1}\delta_{k}P_{k}}, avec des {\delta_{k}\ge0}.

    On a donc réduit le nombre des {P_{k}} (d’au moins une, et il peut y avoir des {\delta_{k}} nuls).

    Cette réduction est possible tant que le nombre de {P_{k}} est {\gt(n-1)^{2}+1}.

    Le résultat est donc le suivant :
    Toute matrice positive magique de somme {\mu>0} peut s’écrire sous la forme d’une combinaison linéaire à coefficients {\alpha_{k}>0} de matrices de permutation; la somme des {\alpha_{k}} vaut {\mu}; le nombre de matrices de permutation entrant dans cette décomposition peut être rendu inférieur ou égal à {(n-1)^{2}+1}.

    Pour les matrices bistochastiques (donc quand {\mu=1}), on obtient l’énoncé suivant:
    Toute matrice bistochastique d’ordre {n} peut s’écrire comme un barycentre à coefficients strictement positifs d’au plus {(n-1)^{2}+1} matrices de permutations.