Permanent

Imaginez deux personnes et deux tâches, avec un nombre dans chaque case pour indiquer la valeur d’une attribution. Une attribution complète donne une tâche différente à chaque personne. Pour chaque attribution possible, on multiplie les deux nombres choisis, puis on additionne les résultats.

Cette somme est le permanent de la matrice. Avec seulement des 0 et des 1, elle compte directement les façons de réaliser toutes les attributions autorisées.

Le permanent s’applique à une matrice carrée, c’est-à-dire ayant autant de lignes que de colonnes. Soit A une matrice de taille n : le symbole a_ij désigne l’entrée située à la ligne i et à la colonne j. Une permutation du nombre de colonnes attribue à chaque ligne une colonne distincte.

Pour chaque permutation notée sigma, on multiplie les n entrées sélectionnées, puis on additionne ces produits :

Ici, S_n est l’ensemble des permutations des n colonnes. Tous les produits sont ajoutés avec le signe plus. Le permanent n’est donc pas alternant : échanger deux lignes ne change pas sa valeur, tandis qu’une opération analogue change le signe du déterminant. Pour une matrice de 0 et de 1 décrivant les arêtes d’un graphe biparti, chaque produit égal à 1 correspond à un couplage parfait. Leur somme compte ces couplages. Le calcul direct examine n! permutations, ce qui rend le calcul général difficile quand la taille augmente.

Prenons une matrice carrée à deux lignes et deux colonnes. Ses quatre entrées valent 1. Les données sont donc a₁₁ = 1, a₁₂ = 1, a₂₁ = 1 et a₂₂ = 1.

1. La permutation qui conserve l’ordre des colonnes sélectionne a₁₁ et a₂₂.
2. Leur produit vaut 1 × 1 = 1.

3. La permutation qui échange les colonnes sélectionne a₁₂ et a₂₁.
4. Leur produit vaut aussi 1 × 1 = 1.

5. L’addition donne permanent = 1 + 1 = 2. Le graphe biparti associé relie chacune des deux lignes à chacune des deux colonnes. Il possède donc les deux couplages parfaits comptés par le permanent.

Le contrôle consiste à énumérer les attributions : ligne 1 avec colonne 1 et ligne 2 avec colonne 2, ou bien ligne 1 avec colonne 2 et ligne 2 avec colonne 1. Il y en a exactement deux.

Dans un problème d’affectation, une matrice de 0 et de 1 indique quelles associations sont autorisées. Le permanent donne le nombre d’affectations complètes. Si l’on cherche plutôt la meilleure affectation selon un coût, il faut employer une méthode d’optimisation, car le permanent ne choisit pas une solution.

Dans un graphe biparti, les lignes représentent les sommets d’un groupe et les colonnes ceux de l’autre. Une entrée égale à 1 signale une arête. Le permanent de cette matrice compte les couplages parfaits, c’est-à-dire ceux qui associent chaque sommet une seule fois.

Pour une petite matrice, on peut vérifier le résultat en listant toutes les permutations. Quand la taille augmente, cette énumération devient vite impraticable ; le calcul exact du permanent demande alors des méthodes spécialisées.

Permanent et déterminant. Les deux utilisent un produit par permutation, mais le déterminant affecte chaque produit du signe de la permutation. Pour la matrice 2 × 2 dont toutes les entrées valent 1, le permanent vaut 2 alors que le déterminant vaut 0.

Permanent et permutation. Une permutation est une seule manière d’attribuer les colonnes aux lignes. Le permanent est la somme des produits obtenus avec toutes ces manières ; ce n’est donc ni une permutation particulière ni leur simple nombre lorsque les entrées ne valent pas seulement 0 ou 1.

Matrice non carrée. La définition donnée ici exige autant de lignes que de colonnes. Si les deux groupes d’un problème d’affectation n’ont pas la même taille, il faut reformuler le problème ou compléter sa matrice avant d’appliquer cette définition.

Entrées autres que 0 ou 1. Le permanent reste une somme de produits, mais il ne compte plus directement des couplages. Le symptôme est qu’un produit peut porter un poids différent de 1 ; il faut alors interpréter le résultat comme une somme pondérée.

Annulations trompeuses. Avec des entrées négatives, certains termes de la somme peuvent être positifs ou négatifs et se compenser entre eux malgré l’absence des signes de permutation ; un produit individuel n’est nul que si l’un de ses facteurs est nul. Il ne faut donc pas conclure qu’un permanent nul signifie toujours qu’aucune sélection n’existe. Cette lecture de comptage vaut pour une matrice de 0 et de 1.

Explosion du calcul direct. Une matrice de taille n conduit à n! produits dans la définition. Dès que n augmente, les énumérer un à un devient le piège principal ; le calcul général du permanent est difficile du point de vue algorithmique.

Le graphe biparti donne une lecture visuelle des lignes, des colonnes et des couplages parfaits comptés par le permanent.

La signature d'une permutation précise le signe que le déterminant utilise et que le permanent omet.

L’analyse combinatoire replace les permutations et les dénombrements d’affectations dans leur cadre général.