Overlapping Pfaffians

Donald E. Knuth, Computer Science Department, Stanford University

To Dominique Cyprien Foata on his 60th birthday

Submitted: March 16, 1995; Accepted: May 14, 1995

Abstract. A combinatorial construction proves an identity for the product of the Pfaffian of a skew-symmetric matrix by the Pfaffian of one of its submatrices. Several applications of this identity are followed by a brief history of Pfaffians.

0. Definitions. Let X be a possibly infinite index set. We consider quantities f[xy] defined on ordered pairs of elements of X, satisfying the law of skew symmetry

f[xy] = −f[yx] ,  for x, y ∈ X .  (0.0)

This notation is extended to f[α] for arbitrary words α = x_{1} … x_{2n} of even length over X by defining the Pfaffian

f[x_{1} … x_{2n}] = ∑ s(x_{1} … x_{2n}, y_{1} … y_{2n}) f[y_{1}y_{2}] … f[y_{2n−1}y_{2n}] ,  (0.1)

where the sum is over all (2n − 1)(2n − 3) … (1) ways to write {x_{1}, … x_{2n}} as a union of pairs {y_{1}, y_{2}} ∪ ⋯ ∪ {y_{2n−1}, y_{2n}}, and where s(x_{1} … x_{2n}, y_{1} … y_{2n}) is the sign of the permutation that takes x_{1} … x_{2n} into y_{1} … y_{2n}.

The Pfaffian is well defined, even though there are 2^{n}n! different permutations y_{1} … y_{2n} that yield the same partition {y_{1}, y_{2}}∪…∪{y_{2n−1}, y_{2n}} into pairs. For if we interchange y_{2j−1} with y_{2j}, we change the sign of both s(x_{1} … x_{2n}, y_{1} … y_{2n}) and f[y_{1}, y_{2}] … f[y_{2n−1}y_{n}], by (0.0); if we interchange y_{2i−1} with y_{2j−1} and y_{2i} with y_{2j}, both factors stay the same. Thus, for example,

f[wxyz] = f[wx]f[yz] − f[wy]f[xz] + f[wz]f[xy]
= f[wx]f[yz] + f[wy]f[zx] + f[wz]f[xy] .  (0.2)

A partition into pairs is commonly called a perfect matching. Therefore it is convenient to abbreviate (0.1) in the form

f[α] = ∑_{μ∈M(α)} s(α, μ) Πf[μ]  (0.3)

where M(α) is the set of perfect matchings of α represented as words y_{1} … y_{2n} in some canonical way, and Πf[y_{1} … y_{2n}] = f[y_{1}y_{2}] … f[y_{2n−1}y_{2n}].

Notice that we have

f[wxyz] = −f[xyzw] .  (0.4)

In general, an odd permutation of α will reverse the sign of f[α], because every term in (0.3) changes sign.

Pfaffians can also be defined recursively, starting with the null word ϵ and proceeding to words of greater length:

f[ϵ] = 1 ;
f[x_{1} … x_{2n}] = ∑_{j=2}^{2n} f[x_{1}x_{j}]f[x_{j+1} … x_{2n}x_{2} … x_{j−1}] ,  n > 0 .  (0.5)

This recurrence [9] corresponds to a procedure that constructs all perfect matchings by starting with {x_{1}, x_{2}} ∪ ⋯ ∪ {x_{2n−1}, x_{2n}} and making cyclic permutations of the indices in positions {2, …, 2n}, {4, …, 2n}, …; each of these permutations is even.

It will be convenient in the sequel to extend the sign function s to s(α, β) for arbitrary words α, β ∈ X^{∗}. We define s(α, β) = 0 if either α or β has a repeated letter, or if β contains a letter not in α. Otherwise s(α, β) is the sign of the permutation that takes α into the word

β (α\β) ,

where α\β is the word that remains when the elements of β are removed from α. Thus, for example,

s(αβγ, β) = \begin{cases}0 , & if αβγ contains a repeated letter; \\ (−1)^{|α| |β|} , & otherwise. \end{cases}  (0.6)

We also have

s(α, βγ) = s(α, β)s(α\β, γ) ,  (0.7)

since both sides vanish unless the letters of βγ are distinct and contained in the distinct letters of α, and in the latter case s(α, βγ) is the parity of the number of transpositions needed to bring β to the left of α and γ to the left of the remaining word α\β.

If α has repeated letters, the Pfaffian f[α] is zero, because f[α] = −f[α] when we transpose two identical letters. Therefore our convention that s(α, β) = 0 when α or β has repeated letters does not invalidate definition (0.1), which used a different convention for s(x_{1} … x_{2n}, y_{1} … y_{2n}). One consequence of the new convention is the identity

