Permanent (mathématiques)

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

${\displaystyle \operatorname {per} (A)=\sum _{\sigma \in {\mathfrak {S}}_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}.}$

${\displaystyle {\mathfrak {S}}_{n}}$ désigne le groupe symétrique d'indice n. Par exemple :

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

Lien avec le déterminant

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

${\displaystyle \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 ${\displaystyle {\mathfrak {S}}_{n}}$ 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 ${\displaystyle A=(a_{ij})}$, et ${\displaystyle A_{ij}}$ est la matrice obtenue à partir de A en supprimant la i-ième ligne et la j-ième colonne, alors ${\displaystyle {\rm {per}}(A)=\sum _{i=1}^{n}a_{ij}{\rm {per}}(A_{ij})}$.
3. Le permanent d'une matrice triangulaire par blocs ${\displaystyle A=\left({\begin{matrix}A_{1}&&&(0)\\&A_{2}&&\\&&\cdot &\\(*)&&&A_{k}\\\end{matrix}}\right)}$ vaut ${\displaystyle {\rm {per}}(A)=\prod _{i=1}^{k}{\rm {per}}(A_{i})}$.

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

Lien avec la théorie des graphes

Une matrice booléenne carrée ${\displaystyle n\times n}$, ${\displaystyle A=(a_{ij})}$ peut être comprise comme la matrice d'adjacence d'un graphe biparti dont les sommets seraient ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ d'une part et ${\displaystyle y_{1},y_{2},\dots ,y_{n}}$ de l'autre, où ${\displaystyle a_{ij}}$ vaut 1 s'il existe un lien entre le sommet ${\displaystyle x_{i}}$ et le sommet ${\displaystyle y_{j}}$ 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 ${\displaystyle \sigma }$ des sommets telle que ${\displaystyle \prod _{i=1}^{n}a_{i,\sigma (i)}=1}$. On peut donc interpréter le permanent de A comme le nombre de couplages parfaits du graphe biparti associé à la matrice carrée ${\displaystyle A}$.

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!/nⁿ, 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 ${\displaystyle A_{k}}$ obtenue en supprimant ${\displaystyle k}$ colonnes dans ${\displaystyle A}$, soit ${\displaystyle P(A_{k})}$ le produit des sommes des lignes de ${\displaystyle A_{k}}$. Soit ${\displaystyle \Sigma _{k}}$ la somme des ${\displaystyle P(A_{k})}$ pour toutes les matrices ${\displaystyle A_{k}}$. Alors

${\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{n-1}(-1)^{k}\Sigma _{k}}$.

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

${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$

La formule de Ryser peut être évaluée en ${\displaystyle O(2^{n-1}n^{2})}$ opérations arithmétiques, ou en ${\displaystyle O(2^{n-1}n)}$ en traitant les ensembles ${\displaystyle S}$ 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,‎ 1926, p. 117.
2. (en) B. Gyires, « The common source of several inequalities concerning doubly stochastic matrices », Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, vol. 27, n^os 3-4,‎ 1980, p. 291-304 (MR 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.,‎ 1980, p. 12 (MR 602332).
4. (ru) G. P. Egorychev, « Proof of the van der Waerden conjecture for permanents », Akademiya Nauk SSSR, vol. 22, n^o 6,‎ 1981, p. 65-71, 225 (MR 638007).
5. (en) G. P. Egorychev, « The solution of van der Waerden's problem for permanents », Advances in Mathematics, vol. 42, n^o 3,‎ 1981, p. 299-305 (DOI 10.1016/0001-8708(81)90044-X, MR 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, n^o 6,‎ 1981, p. 931-938, 957 (MR 625097).
7. (en) « Past Winners of the Fulkerson Prize », sur Mathematical Optimization Society, 19 aout 2012.
8. (en) Leslie G. Valiant, « The Complexity of Computing the Permanent », Theoretical Computer Science, Elsevier, vol. 8, n^o 2,‎ 1979, 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, n^o 4,‎ 2004, 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 » (n^o 14), 1963
11. Jacobus Hendricus van Lint et Richard Michale Wilson, A Course in Combinatorics, 2001 (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, 2002 (1^re éd. 1998), 3252 p. (ISBN 1-58488-347-2), « Permanent »
13. Albert Nijenhuis et Herbert S. Wilf, Combinatorial Algorithms, Academic Press, 1978
14. (en) V.E. Tarakanov, « Permanent », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne).

Voir aussi

Immanant d'une matrice