# Pfaffian

In

mathematics , thedeterminant of askew-symmetric matrix can always be written as the square of apolynomial in the matrix entries. This polynomial is called the**Pfaffian**of the matrix. The Pfaffian is nonvanishing only for 2"n" × 2"n" skew-symmetric matrices, in which case it is a polynomial of degree "n".**Examples**:$mbox\{Pf\}egin\{bmatrix\}\; 0\; a\; \backslash \; -a\; 0\; end\{bmatrix\}=a.$

:$mbox\{Pf\}egin\{bmatrix\}\; 0\; a\; b\; c\; \backslash \; -a\; 0\; d\; e\; \backslash \; -b\; -d\; 0\; f\; \backslash -c\; -e\; -f\; 0\; end\{bmatrix\}=af-be+dc.$

:$mbox\{Pf\}egin\{bmatrix\}egin\{matrix\}0\; lambda\_1\backslash \; -lambda\_1\; 0end\{matrix\}\; 0\; cdots\; 0\; \backslash 0\; egin\{matrix\}0\; lambda\_2\backslash \; -lambda\_2\; 0end\{matrix\}\; 0\; \backslash vdots\; ddots\; vdots\; \backslash 0\; 0\; cdots\; egin\{matrix\}0\; lambda\_n\backslash \; -lambda\_n\; 0end\{matrix\}end\{bmatrix\}\; =\; lambda\_1lambda\_2cdotslambda\_n.$