f[α] = ∑_{x_{1}<···<x_{n}} ∑_{y_{1}>x_{1}} ⋯ ∑_{y_{n}>x_{n}} s(α, x_{1}y_{1} … x_{n}y_{n}) f[x_{1}y_{1}] … f[x_{n}y_{n}]  (0.8)

for any word α of length 2n, assuming that X is an ordered set; the sum is over all conceivable perfect matchings μ = x_{1}y_{1} … x_{n}y_{n}, but s(α, μ) is zero unless μ is a perfect matching of α.

1. The basic identity. The following identity due to H. W. L. Tanner [24] can now be proved:

f[α] f[αβ] = ∑_{y} s(β, xy) f[αxy] f[αβ\xy] ,  for all x ∈ β.  (1.0)

This formula is vacuous when |β| = 0 and trivial when |β| = 2, but when |β| = 4 it says in particular that

f[α] f[αwxyz] = f[αwx] f[αyz] − f[αwy] f[αxz] + f[αwz] f[αxy]
= f[αwx] f[αyz] + f[αwy] f[αzx] + f[αwz] f[αxy] .  (1.1)

We will demonstrate (1.0) by giving a combinatorial interpretation to each term on the left and right sides of the equation, when the Pfaffians are expanded as sums over perfect matchings.

A typical term on the right of (1.0) is

s(β, xy) s(αxy, μ) s(αβ\xy, ν) Πf[μ] Πf[ν] ,  (1.2)

where x and y are distinct elements of β, μ is a perfect matching of αxy, and ν is a perfect matching of αβ\xy. Ignoring the sign for the moment, we can construct a graph by superimposing the matchings μ and ν. In this graph all vertices of α have degree 2 because they are matched in both μ and ν; all vertices of β have degree 1.

There is a unique maximal path that starts at y and uses edges from μ and ν alternately. This path ends at some element of β, call it z. Let μ_{1} and ν_{1} be the edges of μ and ν on this path; let μ_{0} and ν_{0} be the other edges. Then we define corresponding matchings

μ′ = μ_{0} ∪ ν_{1} ,  ν′ = ν_{0} ∪ μ_{1} ,  (1.3)

which will be the key to establishing (1.0).

Case 1, z ≠ x. In this case |μ_{1}| = |ν_{1}|, since the path from y starts with an element of μ and ends with an element of ν. Thus the matchings μ′ and ν′ correspond to another term on the right side of (1.0); we will prove that this other term cancels with (1.2). Since μ′′ = μ and ν′′ = ν, this will set up an involution between cancelling terms.

We have

Πf[μ] Πf[ν] = Πf[μ_{0}] Πf[μ_{1}] Πf[ν_{0}] Πf[ν_{1}] = Πf[μ′] Πf[ν′] ,  (1.4)

so (1.2) will cancel with its counterpart if the signs differ. The sign of (1.2) is

s(αxyz, μ_{0}μ_{1}z) s(αβ, xyν_{0}ν_{1}) ,  (1.5)

because s(β, xy) = s(αβ, xy) and s(αβ, xy) s(αβ\xy, ν) = s(αβ, xyν) by (0.7). The sign of the permutation that takes μ_{1}z into ν_{1}y is the same as the sign of the permutation that takes yν_{0}ν_{1} into zν_{0}μ_{1}, hence (1.5) equals

s(αxyz, μ_{0}ν_{1}y) s(αβ, xzν_{0}μ_{1}) .

But this is the negative of s(αxzy, μ_{0}ν_{1}y) s(αβ, xzν_{0}μ_{1}), the sign of the term that corresponds to μ′ and ν′.

Case 2, z = x. In this case we have |μ_{1}| = |ν_{1}| + 2, since μ_{1} includes both x and y while ν_{1} is contained in α. It follows that μ′ and ν′ are perfect matchings of α and αβ, respectively, so they define a typical term

s(α, μ′) s(αβ, ν′) Πf[μ′] Πf[ν′]  (1.6)

from the left side of (1.0). Conversely, every such term corresponds to matchings μ and ν for a uniquely defined term (1.2) on the right. The sign of this term,

s(αxy, μ_{0}μ_{1}) s(αβ, xyν_{0}ν_{1}) ,

agrees with s(α, μ′) s(αβ, ν′) = s(αxy, μ_{0}ν_{1}xy) s(αβ, ν_{0}μ_{1}), because the permutation that takes μ_{1} into ν_{1}xy has the same sign as the permutation that takes xyν_{0}ν_{1} into ν_{0}μ_{1}.

2. Basic applications. The special case α = ϵ of (1.0) reads

f[β] = ∑_{y} s(β, xy) f[xy] f[β\xy] ,  for all x ∈ β.  (2.0)

This is a mild generalization of the recurrence (0.5); it tells us how to expand f[β] with respect to any element of β. We can get rid of the constraint x ∈ β by summing over all x:

f[β] = \frac{1}{|β|} ∑_{x} ∑_{y} s(β, xy) f[xy] f[β\xy] .  (2.1)

