Inmathematics, thedeterminant of anm-by-mskew-symmetric matrix can always be written as the square of apolynomial in thematrix entries, a polynomial withinteger coefficients that only depends onm. Whenm isodd, the polynomial is zero, and whenm iseven, it is a nonzero polynomial ofdegreem/2, and is unique up to multiplication by ±1. The convention on skew-symmetric tridiagonal matrices, given below in the examples, then determines one specific polynomial, called thePfaffian polynomial. The value of this polynomial, when applied to the entries of a skew-symmetric matrix, is called thePfaffian of that matrix. The term Pfaffian was introduced byCayley (1852), who indirectly named them afterJohann Friedrich Pfaff.

Explicitly, for a skew-symmetric matrix${\displaystyle A}$,

${\displaystyle \mathrm{pf}(A{)}^2=det(A),}$

which was firstproved byCayley (1849), who citesJacobi for introducing these polynomials in work onPfaffiansystems of differential equations. Cayley obtains this relation by specialising a more general result on matrices that deviate from skew symmetry only in the first row and the first column. The determinant of such a matrix is the product of the Pfaffians of the two matrices obtained by first setting in the original matrix the upper left entry to zero and then copying, respectively, the negativetranspose of the first row to the first column and the negative transpose of the first column to the first row. This is proved byinduction by expanding the determinant onminors and employing the recursion formula below.

(3 is odd, so the Pfaffian of B is 0)

The Pfaffian of a 2n × 2n skew-symmetrictridiagonal matrix is given as

(Note that any skew-symmetric matrix can be reduced to this form; seeSpectral theory of a skew-symmetric matrix.)

LetA = (a_ij) be a 2n × 2n skew-symmetric matrix. The Pfaffian ofA is explicitly defined by the formula

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

whereS_2n is thesymmetric group of degree 2n and sgn(σ) is thesignature of σ.

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

${\displaystyle \alpha =\{(i_1,j_1),(i_2,j_2),\cdots ,(i_n,j_n)\}}$

withi_k <j_k and. Let

be the corresponding permutation. Given a partition α as above, define

${\displaystyle A_{\alpha }=\mathrm{sgn}({\pi }_{\alpha })a_{i_1,j_1}{a}_{i_2,j_2}\cdots a_{i_n,j_n}.}$

The Pfaffian ofA is then given by

${\displaystyle \mathrm{pf}(A)=\sum _{\alpha \in \mathrm{\Pi }}{A}_{\alpha }.}$

The Pfaffian of an ×n skew-symmetric matrix forn odd is defined to be zero, as the determinant of an odd skew-symmetric matrix is zero, since for a skew-symmetric matrix,$${\displaystyle detA=det{A}^{\text{T}}=det(-A)=(-1{)}^{n}detA,}$$and forn odd, this implies${\displaystyle detA=0}$.

By convention, the Pfaffian of the 0 × 0 matrix is equal to one. The Pfaffian of a skew-symmetric 2n × 2n matrixA withn > 0 can be computed recursively as

${\displaystyle \mathrm{pf}(A)=\sum _{\genfrac{}{}{0ex}{}{j=1}{j\ne i}}^{2n}(-1{)}^{i+j+1+\theta (i-j)}{a}_{ij}\mathrm{pf}(A_{\hat{ı}\hat{ȷ}}),}$

where the indexi can be selected arbitrarily,${\displaystyle \theta (i-j)}$ is theHeaviside step function, and${\displaystyle A_{\hat{ı}\hat{ȷ}}}$ denotes the matrixA with both thei-th andj-th rows and columns removed.^[1] Note how for the special choice${\displaystyle i=1}$ this reduces to the simpler expression:

${\displaystyle \mathrm{pf}(A)=\sum _{j=2}^{2n}(-1{)}^j{a}_{1j}\mathrm{pf}(A_{\hat{1}\hat{ȷ}}).}$

