imported>Peter Gröbner: Änderung 257151713 von Schradri8 rückgängig gemacht; meines Erachtens sind die Informationen des Zielartikels der Verlinkung für das Verständnis des vorliegenden Artikels nicht hilfreich und allfälligen Lesern bekannt.

2025-06-18T19:36:16Z

Änderung 257151713 von Schradri8 rückgängig gemacht; meines Erachtens sind die Informationen des Zielartikels der Verlinkung für das Verständnis des vorliegenden Artikels nicht hilfreich und allfälligen Lesern bekannt.

Neue Seite

Die '''Permanente''' bezeichnet ein Objekt aus der [[lineare Algebra|linearen Algebra]]. Sie ist für [[Matrix (Mathematik)|Matrizen]] ähnlich der [[Determinante]] als ein Polynom in den Einträgen der Matrix definiert.

== Definition ==
Sei A eine <math>(n \times n)</math>-Matrix, dann ist die Permanente <math>\operatorname{perm}(A)</math> definiert als

:<math>\operatorname{perm}(A):=\sum_{\sigma \in S_n}\prod_{i=1}^n a_{i,\sigma(i)}</math>,

wobei sich die Summe über alle Elemente <math>\sigma</math> der [[Symmetrische Gruppe|symmetrischen Gruppe]] <math>S_n</math> erstreckt.

Bis auf das fehlende [[Vorzeichen (Zahl)|Vorzeichen]] der einzelnen Summanden entspricht diese Definition derjenigen der [[Determinante]].

== Anwendungen ==
Im Gegensatz zur Determinante ist keine einfache geometrische Interpretation bekannt. Anwendungen finden sich hauptsächlich in der [[Kombinatorik]], zum Beispiel bei der Berechnung von [[Paarung (Graphentheorie)|Paarungen]] [[Bipartiter Graph|bipartiter Graphen]]. Wenn auch selten genutzt, stellt sie in der Quantenmechanik das [[Boson|bosonische]] Gegenstück zur [[Fermion|fermionischen]] [[Slater-Determinante]] dar.

== Berechnungsaufwand ==
Ein weiterer Unterschied zur Determinante besteht in der Berechnungs-[[Komplexität]]. Der polynomiale Algorithmus zur Berechnung der Determinante (siehe [[Gaußsches Eliminationsverfahren|Gauß-Algorithmus]]) ist auf die Permanente nicht anwendbar. Aus einem Spezialfall für binäre Matrizen kann man schließen, dass ein polynomialer Algorithmus für die Permanente gleichbedeutend mit der Aussage [[FP (Komplexitätsklasse)|FP]] = [[Sharp-P|#P]] für Komplexitätsklassen wäre (eine stärkere Aussage als [[P (Komplexitätsklasse)|P]]=[[NP (Komplexitätsklasse)|NP]]).

== Eigenschaften ==
Die Permanente ist multilinear, vollsymmetrisch und normiert. Dabei wird eine quadratische Matrix spaltenweise als <math>A=(v_1,\ldots, v_n)</math> geschrieben:

* Sie ist ''multilinear'', d. h. linear in jeder Spalte:
:Für alle <math>v_1,\ldots,v_n,w \in V</math> gilt:
::<math>\begin{align}
&\operatorname{perm}(v_1,\ldots,v_{i-1},v_i+w,v_{i+1},\ldots,v_n)\\
&=\operatorname{perm}(v_1,\ldots,v_{i-1},v_i,v_{i+1},\ldots,v_n) + \operatorname{perm} (v_1,\ldots,v_{i-1},w,v_{i+1},\ldots,v_n)
\end{align}</math>
:Für alle <math> v_1,\ldots,v_n \in V</math> und alle <math> r \in K</math> gilt
::<math>\operatorname{perm}(v_1,\ldots,v_{i-1},r\cdot v_i,v_{i+1},\ldots,v_n) = r \cdot \operatorname{perm}(v_1,\ldots,v_{i-1},v_i,v_{i+1},\ldots,v_n)</math>
* Sie ist ''vollsymmetrisch'':
:Es ändert sich nichts, wenn man zwei Spalten vertauscht:
:Für alle <math>v_1,\ldots,v_n \in V</math> und alle <math>i, j \in \{1,\ldots,n\}, i\ne j</math> gilt:
::<math>\operatorname{perm}(v_1,\ldots,v_i,\ldots,v_j,\ldots,v_n) = \operatorname{perm}(v_1,\ldots,v_j,\ldots,v_i,\ldots,v_n)\,</math>
* Sie ist ''normiert'', d. h. die [[Einheitsmatrix]] hat die Permanente 1:
:<math>\operatorname{perm}(E_n)=1</math>

== Verallgemeinerung ==
Wie auch bei der Determinante handelt es sich bei der Permanente um einen Spezialfall einer [[Immanente]]. Für einen komplexen [[Charakter (Mathematik)|Charakter]] <math>\chi: S_n\rightarrow\mathbb{C}</math> der symmetrischen Gruppe ist diese definiert als

:<math>\operatorname{imm}_\chi(A):=\sum_{\sigma\in S_n}\chi(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}.</math>

Die Permanente ergibt sich durch Wahl des trivialen Charakters, die Determinante durch Wahl der [[Vorzeichen (Permutation)|Signumfunktion]]; dabei sind diese beiden Möglichkeiten insofern speziell, als dass sie die einzigen eindimensionalen [[Darstellung (Gruppe)|Darstellungen]] der symmetrischen Gruppe sind.

== Weblinks ==
* [https://mathworld.wolfram.com/Permanent.html Eintrag bei Mathworld] (englisch)
* [https://matheplanet.com/default3.html?article=444 Derangements revisited] – Anwendung von Permanenten bei einem kombinatorischen Problem.

[[Kategorie:Lineare Algebra]]

Permanente - Versionsgeschichte

imported>Peter Gröbner: Änderung 257151713 von Schradri8 rückgängig gemacht; meines Erachtens sind die Informationen des Zielartikels der Verlinkung für das Verständnis des vorliegenden Artikels nicht hilfreich und allfälligen Lesern bekannt.