Pfaffian

In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries. This polynomial is called the Pfaffian of the matrix. The Pfaffian is nonvanishing only for 2n × 2n skew-symmetric matrices, in which case it is a polynomial of degree n.

Examples

{\mbox{Pf}}{\begin{bmatrix}0&a\\-a&0\end{bmatrix}}=a.

{\mbox{Pf}}{\begin{bmatrix}0&a&b&c\\-a&0&d&e\\-b&-d&0&f\\-c&-e&-f&0\end{bmatrix}}=af-be+dc.

{\mbox{Pf}}{\begin{bmatrix}{\begin{matrix}0&\lambda _{1}\\-\lambda _{1}&0\end{matrix}}&0&\cdots &0\\0&{\begin{matrix}0&\lambda _{2}\\-\lambda _{2}&0\end{matrix}}&&0\\\vdots &&\ddots &\vdots \\0&0&\cdots &{\begin{matrix}0&\lambda _{n}\\-\lambda _{n}&0\end{matrix}}\end{bmatrix}}=\lambda _{1}\lambda _{2}\cdots \lambda _{n}.

Formal definition

Let A = {a_i,j} be a 2n×2n skew-symmetric matrix. The Pfaffian of A is defined by the equation

\mathrm {Pf} (A)={\frac {1}{2^{n}n!}}\sum _{\sigma \in S_{2n}}\mathrm {sgn} (\sigma )\prod _{i=1}^{n}a_{\sigma (2i-1),\sigma (2i)}

where S_2n is the symmetric group and sgn(σ) is the signature of σ.

One can make use of the skew-symmetry of A to avoid summing over all possible permutations. Let Π be the set of all partitions of {1, 2, …, 2n} into pairs without regard to order. There are (2n − 1)!! such partitions. An element α ∈ Π, can be written as

\alpha =\{(i_{1},j_{1}),(i_{2},j_{2}),\cdots ,(i_{n},j_{n})\}

with i_k < j_k and $i_{1}<i_{2}<\cdots <i_{n}$ . Let

\pi ={\begin{bmatrix}1&2&3&4&\cdots &2n\\i_{1}&j_{1}&i_{2}&j_{2}&\cdots &j_{n}\end{bmatrix}}

be a corresponding permutation. This depends only on the partition α and not on the particular choice of π. Given a partition α as above define

A_{\alpha }=\operatorname {sgn} (\pi )a_{i_{1},j_{1}}a_{i_{2},j_{2}}\cdots a_{i_{n},j_{n}}.

The Pfaffian of A is then given by

\operatorname {Pf} (A)=\sum _{\alpha \in \Pi }A_{\alpha }.

The Pfaffian of a n×n skew-symmetric matrix for n odd is defined to be zero.

Alternative definition

One can associate to any skew-symmetric 2n×2n matrix A ={a_ij} a bivector

\omega =\sum _{i<j}a_{ij}\;e^{i}\wedge e^{j}.

where {e¹, e², …, e²ⁿ} is the standard basis of R²ⁿ. The Pfaffian is then defined by the equation

{\frac {1}{n!}}\omega ^{n}={\mbox{Pf}}(A)\;e^{1}\wedge e^{2}\wedge \cdots \wedge e^{2n},

here ωⁿ denotes the wedge product of n copies of ω with itself.

Identities

For a 2n × 2n skew-symmetric matrix A and an arbitrary 2n × 2n matrix B,

${\mbox{Pf}}(A)^{2}=\det(A)$

${\mbox{Pf}}(BAB^{T})=\det(B){\mbox{Pf}}(A)$

${\mbox{Pf}}(\lambda A)=\lambda ^{n}{\mbox{Pf}}(A)$

${\mbox{Pf}}(A^{T})=(-1)^{n}{\mbox{Pf}}(A)$

For a block-diagonal matrix

A_{1}\oplus A_{2}={\begin{bmatrix}A_{1}&0\\0&A_{2}\end{bmatrix}}

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

For an arbitrary n × n matrix M:

{\mbox{Pf}}{\begin{bmatrix}0&M\\-M^{T}&0\end{bmatrix}}=(-1)^{n(n-1)/2}\det M.

Applications

The Pfaffian is an invariant polynomial of a skew-symmetric matrix (note that it is not invariant under a general change of basis but rather under a proper orthogonal transformation). As such, it is important in the theory of characteristic classes. In particular, it can be used to define the Euler class of a Riemannian manifold which is used in the generalized Gauss-Bonnet theorem.

The number of perfect matchings in a planar graph turns out to be the absolute value of a Pfaffian, hence is polynomial time computable. This is surprising given that for a general graph, the problem is very difficult (so called #P-complete). This result is used in physics to calculate the partition function of Ising models of spin glasses, where the underlying graph is planar. Recently it is also used to derive efficient algorithms for some otherwise seemingly intractable problems, including the efficient simulation of certain types of restricted quantum computation.

History

The term Pfaffian was introduced by Arthur Cayley, who used the term in 1852: "The permutants of this class (from their connection with the researches of Pfaff on differential equations) I shall term Pfaffians." The term honors German mathematician Johann Friedrich Pfaff.

External link