Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Permanent (mathématiques)
Résumé
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 :
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-ième ligne et la j-ième colonne, alors .
Le permanent d'une matrice triangulaire par blocs vaut .
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!/n, valeur atteinte par la matrice ne contenant que des 1/n.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.