**Formal definition**Let "A" = {"a"

_{"i,j"}} be a 2"n"×2"n" skew-symmetric matrix. The Pfaffian of "A" is defined by the equation:$mathrm\{Pf\}(A)\; =\; frac\{1\}\{2^n\; n!\}sum\_\{sigmain\; S\_\{2nmathrm\{sgn\}(sigma)prod\_\{i=1\}^\{n\}a\_\{sigma(2i-1),sigma(2i)\}$

where "S"

_{2"n"}is thesymmetric group and sgn(σ) is the signature of σ.One can make use of the skew-symmetry of "A" to avoid summing over all possible

permutation s. Let Π be the set of all partitions of {1, 2, …, 2"n"} into pairs without regard to order. There are (2"n" − 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=egin\{bmatrix\}\; 1\; 2\; 3\; 4\; cdots\; 2n\; \backslash \; 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\_\{alphainPi\}\; A\_alpha.$

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

**Recursive definition**By convention, the Pfaffian of the 0×0 matrix is equal to one. The Pfaffian of a skew-symmetric 2"n"×2"n" matrix "A" with "n">0 can be computed recursively as

:$mbox\{Pf\}(A)=sum\_\{i=2\}^\{2n\}(-1)^\{i\}a\_\{1i\}mbox\{Pf\}(A\_\{hat\{1\}hat\{i),$

where $A\_\{hat\{1\}hat\{i$ denotes the matrix "A" with both the first and "i"-th rows and columns removed.

**Alternative definition**One can associate to any skew-symmetric 2"n"×2"n" matrix "A" ={"a"

_{"ij"}} a bivector:$omega=sum\_\{i\}\; a\_\{ij\};e^iwedge\; e^j.\; math>$

where {"e"

^{1}, "e"^{2}, …, "e"^{2"n"}} is the standard basis of**R**^{2n}. The Pfaffian is then defined by the equation:$frac\{1\}\{n!\}omega^n\; =\; mbox\{Pf\}(A);e^1wedge\; e^2wedgecdotswedge\; e^\{2n\},$here ω

^{"n"}denotes thewedge product of "n" copies of ω with itself.**Derivation from Determinant**The Pfaffian can be derived from the

determinant for askew-symmetric matrix A as follows. UsingLaplace's formula we can write the determinant as:$det(A)=(-1)^\{p+1\}a\_\{p1\}A\_\{p1\}\; +\; (-1)^\{p+2\}a\_\{p2\}A\_\{p2\}+cdots+(-1)^\{n+p\}a\_\{pn\}A\_\{pn\},$

where $A\_\{pi\}$ is the p,i minor matrix of the matrix A.We further use

Laplace's formula to note that:$det(A\; [A\_\{ij\}]\; )=|A|^n,$

since this determinant is that of an $n\; imes\; n$ matrix whose only non-zero elements are the diagonals (each with value det(A)) and [A_{ij}] is a matrix whose i,jth component is the corresponding i,j minor matrix. In this way, following a proof by Parameswaran, we can write the determinant as,

:$det(A)equivDelta\_n=left|\; egin\{array\}\{cccc\}a\_\{11\}a\_\{12\}cdotsa\_\{1n\}\backslash a\_\{21\}a\_\{22\}cdotsa\_\{2n\}\backslash vdotsvdots\backslash \; a\_\{n1\}a\_\{n2\}cdotsa\_\{nn\}end\{array\}\; ight$

.The minor of $left|\; egin\{array\}\{cc\}\; a\_\{11\}a\_\{12\}\backslash a\_\{21\}a\_\{22\}end\{array\}\; ight|$ would be $Delta\_\{n-2\}$. With this notation:$left|\; egin\{array\}\{cccc\}10cdots0\backslash \; 01cdots0\backslash \; a\_\{31\}a\_\{32\}cdotsa\_\{3n\}\backslash \; cdotscdotscdotscdots\backslash \; a\_\{n1\}a\_\{n2\}cdotsa\_\{nn\}end\{array\}\; ight$

imes left| egin{array}{cccc}A_{11}&A_{21}&cdots&A_{n1}\ A_{12}&A_{22}&cdots&A_{n2}\ A_{13}&A_{23}&cdots&A_{n3}\ cdots&cdots&cdots&cdots\ A_{1n}&A_{2n}&cdots&A_{nn}end{array} ight

=left| egin{array}{cc} A_{11}&A_{21}\A_{12}&a_{22}end{array} ight|Delta_n^{n-2}.Thus

:$Delta\_\{n-2\}Delta\_n^\{n-1\}=left|\; egin\{array\}\{cc\}\; A\_\{11\}A\_\{21\}\backslash A\_\{12\}a\_\{22\}end\{array\}\; ight|Delta\_n^\{n-2\}.$

Of course, it was only arbitrarily that we chose to remove the first two rows, and more generically we can write

:$A\_\{rr\}A\_\{ss\}-A\_\{rs\}A\_\{sr\}=Delta\_\{rs,rs\}Delta\_\{n\}$

where $Delta\_\{rs,rs\}$ is the determinant of the original matrix with the rows r and s, as well as the columns r and s removed.The equation above simplifies in the skew-symmetric case to

:$A\_\{rs\}\; =\; sqrt\{Delta\_\{rs,rs\}Delta\_n\}$.

We now plug this back into the original formula for the determinant,

:$Delta\_n=(-1)^\{p+1\}a\_\{p1\}sqrt\{Delta\_\{p1,p1\}Delta\_n\}\; +\; (-1)^\{p+2\}a\_\{p2\}sqrt\{Delta\_\{p2,p2\}Delta\_n\}+cdots+(-1)^\{n+p\}a\_\{pn\}sqrt\{Delta\_\{pn,pn\}Delta\_n\},$

or with slight manipulation,

:$sqrt\{Delta\_n\}=(-1)^\{p+1\}left(\; a\_\{p1\}sqrt\{Delta\_\{p1,p1\; -\; a\_\{p2\}sqrt\{Delta\_\{p2,p2+cdots+(-1)^\{n-1\}a\_\{pn\}sqrt\{Delta\_\{pn,pn\; ight),$

The

determinant is thus the square of the right hand side, and so we identify the right hand side as the Pfaffian.**Identities**For a 2"n" × 2"n" skew-symmetric matrix "A" and an arbitrary 2"n" × 2"n" 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)^nmbox\{Pf\}(A)$

* For a block-diagonal matrix

::$A\_1oplus\; A\_2=egin\{bmatrix\}\; A\_1\; 0\; \backslash \; 0\; A\_2\; end\{bmatrix\},$

: Pf("A"

_{1}⊕"A"_{2}) = Pf("A"_{1})Pf("A"_{2}).*For an arbitrary "n" × "n" matrix "M":::$mbox\{Pf\}egin\{bmatrix\}\; 0\; M\; \backslash \; -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 class es. In particular, it can be used to define theEuler class of aRiemannian manifold which is used in thegeneralized Gauss-Bonnet theorem .*The number of

perfect matching s in aplanar 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 to calculate thepartition function ofIsing model s ofspin glass es in physics, respectively ofMarkov random fields inmachine learning (Globerson and Jaakkola, 2007), 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 ofrestricted quantum computation .*The calculation of the number of possible ways to tile a standard

chessboard or 8-by-8checkerboard with 32domino es is a simple example of a problem which may be solved through the use of the Pfaffian technique. There are 12,988,816 possible ways to tile a chessboard in this manner. Specifically, 12988816 is the number of possible ways to cover an 8-by-8 square with 32 1-by-2 rectangles. 12988816 is asquare number : 12988816 = 3604^{2}). Note that 12988816 can be written in the form: $2x1802^2+2x1802^2$, where all the numbers have adigital root of 2.:More generally, the number of ways to cover a $2n$-by-$2n$ square with $2n^2$ dominoes (as calculated independently by Temperley and

M.E. Fisher and Kasteleyn in 1961) is given by:$prod\_\{j=1\}^N\; prod\_\{k=1\}^N\; left\; (\; 4cos^2\; frac\{pi\; j\}\{2n\; +\; 1\}\; +\; 4cos^2\; frac\{pi\; k\}\{2n\; +\; 1\}\; ight\; ).$

:This technique can be applied in many mathematics-related subjects, for example, in the classical,

2-dimensional computation of thedimer-dimer correlator function inquantum mechanics .**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 mathematicianJohann Friedrich Pfaff .**ee also***

Dimer

*Polyomino

*Statistical mechanics **References***"The statistics of dimers on a lattice, Part I", "Physica", vol.27, 1961, pp.1209-25, P.W. Kasteleyn.

* .

*.

*"The Games and Puzzles Journal", No.14, 1996, pp.204-5, Robin J. Chapman, University of Exeter

*"Domino Tilings and Products ofFibonacci andPell number s", "Journal of Integer Sequences", Vol.5, 2002, Article 02.1.2, James A. Sellers,The Pennsylvania State University

* "The Penguin Dictionary of Curious and Interesting Numbers", revised ed., 1997, ISBN 0-14-026149-4, David Wells, p.182.

* "A Treatise on the Theory of Determinants", 1882, Macmillan and Co., Thomas Muir, [*http://books.google.com/books?id=pk4DAAAAQAAJ&dq=thomas+muir+treatise+on+the+theory+of+determinant&psp=1 "Online"*]

* "Skew-Symmetric Determinants", "The American Mathematical Monthly", vol. 61, no.2., 1954, p.116, S. Parameswaran [*http://www.jstor.org/stable/2307800 "JSTOR link"*]**External links*** [

*http://planetmath.org/encyclopedia/Pfafian.html Pfaffian at PlanetMath.org*]

* T. Jones, [*http://www.physics.drexel.edu/~tim/open/pfaff/pfaff.pdf "The Pfaffian and the Wedge Product" (a demonstration of the proof of the Pfaffian/determinant relationship)*]

* R. Kenyon and A. Okounkov, [*http://www.ams.org/notices/200503/what-is.pdf "What is ... a dimer?"*]

*

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Pfaffian**— noun The determinant of a skew symmetric matrix, capable of being written as the square of a polynomial in the matrix entries … Wiktionary**Pfaffian**— … Useful english dictionary**Pfaffian function**— Not to be confused with Pfaffian. In mathematics, the Pfaffian functions are a certain class of functions introduced by Askold Georgevich Khovanskiǐ in the 1970s. They are named after German mathematician Johann Pfaff. Contents 1 Basic definition … Wikipedia**Pfaffian constraint**— In robot motion planning, a Pfaffian constraint is a set of k linearly independent constraints linear in velocity, i.e., of the formA(q) dot q=0One source of Pfaffian constraints is rolling without slipping in wheeled robots.cite book author =… … Wikipedia**Integrability conditions for differential systems**— In mathematics, certain systems of partial differential equations are usefully formulated, from the point of view of their underlying geometric and algebraic structure, in terms of a system of differential forms. The idea is to take advantage of… … Wikipedia**Johann Friedrich Pfaff**— Infobox Scientist name = Johann Friedrich Pfaff image width = 228px caption = Johann Friedrich Pfaff birth date = birth date|1765|12|22|mf=y birth place = Stuttgart, Germany death date = death date and age|1825|4|21|1765|12|22|mf=y death place =… … Wikipedia**Frobenius theorem (differential topology)**— In mathematics, Frobenius theorem gives necessary and sufficient conditions for finding a maximal set of independent solutions of an overdetermined system of first order homogeneous linear partial differential equations. In modern geometric terms … Wikipedia**Affine connection**— An affine connection on the sphere rolls the affine tangent plane from one point to another. As it does so, the point of contact traces out a curve in the plane: the development. In the branch of mathematics called differential geometry, an… … Wikipedia**List of mathematics articles (P)**— NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… … Wikipedia**Schwartz-Zippel lemma and testing polynomial identities**— Polynomial identity testing is the problem of determining whether a given multivariate polynomial is the0 polynomial or identically equal to 0. The input to the problem is an n variable polynomial over a fieldF. It can occur in the following… … Wikipedia