Permanent (mathématiques)

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

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

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 $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 triangulaire 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.

Lien avec la théorie des graphes

Une matrice booléenne carrée $n\times n$, $A=(a_{ij})$ peut être comprise comme la matrice d'adjacence d'un graphe biparti dont les sommets seraient $x_{1},x_{2},\dots ,x_{n}$ d'une part et $y_{1},y_{2},\dots ,y_{n}$ de l'autre, où $a_{ij}$ vaut 1 s'il existe un lien entre le sommet $x_{i}$ et le sommet $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 $\sigma$ des sommets telle que $\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 $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. Des démonstrations de ce résultat ont été publiées, en 1980 par B. Gyires, et en 1981 par G. P. Egorychev (en utilisant l'inégalité d'Alexandrov-Fenchel (en)) et D. I. Falikman. Egorychev et Falikman ont remporté le prix Fulkerson en 1982 pour ces preuves.

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. Il peut être approché en temps polynomial par des algorithmes probabilistes dans le cas des matrices à coefficients positifs.

Formule de Ryser

La formule de Ryser, due à Herbert Ryser, est un algorithme de calcul du permanent basé sur le principe d'inclusion-exclusion et qui peut être formulé comme suit : Pour une matrice $A_{k}$ obtenue en supprimant $k$ colonnes dans $A$, soit $P(A_{k})$ le produit des sommes des lignes de $A_{k}$. Soit $\Sigma _{k}$ la somme des $P(A_{k})$ pour toutes les matrices $A_{k}$. Alors

$\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 :

$\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 $O(2^{n-1}n^{2})$ operations artihmétiques, ou en $O(2^{n-1}n)$ se traitant les ensembles $S$ dans l'ordre donné par le code de Gray .

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.

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).

Voir aussi

Immanant d'une matrice