Die Permanente bezeichnet ein Objekt aus der linearen Algebra. Sie ist für Matrizen ähnlich der Determinante als ein Polynom in den Einträgen der Matrix definiert.

Definition

Bearbeiten

Sei A eine  -Matrix, dann ist die Permanente   definiert als

 ,

wobei sich die Summe über alle Elemente   der symmetrischen Gruppe   erstreckt.

Bis auf das fehlende Vorzeichen der einzelnen Summanden entspricht diese Definition derjenigen der Determinante.

Anwendungen

Bearbeiten

Im Gegensatz zur Determinante ist keine einfache geometrische Interpretation bekannt. Anwendungen finden sich hauptsächlich in der Kombinatorik, zum Beispiel bei der Berechnung von Paarungen bipartiter Graphen. Wenn auch selten genutzt, stellt sie in der Quantenmechanik das bosonische Gegenstück zur fermionischen Slater-Determinante dar.

Berechnungsaufwand

Bearbeiten

Ein weiterer Unterschied zur Determinante besteht in der Berechnungs-Komplexität. Der polynomiale Algorithmus zur Berechnung der Determinante (siehe 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 = #P für Komplexitätsklassen wäre (eine stärkere Aussage als P=NP).

Eigenschaften

Bearbeiten

Die Permanente ist multilinear, vollsymmetrisch und normiert. Dabei wird eine quadratische Matrix spaltenweise als   geschrieben:

  • Sie ist multilinear, d. h. linear in jeder Spalte:
Für alle   gilt:
 
Für alle   und alle   gilt
 
  • Sie ist vollsymmetrisch:
Es ändert sich nichts, wenn man zwei Spalten vertauscht:
Für alle   und alle   gilt:
 
 

Verallgemeinerung

Bearbeiten

Wie auch bei der Determinante handelt es sich bei der Permanente um einen Spezialfall einer Immanente. Für einen komplexen Charakter   der symmetrischen Gruppe ist diese definiert als

 

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

Bearbeiten