View source for Pfaffian

{{distinguish|Pfaffian function|Pfaffian system|Pfaffian orientation}}
In [[mathematics]], the [[determinant]] of a [[skew-symmetric matrix]] can always be written as the square of a [[polynomial]] in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, when applied to the coefficients of a skew-symmetric matrix, is called the '''Pfaffian''' of that matrix. The term ''Pfaffian'' was introduced by {{harvs|txt|authorlink=Arthur Cayley|last=Cayley|year=1852}} who indirectly named them after [[Johann Friedrich Pfaff]].  The Pfaffian (considered as a polynomial) is nonvanishing only for 2''n'' &times; 2''n'' skew-symmetric matrices, in which case it is a polynomial of degree ''n''.

Explicitly, for a skew-symmetric matrix '''A''',
:<math> \operatorname{pf}(A)^2=\det(A),</math>
which was first proved by {{harvs|txt|authorlink=Arthur Cayley|last=Cayley|year=1849}}, a work based on earlier work on Pfaffian systems of ordinary differential equations by [[Carl Gustav Jacob Jacobi|Jacobi]].

The fact that the determinant of any skew symmetric matrix is the square of a polynomial can be shown by writing the matrix as a block matrix,
then using induction and examining the [[Schur complement]], which is skew symmetric as well.<ref>Ledermann, W. "A note on skew-symmetric determinants"</ref>

==Examples==

:<math>A=\begin{bmatrix}  0 & a \\ -a & 0  \end{bmatrix}.\qquad\operatorname{pf}(A)=a.</math>

:<math>B=\begin{bmatrix}   0     & a & b \\ -a & 0        & c  \\   -b      &  -c       & 0 \end{bmatrix}.\qquad\operatorname{pf}(B)=0.</math>

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

:<math>\operatorname{pf}\begin{bmatrix}    0     & a & b & c \\ -a & 0        & d & e  \\   -b      &  -d       & 0& f    \\-c &  -e      & -f & 0 \end{bmatrix}=af-be+dc.</math>