One can associate to any skew-symmetric 2n × 2n matrixA = (a_ij) abivector

where {e₁,e₂, ...,e_2n} is thestandard basis ofR²ⁿ. The Pfaffian is then defined by the equation

${\displaystyle \frac{1}{n!}{\omega }^n=\mathrm{pf}(A)e_1\wedge e_2\wedge \cdots \wedge e_{2n},}$

hereωⁿ denotes thewedge product ofn copies ofω.

Equivalently, we can consider the bivector (which is more convenient when we do not want to impose the summation constraint):$${\displaystyle {\omega }^{\prime }=2\omega =\sum _{i,j}{a}_{ij}{e}_i\wedge e_j,}$$which gives${\displaystyle {\omega }^{\prime n}=2^{n}n!\mathrm{pf}(A)e_1\wedge e_2\wedge \cdots \wedge e_{2n}.}$

A non-zero generalisation of the Pfaffian to odd-dimensional matrices is given in the work of de Bruijn on multiple integrals involving determinants.^[2] In particular for anym × m matrixA, we use the formal definition above but set${\displaystyle n=\lfloor m/2\rfloor }$. Form odd, one can then show that this is equal to the usual Pfaffian of an (m+1) × (m+1)-dimensional skew symmetric matrix where we have added an (m+1)th column consisting ofm elements 1, an (m+1)th row consisting ofm elements −1, and the corner element is zero. The usual properties of Pfaffians, for example the relation to the determinant, then apply to this extended matrix.

Pfaffians have the following properties, which are similar to those of determinants.

• Multiplication of a row and a column by a constant is equivalent to multiplication of the Pfaffian by the same constant.
• Simultaneous interchange of two different rows and corresponding columns changes the sign of the Pfaffian.
• A multiple of a row and corresponding column added to another row and corresponding column does not change the value of the Pfaffian.

Using these properties, Pfaffians can be computed quickly, akin to the computation of determinants.

For a 2n × 2n skew-symmetric matrixA

${\displaystyle \mathrm{pf}(A^{\text{T}})=(-1{)}^n\mathrm{pf}(A).}$

${\displaystyle \mathrm{pf}(\lambda A)={\lambda }^n\mathrm{pf}(A).}$

${\displaystyle \mathrm{pf}(A{)}^2=det(A).}$

For an arbitrary 2n × 2n matrixB,

${\displaystyle \mathrm{pf}(BA{B}^{\text{T}})=det(B)\mathrm{pf}(A).}$

Substituting in this equationB = A^m, one gets for all integerm

${\displaystyle \mathrm{pf}(A^{2m+1})=(-1{)}^{nm}\mathrm{pf}(A{)}^{2m+1}.}$

Proof of${\displaystyle \mathrm{pf}(BA{B}^{\text{T}})=det(B)\mathrm{pf}(A)}$:

As previously said,${\displaystyle A\to \sum _{ij}{A}_{ij}{e}_i\wedge e_j\underset{}{\overset{\wedge n}{\to }}{2}^{n}n!Pf(A)e_1\wedge \cdots \wedge e_{2n}.}$ The same with${\displaystyle BA{B}^{\mathrm{T}}}$:where we defined${\displaystyle f_k=\sum _i{B}_{ik}{e}_i}$.

Since${\displaystyle f_1\wedge \cdots \wedge f_{2n}=det(B)e_1\wedge \cdots \wedge e_{2n},}$ the proof is finished.

Proof of${\displaystyle \mathrm{pf}(A{)}^2=det(A)}$:

Since${\displaystyle \mathrm{pf}(A{)}^2=det(A)}$ is an equation of polynomials, it suffices to prove it for real matrices, and it would automatically apply forcomplex matrices as well.

