Pfaffian

Not to be confused with Pfaffian function or Pfaffian system.

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 term Pfaffian was introduced by Cayley (1852) who named them after Johann Friedrich Pfaff. The Pfaffian is nonvanishing only for 2n × 2n skew-symmetric matrices, in which case it is a polynomial of degree n.

Explicitly, for a skew-symmetric matrix A,

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

which was first proved by Thomas Muir in 1882 (Muir 1882).

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.

Examples

$A={\begin{bmatrix}0&a\\-a&0\end{bmatrix}}.\qquad \operatorname {pf} (A)=a.$

$B={\begin{bmatrix}0&a&b\\-a&0&c\\-b&-c&0\end{bmatrix}}.\qquad \operatorname {pf} (B)=0.$

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

$\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.$

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

$\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 &&b_{n-1}\\&&&&-b_{n-1}&0&a_{n}\\&&&&&-a_{n}&0\end{bmatrix}}=a_{1}a_{2}\cdots a_{n}.$

(Note that any skew-symmetric matrix can be reduced to this form with all $b_{i}$ equal to zero, see Spectral theory of a skew-symmetric matrix)

Formal definition

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

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

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 the corresponding permutation. 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, as the determinant of an odd skew-symmetric matrix is zero, since for a skew-symmetric matrix, $\det \,A=\det \,A^{\text{T}}=\det \left(-A\right)=(-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 2n×2n matrix A with n>0 can be computed recursively as

$\operatorname {pf} (A)=\sum _{{j=1} \atop {j\neq i}}^{2n}(-1)^{i+j+1+\theta (i-j)}a_{ij}\operatorname {pf} (A_{{\hat {i}}{\hat {j}}}),$

where index i can be selected arbitrarily, $\theta (i-j)$ is the Heaviside step function, and $A_{{\hat {i}}{\hat {j}}}$ denotes the matrix A with both the i-th and j-th rows and columns removed. Note how for the special choice $i=1$ this reduces to the simpler expression:

$\operatorname {pf} (A)=\sum _{j=2}^{2n}(-1)^{j}a_{1j}\operatorname {pf} (A_{{\hat {1}}{\hat {j}}}).$

Alternative definitions

• 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}=\operatorname {pf} (A)\;e^{1}\wedge e^{2}\wedge \cdots \wedge e^{2n},$

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

Identities

For a 2n × 2n skew-symmetric matrix A

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

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

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

For an arbitrary 2n × 2n matrix B,

$\operatorname {pf} (BAB^{\text{T}})=\det(B)\operatorname {pf} (A).$

Substituting in this equation B = A^m, one gets for all integer m

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

For a block-diagonal matrix

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

$\operatorname {pf} (A_{1}\oplus A_{2})=\operatorname {pf} (A_{1})\operatorname {pf} (A_{2}).$

For an arbitrary n × n matrix M:

$\operatorname {pf} {\begin{bmatrix}0&M\\-M^{\text{T}}&0\end{bmatrix}}=(-1)^{n(n-1)/2}\det M.$

If A depends on some variable x_i, then the gradient of a Pfaffian is given by

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

and the Hessian of a Pfaffian is given by

${\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).$

Properties

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 Pfaffian by the same constant.
• Simultaneous interchange of two different rows and corresponding columns changes the sign of Pfaffian.
• A multiple of a row and corresponding column added to another row and corresponding column does not change the value of Pfaffian.

These properties can be derived from the identity $\operatorname {pf} (BAB^{\text{T}})=\det(B)\operatorname {pf} (A)$.

Applications

• There exist programs for the numerical computation of the Pfaffian on various platforms (Python, Matlab, Mathematica) (Wimmer 2012).

• The Pfaffian is an invariant polynomial of a skew-symmetric matrix under a proper orthogonal change of basis. 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 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 #P-complete). This result is used to calculate the number of domino tilings of a rectangle, the partition function of Ising models in physics, or of Markov random fields in machine 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 of restricted quantum computation. Read Holographic algorithm for more information.

See also

• Determinant
• Dimer model
• Polyomino
• Statistical mechanics

References

• Cayley, Arthur (1852). "On the theory of permutants". Cambridge and Dublin Mathematical Journal. VII: 40–51Template:Inconsistent citations {{cite journal}}: Invalid |ref=harv (help)CS1 maint: postscript (link) Reprinted in Collected mathematical papers, volume 2.
• Kasteleyn, P. W. (1961). "The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice". Physica. 27 (12): 1209–1225. doi:10.1016/0031-8914(61)90063-5. {{cite journal}}: Invalid |ref=harv (help)
• Propp, James (2004). "Lambda-determinants and domino-tilings". arXiv:math/0406301. {{cite arXiv}}: Invalid |ref=harv (help)
• Globerson, Amir; Jaakkola, Tommi (2007). "Advances in Neural Information Processing Systems 19". MIT PressTemplate:Inconsistent citations {{cite journal}}: |contribution= ignored (help); Cite journal requires |journal= (help); Invalid |ref=harv (help)CS1 maint: postscript (link).
• Schraudolph, Nicol; Kamenetsky, Dmitry (2009). "Advances in Neural Information Processing Systems 21". MIT PressTemplate:Inconsistent citations {{cite journal}}: |contribution= ignored (help); Cite journal requires |journal= (help); Invalid |ref=harv (help)CS1 maint: postscript (link).
• Jeliss, G.P.; Chapman, Robin J. (1996). "Dominizing the Chessboard". The Games and Puzzles Journal. 2 (14): 204–5. {{cite journal}}: Invalid |ref=harv (help)
• Sellers, James A. (2002). "Domino Tilings and Products of Fibonacci and Pell numbers". Journal of Integer Sequences. 5 (1): 02.1.2. {{cite journal}}: Invalid |ref=harv (help)
• Wells, David (1997). The Penguin Dictionary of Curious and Interesting Numbers (revised ed.). p. 182. ISBN 0-14-026149-4. {{cite book}}: Invalid |ref=harv (help)
• Muir, Thomas (1882). A Treatise on the Theory of Determinants. Macmillan and Co. {{cite book}}: Invalid |ref=harv (help) Online
• Parameswaran, S. (1954). "Skew-Symmetric Determinants". The American Mathematical Monthly. 61 (2): 116. JSTOR 2307800. {{cite journal}}: Invalid |ref=harv (help)
• Wimmer, M. (2012). "Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices". ACM Trans. Math. Software. 38: 30. arXiv:1102.3440. doi:10.1145/2331130.2331138. {{cite journal}}: Invalid |ref=harv (help)

External links

• "Pfaffian", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Pfaffian at PlanetMath.org
• T. Jones, The Pfaffian and the Wedge Product (a demonstration of the proof of the Pfaffian/determinant relationship)
• R. Kenyon and A. Okounkov, What is ... a dimer?
• (sequence A004003 in the OEIS)
• W. Ledermann "A note on skew-symmetric determinants" http://www.researchgate.net/publication/231827602_A_note_on_skew-symmetric_determinants