Applying this rule to f[β\xy] and repeating until words of length 2 are reached yields a |β|-fold sum,

f[β] = \frac{1}{(2n)(2n − 2) … 2} ∑_{x_{1}} ⋯ ∑_{x_{2n}} s(β, x_{1} … x_{2n}) f[x_{1}x_{2}] … f[x_{2n−1}x_{2n}] ,  (2.2)

when |β| = 2n; this is, of course, the same as (0.8) when we collect equal terms.

Now let α be a fixed word such that f[α] ≠ 0, and consider the function

g(β) = f[αβ]/f[α]  (2.3)

on the words of X. Tanner’s identity (1.0) tells us that

g(β) = ∑_{y} s(β, xy) g(xy) g(β\xy) ,  for all x ∈ β.  (2.4)

But this is the same relation as (2.0); so g satisfies the Pfaffian recurrence (0.5). Therefore any identity for Pfaffians leads a fortiori to an identity for g. In particular, (0.3) tells us that

g(β) = ∑_{μ∈M(β)} s(β, μ) Πg(μ) ,

which is equivalent to

f[α]^{n−1} f[αβ] = ∑_{M(β)} s(β, x_{1}y_{1} … x_{n}y_{n}) f[αx_{1}y_{1}] … f[αx_{n}y_{n}]  (2.5)

when |β| = 2n, where the sum is over all perfect matchings x_{1}y_{1} … x_{n}y_{n} of β. The special case n = 2 appears in (1.1).

We can also construct a dual formula by starting with a fixed αβ such that f[αβ] ≠ 0 and defining

h(γ) = s(αβ, γ) f[αβ\γ]/f[αβ]  (2.6)

on the words γ contained in αβ. Then (1.0) yields

h(β) = ∑_{y} s(β, xy) h(β\xy) h(xy) ,  for all x ∈ β;  (2.7)

so we can derive a companion to (2.5) in a similar fashion:

f[α] f[αβ]^{n−1} = ∑_{M(β)} s(β, x_{1}y_{1} … x_{n}y_{n}) f[αβ\x_{1}y_{1}] … f[αβ\x_{n}y_{n}] .  (2.8)

Identities (2.4) and (2.7) are the Pfaffian analogs of theorems about determinants that Muir called the Law of Extensible Minors and the Law of Complementaries. (See [15], §179 and §98 in the original edition; §187 and §179 in Metzler’s revision.)

3. Applications to determinants. Determinants are the special case of Pfaffians in which the index set is bipartite with respect to f, in the sense that f[xy] = 0 when x and y belong to the same part. It is convenient to imagine that the set of indices consists of two disjoint parts X and X̄, so that x belongs to X if and only if x̄ belongs to X̄, and f[xy] = f[x̄ ȳ] = 0 for all x, y ∈ X. The independent quantities are now f[xȳ] = −f[ȳx]; we can regard X as a set of “rows” and X̄ as a set of “columns,” so that f[xȳ] is essentially an element of the matrix f. We use f[x, y] as an alternative notation for f[xȳ]. In fact, when α and β are arbitrary words of X we write

f[α, β] = f[αβ̄^{R}]  (3.0)

for the determinant formed from rows α and columns β. Here β̄^{R} stands for the reverse complement of β:

\overline{y_{1}y_{2} … y_{n}}^{R} = ȳ_{n} … ȳ_{2}ȳ_{1} .  (3.1)

Definition (3.0) agrees with the usual definition of determinants, when |α| = |β| = n, since the perfect matchings of αβ̄^{R} that do not have vanishing products correspond to the products

f[x_{1}ȳ_{1}] … f[x_{n}ȳ_{n}] = f[x_{1}, y_{1}] … f[x_{n}, y_{n}] ,  (3.2)

where α = x_{1} … x_{n} and y_{1} … y_{n} is a permutation of β; the corresponding sign s(αβ̄^{R}, x_{1}ȳ_{1} … x_{n}ȳ_{n}) is just s(β, y_{1} … y_{n}), because the permutation that takes x_{1} … x_{n}ȳ_{n} … ȳ_{1} to x_{1}ȳ_{1} … x_{n}ȳ_{n} is even. For example, we have

f[wx, yz] = f[wxz̄ȳ]
= f[wx] f[z̄ȳ] − f[wz̄] f[xȳ] + f[wȳ] f[xz̄]
= 0 − f[w, z] f[x, y] + f[w, y] f[x, z] ,

the usual 2 × 2 determinant

| \begin{matrix}f[w, y] & f[w, z] \\ f[x, y] & f[x, z] \end{matrix} | .

Theorem (1.0) immediately yields a corresponding identity for determinants, when we apply these definitions:

f[α, β] f[αγ, βδ] = ∑_{y} s(γ, x) s(δ, y) f[αx, βy] f[αγ\x, βδ\y] ,  (3.3)

