Permanente

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 (n,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[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 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).

Eigenschaften[Bearbeiten]

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{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) + \det (v_1,\ldots,v_{i-1},w,v_{i+1},\ldots,v_n)
\end{align}
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\ne 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)\,
\operatorname{perm}(E_n)=1

Verallgemeinerung[Bearbeiten]

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[Bearbeiten]