Matrices bistochastiques, épisode 8

Publié le 25/01/17

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5, Ep6, Ep7.
Soit A une matrice \mu-magique d’ordre n, avec \mu\gt0.
On sait que {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}}{\alpha_{k}>0}, {\displaystyle\sum_{k=1}^{m}\alpha_{k}=\mu}, les {P_{k}} des matrices de permutation.
On sait aussi qu’il y a une solution avec {m\lt (n-1)^{2}+1},

On demande ici d’écrire une fonction decomp d’argument A, et renvoyant la liste {L=[[\alpha_{1},P_{1}],[\alpha_{2},P_{2}],\ldots,[\alpha_{m},P_{m}]]} au sens de l’écriture précédente.

Si A est bistochastique, on obtient ainsi une représentation de {A} comme barycentre (à coefficients strictement positifs) de matrices de permutation.

On vérifiera emipiriquement que l’algorithme décompose {A} en une combinaison linéaire d’au plus {(n-1)^{2}+1} matrices de permutation (il est donc plutôt optimal).

Pour vérifier le bon fonctionnement de la fonction decomp, on écrira une fonction recomp reconstituant la matrice {A} à partir de sa décomposition.

Voici la fonction decomp :

Remarque: une matrice positive magique {A} de somme {\mu>0} a au moins un coefficient non nul dans chaque ligne et dans chaque colonne.

En fait si {A} a seulement {n} coefficients non nuls, alors elle en possède un et un seul dans chaque ligne et dans chaque colonne, et comme elle est magique de somme {\mu>0} elle s’écrit {A=\mu P}, où {P} est une matrice de permutation.

Dans la décomposition {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}} de l’algorithme précédent, chaque nouvelle matrice {P_{k}} correspond à l’annulation d’au moins un coefficient supplémentaire.

Au pire, il faut {n^{2}-n} étapes pour annuler {n^{2}-n} coefficients: la matrice {A_{k}} obtenue n’ayant que {n} coefficients non nuls est de la forme {\alpha_{k}P_{k}}, et c’est fini à l’étape suivante.

Bien sûr, l’arrivée sur une matrice {A_{k}=\alpha_{k}P_{k}} peut se produire avant. Mais en définitive, on est certain que l’algorithme produit une décomposition de {A} en au plus {n^{2}-n+1} matrices {P_{k}} (alors qu’en théorie on peut descendre jusqu’à plus {(n-1)^{2}+1} matrices {P_{k}}).

Pour illustrer decomp, on forme (puis on décompose) une matrice positive 100-magique d’ordre {n=5} (obtenue en ajoutant {100} matrices de permutation aléatoires).

Le résultat de la décomposition de {A} est placée dans decA.

On voit que cette décomposition est de longueur {(n-1)^{2}=16}.

On demande ensuite l’affichage des {\alpha_{k}} et des matrices {P_{k}} de la décomposition :

Voici les affichages obtenus:

Voici maintenant la fonction recomp reformant une matrice décomposée par decomp :

On applique recomp au contenu de decA et on retrouve notre matrice {A} :

Nouvel exemple, on forme une matrice {B}, bistochastique d’ordre {5} :

On calcule la décomposition de {B}.
Elle est de longueur {17}, c’est-à-dire {(n-1)^{2}+1} avec {n=5}.
On vérifie que la somme des coefficients {\alpha_{k}} est bien égale à {1}.
On affiche ensuite les couples {(\alpha_{k},P_{k})} de cette décomposition.

Voici les résultats de cet affichage:

Enfin, on retrouve bien la matrice {B} en appliquant recomp au contenu de decB :