Matrices bistochastiques, épisode 4

Publié le 21/01/17

On reprend les définitions et les notations de l’épisode 1.
Pour {A\in\mathcal{M}_{n}(\mathbb{R})}, et pour {\sigma\in\mathcal{S}_{n}}, on note {\sigma(A)=\displaystyle\prod_{j=1}^{n}a_{\sigma(j),j}}.
On dit que {A} est traversable s’il existe {\sigma\in\mathcal{S}_{n}} telle que {\sigma(A)\ne0}.
On souhaite montrer l’équivalence des propositions:
{(\star)\quad} {A} n’est pas traversable
{(\star\star)} {A} possède une sous-matrice nulle de taille {r\times s}, où {r+s=n+1}

  1. Montrer que permuter les lignes ou colonnes ne modifie pas la traversabilité.
  2. Prouver que {(\star\star)} implique {(\star)}.
  3. Établir que {(\star)} implique {(\star\star)} par récurrence sur {n}.
  4. En déduire que toute matrice magique de somme {\mu>0} (et en particulier toute matrice bistochastique) est traversable (raisonner par l’absurde).

  1. Soit {s} dans {\mathcal{S}_{n}(\mathbb{R})}. Soit {A} dans {\mathcal{M}_{n}(\mathbb{R})}.{\sigma(P_{s}^{-1}A)=\displaystyle\prod_{j=1}^{n}(P_{s}^{-1}A)_{\sigma(j),j}=\displaystyle\prod_{i=1}^{n}a_{s(\sigma(j)),j}=(s\sigma)(A)}{\begin{array}{rl}\sigma(AP_{s})&=\displaystyle\prod_{j=1}^{n}(AP_{s})_{\sigma(j),j}=\displaystyle\prod_{j=1}^{n}a_{\sigma(j),s(j)}\\\\&=\displaystyle\prod_{j=1}^{n}a_{\sigma(s^{-1}(j)),j}=(\sigma s^{-1})(A)\end{array}}Plus généralement : {\sigma(P_{s}^{-1}AP_{s})=(s\sigma)(AP_{s})=(s\sigma s^{-1})(A)}

    Mais {\sigma\mapsto s\sigma}, {\sigma\mapsto \sigma s^{-1}} et {\sigma\mapsto s\sigma s^{-1}} sont des bijections de {\mathcal{S}_{n}}.

    Pour toute matrice de permutation {P}, les matrices {A}, {PA}, {AP}, {P^{-1}AP} sont donc toutes traversables (ou toutes non traversables): la traversabilité de {A} n’est pas modifiée par une renumérotation des lignes et/ou des colonnes.

  2. Soit {A\in\mathcal{M}_{n}(\mathbb{R})}, ayant une matrice extraite nulle {A_{r,s}\in\mathcal{M}_{r,s}(\mathbb{R})}, où {r+s=n+1}.

    Quitte à permuter lignes et/ou colonnes (ça ne change pas la traversabilité), on suppose que {A_{r,s}} est l’intersection des {r} premières lignes et des {s} premières colonnes.

    Ainsi {a_{i,j}=0} pour {1\le i\le r} et {1\le j\le s}. Soit {\sigma} quelconque dans \mathcal{S}_{n}.

    L’ensemble {\sigma([[ 1,s]])}, de cardinal s, n’est pas inclus dans {[[ r+1,n]]} (de cardinal {s-1}).

    Il existe donc {j\in[[1,s]]} avec {\sigma(j)\in[[ 1,r]]}, c’est-à-dire {a_{\sigma(j),j}=0}.

    Ainsi {\sigma(A)=0}, et ceci pour tout {\sigma\in\mathcal{S}_{n}}, donc {A} n’est pas traversable.

    • Si la dernière colonne est nulle, alors c’est fini en choisissant cette colonne (qui est de taille {(n+1)\times 1}) comme sous-matrice nulle.

    • On suppose donc que la dernière colonne de A n’est pas nulle.

      Quitte à renuméroter les lignes de {A}, on peut supposer {a_{n+1,n+1}\ne0}.

      Soit {B} la sous-matrice de {A} formée des {n} premières lignes et colonnes.

      On étend tout {\sigma\in\mathcal{S}_{n}} en une permutation de {[[ 1,n+1]]} par {\sigma(n+1)=n+1}.

      On a alors {0=\sigma(A)=\sigma(B)a_{n+1,n+1}} donc {\sigma(B)=0}, pour tout {\sigma} de {\mathcal{S}_{n}}.

      Par hyp. de récurrence, {B} (donc {A}) a un bloc nul de taille {p\times q}, où {p+q=n+1}.

      Quitte à permuter lignes et/ou colonnes, on peut supposer qu’il se situe en bas à gauche.

    • Ainsi {A=\begin{pmatrix}C&D\\0&E\end{pmatrix}\in\mathcal{M}_{n+1}(\mathbb{R})}, où {0} est de taille {p\times q} (et {p+q=n+1}).

      Ici C est carrée d’ordre {q} et {E} est carrée d’ordre {p}.

      Si {C} et {E} étaient traversables (la première avec une permutation {\sigma_{1}} de {[[ 1,q]]}, et la deuxième avec une permutation {\sigma_{2}} de {[[ 1,p]]}), alors {A} serait traversable (avec la permutation {\sigma} de {[[ 1,n+1]]} formée par concaténation de {\sigma_{1}} et de {\sigma_{2}}).

      Ainsi l’une au moins des deux matrices {C} ou {E} n’est pas traversable, et sans rien changer à la généralité du problème on peut bien supposer qu’il s’agit de {C}.

    • Par hyp. de récurrence, {C} a un bloc nul {C'} de taille {r\times s}{r+s=q+1}.

      Quitte à permuter lignes/colonnes, on peut supposer que {C'} est en bas à gauche de {C}.

      On peut donc écrire {A=\begin{pmatrix}X&Y&D'\\0_1&Z&D''\\0_2&0_3&E\end{pmatrix}}{0_1\in\mathcal{M}_{r,s}(\mathbb{R})} et {0_2\in\mathcal{M}_{p,s}(\mathbb{R})}
      Le bloc nul {\begin{pmatrix}0_1\\0_2\end{pmatrix}} est de taille {(r+p)\times s}.

      Or {r+p+s=p+q+1=n+2}, donc c’est gagné!

      Rappelons que la matrice finale est certainement obtenue à partir de la matrice initiale {A} par permutation des lignes et des colonnes, mais que ça ne change rien aux propriétés de traversabilité ni à l’existence de sous-matrices nulles!

    • Concluons : on a donc prouvé par récurrence forte sur {n} que, si {A\in\mathcal{M}_{n}(\mathbb{R})} est non traversable, alors elle possède une sous-matrice nulle de taille {r\times s} avec {r+s=n+1}.

  3. Soit {A\ge0} dans {\mathcal{M}_{n}(\mathbb{R})}, magique de somme {\mu>0}.

    Par l’absurde, on la suppose non traversable.

    D’après ce qui précède, et au besoin après une permutation des lignes/colonnes, on peut donc écrire {A=\begin{pmatrix}X&Y\\0&Z\end{pmatrix}} où le bloc nul est de taille {r\times s} et {r+s=n+1}.

    Chacune des {s} colonnes de {X} est de somme {\mu}, tout comme chacune des {r} lignes de {Z}.

    La somme des coefficients de {X} et {Z} est donc {(r+s)\mu=(n+1)\mu}.

    Donc celle de {A} est {\ge(n+1)\mu}, ce qui est absurde car la somme des coefficients d’une matrice magique d’ordre {n} et de somme {\mu} est {n\mu}.

    Conclusion finale: toute matrice magique de somme {\mu>0} (notamment toute matrice bistochastique) est donc traversable.