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.

Cliquer ici pour voir (ou cacher) le corrigé