Pfaffsche Determinante

Grundidee und Bedeutung

Die pfaffsche Determinante, geschrieben als Pf(A), ist ein Polynom, das zu einer alternierenden Matrix A gehört. Eine alternierende Matrix erfüllt aᵢᵢ = 0 und aᵢⱼ = −aⱼᵢ. Ihre gewöhnliche Determinante lässt sich stets als Quadrat der pfaffschen Determinante darstellen:

Pf(A)² = det(A).

Die pfaffsche Determinante kann nur bei alternierenden Matrizen gerader Größe 2n × 2n von null verschieden sein. Dann ist Pf(A) ein Polynom vom Grad n in den Matrixeinträgen. Für eine alternierende Matrix ungerader Größe wird die pfaffsche Determinante als null definiert.

Definition über Paarpartitionen

Sei Π die Menge aller Partitionen der Indexmenge {1, 2, …, 2n} in n Paare. Eine solche Partition heißt hier eine vollständige Aufteilung aller Indizes in Zweiergruppen. Es gibt (2n−1)!! solcher Partitionen; das Zeichen !! steht für die Doppelfakultät.

Jede Partition α ∈ Π kann eindeutig in der Form

α = {(i₁,j₁), (i₂,j₂), …, (iₙ,jₙ)}

geschrieben werden, wobei iₖ < jₖ und i₁ < i₂ < … < iₙ gilt. Aus der Reihenfolge

(1,2,3,4,…,2n) ↦ (i₁,j₁,i₂,j₂,…,iₙ,jₙ)

entsteht eine Permutation π. Ihr Signum sgn(α) ist +1 bei einer geraden und −1 bei einer ungeraden Anzahl von Vertauschungen.

Für eine alternierende Matrix A = (aᵢⱼ) setzt man für jede Partition

Aα = sgn(α) · aᵢ₁ⱼ₁ aᵢ₂ⱼ₂ ··· aᵢₙⱼₙ.

Die pfaffsche Determinante ist die Summe dieser Terme über alle Paarpartitionen:

Pf(A) = Σα∈Π Aα.

Eine gleichwertige Definition verwendet das Keilprodukt. Der Matrix A wird der Bivektor

ω = Σi<j aᵢⱼ eᵢ ∧ eⱼ

zugeordnet, wobei {e₁, e₂, …, e₂ₙ} die Standardbasis von ℝ²ⁿ ist. Dann ist Pf(A) durch

(1/n!) ωⁿ = Pf(A) · e₁ ∧ e₂ ∧ ··· ∧ e₂ₙ

bestimmt. Dabei ist ωⁿ das Keilprodukt von n Kopien von ω.

Beispiele und wichtige Rechenregeln

Für die alternierende 2 × 2-Matrix gilt unmittelbar:

Pf([[0,a], [−a,0]]) = a.

Bei einer alternierenden 4 × 4-Matrix erhält man:

Pf([[0,a,b,c], [−a,0,d,e], [−b,−d,0,f], [−c,−e,−f,0]]) = af − be + dc.

Für die im Artikel angegebene alternierende Bandmatrix mit den Einträgen λ₁, …, λₙ und ω₁, …, ωₙ₋₁ ist

Pf(A) = λ₁λ₂ ··· λₙ.

Für eine alternierende 2n × 2n-Matrix A, eine beliebige 2n × 2n-Matrix B und einen Skalar λ gelten folgende Eigenschaften:

• Pf(A)² = det(A).

• Pf(BABᵀ) = det(B) Pf(A).

• Pf(λA) = λⁿ Pf(A).

• Pf(Aᵀ) = (−1)ⁿ Pf(A).

Für eine blockdiagonale Matrix A₁ ⊕ A₂ = [[A₁,0], [0,A₂]] ist die pfaffsche Determinante das Produkt der pfaffschen Determinanten der Blöcke:

Pf(A₁ ⊕ A₂) = Pf(A₁) Pf(A₂).

Ist M eine beliebige n × n-Matrix, so gilt außerdem:

Pf([[0,M], [−Mᵀ,0]]) = (−1)ⁿ⁽ⁿ⁻¹⁾⁄² det(M).

Anwendungen

Die pfaffsche Determinante ist ein invariantes Polynom einer alternierenden Matrix. Sie bleibt allerdings nicht unter beliebigen Basiswechseln invariant, sondern nur unter orthogonalen Transformationen. In der Theorie der charakteristischen Klassen wird sie auch Euler-Polynom genannt. Mit ihr kann insbesondere die Eulerklasse einer riemannschen Mannigfaltigkeit definiert werden; diese kommt im Satz von Gauß-Bonnet vor.

Eine weitere Anwendung betrifft perfekte Paarungen in planaren Graphen. Eine perfekte Paarung ist eine Auswahl von Kanten, bei der jeder Knoten genau einmal beteiligt ist. Die Anzahl solcher Paarungen ist bei einem planaren Graphen gleich dem Absolutwert einer geeignet konstruierten pfaffschen Determinante. Da diese in polynomialer Zeit berechnet werden kann, erhält man einen effizienten Algorithmus. Für allgemeine Graphen ist das entsprechende Problem dagegen Sharp-P-vollständig und damit sehr schwer.

In der Physik wird dieses Verfahren verwendet, um die Zustandssumme des Ising-Modells von Spingläsern zu berechnen, wenn der zugrunde liegende Graph planar ist. Die pfaffsche Determinante wurde außerdem zur Entwicklung effizienter Algorithmen für andere scheinbar unlösbare Probleme eingesetzt, darunter die effiziente Simulation bestimmter Typen von Quantenberechnungen.