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 linéaire. 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'indice 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 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 \mathfrak{S}_n dans un groupe abélien.

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-ième ligne et la j-ième colonne, alors {\rm per}(A) = \sum_{i=1}^n a_{ij}{\rm 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 {\rm per}(A) = \prod_{i=1}^k{\rm 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 est supérieure à n!/nn, 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]

Le permanent est a priori 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 approximé en temps polynomial par des algorithmes probabilistes dans le cas des matrices à coefficients positifs[9].

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[10].

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

(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, no 3-4,‎ , 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.,‎ , p. 12.
  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.
  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).
  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.
  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. (en) V.E. Tarakanov, « Permanent », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer,‎ (ISBN 978-1556080104, lire en ligne).

Voir aussi[modifier | modifier le code]

Immanant d'une matrice