The Pfaffian of a 2''n'' &times; 2''n'' skew-symmetric [[tridiagonal matrix]] is given as
:<math>\operatorname{pf}\begin{bmatrix}
0 & a_1 & 0 & 0\\ -a_1 & 0 & b_1 & 0\\  0 & -b_1 &0 & a_2 \\ 0 & 0 & -a_2 &\ddots&\ddots\\
&&&\ddots&\ddots&b_{n-1}\\
&&&&-b_{n-1}&0&a_n\\
&&&&&-a_n&0
\end{bmatrix} = a_1 a_2\cdots a_n.</math>
(Note that any skew-symmetric matrix can be reduced to this form with all <math>b_i</math> equal to zero, see [[Skew-symmetric matrix#Spectral theory|Spectral theory of a skew-symmetric matrix]]..)

==Formal definition==

Let ''A'' = {''a''<sub>''i,j''</sub>} be a 2''n'' × 2''n'' skew-symmetric matrix. The Pfaffian of ''A'' is defined by the equation

:<math>\operatorname{pf}(A) = \frac{1}{2^n n!}\sum_{\sigma\in S_{2n}}\operatorname{sgn}(\sigma)\prod_{i=1}^{n}a_{\sigma(2i-1),\sigma(2i)}</math>

where ''S''<sub>2''n''</sub> is the [[symmetric group]] of order (2''n'')! and sgn(σ) is the [[signature (permutation)|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 [[partition of a set|partition]]s of {1, 2, ..., 2''n''} into pairs without regard to order. There are (2''n'')!/(2<sup>''n''</sup>''n''!) = (2''n'' - 1)[[double factorial|!!]] such partitions. An element α ∈ Π can be written as

:<math>\alpha=\{(i_1,j_1),(i_2,j_2),\cdots,(i_n,j_n)\}</math>

with ''i''<sub>''k''</sub> < ''j''<sub>''k''</sub> and <math>i_1 < i_2 < \cdots < i_n</math>. Let

:<math>\pi_\alpha=\begin{bmatrix} 1 & 2 & 3 & 4 & \cdots & 2n -1 & 2n \\ i_1 & j_1 & i_2 & j_2 & \cdots & i_n & j_{n} \end{bmatrix}</math>

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

:<math> A_\alpha =\operatorname{sgn}(\pi_\alpha)a_{i_1,j_1}a_{i_2,j_2}\cdots a_{i_n,j_n}.</math>

The Pfaffian of ''A'' is then given by

:<math>\operatorname{pf}(A)=\sum_{\alpha\in\Pi} A_\alpha.</math>

The Pfaffian of a ''n''&times;''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,

<math display="block">\det\,A = \det\,A^\text{T} = \det\left(-A\right) = (-1)^n \det\,A,</math>

and for ''n'' odd, this implies <math>\det\,A = 0</math>.

===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

:<math>\operatorname{pf}(A)=\sum_{{j=1}\atop{j\neq i}}^{2n}(-1)^{i+j+1+\theta(i-j)}a_{ij}\operatorname{pf}(A_{\hat{\imath}\hat{\jmath}}),</math>

where index ''i'' can be selected arbitrarily, <math>\theta(i-j)</math> is the [[Heaviside step function]], and <math>A_{\hat{\imath}\hat{\jmath}}</math> denotes the matrix ''A'' with both the ''i''-th and ''j''-th rows and columns removed.<ref>http://jesusmtz.public.iastate.edu/soliton/REPORT%202.pdf</ref> Note how for the special choice <math>i=1</math> this reduces to the simpler expression:

:<math>\operatorname{pf}(A)=\sum_{j=2}^{2n}(-1)^{j}a_{1j}\operatorname{pf}(A_{\hat{1}\hat{\jmath}}).</math>

===Alternative definitions===
One can associate to any skew-symmetric 2''n''×2''n'' matrix ''A'' ={''a''<sub>''ij''</sub>} a [[exterior algebra|bivector]]

:<math>\omega=\sum_{i<j} a_{ij}\;e_i\wedge e_j.</math>

where {''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>2''n''</sub>} is the standard basis of '''R'''<sup>2n</sup>. The Pfaffian is then defined by the equation

:<math>\frac{1}{n!}\omega^n = \operatorname{pf}(A)\;e_1\wedge e_2\wedge\cdots\wedge e_{2n},</math>
here ω<sup>''n''</sup> denotes the [[wedge product]] of ''n'' copies of ω.

A non-zero generalisation of the Pfaffian to odd dimensional matrices is given in the work of de Bruijn on multiple integrals involving determinants.<ref>http://alexandria.tue.nl/repository/freearticles/597510.pdf</ref> In particular for any ''m'' x ''m'' matrix ''A'', we use the formal definition above but set <math> n = \lfloor m/2\rfloor </math>. For ''m'' odd, one can then show that this is equal to the usual Pfaffian of an ''m+1'' x ''m+1'' dimensional skew symmetric matrix where we have added an ''m+1''th column consisting of ''m'' elements 1, an ''m+1''th row consisting of ''m'' 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.

==Properties and identities==

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.

=== Miscellaneous ===

For a 2''n'' &times; 2''n'' skew-symmetric matrix ''A''
:<math>\operatorname{pf}(A^\text{T}) = (-1)^n\operatorname{pf}(A).</math>
:<math>\operatorname{pf}(\lambda A) = \lambda^n \operatorname{pf}(A).</math>
:<math>\operatorname{pf}(A)^2 = \det(A).</math>
For an arbitrary 2''n'' &times; 2''n'' matrix ''B'',
:<math>\operatorname{pf}(BAB^\text{T})= \det(B)\operatorname{pf}(A).</math>
Substituting in this equation ''B = A<sup>m</sup>'', one gets for all integer ''m''
:<math>\operatorname{pf}(A^{2m+1})= (-1)^{nm}\operatorname{pf}(A)^{2m+1}.</math>

=== Derivative identities ===

If ''A'' depends on some variable ''x''<sub>''i''</sub>, then the gradient of a Pfaffian is given by
:<math>\frac{1}{\operatorname{pf}(A)}\frac{\partial\operatorname{pf}(A)}{\partial x_i}=\frac{1}{2}\operatorname{tr}\left(A^{-1}\frac{\partial A}{\partial x_i}\right),</math>
and the [[Hessian matrix|Hessian]] of a Pfaffian is given by
:<math>\frac{1}{\operatorname{pf}(A)}\frac{\partial^2\operatorname{pf}(A)}{\partial x_i\partial x_j}=\frac{1}{2}\operatorname{tr}\left(A^{-1}\frac{\partial^2 A}{\partial x_i\partial x_j}\right)-\frac{1}{2}\operatorname{tr}\left(A^{-1}\frac{\partial A}{\partial x_i}A^{-1}\frac{\partial A}{\partial x_j}\right)+\frac{1}{4}\operatorname{tr}\left(A^{-1}\frac{\partial A}{\partial x_i}\right)\operatorname{tr}\left(A^{-1}\frac{\partial A}{\partial x_j}\right).</math>

=== Trace identities ===

The product of the Pfaffians of skew-symmetric matrices ''A'' and ''B'' under the condition that ''A<sup>T</sup>B'' is a [[positive-definite matrix]] can be represented in the form of an exponential
:<math>\textrm{pf}(A)\textrm{pf}(B) = \exp(\frac{1}{2}\mathrm{tr}\log(A^\text{T}B)).</math>

Suppose ''A'' and ''B'' are ''2n × 2n'' skew-symmetric matrices, then
:<math> \mathrm{pf}(A) \mathrm{pf}(B) = \frac{1}{n!} B_n(s_1, s_2, \ldots, s_n), \qquad \mathrm{where} \qquad s_l = - \frac{1}{2}(l - 1)!\mathrm{tr}((AB)^l)</math>
and ''B''<sub>n</sub>(''s''<sub>1</sub>,''s''<sub>2</sub>,...,''s''<sub>n</sub>) are [[Bell polynomials]].

=== Block matrices ===

For a block-diagonal matrix
::<math>A_1\oplus A_2=\begin{bmatrix}  A_1 & 0 \\ 0 & A_2 \end{bmatrix},</math>
:<math>\operatorname{pf}(A_1\oplus A_2) =\operatorname{pf}(A_1)\operatorname{pf}(A_2).</math>
For an arbitrary ''n'' &times; ''n'' matrix ''M'':
:<math>\operatorname{pf}\begin{bmatrix}  0 & M \\ -M^\text{T} & 0  \end{bmatrix} = 
(-1)^{n(n-1)/2}\det M.</math>

It is often required to compute the pfaffian of a skew-symmetric matrix <math> S </math> with the block structure
:<math>
 S = \begin{pmatrix} M & Q\\-Q^T & N \end{pmatrix}\,
</math>
where <math> M </math> and <math> N </math> are skew-symmetric matrices and <math> Q </math> is a general rectangular matrix.

When <math> M </math> is invertible, one has
:<math>
\operatorname{pf}( S) = \operatorname{pf}( M)\operatorname{pf}( N+  Q^T   M^{-1}  Q).
</math>
This can be seen from Aitken block-diagonalization formula,<ref>A. C. Aitken. Determinants and matrices. Oliver and Boyd, Edinburgh, fourth edition, 1939.</ref><ref>	
Zhang, Fuzhen, ed. The Schur complement and its applications. Vol. 4. Springer Science & Business Media, 2006.</ref><ref>Bunch, James R. "A note on the stable decomposition of skew-symmetric matrices." Mathematics of Computation 38.158 (1982): 475-479.</ref>
:<math>\begin{pmatrix}M& 0\\ 0 & N+Q^T M^{-1} Q\end{pmatrix} = \begin{pmatrix}I& 0\\ Q^T M^{-1} & I\end{pmatrix}\begin{pmatrix} M& Q\\ -Q^T & N\end{pmatrix} \begin{pmatrix}I& -M^{-1} Q\\ 0& I \end{pmatrix}.</math>
This decomposition involves a [[congruence transformations]] that allow to use the pfaffian property <math> \operatorname{pf}(BAB^T) = \operatorname{det}(B)\operatorname{pf}(A)</math>.

Similarly, when <math> N </math> is invertible, one has
:<math>
\operatorname{pf}( S) =
\operatorname{pf}(N)\operatorname{pf}( M+ Q  N^{-1} Q^T),
</math>
as can be seen by employing the decomposition 
:<math>\begin{pmatrix}M+Q N^{-1} Q^T& 0\\ 0 & N\end{pmatrix} = \begin{pmatrix}I& -Q N^{-1}\\ 0 & I\end{pmatrix}\begin{pmatrix} M& Q\\ -Q^T & N\end{pmatrix} \begin{pmatrix}I& 0\\ N^{-1} Q^T& I \end{pmatrix}.</math>

== Calculating the Pfaffian numerically ==
Suppose ''A'' is a ''2n × 2n'' skew-symmetric matrices, then
:<math>\textrm{pf}(A) = i^{(n^2)} \exp\left(\frac{1}{2}\mathrm{tr}\log((\sigma_y\otimes I_n)^T\cdot A)\right), </math>
where <math>\sigma_y</math> is the second [[Pauli matrices|Pauli matrix]], <math>I_n</math> is an identity matrix of dimension ''n'' and we took the trace over a [[matrix logarithm]].

This equality is based on the [[Pfaffian#Trace identities|trace identity]]
: <math>\textrm{pf}(A)\textrm{pf}(B) = \exp\left(\frac{1}{2}\mathrm{tr}\log(A^\text{T}B)\right)</math>
and on the observation that <math>\textrm{pf}(\sigma_y\otimes I_n)=(-i)^{n^2}</math>.

Since calculating the [[Logarithm of a matrix]] is a computationally demanding task, one can instead compute all eigenvalues of <math>((\sigma_y\otimes I_n)^T\cdot A)</math>, take the log of all of these and sum them up. This procedure merely exploits the [[Logarithm of a matrix#Properties|property]] <math>\operatorname{tr}{\log{(AB)}} = \operatorname{tr}{\log{(A)}} + \operatorname{tr}{\log{(B)}} </math>. This can be implemented in [[Wolfram Mathematica|Mathematica]] within a single line:

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

For other efficient algorithms see {{harv|Wimmer|2012}}.

==Applications==
*There exist programs for the numerical computation of the Pfaffian on various platforms (Python, Matlab, Mathematica) {{harv|Wimmer|2012}}.
*The Pfaffian is an [[invariant polynomial]] of a skew-symmetric matrix under a proper [[orthogonal group|orthogonal]] change of basis.  As such, it is important in the theory of [[characteristic class]]es. 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 matching]]s in a [[planar graph]] is given by a Pfaffian, hence is polynomial time computable via the [[FKT algorithm]]. This is surprising given that for general graphs, the problem is very difficult (so called [[Sharp-P-complete|#P-complete]]). This result is used to calculate the number of [[domino tiling]]s of a rectangle, the [[partition function (statistical mechanics)|partition function]] of [[Ising model]]s in physics, or of [[Markov random field]]s in [[machine learning]] ({{harvnb|Globerson|Jaakkola|2007}}; {{harvnb|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 of [[restricted quantum computation]]. Read [[Holographic algorithm]] for more information.

==See also==
*[[Determinant]]
*[[Dimer model]]
*[[Hafnian]]
*[[Polyomino]]
*[[Statistical mechanics]]

==Notes==
{{Reflist}}

==References==
* {{cite journal | first=Arthur | last=Cayley  |title=Sur les déterminants gauches | journal=Journal für die reine und angewandte Mathematik | volume=38 | year=1849 | pages= 93–96 |url=http://eudml.org/doc/183267|ref=harv}}
*{{Cite journal | last1=Cayley | first1=Arthur | author1-link=Arthur Cayley | title=On the theory of permutants | url=https://archive.org/stream/collectedmathema02cayluoft#page/16/mode/2up | year=1852 | journal=Cambridge and Dublin Mathematical Journal  | volume=VII | pages=40–51 | ref=harv | postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}} Reprinted in Collected mathematical papers, volume 2.
* {{cite journal | ref=harv
 | title = The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice
 | journal = Physica
 | volume = 27 | issue = 12 | year = 1961 | pages = 1209–1225
 | first = P. W. | last = Kasteleyn
 | authorlink = Pieter_Kasteleyn
 | doi = 10.1016/0031-8914(61)90063-5| bibcode = 1961Phy....27.1209K}}
* {{cite arXiv | first=James | last=Propp | year=2004 |title=Lambda-determinants and domino-tilings |eprint=math/0406301 |ref=harv}}
* {{Cite book | first=Amir | last=Globerson | first2=Tommi | last2=Jaakkola | year = 2007 | contribution= Approximate inference using planar graph decomposition | contribution-url= http://books.nips.cc/papers/files/nips19/NIPS2006_0703.pdf | title=Advances in Neural Information Processing Systems 19  | url=http://books.nips.cc/ | publisher=MIT Press | ref=harv | postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}}.
* {{Cite book | first=Nicol | last=Schraudolph | first2=Dmitry | last2=Kamenetsky | year = 2009 | contribution= Efficient exact inference in planar Ising models | contribution-url= http://books.nips.cc/papers/files/nips21/NIPS2008_0401.pdf | title=Advances in Neural Information Processing Systems 21  | url=http://books.nips.cc/ | publisher=MIT Press | ref=harv | postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}}.
* {{cite journal | ref=harv | journal=The Games and Puzzles Journal | volume=2 | year=1996 | pages=204–5 | first1=G.P. |last=Jeliss | first2=Robin J. | last2=Chapman | title=Dominizing the Chessboard | issue=14}}
* {{cite journal | ref=harv | title=Domino Tilings and Products of Fibonacci and Pell numbers| journal=Journal of Integer Sequences | volume=5 | year=2002 | first=James A. | last=Sellers | issue=1 |page=02.1.2 | url=http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Sellers/sellers4.html }}
* {{cite book | ref=harv | title=[[The Penguin Dictionary of Curious and Interesting Numbers]] | edition=revised | year=1997 | isbn=0-14-026149-4 |  first=David | last=Wells | page=182 }}
* {{cite book | ref=harv | title=A Treatise on the Theory of Determinants | url=https://archive.org/details/atreatiseontheo00muirgoog | year=1882 | publisher=Macmillan and Co. | first=Thomas | last=Muir}} [https://books.google.com/books?id=pk4DAAAAQAAJ&dq=thomas+muir+treatise+on+the+theory+of+determinant&psp=1 ''Online'']
* {{cite journal | ref=harv | title=Skew-Symmetric Determinants | journal=The American Mathematical Monthly | volume=61 | year=1954 | page=116 | first=S. | last=Parameswaran | jstor=2307800 | issue=2|doi=10.2307/2307800}}
* {{cite journal| ref=harv |title=Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices|journal=[[ACM Trans. Math. Softw.]]|volume=38|page=30|year=2012 | first=M. | last=Wimmer | arxiv=1102.3440 | doi = 10.1145/2331130.2331138 }}
* {{cite journal| ref=harv |title=On some multiple integrals involving determinants|journal=[[J. Indian Math. Soc.]]|volume=19|pages=131–151|year=1955 | first=N. G. | last=de Bruijn}}

==External links==
* {{springer|title=Pfaffian|id=p/p072500}}
* [http://planetmath.org/encyclopedia/Pfaffian.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 [[Andrei Okounkov|A. Okounkov]], [http://www.ams.org/notices/200503/what-is.pdf ''What is ... a dimer?'']
* {{OEIS el|1=A004003|2=Number of domino tilings (or dimer coverings)|formalname=Number of domino tilings (or dimer coverings) of a 2n X 2n square}}
* W. Ledermann "A note on skew-symmetric determinants" https://www.researchgate.net/publication/231827602_A_note_on_skew-symmetric_determinants

[[Category:Determinants]]
[[Category:Multilinear algebra]]