for all x ∈ γ. When |γ| = |δ| is 2 or 3, this identity reads

f[α, β] f[αwx, βyz] = f[αw, βy] f[αx, βz] − f[αw, βz] f[αx, βy] ;  (3.4)
f[α, β] f[αuvw, βxyz] = f[αu, βx] f[αvw, βyz]
− f[αu, βy] f[αvw, βxz]
+ f[αu, βz] f[αvw, βxy] .  (3.5)

Here are some small examples written in more conventional notation:

a_{11} | \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix} | = | \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} | | \begin{matrix}a_{11} & a_{13} \\ a_{31} & a_{33} \end{matrix} | − | \begin{matrix}a_{11} & a_{13} \\ a_{21} & a_{23} \end{matrix} | | \begin{matrix}a_{11} & a_{12} \\ a_{31} & a_{32} \end{matrix} | ;  (3.6)

| \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} | | \begin{matrix}a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix} | = | \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix} | | \begin{matrix}a_{11} & a_{12} & a_{14} \\ a_{21} & a_{22} & a_{24} \\ a_{41} & a_{42} & a_{44} \end{matrix} | − | \begin{matrix}a_{11} & a_{12} & a_{14} \\ a_{21} & a_{22} & a_{24} \\ a_{31} & a_{32} & a_{34} \end{matrix} | | \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{41} & a_{42} & a_{43} \end{matrix} | ;
(3.7)

a_{11} | \begin{matrix}a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix} | = | \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} | | \begin{matrix}a_{11} & a_{13} & a_{14} \\ a_{31} & a_{33} & a_{34} \\ a_{41} & a_{43} & a_{44} \end{matrix} | − | \begin{matrix}a_{11} & a_{13} \\ a_{21} & a_{23} \end{matrix} | | \begin{matrix}a_{11} & a_{12} & a_{14} \\ a_{31} & a_{32} & a_{34} \\ a_{41} & a_{42} & a_{44} \end{matrix} |

+ | \begin{matrix}a_{11} & a_{14} \\ a_{21} & a_{24} \end{matrix} | | \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{31} & a_{32} & a_{33} \\ a_{41} & a_{42} & a_{43} \end{matrix} | .  (3.8)

Of course determinants have been investigated rather thoroughly for nearly 250 years, so it would be surprising indeed if these identities were new. Equation (3.6) was, for instance, noted by Lagrange in 1773 [16, page 39]; (3.7) and higher examples of (3.4) were discussed by Desnanot in 1819 [16, page 142].

One particularly interesting case in which (3.4) played a crucial role is C. L. Dodgson’s elegant “condensation method” for determinant evaluation [7], discovered between the times when he wrote Alice in Wonderland and Through the Looking Glass: Suppose the index set X is the integers, and let f_{0}[x, y] = 1 for all x and y, while f_{1}[x, y] is the entry in row x and column y of a given matrix. Then for k ≥ 1 let

f_{k+1}[x, y] = | \begin{matrix}f_{k}[x, y] & f_{k}[x, y + 1] \\ f_{k}[x + 1, y] & f_{k}[x + 1, y + 1] \end{matrix} | / f_{k−1}[x + 1, y + 1] .  (3.9)

It follows that

f_{k}[x, y] = f_{1}[x(x + 1) … (x + k − 1), y(y + 1) … (y + k − 1)]  for k ≥ 0 ,  (3.10)

by induction on k using (3.4). To evaluate the n × n determinant f[1 2 … n, 1 2 … n], we may therefore simply compute f_{k}[x, y] for 1 ≤ x, y ≤ n + 1 − k and k = 2, …, n, hoping that it will not be necessary to divide by zero. Dodgson’s condensation method provided the original motivation for Robbins and Rumsey’s recent work on alternating sign matrices [19].

The earliest known identity involving products of determinants is

f[ab, 12] f[ab, 34] − f[ab, 13] f[ab, 24] + f[ab, 14] f[ab, 23] = 0 ,  (3.11)

which Alexis Fontaine des Bertins proudly wrote out 126 times for different choices of the indices and then said “et cetera.” He submitted this and other memoirs to the French academy in 1748, but the works remained unpublished until 1764 [16, pp. 10–11]. From (1.0) we can now recognize that the right-hand side of (3.8) is actually a Pfaffian product

f[ab] f[a b ¯1 ¯2 ¯3 ¯4 ] ,

which is indeed zero in the bipartite case. Bezout, in 1779, gave the similar formula

f[abc, 123] f[abc, 456] − f[abc, 124] f[abc, 356]
+ f[abc, 125] f[abc, 346] − f[abc, 126] f[abc, 345] = 0 ,  (3.12)

and said “on voit qu’il y a une infinité d’autres combinaisons à faire” [16, page 51]; the right-hand side in this case is

