Permanent (mathématiques)

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 :

1. Le permanent de la transposée d'une matrice est égal au permanent de la matrice.
2. Il existe une formule similaire de développement d'un permanent le long d'une colonne : si ${\displaystyle A=(a_{ij})}$, et ${\displaystyle A_{ij}}$ est la matrice obtenue à partir de A en supprimant la i-ième ligne et la j-ième colonne, alors ${\displaystyle {\rm {per}}(A)=\sum _{i=1}^{n}a_{ij}{\rm {per}}(A_{ij})}$.
3. Le permanent d'une matrice triangulaire par blocs ${\displaystyle A=\left({\begin{matrix}A_{1}&&&(0)\\&A_{2}&&\\&&\cdot &\\(*)&&&A_{k}\\\end{matrix}}\right)}$ vaut ${\displaystyle {\rm {per}}(A)=\prod _{i=1}^{k}{\rm {per}}(A_{i})}$.

Mais contrairement au déterminant, le permanent n'est pas multiplicatif.

Une matrice booléenne carrée ${\displaystyle n\times n}$, ${\displaystyle A=(a_{ij})}$ peut être comprise comme la matrice d'adjacence d'un graphe biparti dont les sommets seraient ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ d'une part et ${\displaystyle y_{1},y_{2},\dots ,y_{n}}$ de l'autre, où ${\displaystyle a_{ij}}$ vaut 1 s'il existe un lien entre le sommet ${\displaystyle x_{i}}$ et le sommet ${\displaystyle y_{j}}$ 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 ${\displaystyle \sigma }$ des sommets telle que ${\displaystyle \prod _{i=1}^{n}a_{i,\sigma (i)}=1}$. On peut donc interpréter le permanent de A comme le nombre de couplages parfaits du graphe biparti associé à la matrice carrée ${\displaystyle A}$.

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[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].

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 ${\displaystyle A_{k}}$ obtenue en supprimant ${\displaystyle k}$ colonnes dans ${\displaystyle A}$, soit ${\displaystyle P(A_{k})}$ le produit des sommes des lignes de ${\displaystyle A_{k}}$. Soit ${\displaystyle \Sigma _{k}}$ la somme des ${\displaystyle P(A_{k})}$ pour toutes les matrices ${\displaystyle A_{k}}$. Alors

${\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{n-1}(-1)^{k}\Sigma _{k}}$.

On peut réécrire la formule en fonction des entrées de la matrice comme suit[12] :

${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$

La formule de Ryser peut être évaluée en ${\displaystyle O(2^{n-1}n^{2})}$ operations artihmétiques, ou en ${\displaystyle O(2^{n-1}n)}$ se traitant les ensembles ${\displaystyle S}$ dans l'ordre donné par le code de Gray [13].