By thespectral theory of skew-symmetric real matrices,${\displaystyle A=Q\mathrm{\Sigma }{Q}^{\mathrm{T}}}$, where${\displaystyle Q}$ isorthogonal andfor real numbers${\displaystyle a_k}$. Now apply the previous theorem, we have${\displaystyle pf(A{)}^2=pf(\mathrm{\Sigma }{)}^{2}det(Q{)}^2=pf(\mathrm{\Sigma }{)}^2={\left(\prod a_i\right)}^2=det(A)}$.

IfA depends on some variablex_i, then the gradient of a Pfaffian is given by

${\displaystyle \frac{1}{\mathrm{pf}(A)}\frac{\mathrm{\partial }\mathrm{pf}(A)}{\mathrm{\partial }{x}_i}=\frac{1}{2}\mathrm{tr}\left(A^{-1}\frac{\mathrm{\partial }A}{\mathrm{\partial }{x}_i}\right),}$

and theHessian of a Pfaffian is given by

${\displaystyle \frac{1}{\mathrm{pf}(A)}\frac{{\mathrm{\partial }}^2\mathrm{pf}(A)}{\mathrm{\partial }{x}_i\mathrm{\partial }{x}_j}=\frac{1}{2}\mathrm{tr}\left(A^{-1}\frac{{\mathrm{\partial }}^{2}A}{\mathrm{\partial }{x}_i\mathrm{\partial }{x}_j}\right)-\frac{1}{2}\mathrm{tr}\left(A^{-1}\frac{\mathrm{\partial }A}{\mathrm{\partial }{x}_i}{A}^{-1}\frac{\mathrm{\partial }A}{\mathrm{\partial }{x}_j}\right)+\frac{1}{4}\mathrm{tr}\left(A^{-1}\frac{\mathrm{\partial }A}{\mathrm{\partial }{x}_i}\right)\mathrm{tr}\left(A^{-1}\frac{\mathrm{\partial }A}{\mathrm{\partial }{x}_j}\right).}$

The following formula applies even if the matrix${\displaystyle A}$ is singular for some values of the variable${\displaystyle x}$:

where${\displaystyle A_{\hat{i}\hat{j}}}$ is the${\displaystyle (2n-2)\times (2n-2)}$ skew-symmetric matrix obtained from${\displaystyle A}$ by deleting rows and columns${\displaystyle (i,j)}$.

The product of the Pfaffians of skew-symmetric matricesA andB can be represented in the form of an exponential

${\displaystyle \text{pf}(A)\text{pf}(B)=\exp (\frac{1}{2}\mathrm{t}\mathrm{r}\log (A^{\text{T}}B)).}$

SupposeA andB are 2n × 2n skew-symmetric matrices, then

${\displaystyle \mathrm{p}\mathrm{f}(A)\mathrm{p}\mathrm{f}(B)=\frac{1}{n!}{B}_n(s_1,s_2,\dots ,s_n),\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}{s}_l=-\frac{1}{2}(l-1)!\mathrm{t}\mathrm{r}((AB{)}^l)}$

andB_n(s₁,s₂,...,s_n) areBell polynomials.

For a block-diagonal matrix

${\displaystyle \mathrm{pf}(A_1\oplus A_2)=\mathrm{pf}(A_1)\mathrm{pf}(A_2).}$

For an arbitraryn ×n matrixM:

It is often required to compute the Pfaffian of a skew-symmetric matrix${\displaystyle S}$ with the block structure

where${\displaystyle M}$ and${\displaystyle N}$ are skew-symmetric matrices and${\displaystyle Q}$ is a general rectangular matrix.

When${\displaystyle M}$ isinvertible, one has

${\displaystyle \mathrm{pf}(S)=\mathrm{pf}(M)\mathrm{pf}(N+Q^{\mathrm{T}}{M}^{-1}Q).}$

This can be seen from Aitken block-diagonalization formula,^[3][4][5]

This decomposition involves acongruence transformations that allow to use the Pfaffian property${\displaystyle \mathrm{pf}(BA{B}^{\mathrm{T}})=\det (B)\mathrm{pf}(A)}$.