f[a b c ¯1 ¯2 ] f[a b c ¯1 ¯2 ¯3 ¯4 ¯5 ¯6 ]

when we replace determinants by Pfaffians.

Another instance of (1.0) yields

f[ab] f[a b c ¯1 ¯2 ¯3 ¯4 ¯5 ] = f[a b ¯1 ¯2 ] f[a b c ¯3 ¯4 ¯5 ] − f[a b ¯1 ¯3 ] f[a b c ¯2 ¯4 ¯5 ]
+ f[a b ¯1 ¯4 ] f[a b c ¯2 ¯3 ¯5 ] − f[a b ¯1 ¯5 ] f[a b c ¯2 ¯3 ¯4 ]
− f[a b ¯1 c] f[a b ¯2 ¯3 ¯4 ¯5 ] .  (3.13)

Under bipartite restrictions this becomes an identity in determinants,

f[ab, 12] f[abc, 345] − f[ab, 13] f[abc, 245] + f[ab, 14] f[abc, 235] − f[ab, 15] f[abc, 234] = 0 , (3.14)

which Desnanot [6] seems to have known only in the special case

f[ab, 12] f[abc, 134] − f[ab, 13] f[abc, 124] + f[ab, 14] f[abc, 123] = 0  (3.15)

where column 1 = column 5, although he knew the general result (3.3) [16, page 145].

Thus we see that the single Pfaffian identity (1.0) unifies a variety of different-appearing determinant identities that arise when the indices are given bipartite structure in different ways.

When identity (2.8) is specialized to determinants, it gives a formula for minors of the adjugate of a matrix (i.e., determinants of cofactors):

f[α, β] f[αx_{1} … x_{n}, βu_{1} … y_{n}]^{n−1}
= | \begin{matrix}f[αx_{2} … x_{n}, βy_{2} … y_{n}] & … & f[αx_{2} … x_{n}, βy_{1} … y_{n−1}] \\ ⋮ & & ⋮ \\ f[αx_{1} … x_{n−1}, βy_{2} … y_{n}] & … & f[αx_{1} … x_{n−1}, βy_{1} … y_{n−1}] \end{matrix} | .  (3.16)

This general formula was first published by Jacobi in 1834, although special cases had been found by Lagrange in 1773 and Minding in 1829 [16, pp. 39, 197, 208–209]. The formula that corresponds to (2.5),

f[α, β]^{n−1} f[αx_{1}, … x_{n}, βy_{1} … y_{n}] = | \begin{matrix}f[αx_{1}, βy_{1}] & … & f[αx_{1}, βy_{n}] \\ ⋮ & & ⋮ \\ f[αx_{n}, βy_{1}] & … & f[αx_{n}, βy_{n}] \end{matrix} | ,  (3.17)

is simpler but was not discovered until Sylvester introduced a new viewpoint in 1851 [17, pp. 60–61].

4. Applications to closed forms. Let g be the skew-symmetric Blaschke operator

g[xy] = \frac{x − y}{1 − xy} .  (4.0)

Laksov, Lascoux, and Thorup [10, (A.12.3)] and John R. Stembridge [23, Proposition 2.3(e)] independently discovered the remarkable identity

g[x_{1}x_{2} … x_{n}] = ∏_{1≤i<j≤n} \frac{x_{i} − x_{j}}{1 − x_{i}x_{j}} ,  n even,  (4.1)

for which they gave an ingenious but quite special proofs.

We can, however, prove (4.1) as a special case of more general theorem that follows from a special case of (1.0):

Theorem. The identity

f[x_{1} … x_{n}] = ∏_{1≤i<j≤n} f[x_{i}x_{j}]  (4.2)

holds for all even n if and only if it holds for n = 4.

Proof. If n > 4 and the identity holds for smaller even values of n, let α be any word of length n − 4. Then

f[α] f[αwxyz] = f[αwx] f[αyz] − f[αwy] f[αxz] + f[αwz] f[αxy]
= R(f[wx] f[yz] − f[wy] f[xz] + f[wz] f[xy])
= R f[wxyz]
= R f[wx] f[wy] f[wz] f[xy] f[xz] f[yz] ,

where if α = x_{1} … x_{n−4} the common factor R is

( ∏_{1≤i<j≤n−4} f[x_{i}x_{j}]^{2}) ( ∏_{1≤i≤n−4} f[x_{i}w] f[x_{i}x] f[x_{i}y] f[x_{i}z]) .

Therefore

f[x_{1} … x_{n−4}] f[x_{1} … x_{n}] = f[x_{1} … x_{n−4}] ∏_{1≤i<j≤n} f[x_{i}x_{j}] .

Equation (4.2) follows unless f[x_{1} … x_{n−4}] = 0.

