Loading AI tools
De Wikipédia, l'encyclopédie libre
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 :
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.
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 :
Mais contrairement au déterminant, le permanent n'est pas multiplicatif.
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é.
En 1926, van der Waerden conjectura que le permanent d'une matrice bistochastique de dimension n est supérieur à n!/nn, 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].
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].
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 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[12] :
La formule de Ryser peut être évaluée en operations artihmétiques, ou en se traitant les ensembles dans l'ordre donné par le code de Gray [13].
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.