Permanent (mathématiques)

Le permanent est un outil d'algèbre linéaire. Par définition, le permanent d'une matrice carrée d'ordre n vaut :

Pour les articles homonymes, voir Permanent.

désigne le groupe symétrique d'indice n. Par exemple :

Lien avec le déterminant

La définition est très proche de celle du déterminant d'une matrice :

où ε(σ) est la signature de la permutation σ. On peut remarquer que pour tout n, la signature et la fonction constante égale à 1 sont (à isomorphisme près) les seuls morphismes de groupes de dans un groupe abélien.

Propriétés

Similarités et différences avec le déterminant

Le permanent peut être vu comme une forme n-linéaire symétrique prenant n vecteurs comme arguments (les colonnes d'une matrice). Il existe pour le permanent des formules analogues à celles du déterminant :

  1. Le permanent de la transposée d'une matrice est égal au permanent de la matrice.
  2. Il existe une formule similaire de développement d'un permanent le long d'une colonne : si , et est la matrice obtenue à partir de A en supprimant la i-ième ligne et la j-ième colonne, alors .
  3. Le permanent d'une matrice triangulaire par blocs vaut .

Mais contrairement au déterminant, le permanent n'est pas multiplicatif.

Lien avec la théorie des graphes

Une matrice booléenne carrée , peut être comprise comme la matrice d'adjacence d'un graphe biparti dont les sommets seraient d'une part et de l'autre, où vaut 1 s'il existe un lien entre le sommet et le sommet et 0 sinon.

Un couplage est parfait s'il est incident à tous les sommets du graphe, c'est-à-dire qu'on peut l'associer à une permutation des sommets telle que . On peut donc interpréter le permanent de A comme le nombre de couplages parfaits du graphe biparti associé à la matrice carrée .

Notons qu'en définissant le poids d'un couplage comme le produit des poids des arêtes du couplage, un raisonnement similaire avec une matrice carrée quelconque A permet d'affirmer que le permanent de A est la somme des poids de tous les couplages parfaits du graphe biparti pondéré associé.

Bornes et conjecture de van der Waerden

En 1926, van der Waerden conjectura que le permanent d'une matrice bistochastique de dimension n est supérieur à n!/nn, valeur atteinte par la matrice ne contenant que des 1/n[1]. Des démonstrations de ce résultat ont été publiées, en 1980 par B. Gyires[2], et en 1981 par G. P. Egorychev (en utilisant l'inégalité d'Alexandrov-Fenchel (en))[3],[4],[5] et D. I. Falikman[6]. Egorychev et Falikman ont remporté le prix Fulkerson en 1982 pour ces preuves[7].

Aspects algorithmiques

Le permanent est beaucoup plus difficile à calculer que le déterminant. Il n'existe pas d'analogue de l'élimination de Gauss-Jordan pour les permanents. Plus précisément, le problème du calcul du permanent de matrice 0-1 peut être vu comme un problème de comptage et appartient à la classe des problèmes #P-complets[8]. Il peut être approché en temps polynomial par des algorithmes probabilistes dans le cas des matrices à coefficients positifs[9].

Formule de Ryser

La formule de Ryser due à Herbert Ryser[10], est un algorithme de calcul du permanent basé sur le principe d'inclusion-exclusion[11] et qui peut être formulé comme suit : Pour une matrice obtenue en supprimant colonnes dans , soit le produit des sommes des lignes de . Soit la somme des pour toutes les matrices . Alors

.

On peut réécrire la formule en fonction des entrées de la matrice comme suit[12] :

La formule de Ryser peut être évaluée en operations artihmétiques, ou en se traitant les ensembles dans l'ordre donné par le code de Gray [13].

Utilisation et applications

Contrairement au déterminant, le permanent n'a pas de signification géométrique naturelle. Il est utilisé en combinatoire, par exemple pour démontrer le lemme des mariages,[réf. nécessaire] et également en théorie des graphes.

Le permanent apparaît également en physique théorique, notamment pour l'étude de l'adsorption (dimer model), ainsi qu'en physique statistique, en cristallographie et en chimie physique[14].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Permanent » (voir la liste des auteurs).
  1. (en) B. L. van der Waerden, « Aufgabe 45 », Jber. Deutsch. Math.-Verein., vol. 35, , p. 117.
  2. (en) B. Gyires, « The common source of several inequalities concerning doubly stochastic matrices », Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, vol. 27, nos 3-4, , p. 291-304 (Math Reviews 604006).
  3. (ru) G. P. Egoryčev, « Reshenie problemy van-der-Vardena dlya permanentov », Akademiya Nauk Soyuza SSR, Krasnoyarsk, Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., , p. 12 (Math Reviews 602332).
  4. (ru) G. P. Egorychev, « Proof of the van der Waerden conjecture for permanents », Akademiya Nauk SSSR, vol. 22, no 6, , p. 65-71, 225 (Math Reviews 638007).
  5. (en) G. P. Egorychev, « The solution of van der Waerden's problem for permanents », Advances in Mathematics, vol. 42, no 3, , p. 299-305 (DOI 10.1016/0001-8708(81)90044-X, Math Reviews 642395).
  6. (ru) D. I. Falikman, « Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix », Akademiya Nauk Soyuza SSR, vol. 29, no 6, , p. 931-938, 957 (Math Reviews 625097).
  7. (en) « Past Winners of the Fulkerson Prize », sur Mathematical Optimization Society, .
  8. (en) Leslie G. Valiant, « The Complexity of Computing the Permanent », Theoretical Computer Science, Elsevier, vol. 8, no 2, , p. 189-201 (DOI 10.1016/0304-3975(79)90044-6).
  9. (en) Mark Jerrum, Alistair Sinclair et Eric Vigoda, « A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries », Journal of the ACM, vol. 51, no 4, , p. 671-697. Cet article a valu le prix Fulkerson en 2006 à Mark Jerrum, Alistair Sinclair et Eric Vigoda. Voir (en) « Delbert Ray Fulkerson Prize », sur le site de l'AMS.
  10. Herbert John Ryser, Combinatorial Mathematics, Mathematical Association of America, coll. « The Carus Mathematical Monographs » (no 14),
  11. Jacobus Hendricus van Lint et Richard Michale Wilson, A Course in Combinatorics, (ISBN 0-521-00601-5), p. 99
  12. (en) Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, Boca Raton/London/New York etc., Chapman & Hall - CRC Press, (1re éd. 1998), 3252 p. (ISBN 1-58488-347-2), « Permanent »
  13. Albert Nijenhuis et Herbert S. Wilf, Combinatorial Algorithms, Academic Press,
  14. (en) V.E. Tarakanov, « Permanent », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne).

Voir aussi

Immanant d'une matrice

  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.