Permanent (mathématiques)

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.