Today: Saturday 24 July 2021 , 4:19 am


advertisment
search




Permanent (mathématiques)

Dernière mise à jour 5 heure , 58 minute 13 Vues

Advertisement
In this page talks about ( Permanent (mathématiques) ) It was sent to us on 23/07/2021 and was presented on 23/07/2021 and the last update on this page on 23/07/2021

Votre commentaire


Entrez le code
 
Le permanent est un outil d'algèbre linéaire. Par définition, le permanent d'une matrice carrée A = (a_{ij) d'ordre n vaut :
\operatorname{per(A)=\sum_{\sigma\in \mathfrak{S_n\prod_{i=1^n a_{i,\sigma(i).
\mathfrak{S_n désigne le groupe symétrique d'indice n. Par exemple :
\operatorname{per\begin{pmatrixa&b\\c&d\end{pmatrix=ad+bc.

Lien avec le déterminant

La définition est très proche de celle du déterminant d'une matrice :
\operatorname{det(A) = \sum_{\sigma \in \mathfrak{S_n \varepsilon(\sigma) \prod_{i=1^n a_{i,\sigma(i)
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 \mathfrak{S_n dans un groupe abélien.

Propriétés

Similarités et différences avec le déterminant

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 A = (a_{ij), et A_{ij est la matrice obtenue à partir de A en supprimant la i-ième ligne et la j-ième colonne, alors {\rm per(A) = \sum_{i=1^n a_{ij{\rm per(A_{ij).
  3. Le permanent d'une matrice triangulaire par blocs A = \left(
\begin{matrix
A_1 & & & (0) \\
& A_2 & & \\
& & \cdot & \\
(*) & & & A_k \\
\end{matrix
\right) vaut {\rm per(A) = \prod_{i=1^k{\rm per(A_i).
Mais contrairement au déterminant, le permanent n'est pas multiplicatif.

Théorie des graphes

Le permanent de la matrice d'adjacence d'un graphe bipartit est égal au nombres de couplages de ce graphe.

Bornes et conjecture de van der Waerden

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
.. Des démonstrations de ce résultat ont été publiées, en 1980 par B. Gyires
., et en 1981 par G. P. Egorychev (en utilisant l' )
.
.
.
et D. I. Falikman .. Egorychev et Falikman ont remporté le prix Fulkerson en 1982 pour ces preuves ..

Aspects algorithmiques

Le permanent est beaucoup plus difficile à calculer que le déterminant. Il n'existe pas d'analogue de l'élimination de Gauss-Jordan pour les permanents. Plus précisément, le problème du calcul du permanent de matrice 0-1 peut être vu comme un problème de comptage et appartient à la classe des problèmes #P-complets .. Il peut être approché en temps polynomial par des algorithmes probabilistes dans le cas des matrices à coefficients positifs . Cet article a valu le prix Fulkerson en 2006 à Mark Jerrum, Alistair Sinclair et Eric Vigoda. Voir ..

Formule de Ryser

La formule de Ryser due à Herbert Ryser
, est un algorithme de calcul du permanent basé sur le principe d'inclusion-exclusion et qui peut être formulé comme suit : Pour une matrice A_k obtenue en supprimant k colonnes dans A, soit P(A_k) le produit des sommes des lignes de A_k. Soit \Sigma_k la somme des P(A_k) pour toutes les matrices A_k. Alors
\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 :
\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 O(2^{n-1n^2) operations artihmétiques, ou en O(2^{n-1n) se traitant les ensembles S dans l'ordre donné par le code de Gray .

Utilisation et applications

Contrairement au déterminant, le permanent n'a pas de signification géométrique naturelle. Il est utilisé en combinatoire, par exemple pour démontrer le lemme des mariages, et également en théorie des graphes.
Le permanent apparaît également en physique théorique, notamment pour l'étude de l'adsorption ( ), ainsi qu'en physique statistique, en cristallographie et en chimie physique ..

Notes et références


Voir aussi

Immanant d'une matrice
Catégorie:Algèbre multilinéaire
 
commentaires

Il n'y a pas encore de commentaires

vu pour la dernière fois
Most vists