If f[y_{1} … y_{n−4}] = 0 for all subwords y_{1} … y_{n−4} of x_{1} … x_{n}, then f[x_{1} … x_{n}] = 0 and again (4.2) holds. Finally, if y_{1} … y_{n−4} is a subword such that f[y_{1} … y_{n−4}] ≠ 0, there is a permutation y_{1} … y_{n} of x_{1} … x_{n} for which our argument proves f[y_{1} … y_{n}] = ∏_{1≤i<j≤n} f[y_{i}y_{j}]. This establishes (4.2), because permutations of the indices change the signs of both sides in the same manner.

The theorem is of interest because it applies not only to (4.0) but also to the simpler function

f[x_{i}x_{j}] = \frac{x_{i} − x_{j}}{c + x_{i} + x_{j}}  (4.3)

when c is any complex constant. Thus we obtain a more-or-less “closed form” (4.2) for the Pfaffian of a new kind of matrix. (The special case c = 0 was previously noted by Schur [22, §36].)

In fact, the general function

f[x_{i}x_{j}] = \frac{x_{i} − x_{j}}{c + b(x_{i} + x_{j}) + a x_{i}x_{j}} ,  b^{2} = ac ± 1 ,  (4.4)

also satisfies the necessary conditions; this expression includes both (4.0) and (4.3). Are there other skew-symmetric rational functions of two variables that satisfy

f[wx] f[yz]+f[wy] f[zx] + f[wz] f[xy]
= f[wx] f[wy] f[wz] f[xy] f[xz] f[yz] ?  (4.5)

One can, of course, replace f[xy] by f[r(x)r(y)] for any rational function r, so any solution of (4.5) implies an infinite class of equivalent solutions. Alain Lascoux [11] has recently found strong reasons for believing that there are no other solutions, up to changes of variables.

When f[xy] is a polynomial, an amusing closed form of a similar type was noticed by G. Torelli [25]: Let f_{k}[xy] = (x − y)^{k}; then

f_{n−1}[x_{1} … x_{n}] = (−1)^{\binom{n/2}{2}} ( ∏_{k=0}^{n/2−1} \binom{n − 1}{k}) ∏_{1≤i<j≤n}(x_{i} − x_{j})  (4.6)

when n is even. It is easy to prove this identity, as well as the fact that f_{2m−1}[x_{1} … x_{n}] = 0 for 2m < n, by observing that the Pfaffian must vanish when x_{i} = x_{j}.

5. Generalization of the basic identity. Equation (1.0), which gives an expression for f[α] f[αβ] when α is a proper subword of αβ, leads to a similar identity that is useful when two words have an odd number of letters in common. Suppose αβγ has no repeated letters, and let x ∈ β. Then

f[αβ] f[αγ] = ∑_{y} s(β, xy) f[αβ\xy] f[αγxy]
+ ∑_{y} s(β, x) s(γ, y) f[αyβ\x] f[αxγ\y] .  (5.0)

For example, when |α| is odd we have

f[αxyz] f[αuvw] = f[αz] f[αuvwxy] − f[αy] f[αuvwxz]
+ f[αuyz] f[αxvw] − f[αvyz] f[αxuw] + f[αwyz] f[αxuv] . (5.1)

To prove (5.0), let γ = x_{1} … x_{k}. We will construct a “cancelling” word γ′ = x′_{k} … x′_{1} on new indices, by defining

f[yx′_{j}] = 0 if y ≠ x_{j} ;  f[x_{j}x′_{j}] = 1 .  (5.2)

Then f[αβ] = f[αγγ′β], and we can use (1.0) to conclude that

f[αβ] f[αγ] = ∑_{y} s(γ′β, xy) f[αγγ′β\xy] f[αγxy] .  (5.3)

Now if y ∈ β we have s(γ′β, xy) = s(β, xy), and f[αγγ′β\xy] = f[αβ\xy]. But if y = x′_{j} we have s(γ′β, xy) = (−1)^{j}s(β, x), f[αγγ′β\xy] = (−1)^{j−1} f[αyβ\x], f[αγxy] = (−1)^{j}f[αxγ\y], and s(γ, y) = (−1)^{j−1}.

6. A brief history of Pfaffians. Johann Friedrich Pfaff introduced the functions that now bear his name in 1815 [18] [16, pp. 396–401], while studying a general way to solve systems of firstorder partial differential equations. He gave two procedures for listing all perfect matchings, and observed that when the matchings are ordered lexicographically the corresponding signs are strictly alternating +, −, +, …, +.

Jacobi developed Pfaff’s method further in 1827 [9], and discovered an analog of “Cramer’s rule” for the solution of general systems of skew-symmetric linear equations

∑_{j=1}^{2n} f[ij] z_{j} = f[i0] ,  n even ;  (6.0)

namely,

z_{j} = \frac{f[1 … (j − 1) 0 (j + 1) … n]}{f[1 … n]} .  (6.1)

This implicitly proves that the Pfaffian f[1 … n] is a factor of the general skew-symmetric determinant

