- Source: Pfaffian
In mathematics, the determinant of an m-by-m skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depends on m. When m is odd, the polynomial is zero, and when m is even, it is a nonzero polynomial of degree m/2, and is unique up to multiplication by ±1. The convention on skew-symmetric tridiagonal matrices, given below in the examples, then determines one specific polynomial, called the Pfaffian polynomial. The value of this polynomial, when applied to the entries of a skew-symmetric matrix, is called the Pfaffian of that matrix. The term Pfaffian was introduced by Cayley (1852), who indirectly named them after Johann Friedrich Pfaff.
Explicitly, for a skew-symmetric matrix
A
{\displaystyle A}
,
pf
(
A
)
2
=
det
(
A
)
,
{\displaystyle \operatorname {pf} (A)^{2}=\det(A),}
which was first proved by Cayley (1849), who cites Jacobi for introducing these polynomials in work on Pfaffian systems of differential equations. Cayley obtains this relation by specialising a more general result on matrices that 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
A
=
[
0
a
−
a
0
]
,
pf
(
A
)
=
a
.
{\displaystyle A={\begin{bmatrix}0&a\\-a&0\end{bmatrix}},\qquad \operatorname {pf} (A)=a.}
B
=
[
0
a
b
−
a
0
c
−
b
−
c
0
]
,
pf
(
B
)
=
0.
{\displaystyle B={\begin{bmatrix}0&a&b\\-a&0&c\\-b&-c&0\end{bmatrix}},\qquad \operatorname {pf} (B)=0.}
(3 is odd, so the Pfaffian of B is 0)
pf
[
0
a
b
c
−
a
0
d
e
−
b
−
d
0
f
−
c
−
e
−
f
0
]
=
a
f
−
b
e
+
d
c
.
{\displaystyle \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
pf
[
0
a
1
0
0
−
a
1
0
0
0
0
0
0
a
2
0
0
−
a
2
0
⋱
⋱
⋱
0
a
n
−
a
n
0
]
=
a
1
a
2
⋯
a
n
.
{\displaystyle \operatorname {pf} {\begin{bmatrix}0&a_{1}&0&0\\-a_{1}&0&0&0\\0&0&0&a_{2}\\0&0&-a_{2}&0&\ddots \\&&&\ddots &\ddots &\\&&&&&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; see Spectral theory of a skew-symmetric matrix.)
Formal definition
Let A = (aij) be a 2n × 2n skew-symmetric matrix. The Pfaffian of A is explicitly defined by the formula
pf
(
A
)
=
1
2
n
n
!
∑
σ
∈
S
2
n
sgn
(
σ
)
∏
i
=
1
n
a
σ
(
2
i
−
1
)
,
σ
(
2
i
)
,
{\displaystyle \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 S2n is the symmetric group of degree 2n 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)!/(2nn!) = (2n − 1)!! such partitions. An element α ∈ Π can be written as
α
=
{
(
i
1
,
j
1
)
,
(
i
2
,
j
2
)
,
⋯
,
(
i
n
,
j
n
)
}
{\displaystyle \alpha =\{(i_{1},j_{1}),(i_{2},j_{2}),\cdots ,(i_{n},j_{n})\}}
with ik < jk and
i
1
<
i
2
<
⋯
<
i
n
{\displaystyle i_{1}
. Let
π
α
=
[
1
2
3
4
⋯
2
n
−
1
2
n
i
1
j
1
i
2
j
2
⋯
i
n
j
n
]
{\displaystyle \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}}}
be the corresponding permutation. Given a partition α as above, define
A
α
=
sgn
(
π
α
)
a
i
1
,
j
1
a
i
2
,
j
2
⋯
a
i
n
,
j
n
.
{\displaystyle A_{\alpha }=\operatorname {sgn} (\pi _{\alpha })a_{i_{1},j_{1}}a_{i_{2},j_{2}}\cdots a_{i_{n},j_{n}}.}
The Pfaffian of A is then given by
pf
(
A
)
=
∑
α
∈
Π
A
α
.
{\displaystyle \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
,
{\displaystyle \det A=\det A^{\text{T}}=\det(-A)=(-1)^{n}\det A,}
and for n odd, this implies
det
A
=
0
{\displaystyle \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
pf
(
A
)
=
∑
j
=
1
j
≠
i
2
n
(
−
1
)
i
+
j
+
1
+
θ
(
i
−
j
)
a
i
j
pf
(
A
ı
^
ȷ
^
)
,
{\displaystyle \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 }}}),}
where the index i can be selected arbitrarily,
θ
(
i
−
j
)
{\displaystyle \theta (i-j)}
is the Heaviside step function, and
A
ı
^
ȷ
^
{\displaystyle A_{{\hat {\imath }}{\hat {\jmath }}}}
denotes the matrix A with both the i-th and j-th rows and columns removed. Note how for the special choice
i
=
1
{\displaystyle i=1}
this reduces to the simpler expression:
pf
(
A
)
=
∑
j
=
2
2
n
(
−
1
)
j
a
1
j
pf
(
A
1
^
ȷ
^
)
.
{\displaystyle \operatorname {pf} (A)=\sum _{j=2}^{2n}(-1)^{j}a_{1j}\operatorname {pf} (A_{{\hat {1}}{\hat {\jmath }}}).}
= Alternative definitions
=One can associate to any skew-symmetric 2n × 2n matrix A = (aij) a bivector
ω
=
∑
i
<
j
a
i
j
e
i
∧
e
j
,
{\displaystyle \omega =\sum _{i
where {e1, e2, ..., e2n} is the standard basis of R2n. The Pfaffian is then defined by the equation
1
n
!
ω
n
=
pf
(
A
)
e
1
∧
e
2
∧
⋯
∧
e
2
n
,
{\displaystyle {\frac {1}{n!}}\omega ^{n}=\operatorname {pf} (A)\;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n},}
here ω n denotes the wedge product of n copies of ω.
Equivalently, we can consider the bivector (which is more convenient when we do not want to impose the summation constraint
i
<
j
{\displaystyle i
):
ω
′
=
2
ω
=
∑
i
,
j
a
i
j
e
i
∧
e
j
,
{\displaystyle \omega '=2\omega =\sum _{i,j}a_{ij}\;e_{i}\wedge e_{j},}
which gives
ω
′
n
=
2
n
n
!
pf
(
A
)
e
1
∧
e
2
∧
⋯
∧
e
2
n
.
{\displaystyle \omega '^{n}=2^{n}n!\operatorname {pf} (A)\;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n}.}
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 × m matrix A, we use the formal definition above but set
n
=
⌊
m
/
2
⌋
{\displaystyle n=\lfloor m/2\rfloor }
. For m odd, one can then show that this is equal to the usual Pfaffian of an (m+1) × (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 2n × 2n skew-symmetric matrix A
pf
(
A
T
)
=
(
−
1
)
n
pf
(
A
)
.
{\displaystyle \operatorname {pf} (A^{\text{T}})=(-1)^{n}\operatorname {pf} (A).}
pf
(
λ
A
)
=
λ
n
pf
(
A
)
.
{\displaystyle \operatorname {pf} (\lambda A)=\lambda ^{n}\operatorname {pf} (A).}
pf
(
A
)
2
=
det
(
A
)
.
{\displaystyle \operatorname {pf} (A)^{2}=\det(A).}
For an arbitrary 2n × 2n matrix B,
pf
(
B
A
B
T
)
=
det
(
B
)
pf
(
A
)
.
{\displaystyle \operatorname {pf} (BAB^{\text{T}})=\det(B)\operatorname {pf} (A).}
Substituting in this equation B = Am, one gets for all integer m
pf
(
A
2
m
+
1
)
=
(
−
1
)
n
m
pf
(
A
)
2
m
+
1
.
{\displaystyle \operatorname {pf} (A^{2m+1})=(-1)^{nm}\operatorname {pf} (A)^{2m+1}.}
= Derivative identities
=If A depends on some variable xi, then the gradient of a Pfaffian is given by
1
pf
(
A
)
∂
pf
(
A
)
∂
x
i
=
1
2
tr
(
A
−
1
∂
A
∂
x
i
)
,
{\displaystyle {\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
1
pf
(
A
)
∂
2
pf
(
A
)
∂
x
i
∂
x
j
=
1
2
tr
(
A
−
1
∂
2
A
∂
x
i
∂
x
j
)
−
1
2
tr
(
A
−
1
∂
A
∂
x
i
A
−
1
∂
A
∂
x
j
)
+
1
4
tr
(
A
−
1
∂
A
∂
x
i
)
tr
(
A
−
1
∂
A
∂
x
j
)
.
{\displaystyle {\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).}
= Trace identities
=The product of the Pfaffians of skew-symmetric matrices A and B can be represented in the form of an exponential
pf
(
A
)
pf
(
B
)
=
exp
(
1
2
t
r
log
(
A
T
B
)
)
.
{\displaystyle {\textrm {pf}}(A)\,{\textrm {pf}}(B)=\exp({\tfrac {1}{2}}\mathrm {tr} \log(A^{\text{T}}B)).}
Suppose A and B are 2n × 2n skew-symmetric matrices, then
p
f
(
A
)
p
f
(
B
)
=
1
n
!
B
n
(
s
1
,
s
2
,
…
,
s
n
)
,
w
h
e
r
e
s
l
=
−
1
2
(
l
−
1
)
!
t
r
(
(
A
B
)
l
)
{\displaystyle \mathrm {pf} (A)\,\mathrm {pf} (B)={\tfrac {1}{n!}}B_{n}(s_{1},s_{2},\ldots ,s_{n}),\qquad \mathrm {where} \qquad s_{l}=-{\tfrac {1}{2}}(l-1)!\,\mathrm {tr} ((AB)^{l})}
and Bn(s1,s2,...,sn) are Bell polynomials.
= Block matrices
=For a block-diagonal matrix
A
1
⊕
A
2
=
[
A
1
0
0
A
2
]
,
{\displaystyle A_{1}\oplus A_{2}={\begin{bmatrix}A_{1}&0\\0&A_{2}\end{bmatrix}},}
pf
(
A
1
⊕
A
2
)
=
pf
(
A
1
)
pf
(
A
2
)
.
{\displaystyle \operatorname {pf} (A_{1}\oplus A_{2})=\operatorname {pf} (A_{1})\operatorname {pf} (A_{2}).}
For an arbitrary n × n matrix M:
pf
[
0
M
−
M
T
0
]
=
(
−
1
)
n
(
n
−
1
)
/
2
det
M
.
{\displaystyle \operatorname {pf} {\begin{bmatrix}0&M\\-M^{\text{T}}&0\end{bmatrix}}=(-1)^{n(n-1)/2}\det M.}
It is often required to compute the Pfaffian of a skew-symmetric matrix
S
{\displaystyle S}
with the block structure
S
=
(
M
Q
−
Q
T
N
)
{\displaystyle S={\begin{pmatrix}M&Q\\-Q^{\mathrm {T} }&N\end{pmatrix}}\,}
where
M
{\displaystyle M}
and
N
{\displaystyle N}
are skew-symmetric matrices and
Q
{\displaystyle Q}
is a general rectangular matrix.
When
M
{\displaystyle M}
is invertible, one has
pf
(
S
)
=
pf
(
M
)
pf
(
N
+
Q
T
M
−
1
Q
)
.
{\displaystyle \operatorname {pf} (S)=\operatorname {pf} (M)\operatorname {pf} (N+Q^{\mathrm {T} }M^{-1}Q).}
This can be seen from Aitken block-diagonalization formula,
(
M
0
0
N
+
Q
T
M
−
1
Q
)
=
(
I
0
Q
T
M
−
1
I
)
(
M
Q
−
Q
T
N
)
(
I
−
M
−
1
Q
0
I
)
.
{\displaystyle {\begin{pmatrix}M&0\\0&N+Q^{\mathrm {T} }M^{-1}Q\end{pmatrix}}={\begin{pmatrix}I&0\\Q^{\mathrm {T} }M^{-1}&I\end{pmatrix}}{\begin{pmatrix}M&Q\\-Q^{\mathrm {T} }&N\end{pmatrix}}{\begin{pmatrix}I&-M^{-1}Q\\0&I\end{pmatrix}}.}
This decomposition involves a congruence transformations that allow to use the Pfaffian property
pf
(
B
A
B
T
)
=
det
(
B
)
pf
(
A
)
{\displaystyle \operatorname {pf} (BAB^{\mathrm {T} })=\operatorname {det} (B)\operatorname {pf} (A)}
.
Similarly, when
N
{\displaystyle N}
is invertible, one has
pf
(
S
)
=
pf
(
N
)
pf
(
M
+
Q
N
−
1
Q
T
)
,
{\displaystyle \operatorname {pf} (S)=\operatorname {pf} (N)\operatorname {pf} (M+QN^{-1}Q^{\mathrm {T} }),}
as can be seen by employing the decomposition
(
M
+
Q
N
−
1
Q
T
0
0
N
)
=
(
I
−
Q
N
−
1
0
I
)
(
M
Q
−
Q
T
N
)
(
I
0
N
−
1
Q
T
I
)
.
{\displaystyle {\begin{pmatrix}M+QN^{-1}Q^{\mathrm {T} }&0\\0&N\end{pmatrix}}={\begin{pmatrix}I&-QN^{-1}\\0&I\end{pmatrix}}{\begin{pmatrix}M&Q\\-Q^{\mathrm {T} }&N\end{pmatrix}}{\begin{pmatrix}I&0\\N^{-1}Q^{\mathrm {T} }&I\end{pmatrix}}.}
Calculating the Pfaffian numerically
Suppose A is a 2n × 2n skew-symmetric matrices, then
pf
(
A
)
=
i
(
n
2
)
exp
(
1
2
t
r
log
(
(
σ
y
⊗
I
n
)
T
⋅
A
)
)
,
{\displaystyle {\textrm {pf}}(A)=i^{(n^{2})}\exp \left({\tfrac {1}{2}}\mathrm {tr} \log((\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A)\right),}
where
σ
y
{\displaystyle \sigma _{y}}
is the second Pauli matrix,
I
n
{\displaystyle I_{n}}
is an identity matrix of dimension n and we took the trace over a matrix logarithm.
This equality is based on the trace identity
pf
(
A
)
pf
(
B
)
=
exp
(
1
2
t
r
log
(
A
T
B
)
)
{\displaystyle {\textrm {pf}}(A)\,{\textrm {pf}}(B)=\exp \left({\tfrac {1}{2}}\mathrm {tr} \log(A^{\text{T}}B)\right)}
and on the observation that
pf
(
σ
y
⊗
I
n
)
=
(
−
i
)
n
2
{\displaystyle {\textrm {pf}}(\sigma _{y}\otimes I_{n})=(-i)^{n^{2}}}
.
Since calculating the logarithm of a matrix is a computationally demanding task, one can instead compute all eigenvalues of
(
(
σ
y
⊗
I
n
)
T
⋅
A
)
{\displaystyle ((\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A)}
, take the log of all of these and sum them up. This procedure merely exploits the property
tr
log
(
A
B
)
=
tr
log
(
A
)
+
tr
log
(
B
)
{\displaystyle \operatorname {tr} {\log {(AB)}}=\operatorname {tr} {\log {(A)}}+\operatorname {tr} {\log {(B)}}}
. This can be implemented in Mathematica with a single statement:
Pf[x_] := Module[{n = Dimensions[x][[1]] / 2}, 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
(
σ
y
⊗
I
n
)
T
⋅
A
{\displaystyle (\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A}
will generally be complex, and the logarithm of these complex eigenvalues are generally taken to be in
[
−
π
,
π
]
{\displaystyle [-\pi ,\pi ]}
. Under the summation, for a real valued Pfaffian, the argument of the exponential will be given in the form
x
+
k
π
/
2
{\displaystyle x+k\pi /2}
for some integer
k
{\displaystyle k}
. When
x
{\displaystyle x}
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 Wimmer 2012.
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 that 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. See Holographic algorithm for more information.
See also
Determinant
Dimer model
Hafnian
Polyomino
Statistical mechanics
Notes
References
External links
Kata Kunci Pencarian:
- Determinan
- Daftar topik aljabar linear
- Frank Wilczek
- Johann Friedrich Pfaff
- Daftar singkatan matematis
- Integral Berezin
- Pfaffian
- Pfaffian function
- Pfaffian orientation
- Integrability conditions for differential systems
- Holonomic constraints
- Pfaffian constraint
- Johann Friedrich Pfaff
- FKT algorithm
- One-form (differential geometry)
- O-minimal theory
