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).

Cliquer ici pour voir (ou cacher) le corrigé