Similarly, when${\displaystyle N}$ is invertible, one has

${\displaystyle \mathrm{pf}(S)=\mathrm{pf}(N)\mathrm{pf}(M+Q{N}^{-1}{Q}^{\mathrm{T}}),}$

as can be seen by employing the decomposition

SupposeA is a2n × 2n skew-symmetric matrices, then

${\displaystyle \text{pf}(A)=i^{(n^2)}\exp \left(\frac{1}{2}\mathrm{t}\mathrm{r}\log (({\sigma }_y\otimes I_n{)}^{\mathrm{T}}\cdot A)\right),}$

where${\displaystyle {\sigma }_y}$ is the secondPauli matrix,${\displaystyle I_n}$ is anidentity matrix of dimensionn and we took the trace over amatrix logarithm.

This equality is based on thetrace identity

${\displaystyle \text{pf}(A)\text{pf}(B)=\exp \left(\frac{1}{2}\mathrm{t}\mathrm{r}\log (A^{\text{T}}B)\right)}$

and on the observation that${\displaystyle \text{pf}({\sigma }_y\otimes I_n)=(-i{)}^{n^2}}$.

Since calculating thelogarithm of a matrix is a computationally demanding task, one can instead compute alleigenvalues of${\displaystyle (({\sigma }_y\otimes I_n{)}^{\mathrm{T}}\cdot A)}$, take the log of all of these and sum them up. This procedure merely exploits theproperty${\displaystyle \mathrm{tr}\log (AB)=\mathrm{tr}\log (A)+\mathrm{tr}\log (B)}$. This can be implemented inMathematica with a single statement:

Pf[x_] := Module[{n = Dimensions[x][[1]] / 2}, I^(n^2) Exp[ 1/2 Total[ Log[Eigenvalues[ Dot[Transpose[KroneckerProduct[PauliMatrix[2], IdentityMatrix[n]]], x] ]]]]]

However, this algorithm is unstable when the Pfaffian is large. The eigenvalues of${\displaystyle ({\sigma }_y\otimes I_n{)}^{\mathrm{T}}\cdot A}$ will generally be complex, and the logarithm of these complex eigenvalues are generally taken to be in${\displaystyle [-\pi ,\pi ]}$. Under the summation, for a real valued Pfaffian, the argument of the exponential will be given in the form${\displaystyle x+k\pi /2}$ for some integer${\displaystyle k}$. When${\displaystyle x}$ is very large, rounding errors in computing the resulting sign from the complex phase can lead to a non-zero imaginary component.

For other (more) efficient algorithms seeWimmer 2012.

• There exist programs for the numerical computation of the Pfaffian on various platforms (Python,Matlab, Mathematica) (Wimmer 2012).
• The Pfaffian is aninvariant polynomial of a skew-symmetric matrix under a properorthogonalchange of basis. As such, it is important in the theory ofcharacteristic classes. In particular, it can be used to define theEuler class of aRiemannian manifold that is used in thegeneralized Gauss–Bonnet theorem.
• The number ofperfect matchings in aplanar graph is given by a Pfaffian, hence ispolynomial time computable via theFKT algorithm. This is surprising given that for general graphs, the problem is very difficult (so called#P-complete). This result is used to calculate the number ofdomino tilings of a rectangle, thepartition function ofIsing models in physics, or ofMarkov random fields inmachine learning (Globerson & Jaakkola 2007;Schraudolph & Kamenetsky 2009), where the underlying graph is planar. It is also used to derive efficient algorithms for some otherwise seemingly intractable problems, including the efficient simulation of certain types ofrestricted quantum computation. SeeHolographic algorithm for more information.

• Determinant
• Dimer model
• Hafnian
• Polyomino
• Statistical mechanics

• Determinants
• Multilinear algebra

• CS1 maint: archived copy as title
• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata