1 Permanent (mathématiques)[modifier]

Le permanent est une fonction mathématique utilisée principalement en algèbre linéaire et en combinatoire, proche du déterminant d'une matrice carrée, mais avec des propriétés et des applications distinctes. Il joue un rôle clé dans divers domaines comme la théorie des matrices, la physique mathématique, et l'informatique théorique.

1.1 Définition du permanent d'une matrice carrée[modifier]

Soit une matrice carrée $ A = [a_{i,j}] $ d'ordre $ n $ avec des coefficients dans un anneau commutatif. Le permanent de $ A $, noté Modèle:Math, est défini par la formule :

$per (A) = \sum_{σ \in S_{n}} \prod_{i = 1}^{n} a_{i, σ (i)}$

où $ S_n $ est le groupe des permutations de l'ensemble $\{1, 2, \ldots, n\}$.

Contrairement au déterminant, le permanent ne comporte pas de signe lié à la parité de la permutation.

1.2 Propriétés principales du permanent[modifier]

Similitude avec le déterminant: Le permanent ressemble au déterminant mais sans le facteur de signe.
Non-linéarité par rapport aux opérations élémentaires: Le calcul du permanent n'est pas affecté par les mêmes règles que celles du déterminant (ex. échange de lignes ne change pas le permanent).
Croissance combinatoire rapide: Le temps de calcul du permanent explose exponentiellement avec la taille de la matrice.

1.2.1 Invariance et symétries[modifier]

Le permanent est invariant par permutation simultanée des lignes ou colonnes.
Il est symétrique par rapport à la transposition : Modèle:Math.

1.3 Calcul et complexité algorithmique[modifier]

Le calcul direct du permanent utilise la définition combinatoire, impliquant une somme sur $ n! $ permutations, ce qui est rapidement prohibitif dès que $ n $ croît.

Complexité:

Le calcul du permanent est un problème #P-complet, ce qui signifie qu'il est considéré comme au moins aussi difficile que les problèmes NP-complets en complexité informatique.

1.3.1 Algorithmes exacts[modifier]

Algorithme de Ryser : un algorithme plus efficace (mais toujours exponentiel) basé sur la formule d'inclusion-exclusion.
Algorithme de Glynn : une amélioration des algorithmes par des techniques combinatoires.

1.3.2 Approximations et cas particuliers[modifier]

Pour les matrices à coefficients positifs, il existe des algorithmes d'approximation polynomiale probabiliste.
Pour certaines classes de matrices (ex. matrices de rang 1, matrices diagonales), le permanent est trivial à calculer.

1.4 Applications du permanent[modifier]

Combinatoire: Comptage de configurations, de placements non-interférents, nombres de couplages parfaits dans un graphe biparti.
Physique quantique: Étude des états bosoniques et dans l’optique quantique, notamment dans le cadre du boson sampling.
Théorie des graphes: Calcul du nombre de couplages parfaits comme nombre de permanents de la matrice d'adjacence.
Informatique théorique: Complexité de calcul, cryptographie et théorie algorithmique.

1.5 Exemple simple[modifier]

Soit $ A = \begin{pmatrix}1 & 2\\ 3 & 4\end{pmatrix} $, alors :

$per (A) = a_{1, 1} a_{2, 2} + a_{1, 2} a_{2, 1} = (1) (4) + (2) (3) = 4 + 6 = 10$

À noter que le déterminant est : $ \det(A) = 1 \times 4 - 2 \times 3 = -2 $, illustrant la différence fondamentale entre les deux.

1.6 Voir aussi[modifier]

1.7 Références[modifier]

Erreur de référence : La balise <ref> définie dans <references> n’a pas d’attribut de nom.

1.8 Liens externes[modifier]