Permanente

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

Sei A eine $(n\times n)$-Matrix, dann ist die Permanente $\operatorname {perm} (A)$ definiert als

$\operatorname {perm} (A):=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}$,

wobei sich die Summe über alle Elemente $\sigma$ der symmetrischen Gruppe $S_{n}$ erstreckt.

Bis auf das fehlende 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 Paarungen bipartiter Graphen. Wenn auch selten genutzt, stellt sie in der Quantenmechanik das bosonische Gegenstück zur 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ß-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

Die Permanente ist multilinear, vollsymmetrisch und normiert. Dabei wird eine quadratische Matrix spaltenweise als $A=(v_{1},\ldots ,v_{n})$ geschrieben:

• Sie ist multilinear, d. h. linear in jeder Spalte:

Für alle $v_{1},\ldots ,v_{n},w\in V$ gilt:

${\begin{aligned}&\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{aligned}}$

Für alle $v_{1},\ldots ,v_{n}\in V$ und alle $r\in K$ gilt

$\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})$

• Sie ist vollsymmetrisch:

Es ändert sich nichts, wenn man zwei Spalten vertauscht:

Für alle $v_{1},\ldots ,v_{n}\in V$ und alle $i,j\in \{1,\ldots ,n\},i\neq j$ gilt:

$\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})\,$

• Sie ist normiert, d. h. die Einheitsmatrix hat die Permanente 1:

$\operatorname {perm} (E_{n})=1$

Verallgemeinerung

Wie auch bei der Determinante handelt es sich bei der Permanente um einen Spezialfall einer Immanente. Für einen komplexen Charakter $\chi :S_{n}\rightarrow \mathbb {C}$ der symmetrischen Gruppe ist diese definiert als

$\operatorname {imm} _{\chi }(A):=\sum _{\sigma \in S_{n}}\chi (\sigma )\prod _{i=1}^{n}a_{i,\sigma (i)}.$

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.

Weblinks

• Eintrag bei Mathworld (englisch)
• Derangements revisited – Anwendung von Permanenten bei einem kombinatorischen Problem.