In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of a
skew-symmetric matrix
In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition
In terms of the entries of the matrix, if a_ ...
can always be written as the square of a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
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 who indirectly named them after
Johann Friedrich Pfaff
Johann Friedrich Pfaff (sometimes spelled Friederich; 22 December 1765 – 21 April 1825) was a German mathematician. He was described as one of Germany's most eminent mathematicians during the 19th century. He was a precursor of the German school ...
. The Pfaffian (considered as a polynomial) is nonvanishing only for 2''n'' × 2''n'' skew-symmetric matrices, in which case it is a polynomial of degree ''n''.
Explicitly, for a skew-symmetric matrix
,
:
which was first proved by , who cites
Jacobi Jacobi may refer to:
* People with the surname Jacobi (surname), Jacobi
Mathematics:
* Jacobi sum, a type of character sum
* Jacobi method, a method for determining the solutions of a diagonally dominant system of linear equations
* Jacobi eigenva ...
for introducing these polynomials in work on
Pfaffian
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, ...
systems of differential equations. Caley obtains this relation by specialising a more general result on matrices which 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 negative transpose of the first row to the first column and the negative transpose of the first column to the first row. This is proved by induction by expanding the determinant on minors and employing the recursion formula below.
Examples
:
:
(3 is odd, so the Pfaffian of B is 0)
:
The Pfaffian of a 2''n'' × 2''n'' skew-symmetric
tridiagonal matrix
In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal below this), and the supradiagonal/upper diagonal (the first diagonal above the main di ...
is given as
:
(Note that any skew-symmetric matrix can be reduced to this form with all
equal to zero; see
Spectral theory of a skew-symmetric matrix.)
Formal definition
Let ''A'' = (''a''
''i,j'') be a 2''n'' × 2''n'' skew-symmetric matrix. The Pfaffian of ''A'' is explicitly defined by the formula
:
where ''S''
2''n'' is the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
of order (2''n'')! and sgn(σ) is the
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
of σ.
One can make use of the skew-symmetry of ''A'' to avoid summing over all possible
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
s. Let Π be the set of all
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
s of into pairs without regard to order. There are (2''n'')!/(2
''n''''n''!) = (2''n'' - 1)
!! such partitions. An element α ∈ Π can be written as
:
with ''i''
''k'' < ''j''
''k'' and
. Let
:
be the corresponding permutation. Given a partition α as above, define
:
The Pfaffian of ''A'' is then given by
:
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,
and for ''n'' odd, this implies
.
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
:
where index ''i'' can be selected arbitrarily,
is the
Heaviside step function
The Heaviside step function, or the unit step function, usually denoted by or (but sometimes , or ), is a step function, named after Oliver Heaviside (1850–1925), the value of which is zero for negative arguments and one for positive argume ...
, and
denotes the matrix ''A'' with both the ''i''-th and ''j''-th rows and columns removed. Note how for the special choice
this reduces to the simpler expression:
:
Alternative definitions
One can associate to any skew-symmetric 2''n''×2''n'' matrix ''A'' =(''a''
''ij'') a
bivector In mathematics, a bivector or 2-vector is a quantity in exterior algebra or geometric algebra that extends the idea of scalar (mathematics), scalars and Euclidean vector, vectors. If a scalar is considered a degree-zero quantity, and a vector is a d ...
:
where is the standard basis of R
2n. The Pfaffian is then defined by the equation
:
here ω
''n'' denotes the
wedge product
A wedge is a triangular shaped tool, and is a portable inclined plane, and one of the six simple machines. It can be used to separate two objects or portions of an object, lift up an object, or hold an object in place. It functions by converti ...
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. In particular for any ''m'' x ''m'' matrix ''A'', we use the formal definition above but set
. 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'' × 2''n'' skew-symmetric matrix ''A''
:
:
:
For an arbitrary 2''n'' × 2''n'' matrix ''B'',
:
Substituting in this equation ''B = A
m'', one gets for all integer ''m''
:
Derivative identities
If ''A'' depends on some variable ''x''
''i'', then the gradient of a Pfaffian is given by
:
and the
Hessian
A Hessian is an inhabitant of the German state of Hesse.
Hessian may also refer to:
Named from the toponym
*Hessian (soldier), eighteenth-century German regiments in service with the British Empire
**Hessian (boot), a style of boot
**Hessian f ...
of a Pfaffian is given by
:
Trace identities
The product of the Pfaffians of skew-symmetric matrices ''A'' and ''B'' can be represented in the form of an exponential
:
Suppose ''A'' and ''B'' are ''2n × 2n'' skew-symmetric matrices, then
:
and ''B''
n(''s''
1,''s''
2,...,''s''
n) are
Bell polynomials
In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are used in the study of set partitions. They are related to Stirling and Bell numbers. They also occur in many applications, such as in the Faà di Bruno's fo ...
.
Block matrices
For a block-diagonal matrix
::
:
For an arbitrary ''n'' × ''n'' matrix ''M'':
:
It is often required to compute the pfaffian of a skew-symmetric matrix
with the block structure
:
where
and
are skew-symmetric matrices and
is a general rectangular matrix.
When
is invertible, one has
:
This can be seen from Aitken block-diagonalization formula,
[Bunch, James R. "A note on the stable decomposition of skew-symmetric matrices." Mathematics of Computation 38.158 (1982): 475-479.]
:
This decomposition involves a
congruence transformations that allow to use the pfaffian property
.
Similarly, when
is invertible, one has
:
as can be seen by employing the decomposition
:
Calculating the Pfaffian numerically
Suppose ''A'' is a ''2n × 2n'' skew-symmetric matrices, then
:
where
is the second
Pauli matrix
In mathematical physics and mathematics, the Pauli matrices are a set of three complex matrices which are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma (), they are occasionally denoted by tau () when used in c ...
,
is an identity matrix of dimension ''n'' and we took the trace over a
matrix logarithm
In mathematics, a logarithm of a matrix is another matrix such that the matrix exponential of the latter matrix equals the original matrix. It is thus a generalization of the scalar logarithm and in some sense an inverse function of the matrix exp ...
.
This equality is based on the
trace identity In mathematics, a trace identity is any equation involving the trace of a matrix.
Properties
Trace identities are invariant under simultaneous conjugation.
Uses
They are frequently used in the invariant theory of n \times n matrices to find th ...
:
and on the observation that
.
Since calculating the
logarithm of a matrix
In mathematics, a logarithm of a matrix is another matrix such that the matrix exponential of the latter matrix equals the original matrix. It is thus a generalization of the scalar logarithm and in some sense an inverse function of the matrix exp ...
is a computationally demanding task, one can instead compute all eigenvalues of
, take the log of all of these and sum them up. This procedure merely exploits the
property
Property is a system of rights that gives people legal control of valuable things, and also refers to the valuable things themselves. Depending on the nature of the property, an owner of property may have the right to consume, alter, share, r ...
. This can be implemented in
Mathematica
Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...
within a single line:
Pf _:= Module 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
will generally be complex, and the logarithm of these complex eigenvalues are generally taken to be in
. Under the summation, for a real valued Pfaffian, the argument of the exponential will be given in the form
for some integer
. When
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 see .
Applications
*There exist programs for the numerical computation of the Pfaffian on various platforms (Python, Matlab, Mathematica) .
*The Pfaffian is an
invariant polynomial In mathematics, an invariant polynomial is a polynomial P that is invariant under a group \Gamma acting on a vector space V. Therefore, P is a \Gamma-invariant polynomial if
:P(\gamma x) = P(x)
for all \gamma \in \Gamma and x \in V.
Cases of p ...
of a skew-symmetric matrix under a proper
orthogonal
In mathematics, orthogonality is the generalization of the geometric notion of ''perpendicularity''.
By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
change of basis. As such, it is important in the theory of
characteristic class
In mathematics, a characteristic class is a way of associating to each principal bundle of ''X'' a cohomology class of ''X''. The cohomology class measures the extent the bundle is "twisted" and whether it possesses sections. Characteristic classes ...
es. In particular, it can be used to define the
Euler class
In mathematics, specifically in algebraic topology, the Euler class is a characteristic class of oriented, real vector bundles. Like other characteristic classes, it measures how "twisted" the vector bundle is. In the case of the tangent bundle of ...
of a
Riemannian manifold
In differential geometry, a Riemannian manifold or Riemannian space , so called after the German mathematician Bernhard Riemann, is a real manifold, real, smooth manifold ''M'' equipped with a positive-definite Inner product space, inner product ...
which is used in the
generalized Gauss–Bonnet theorem
A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set of elements, as well as one or more common characte ...
.
*The number of
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
s in a
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
is given by a Pfaffian, hence is polynomial time computable via the
FKT algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, ...
. 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 tiling
In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by p ...
s of a rectangle, the
partition function of
Ising model
The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
s in physics, or of
Markov random field
In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. In other words, a random field is said to b ...
s in
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
(; ), 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
In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains un ...
for more information.
See also
*
Determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
*
Dimer model
In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by p ...
*
Hafnian
In mathematics, the hafnian of an adjacency matrix of a graph is the number of perfect matchings in the graph. It was so named by Eduardo R. Caianiello "to mark the fruitful period of stay in Copenhagen (Hafnia in Latin)."
The hafnian of a 2n\t ...
*
Polyomino
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.
Polyominoes have been used in pop ...
*
Statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
Notes
References
*
* Reprinted in Collected mathematical papers, volume 2.
*
*
*
*
*
*
*
*
''Online''*
*
*
External links
*
* 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?''* {{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
Determinants
Multilinear algebra