Matrices bistochastiques, épisode 7

Publié le 24/01/17

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5, Ep6.
Écrire une fonction Python traverse d’argument une matrice carrée {A=(a_{i,j})} et renvoyant la première permutation {\sigma} (au sens lexicographique) telle que les {a_{\sigma(j),j}} soient non nuls.
Dire que {\sigma} existe, c’est dire que {A} est traversable.
Si ce n’est pas le cas, traverse renverra la liste {[-1,-1,\ldots,-1]} de longueur {n}.
On cherche donc la première permutation {\sigma} traversant {A}.

On va gérer des « curseurs » (un par colonne) se déplaçant de haut en bas sur leur colonne: au départ, chaque curseur est positionné sur la ligne d’indice {-1} (c’est-à-dire « au-dessus » de la première ligne de {A}, c’est-à-dire de la ligne d’indice 0).

À tout moment, il y a une colonne courante {j}, dont on déplace le curseur vers le bas à la recherche d’un premier coefficient {a_{i,j}} non nul (et sur une ligne non encore occupée par les curseurs des colonnes {0,1,\ldots,j-1}).

Si cette recherche aboutit, on laisse le curseur {j} en ligne {i}, et on continue en colonne {j+1}.

Si au contraire elle n’aboutit pas, on réinitialise le curseur {j} (on le replace « au-dessus » de la matrice) et on reprend la recherche avec le curseur {j-1} (en démarrant juste en dessous de sa position actuelle).

Tout cela va s’arrêter soit parce qu’on a réussi à placer le curseur de la dernière colonne (et alors on a trouvé notre permutation qui traverse {A}) soit parce que des échecs successifs ont amené (par des reculs sur les numéros de colonne) à démarrer une recherche en « colonne » {-1} (ce qui marque l’absence de solution : à ce moment, tous les curseurs sont en position {-1}, c’est-à-dire au-dessus de la matrice).

Voici un exemple d’utilisation, avec une matrice {A} d’ordre 10.

Le premier chemin (ordre lexicographique) traversant {A} est donné par la permutation :
{\sigma=\begin{pmatrix}0&1&2&3&4&5&6&7&8&9\\ 0&2&6&1&3&4&8&7&9&5\end{pmatrix}}.