Pfaffian: Information from Answers.com

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, named 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.

1 Examples
2 Formal definition
3 Identities
4 Applications
5 History
6 See also
7 References
8 External links

Examples

$A=\begin{bmatrix} 0 & a \\ -a & 0 \end{bmatrix}.\,\,\,\,\mbox{Pf(A)}=\sqrt{\mbox{det(A)}}=\sqrt{0\cdot 0 - a\cdot (-a)}=a.$

$B=\begin{bmatrix} 0 & a & b \\ -a & 0 & c \\ -b & -c & 0 \end{bmatrix}.\,\,\,\,\mbox{Pf(B)}= \sqrt{(0 + a c (-b) + (-a)(-c)b) - ((-b) 0 b + (-c) c 0 + 0(-a)a)}=0.$

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

$\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. 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^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 2n×2n 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 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.

Derivation from Determinant

We assume that $n$ is an even number and $A = (a i j)$ is an $n \times n$ skew-symmetric matrix. The Pfaffian of $A$ can be derived as follows. Using the Laplace's formula we can write $det(A)$ as

$\det(A) = \sum_j a_{ij}C_{ij}, \,$

where $C i j = ( - 1) i + j det(A i j)$ is the $i j$ th cofactor of $A$ and $A i j$ is the $i j$ th minor of $A$ . By the adjugate formula, we have

$\det(A \times \mathrm{adj}(A))=\det(A)^n. \,$

We have

$\det\left( \begin{array}{cccc}1&0&\cdots&0\\ 0&1&\cdots&0\\ a_{31}&a_{32}&\cdots&a_{3n}\\ \cdots&\cdots&\cdots&\cdots\\ a_{n1}&a_{n2}&\cdots&a_{nn}\end{array} \right) \times \det \left( \begin{array}{cccc}C_{11}&C_{21}&\cdots&C_{n1}\\ C_{12}&C_{22}&\cdots&C_{n2}\\ C_{13}&C_{23}&\cdots&C_{n3}\\ \cdots&\cdots&\cdots&\cdots\\ C_{1n}&C_{2n}&\cdots&C_{nn}\end{array} \right) = \det\left( \begin{array}{cc} C_{11}&C_{21}\\C_{12}&C_{22}\end{array} \right) \det(A)^{n-2},$

Thus

$\det(A_{12, 12})\det(A)^{n-1} = \det \left( \begin{array}{cc} C_{11} & C_{21}\\ C_{12} & C_{22} \end{array} \right) \det(A)^{n-2},$

where $A_{12, 12} \,$ is the $(n-2) \times (n-2)$ minor of $A$ obtained by deleting the first two rows and the first two columns of $A$ . Of course, it is arbitrary that we have changed the first two rows in the above equation. In general we have

$C_{ii}C_{jj} - C_{ij}C_{ji} = \det(A_{ij,ij})\det(A), \,$

So far we have not used the assumption that $n$ is even and $A$ is skew-symmetric. With that, since $A i i$ is an $(n-1)\times(n-1)$ skew-symmetric matrix and $(n - 1)$ is odd, clearly $det(A i i) = 0$ and hence $C i i = 0$ . Similarly $C j j = 0$ . On the other hand,

$C_{ij} = (-1)^{n-1}C_{ji} = -C_{ji}. \,$

So the above equation is simplified as

$C_{ij} = (-1)^{i+j}\sqrt{\det(A_{ij,ij})\det(A)}. \,$ .

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

$\det(A) = \sum_j a_{ij}(-1)^{i+j}\sqrt{\det(A_{ij,ij})\det(A)}, \,$

which yields

$\sqrt{\det(A)} = \sum_j a_{ij}(-1)^{i+j}\sqrt{\det(A_{ij,ij})}. \,$

Identities

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

$Pf(A) 2 = det(A)$

$Pf(B A B T) = det(B)Pf(A)$

$Pf(λ A) = λ n Pf(A)$

$Pf(A T) = ( - 1) n Pf(A)$

For a block-diagonal matrix

$A_1\oplus A_2=\begin{bmatrix} A_1 & 0 \\ 0 & A_2 \end{bmatrix},$

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 to calculate the partition function of Ising models of spin glasses in physics, respectively of Markov random fields in machine learning (Globerson and Jaakkola 2007; Schraudolph and Kamenetsky 2009), 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.

The calculation of the number of possible ways to tile a standard chessboard or 8-by-8 checkerboard with 32 dominoes 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 a square number: 12988816 = 3604²). Note that 12988816 can be written in the form: $2 x 18022 + 2 x 18022$ , where all the numbers have a digital root of 2.

More generally, the number of ways to cover a

2 n

-by-

2 m

square with

2 n m

dominoes (as calculated independently by Temperley and M.E. Fisher and Kasteleyn in 1961) is given by

$\prod_{j=1}^n \prod_{k=1}^m \left ( 4\cos^2 \frac{\pi j}{2n + 1} + 4\cos^2 \frac{\pi k}{2m + 1} \right ).$

This technique can be applied in many mathematics-related subjects, for example, in the classical, 2-dimensional computation of the dimer-dimer correlator function in quantum 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 mathematician Johann Friedrich Pfaff.

References

The statistics of dimers on a lattice, Part I, Physica, vol.27, 1961, pp.1209-25, P.W. Kasteleyn.
Propp, James (2004), Lambda-determinants and domino-tilings, arΧiv:math.CO/0406301 .
Globerson, Amir; Jaakkola, Tommi (2007), "Approximate inference using planar graph decomposition", Advances in Neural Information Processing Systems 19, MIT Press .
Schraudolph, Nicol; Kamenetsky, Dmitry (2009), "Efficient exact inference in planar Ising models", Advances in Neural Information Processing Systems 21, MIT Press .
The Games and Puzzles Journal, No.14, 1996, pp.204-5, Robin J. Chapman, University of Exeter
Domino Tilings and Products of Fibonacci and Pell numbers, 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, Online
Skew-Symmetric Determinants, The American Mathematical Monthly, vol. 61, no.2., 1954, p.116, S. Parameswaran JSTOR link

External links

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 OEIS)

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

Pfaffian

Contents