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

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 vecteurs colonnes d'une matrice). Il existe pour le permanent des formules analogues à celles du déterminant : Le permanent de la transposée d'une matrice est égal au permanent de la matrice. 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-ème ligne et la j-ème colonne, alors . 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!/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').. . 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. Cet article a valu le prix Fulkerson en 2006 à Mark Jerrum, Alistair Sinclair et Eric Vigoda. Voir ..

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

La formule de Ryser peut être évaluée en opérations arithmétiques, ou en en traitant les ensembles 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, et également en théorie des graphes.

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

Il donne aussi un analogue au déterminant de Slater dans le cas d'un ensemble de bosons.

Notes et références

Voir aussi Immanant d'une matrice

Catégorie:Algèbre multilinéaire