| \begin{matrix}f[11] & … & f[1n] \\ ⋮ & & ⋮ \\ f[n1] & … & f[nn] \end{matrix} | ,  n even.  (6.2)

Cayley proved in 1849 [3] that this determinant is in fact equal to the square of f[1 … n].

An elegant graph-theoretic proof of Cayley’s theorem, somewhat analogous to the derivation of (1.0) above, was found by Veltmann in 1871 [26] and independently by Mertens in 1877 [14]. Their proof anticipated 20th-century studies on the superposition of two matchings, and the ideas have frequently been rediscovered. Cayley himself had claimed that such a proof would be possible, after doing the calculations for n = 4 on the final page of a paper he wrote in 1861 [5]. But we should note that his original method was simpler. In fact, Cayley originally [3] gave a short inductive proof of the more general formula

| \begin{matrix}f[xy] & f[x2] & f[x3] & … & f[xn] \\ f[2y] & f[22] & f[23] & … & f[2n] \\ f[3y] & f[32] & f[33] & … & f[3n] \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ f[ny] & f[n2] & f[n3] & … & f[nn] \end{matrix} | = f[x23 … n] f[y23 … n] ,  (6.3)

for arbitrary x and y when n is even. And he proved several years later [17, pp. 269, 278] that the determinant on the left of (6.3) is f[xy23 … n] f[23 … n] when n is odd. (This determinant is incidentally not the same as f[x2 … n, y2 … n]; the elements of the latter are f[x, y], f[x, 2], … = f[xȳ], f[x¯2 ], …, not f[xy], f[x2], …, according to our conventions. Moreover, we generally use the notation f[x, y] only when we assume that f[xy] = 0.)

It was Cayley who introduced the name Pfaffian, because of its “connexion with the researches of Pfaff on differential equations” [4]. Another name semideterminant (German Halbdeterminant) was proposed by Wilhelm Scheibner [21], but it did not gain many adherents.

Theorem (1.0) was discovered by Henry William Lloyd Tanner in 1878 [24], who gave inductive proofs for the cases |β| = 4 and |β| = 6 from which proof schemata for higher cases could be inferred. Władysław Zajaczkowski found another proof shortly afterward [28] [29] based on Jacobi’s determinant theorem (3.16). The theorem was independently rediscovered in 1901 by J. Brill [1], who found a still better proof. He first established the identity

\binom{n − 1}{k}f[x_{1} … x_{2n}] = ∑_{1≤j_{1}<··· <j_{2k}≤2n} s(x_{1} … x_{2n}, x_{1} … x_{2k})f[x_{1} … x_{2k}]f[x_{1} … x_{2n}\x_{1} … x_{2k}]

(6.4)

by induction on k; then he made the left side zero by setting x_{2n} = x_{1}. A series of further steps led him to (1.0). But the combinatorial proof in section 1 above seems preferable to all three of these early approaches.

Identity (5.0) was recently discovered by Wenzel [27, Proposition 2.3], and demonstrated via exterior algebra by Dress and Wenzel [8].

The fact that Pfaffians are more fundamental than determinants, in the sense that determinants are merely the bipartite special case of a general sum over matchings, went unnoticed for a long time. The first person to observe that every n × n determinant is a Pfaffian was apparently Louis Saalschütz in 1908 [20], but the implicitly bipartite nature of his construction was not stated in his paper; a modern reader sees it only with hindsight. Brioschi had found a complicated way to express a 2n × 2n determinant as a Pfaffian, in 1856 [2]: If A is any 2n × 2n matrix and if Q = I_{n} ⊗ ({0 \atop −1} {1 \atop 0}), the determinant of A is the Pfaffian of A^{T} QA.

Pfaffians continue to find numerous applications, for example in matching theory [13] and in the enumeration of plane partitions [23]. It should prove interesting to extend Leclerc’s combinatorics of relations for determinants [12] to the analogous rules for Pfaffians.

Acknowledgements. Discussions with Lyle Ramshaw helped greatly to clarify my proof of (1.0). Paul Algoet kindly corrected several typographical errors in my preprint. Alain Lascoux referred me to [10] and [12], John Stembridge told me about [22], and an anonymous referee called my attention to [8]. I also thank the editors for their patience.

References

[1] J. Brill, “Note on the algebraic properties of Pfaffians,” Proceedings of the London Mathematical Society 34 (1901), 143–151.

[2] F. Brioschi, “Sur l’analogie entre une classe de déterminants d’order pair; et sur les déterminants binaires,” Journal für die reine und angewandte Mathematik 52 (1856), 133–141.

[3] A. Cayley, “Sur les déterminants gauches,” Journal für die reine und angewandte Mathematik 38 (1849), 93–96. Reprinted in his Collected Mathematical Papers 1, 410–413.

