Permanente
aus Wikipedia, der freien Enzyklopädie
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.
Inhaltsverzeichnis |
[Bearbeiten] Definition
Sei A eine (n,n)-Matrix, dann ist die Permanente 
definiert als
,
wobei sich die Summe über alle Elemente σ der Symmetrischen Gruppe Sn erstreckt.
Bis auf das fehlende Vorzeichen der einzelnen Summanden entspricht diese Definition derjenigen der Determinante.
[Bearbeiten] Anwendungen
Im Gegensatz zur Determinante ist keine einfache geometrische Interpretation möglich. Anwendungen finden sich hauptsächlich in der Kombinatorik, zum Beispiel bei der Berechnung von Paarungen bipartiter Graphen.
[Bearbeiten] Berechenbarkeit
Ein weiterer Unterschied zur Determinante besteht in der Berechnungs-Komplexität. Der polynomiale Algorithmus zur Berechnung der Determinante (siehe Gauss-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).
[Bearbeiten] Verallgemeinerung
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.
[Bearbeiten] Weblinks
- Eintrag bei Mathworld (englisch)
- Derangements revisited – Anwendung von Permanenten bei einem kombinatorischen Problem.
