Permanent (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Permanent.

Le permanent est un outil d'algèbre matricielle. Par définition, le permanent d'une matrice carrée A = (a_{ij}) d'ordre n vaut :

 \operatorname{per}(A)=\sum_{\sigma\in \mathfrak{S}_n}\prod_{i=1}^n a_{i,\sigma(i)}.

\mathfrak{S}_n désigne le groupe symétrique d'ordre n. Par exemple :

\operatorname{per}\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad+bc

Lien avec le déterminant[modifier | modifier le code]

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

\operatorname{det}(A) = \sum_{\sigma \in \mathfrak{S}_n} \varepsilon(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}

où ε(σ) est la signature de la transposition σ. On peut noter qu'il est impossible de définir de manière semblable une autre notion que le permanent ou le déterminant en remplaçant la signature ou la fonction constante égale à 1 par un autre morphisme de groupe de \mathfrak{S}_n dans \mathbb{C}^* : la signature et la fonction constante égale à 1 sont les seuls morphismes de groupe de \mathfrak{S}_n dans \mathbb{C}^*.

Propriétés[modifier | modifier le code]

Similarités et différences avec le déterminant[modifier | modifier le code]

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 A = (a_{ij}), et A_{ij} est la matrice obtenue à partir de A en supprimant la ième ligne et la jème colonne, alors per(A) = \sum_{i=1}^n a_{ij} per(A_{ij}).
  3. Le permanent d'une matrice trigonale par blocs A = \left(
  \begin{matrix}
    A_1 &     &      &   (0)   \\
        & A_2 &      &      \\
        &     &  \cdot &      \\
      (*)  &     &      & A_k  \\
  \end{matrix}
\right) vaut per(A) = \prod_{i=1}^k per(A_i).

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

Théorie des graphes[modifier | modifier le code]

Bornes et conjecture de Van der Waerden[modifier | modifier le code]

En 1926, Van der Waerden conjectura que le permanent d'une matrice bistochastique de dimension n était supérieure à n!/n^n, valeur atteinte par la matrice ne contenant que des 1/n[1]. Des preuves 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[modifier | modifier le code]

Outre la difficulté théorique, le permanent est a priori beaucoup plus dur à 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-complet[8]. Il peut être approximé en temps polynomial par des algorithmes probabilistes dans le cas des matrices à coefficients positifs[9],[10].

Utilisation et applications[modifier | modifier le code]

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, et également en théorie des graphes.

Le permanent apparait aussi en physique théorique, notamment pour l'étude de l'adsorption (dimer model), ainsi qu'en physique statistique, en cristallographie et en chimie physique[11].

Notes et références[modifier | modifier le code]

  1. B. L. van der Waerden, « Aufgabe 45 », Jber. Deutsch. Math.-Verein., vol. 35,‎ 1926, p. 117.
  2. B. Gyires, « The common source of several inequalities concerning doubly stochastic matrices », Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, vol. 27, no 3-4,‎ 1980, p. 291–304
  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.,‎ 1980, p. 12.
  4. (ru) G. P. Egorychev, « Proof of the van der Waerden conjecture for permanents », Akademiya Nauk SSSR, vol. 22, no 6,‎ 1981
  5. G. P. Egorychev, « The solution of van der Waerden's problem for permanents », Advances in Mathematics, vol. 42, no 3,‎ 1981, p. 299–305 (DOI 10.1016/0001-8708(81)90044-X).
  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,‎ 1981, p. 931–938, 957.
  7. Mathematical Optimization Society, « Lauréats du prix Fulkerson »,‎ 19 aout 2012
  8. Leslie G. Valiant, « The Complexity of Computing the Permanent », Theoretical Computer Science, Elsevier, vol. 8, no 2,‎ 1979, p. 189-201 (DOI 10.1016/0304-3975(79)90044-6)
  9. Voir l'article : 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,‎ 2004, p. 671–697
  10. Cet article a valu le prix Fulkerson à Mark Jerrum, Alistair Sinclair et Eric Vigoda. Voir « Delbert Ray Fulkerson Prize », sur le site de l'AMS (consulté en 4 juillet)
  11. (en) V.E. Tarakanov, « Permanent », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer,‎ 2002 (ISBN 978-1556080104, lire en ligne)

Voir aussi[modifier | modifier le code]