[4] A. Cayley, “On the theory of permutants,” Cambridge and Dublin Mathematical Journal 7 (1852), 40–51. Reprinted in his Collected Mathematical Papers 2, 16–26.

[5] A. Cayley, “Note on the theory of determinants,” Philosophical Magazine 21 (1861), 180–185. Reprinted in his Collected Mathematical Papers 5, 45–49.

[6] P. Desnanot, Complément de la Théorie des Équations du Premier Degré (Paris, 1819).

[7] C. L. Dodgson, “Condensation of determinants, being a new and brief method for computing their arithmetical values,” Proceedings of the Royal Society 84 (1866), 150–155. Reprinted in The Mathematical Pamphlets of Charles Lutwidge Dodgson and Related Pieces, edited by Francine F. Abeles (Charlottesville, Virginia: The University Press of Virginia, 1994), 170–180.

[8] Andreas W. M. Dress and Walter Wenzel, “A simple proof of an identity concerning Pfaffians of skew symmetric matrices,” Advances in Mathematics 112 (1995), 120–134.

[9] C. G. Jacobi, “Über die Pfaffsche Methode, eine gewöhnliche lineäre Differential-gleichung zwischen 2n Variabeln durch ein System von n Gleichungen zu integriren,” Journal für die reine und angewandte Mathematik 2 (1827), 347–357. Reprinted in C. G. J. Jacobi’s Gesammelte Werke 4 (1886), 17–29.

[10] D. Laksov, A. Lascoux and A. Thorup, “On Giambelli’s theorem on complete correlations,” Acta Mathematica 162 (1989), 143–199.

[11] Alain Lascoux, personal communication, 10 April 1995.

[12] Bernard Leclerc, “On identities satisfied by minors of a matrix,” Advances in Mathematics 100 (1993), 101–132.

[13] László Lovász and Michael D. Plummer, Matching Theory (Budapest: Akadémiai Kiadó, 1986); North-Holland Mathematics Studies 121.

[14] F. Mertens, “Über die Determinanten, deren correspondirende Elemente a_{pq} und a_{qp} entgegengesetzt gleich sind,” Journal für die reine und angewandte Mathematik 82 (1877), 207–211.

[15] Thomas Muir, A Treatise on the Theory of Determinants (London: Macmillan, 1882). Revised and enlarged by William H. Metzler (London: Longmans, Green, 1933; New York, Dover, 1960).

[16] Thomas Muir, The Theory of Determinants in the Historical Order of Development (London: MacMillan, 1906).

[17] Thomas Muir, The Theory of Determinants in the Historical Order of Development, volume 2 (London: MacMillan, 1911).

[18] J. F. Pfaff, “Methodus generalis, aequationes differentiarum partialium, nec non aequationes differentiales vulgares, utrasque primi ordinis, inter quotcunque variabiles, completi integrandi,” Abhandlungen der Königlich-Preußischen Akademie der Wissenschaften zu Berlin, Mathematische Klasse (1814–1815), 76–136.

[19] David P. Robbins and Howard Rumsey, Jr., “Determinants and alternating sign matrices,” Advances in Mathematics 62 (1986), 169–184.

the electronic journal of combinatorics 3 (2) (1996), #R5 13

[20] Louis Saalschütz, “Zur Determinanten-Lehre,” Journal für die reine und angewandte Mathematik 134 (1908), 187–197.

[21] W. Scheibner, “Über Halbdeterminanten,” Berichte über die Verhandlungen der Königlich Sächsischen Gesellschaft der Wissenschaften zu Leipzig 11 (1859), 151–159.

[22] J. Schur, “Über die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrochene lineare Substitutionen,” Journal für die reine und angewandte Mathematik 139 (1911), 155–250. Reprinted in Issai Schur, Gesammelte Abhandlungen 1 (1973), 346–441.

[23] John R. Stembridge, “Nonintersecting paths, Pfaffians, and plane partitions,” Advances in Mathematics 83 (1990), 96–131.

[24] H. W. Lloyd Tanner, “A theorem relating to Pfaffians,” Messenger of Mathematics 8 (1878), 56–59.

[25] Gabriele Torelli, “Quistione 64,” Giornale di Matematiche 24 (1886), 377.

[26] W. Veltmann, “Beiträge zur Theorie der Determinanten,” Zeitschrift für Mathematik und Physik 16 (1871), 516–525.

[27] Walter Wenzel, “Pfaffian forms and Δ-matroids,” Discrete Mathematics 115 (1993), 253–266.

[28] W. Zajaczkowski, “A theorem relating to Pfaffians,” Messenger of Mathematics 10 (1880), 36–37.

[29] W. Zaja‘czkowski, “O pewnéj własności pfafianu,” Rozprawy i Sprawozdania z Posiedzeń, Wydziału Matematyczno-Przyrodniczego Akademii Umieje‘tności 7 (Krakow, 1880), 67–74.