TRACE IDENTITIES FROM IDENTITIES FOR DETERMINANTS

S. Humphries and C. Krattenthaler^{†}

Mathematics Department, Brigham Young University Provo, UT 84602, USA e-mail: steve@math.byu.edu

                 WWW: http://www.math.byu.edu/~steve

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France. e-mail: kratt@euler.univ-lyon1.fr

                WWW: http://igd.univ-lyon1.fr/~kratt

Abstract. We present new identities for determinants of matrices (A_{i,j}) with entries A_{i,j} equal to a_{i,j} or a_{i,0}a_{0,j} − a_{i,j}, where the a_{i,j}’s are indeterminates. We show that these identities are behind trace identities for SL(2, ℂ) matrices found earlier by Magnus in his study of trace algebras.

1. Introduction. In this paper we derive an infinite family of new trace identities for 2 × 2 matrices by using an infinite family of new determinantal identities. These trace identities generalise a certain trace identity due to Magnus.

Trace identities for 2 × 2 matrices have been studied for over 100 years, one of the original motivations being the investigation of Teichmüller space via representations of surface groups as (certain equivalence classes of) subgroups of SL(2, ℂ). This approach originated with Fricke and Klein [1] and there have been many subsequent attempts at ways of giving real analytic trace coordinates for Teichmüller space (see for example [2, 3, 5, 7] and references therein).

Actions of groups on trace algebras have been investigated by Vogt [10] and more recently by Magnus [4]. Vogt was interested in studying invariants of differential equations, while Magnus was concerned with automorphisms and outer automorphisms of free groups. Physicists have also taken an interest in trace relations [6]. One thus sees the variety of applications that these ideas have.

Typeset by AMS-TEX

2000 Mathematics Subject Classification. Primary 15A15; Secondary 13B25 20G20.

†Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”

In [4], Magnus’s penultimate paper, he investigated the action of the automorphism group Aut(F_{n}) of a free group F_{n} of rank n on the traces of generic 2 × 2 matrices. These generic traces generate an algebra Q_{n} as follows: let m_{1}, …, m_{n} be ‘generic’ matrices in SL(2, ℤ) and for any sequence of distinct elements i_{1} < i_{2} < ⋯ < i_{k}, k ≤ n, of {1, 2, …, n} we let

τ_{i_{1}i_{2}...i_{k}}(m_{1}, m_{2}, …, m_{n}) = tr(m_{i_{1}}m_{i_{2}} ⋯ m_{i_{k}}),

where tr denotes the trace function. Then there are certain relations among traces of 2 × 2 matrices that show that the τ_{i}, τ_{jk}, … generate the algebra of all the traces of elements of the group ⟨m_{1}, …, m_{n}⟩: Take a polynomial algebra Q′_{n} generated by independent indeterminates τ′_{i}, τ′_{jk}, …; let I ⊂ Q′_{n} denote the ideal of all elements r(τ′_{i}, τ′_{jk}, …) ∈ Q′_{n} such that

r(τ_{i}(m_{1}, …, m_{n}), τ_{jk}(m_{1}, …, m_{n}), …) = 0

for all choices of m_{i}. Then Q_{n} = Q′_{n}/I.

In [4] Magnus was concerned with obtaining representations of Out(F_{n}) = Aut(F_{n})/Inn(F_{n}) by looking at an induced action of Out(F_{n}) on the trace algebra Q_{n}. In order to do this he first investigates Q_{n}. In doing this Magnus constructs various remarkable formulae satisfied by the generators of the trace algebra. These are expressed as equations in the determinants of certain matrices whose entries are traces of elements of SL(2, ℂ). He calls these the general identities [4; p. 94] and uses them to derive relations in the trace algebra that are needed for the proof that Q_{n} is finitely generated and other relevant properties.

These general identities are described as follows:

Magnus’s Main Lemma. For m_{i}, M_{j} ∈ SL(2, ℂ), 1 ≤ i, j ≤ 4, we have the following trace relations:

det(tr m_{i}M_{j}) + det(tr m_{i}M_{j}^{−1}) = 0;
det(tr m_{i}m_{j}) det(tr M_{i}M_{j}) = [det(tr m_{i}M_{j})]^{2}.

The goal of this paper is to search for the intrinsic background of trace identities of the above kind. As a first observation, if m_{i}, M_{j} ∈ SL(2, ℂ), 0 ≤ i, j, with m_{0} = M_{0} = I_{2}, the 2 × 2 identity matrix, and if we write a_{i,j} = tr m_{i}M_{j}, so that, in particular, a_{i,0} = tr m_{i} and a_{0,j} = tr M_{j} for i, j ≥ 1, then a simple calculation shows that

tr m_{i}M_{j}^{−1} = a_{i,0}a_{0,j} − a_{i,j}.

Thus, we are led to search for identities involving determinants of matrices (A_{i,j}), in which the entries A_{i,j} may be of the form a_{i,j} or a_{i,0}a_{0,j} − a_{i,j}. We discovered that on this abstract level there are in fact, somewhat surprisingly, several of these. We summarise our findings in Theorems 1, 3 and 6 in the subsequent sections.

As a corollary to Theorem 1 and to the trace theorem Theorem 2, we obtain the following generalisation of the first of Magnus’s formulae.

Magnus’s Main Lemma — Generalised. For n ≥ 1 let

m_{1}, …, m_{n}, M_{1}, …, M_{n} ∈ SL(2, ℂ),

and put m_{0} = M_{0} = I_{2}. Define the (n + 1) × (n + 1) matrix A = (A_{i,j})_{0≤i,j≤n} by

A_{i,j} = \{ \begin{matrix}tr(m_{i}M_{j}^{−1}) & if i + j is even; \\ tr(m_{i}M_{j}) & otherwise, \end{matrix}

and define n × n matrices B = (B_{i,j})_{1≤i,j≤n}, C = (C_{i,j})_{1≤i,j≤n} by B_{i,j} = − tr m_{i}M_{j}, and C_{i,j} = tr m_{i}M_{j}^{−1}. Then

det A = (−1)^{n} det B + det C.  (1)

Further, if n ≥ 4, then det A = 0, while if n > 4, then det B = det C = 0.

Theorem 1 implies (1), while the assertion in the last line follows from Theorem 2. Magnus’s first identity is the above result in the situation n = 4, the first case

where det A = 0, det B ≠ 0 and det C ≠ 0..

In the next section, we state and prove Theorems 1 and 2. In Section 3, we state and prove a general determinant formula (see Theorem 3), which implies new trace identities for traces of the form tr m_{i}m_{j} and tr m_{i}m_{j}^{−1}, where m_{1}, m_{2}, …, m_{n} are given matrices in SL(2, ℂ). (That is, they address the case where the second matrix family M_{1}, M_{2}, …, M_{n} in our generalisation of Magnus’s Main Lemma is identical with the first one.) We close this section with a curious result (see Theorem 6) stating that, in the “skew” case, the determinant of one of the matrices involved in Theorem 3 factors into the product of the “even” part of a Pfaffian and the “odd” part of a Pfaffian, up to a multiplicative constant. (See the paragraph before Theorem 6 for detailed explanations.)

Except for Theorem 2, which is not an abstract determinant identity but a determinant identity specific for traces, we prove our determinant identities by a combinatorial approach, as proposed in [11] (see also [8, Ch. 4]), that is, we combinatorially expand both sides of our identities, and then we bijectively identify the terms on the two sides, possibly helped by an involution which cancels several terms on one side.

Acknowledgement. Many thanks are due to Wayne Barrett for connecting the authors.

2. The determinant identities which imply the generalisation of Magnus’s formula. In this section, we prove a general determinant identity which implies our generalisation (1) of Magnus’s formula (see Theorem 1 below), and a general assertion about the vanishing of determinants formed out of traces (see Theorem 2 below) that implies the last assertion in our generalisation of Magnus’s Main Lemma, but, in addition, produces many more trace identities.

Theorem 1. Let (a_{i,j})_{0≤i,j≤n} be a doubly indexed sequence with the property that a_{0,0} = 2. We let A be the (n + 1) × (n + 1) matrix A = (A_{i,j})_{1≤i,j≤n}, where

A_{i,j} = \{ \begin{matrix}λa_{0,j} & if 0 = i ≠ j, \\ a_{i,j} & if j = 0 or if i + j is even, \\ λa_{i,0}a_{0,j} − a_{i,j} & otherwise. \end{matrix}

Furthermore, we define two n × n matrices B = (B_{i,j})_{1≤i,j≤n} and C = (C_{i,j})_{1≤i,j≤n} by

B_{i,j} = λa_{i,0}a_{0,j} − a_{i,j},

and

C_{i,j} = a_{i,j}.

Then

det A − (−1)^{n} det B − det C = 0.  (2)

Remark. For better clarity, we remark that, by our definitions, the first row of A is

(2, λa_{0,1}, λa_{0,2}, …, λa_{0,n}),

while the first column is

(2, a_{1,0}, a_{2,0}, …, a_{n,0})^{t}.

For example, for n = 4, the matrix A is equal to

( \begin{matrix}2 & λa_{0,1} & λa_{0,2} & λa_{0,3} & λa_{0,4} \\ a_{1,0} & a_{1,1} & λa_{1,0}a_{0,2} − a_{1,2} & a_{1,3} & λa_{1,0}a_{0,4} − a_{1,4} \\ a_{2,0} & λa_{2,0}a_{0,1} − a_{2,1} & a_{2,2} & λa_{2,0}a_{0,3} − a_{2,3} & a_{2,4} \\ a_{3,0} & a_{3,1} & λa_{3,0}a_{0,2} − a_{3,2} & a_{3,3} & λa_{3,0}a_{0,4} − a_{3,4} \\ a_{4,0} & λa_{4,0}a_{0,1} − a_{4,1} & a_{4,2} & λa_{4,0}a_{0,3} − a_{4,3} & a_{4,4} \end{matrix} ) .

In view of this remark, it should be clear that the case λ = 1 of this theorem implies (1).

Proof. The first observation is that, in det A, the coefficient of λ^{m} is zero for m ≥ 2, and the same is true for det B and det C. Clearly, this is trivial for det C, which contains no λ at all. To see the claim for det B, we let B′ be the matrix (λa_{i,0}a_{0,j})_{1≤i,j≤n} and B′′ the matrix (−a_{i,j})_{1≤i,j≤n}. Then we expand det B = det(B′ + B′′) in the following form,

det B = ∑_{J⊆{1,2,...,n}} det B^{J},

where B^{J} denotes the matrix where the columns indexed by elements from J are those from B′, while the remaining columns are those from B′′. Since any two columns from B′ are dependent, we have det B^{J} = 0 whenever |J| ≥ 2. Thus the largest exponent of λ in the expansion of det B is 1.

For det A we proceed in the same way. We let A′ be the matrix which contains the “λ-terms” from A, and we let A′′ be the “rest”. To be precise,

A′_{i,j} = \{ \begin{matrix}λa_{0,j} & if 0 = i ≠ j, \\ 0 & if j = 0 or if i + j is even, \\ λa_{i,0}a_{0,j} & otherwise, \end{matrix} ,

while

A′′_{i,j} = \{ \begin{matrix}0 & if 0 = i ≠ j, \\ a_{i,j} & if j = 0 or if i + j is even, \\ −a_{i,j} & otherwise. \end{matrix}

Again, we have chosen A′ and A′′ so that A = A′ + A′′. Then we do the same expansion as before,

det A = ∑_{J⊆{1,2,...,n}} det A^{J},

with the analogous meaning of A^{J}. Again, we have det A^{J} = 0 if |J| ≥ 2, this time because the 0-th column of A′ is 0, and because any two columns of A′ indexed by j_{1}, j_{2} ≥ 1 which have the same parity are dependent, while if j_{1} and j_{2} have different parity, 1/λa_{0,j_{1}} times the j_{1}-st column plus 1/λa_{0,j_{2}} times the j_{2}-nd column gives the 0-th column of A′′.

It remains to verify that the coefficients of λ^{0} and of λ^{1} in (2) vanish.

Let us begin with the coefficient of λ^{0}. If we set λ = 0 in (2), then det A can be reduced to

2 det((−1)^{i+j}a_{i,j})_{1≤i,j≤n} = 2 det(a_{i,j})_{1≤i,j≤n} = 2 det C,

while

det B = det(−a_{i,j})_{1≤i,j≤n} = (−1)^{n} det C.

Thus, the coefficient of λ^{0} in (2) is indeed zero.

For the coefficient of λ^{1} we only have to look at det A and det B. We shall derive combinatorial expressions for these two determinants. In order to do so, let us write 𝔖_{n} for the symmetric group on {1, 2, …, n}. From the definition of the determinant, we have

det B = ∑_{σ∈𝔖_{n}} sgn σ ∏_{i=1}^{n} B_{i,σ(i)}.

Extracting the coefficient of λ^{1}, we see that the coefficient of λ^{1} in det B is

∑_{σ∈𝔖_{n}} sgn σ ∑_{k=1}^{n} a_{k,0}a_{0,σ(k)}_{∏_{i=1}^{n} ; i≠k}(−a_{i,σ(i)})

= ∑_{k=1}^{n} ∑_{l=1}^{n}(−1)^{k+l}a_{k,0}a_{0,l} ∑_{σ∈𝔖_{n}^{(k,l)}} sgn σ_{∏_{i=1}^{n} ; i≠k}(−a_{i,σ(i)})

= (−1)^{n−1} ∑_{k=1}^{n} ∑_{l=1}^{n}(−1)^{k+l}a_{k,0}a_{0,l} ∑_{σ∈𝔖_{n}^{(k,l)}} sgn σ_{∏_{i=1}^{n} ; i≠k}a_{i,σ(i)},

where 𝔖_{n}^{(k,l)} is the set of bijections from {1, 2, …, n}\{k} to {1, 2, …, n}\{l}, where sgn σ has the obvious meaning when identifying 𝔖_{n}^{(k,l)} with 𝔖_{n−1}.

Aplying a similar procedure to det A, we obtain that the coefficient of λ^{1} in det A is

2 ∑_{σ∈𝔖_{n}}_{∑_{k=1}^{n} ; k+σ(k) odd}(sgn σ) · a_{k,0}a_{0,σ(k)}_{∏_{i=1}^{n} ; i≠k}(−1)^{i+σ(i)}a_{i,σ(i)}

+ ∑_{k=1}^{n} ∑_{l=1}^{n}(−1)^{k+l−1}a_{k,0}a_{0,l} ∑_{σ∈𝔖_{n}^{(k,l)}} sgn σ_{∏_{i=1}^{n} ; i≠k}(−1)^{i+σ(i)}a_{i,σ(i)}

= 2_{∑_{k,l=1}^{n} ; k+l odd}a_{k,0}a_{0,l} ∑_{σ∈𝔖_{n}^{(k,l)}} sgn σ_{∏_{i=1}^{n} ; i≠k}a_{i,σ(i)} − ∑_{k=1}^{n} ∑_{l=1}^{n} a_{k,0}a_{0,l} ∑_{σ∈𝔖_{n}^{(k,l)}} sgn σ_{∏_{i=1}^{n} ; i≠k}a_{i,σ(i)}

= ∑_{k=1}^{n} ∑_{l=1}^{n}(−1)^{k+l−1}a_{k,0}a_{0,l} ∑_{σ∈𝔖_{n}^{(k,l)}} sgn σ_{∏_{i=1}^{n} ; i≠k}a_{i,σ(i)}.

Thus, indeed, the coefficient of λ^{1} in (2) is zero.

This completes the proof of the theorem. □

The last assertion of our generalisation of Magnus’s Main Lemma follows from the following more general result which gives more trace relations.

Theorem 2. Let m_{1}, m_{2}, …, m_{n}, M_{1}, M_{2}, …, M_{n} ∈ SL(2, ℂ) and let ε_{1}, ε_{2}, …, ε_{n} ∈ {±1}. Define the n × n matrix D = (D_{i,j})_{1≤i,j≤n} by D_{i,j} = tr(m_{i}M_{j}^{ε_{i}}). If n ≥ 5, then det D = 0.

Proof. The proof will follow by exhibiting a 0-eigenvector for D.

Fix j ≤ n and let M_{j} = ( \begin{matrix}M_{j1} & M_{j2} \\ M_{j3} & M_{j4} \end{matrix} ), so that M_{j}^{−1} = ( \begin{matrix}M_{j4} & −M_{j2} \\ −M_{j3} & M_{j1} \end{matrix} ). We

also let m_{i} = ( \begin{matrix}m_{i1} & m_{i2} \\ m_{i3} & m_{i4} \end{matrix} ) for all i ≤ n. We will find non-trivial functions v_{1}, …, v_{n} of the variables m_{i,j} such that v = (v_{1}, …, v_{n}) is a (left) 0-eigenvector for D, so that vD = 0. This will be the case if for all j ≤ n we have

∑_{i=1}^{n} v_{i} tr(m_{i}M_{j}^{ε_{i}}) = 0.

But each of the above equations is linear in the variables M_{j1}, M_{j2}, M_{j3}, M_{j4} and the equations that we so obtain are independent of the column index j. We thus have n > 4 linear equations in 4 unknowns. There is thus, generically, a non-trivial solution. Thus, det D = 0 except on a set of measure zero; but since det is continuous it follows that we always have det D = 0. □

3. More determinant identities. Here, we present an identity for determinants of matrices, in which the entries are a_{i,j} or a_{i}a_{j} − a_{i,j}. Interpreting a_{i} as the trace of a matrix m_{i} ∈ SL(2, ℂ) and a_{i,j} as tr m_{i}m_{j}, these identities produce therefore trace identities for the traces tr m_{i}m_{j} and tr m_{i}m_{j}^{−1}. In fact, in the theorem below, we allow two additional parameters, λ and β. By specialising them in different ways, we obtain various new determinant identities. The specialisation in Corollary 4 contains the identity which is relevant to the trace case, whereas Corollary 5 contains a “skew” variation. (The “skew” refers to the fact that the matrix A there is skew-symmetric.) As an aside, we prove in Theorem 6 the curious fact, that, in the “skew” case, the determinant of the matrix C factors into two big factors, one of which collects the “even terms” of the Pfaffian of A, the other collecting its odd terms.

We alert the reader that, when compared to Theorem 1, the two theorems below follow a different index convention in that the entries of the matrix A are indexed by i and j from {1, 2, …, n} (rather than {0, 1, …, n}), and, similarly, the entries of the matrices B and C are indexed by i and j from {2, 3, …, n} (rather than {1, 2, …, n}). This convention has advantages over the other in the formulation of Theorem 6. A further change of convention is that the “trace-like” entries are a_{i,j} − λa_{1,i}a_{1,j} (rather than λa_{1,i}a_{1,j} −a_{i,j}). This allows a more elegant formulation of the following theorem, but, clearly, by multiplying every other row and column of B and C by −1, we could pass to the convention for the “trace-like” entries which is followed in Theorem 1.

Theorem 3. Let (a_{i,j})_{1≤i,j≤n} be a doubly indexed sequence with the property that a_{i,1} = βa_{1,i} for i > 1. We let A be the n × n matrix A = (A_{i,j})_{1≤i,j≤n}, where

A_{i,j} = \{ \begin{matrix}λa_{1,j} & if 1 = i ≠ j, \\ a_{i,j} & otherwise. \end{matrix}

Furthermore, we define two (n − 1) × (n − 1) matrices B = (B_{i,j})_{2≤i,j≤n} and C = (C_{i,j})_{2≤i,j≤n} by

B_{i,j} = \{ \begin{matrix}a_{i,j} − λa_{1,i}a_{1,j} & if i + j is even, \\ a_{i,j} & if i + j is odd, \end{matrix}

and

C_{i,j} = \{ \begin{matrix}a_{i,j} & if i + j is even, \\ a_{i,j} − λa_{1,i}a_{1,j} & if i + j is odd. \end{matrix}

Then

det A − β(det B + det C) = (a_{1,1} − 2β) det(a_{i,j})_{2≤i,j≤n}.  (3)

Remark. For the benefit of the reader, we display the matrices A, B, and C for n = 5:

A = ( \begin{matrix}a_{1,1} & λa_{1,2} & λa_{1,3} & λa_{1,4} & λa_{1,5} \\ βa_{1,2} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} \\ βa_{1,3} & a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ βa_{1,4} & a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ βa_{1,5} & a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} \end{matrix} ) ,

B = ( \begin{matrix}a_{2,2} − λa_{1,2}^{2} & a_{2,3} & a_{2,4} − λa_{1,2}a_{1,4} & a_{2,5} \\ a_{3,2} & a_{3,3} − λa_{1,3}^{2} & a_{3,4} & a_{3,5} − λa_{1,3}a_{1,5} \\ a_{4,2} − λa_{1,2}a_{1,4} & a_{4,3} & a_{4,4} − λa_{1,4}^{2} & a_{4,5} \\ a_{5,2} & a_{5,3} − λa_{1,3}a_{1,5} & a_{5,4} & a_{5,5} − λa_{1,5}^{2} \end{matrix} ) ,

C = ( \begin{matrix}a_{2,2} & a_{2,3} − λa_{1,2}a_{1,3} & a_{2,4} & a_{2,5} − λa_{1,2}a_{1,5} \\ a_{3,2} − λa_{1,2}a_{1,3} & a_{3,3} & a_{3,4} − λa_{1,3}a_{1,4} & a_{3,5} \\ a_{4,2} & a_{4,3} − λa_{1,3}a_{1,4} & a_{4,4} & a_{4,5} − λa_{1,4}a_{1,5} \\ a_{5,2} − λa_{1,2}a_{1,5} & a_{5,3} & a_{5,4} − λa_{1,4}a_{1,5} & a_{5,5} \end{matrix} ) .

Proof. As a first step, we derive combinatorial expressions for det A, det B and det C.

Let us introduce some notation. As earlier, we write 𝔖_{n} for the symmetric group on {1, 2, …, n}. Given a permutation σ ∈ 𝔖_{n}, we let c(σ) be the number of cycles of σ. Furthermore we define the function f_{1} by

f_{1}(σ) = \{ \begin{matrix}1 & if σ(1) = 1, \\ 0 & if σ(1) ≠ 1. \end{matrix}

By the definition of the determinant, we have

det A = ∑_{σ∈𝔖_{n}} sgn σ ∏_{i=1}^{n} A_{i,σ(i)} = ∑_{σ∈𝔖_{n}}(−1)^{n−c(σ)}λ^{1−f_{1}(σ)} ∏_{i=1}^{n} a_{i,σ(i)}.  (4)

In order to describe combinatorial expressions for det B and det C, we need some further notations and definitions. We write 𝔖̃_{n−1} for the symmetric group on {2, 3, …, n}. A signed permutation on {2, 3, …, n} is a pair (π, ε), where π ∈ 𝔖̃_{n−1} and ε ∈ {−1, 1}^{n−1}. For the sake of convenience, we label the components of ε from 2 through n, that is, ε = (ε_{2}, ε_{3}, …, ε_{n}). We define the weight w(π, ε) of a signed permutation (π, ε) by

w(π, ε) = ∏_{i=2}^{n} W_{i,π(i)},

where

W_{i,π(i)} = \{ \begin{matrix}a_{i,π(i)} & if ε_{i} = 1, \\ −λa_{1,i}a_{1,π(i)} & if ε_{i} = −1. \end{matrix}

We need two particular subsets of all signed permutations: let SP_{n−1}^{(1)} denote the set of all signed permutations on {2, 3, …, n} with ε_{i} = 1 whenever i + π(i) is odd, 2 ≤ i ≤ n, and let SP_{n−1}^{(2)} denote the set of all signed permutations on {2, 3, …, n} with ε_{i} = 1 whenever i + π(i) is even, 2 ≤ i ≤ n.

Now, with all this notation, for the determinant of B we have

det B = ∑_{σ∈𝔖̃_{n−1}} sgn σ ∏_{i=2}^{n} B_{i,σ(i)} = ∑_{(π,ε)∈SP_{n−1}^{(1)}}(sgn π) · w(π, ε),  (5)

while for the determinant of C we have

det C = ∑_{σ∈𝔖̃_{n−1}} sgn σ ∏_{i=2}^{n} B_{i,σ(i)} = ∑_{(π,ε)∈SP_{n−1}^{(2)}}(sgn π) · w(π, ε).  (6)

We can now begin the actual proof of (3).

We start by identifying the coefficients of λ^{0}: By inspection, the coefficient of λ^{0} in det A is a_{1,1} det(a_{i,j})_{2≤i,j≤n}. It is equally obvious that the coefficient of λ^{0} in det B, as well as in det C, is equal to det(a_{i,j})_{2≤i,j≤n}. Thus, the coefficients of λ^{0} on both sides of (3) agree.

Next we identify the coefficients of λ^{1}: clearly, the coefficient of λ^{1} on the righthand side of (3) is zero. We now use expressions (4)–(6) for det A, det B, and det C, respectively, to show that this is also the case on the left-hand side. The coefficient of λ^{1} in (4) is

∑_{σ∈𝔖_{n}} ; σ(1)≠1(−1)^{n−c(σ)} ∏_{i=1}^{n} a_{i,σ(i)} = _{∑_{σ∈𝔖_{n}} ; σ(1)≠1}(−1)^{n−c(σ)}a_{σ^{−1}(1),1}a_{1,σ(1)}_{∏_{i=2}^{n} ; i≠σ^{−1}(1)}a_{i,σ(i)}

= β_{∑_{σ∈𝔖_{n}} ; σ(1)≠1}(−1)^{n−c(σ)}a_{1,σ^{−1}(1)}a_{1,σ(1)}_{∏_{i=2}^{n} ; i≠σ^{−1}(1)}a_{i,σ(i)}. (7)

Terms contributing to the coefficient of λ^{1} in (5) and (6) occur exactly for the signed permutations (π, ε) where ε is a vector with exactly one component equal to −1. Let ε^{(k)} denote the vector with all components equal to 1 except for the k-th, which is −1. The coefficient of λ^{1} in (5) is then

∑_{π∈𝔖̃_{n−1}} _{∑_{k=2}^{n} ; k+π(k) even}(sgn π)· \frac{w(π, ε^{(k)})}{λ} = − ∑_{π∈𝔖̃_{n−1}} _{∑_{k=2}^{n} ; k+π(k) even}(sgn π)·a_{1,k}a_{1,π(k)}_{∏_{i=2}^{n} ; i≠k}a_{i,π(i)},

while the coefficient of λ^{1} in (6) is

∑_{π∈𝔖̃_{n−1}} _{∑_{k=2}^{n} ; k+π(k) odd}(sgn π)· \frac{w(π, ε^{(k)})}{λ} = − ∑_{π∈𝔖̃_{n−1}} _{∑_{k=2}^{n} ; k+π(k) odd}(sgn π)·a_{1,k}a_{1,π(k)}_{∏_{i=2}^{n} ; i≠k}a_{i,π(i)}.

The coefficient of λ^{1} in the sum of (5) and (6) is therefore

− ∑_{π∈𝔖̃_{n−1}} ∑_{k=2}^{n}(−1)^{n−1−c(π)} · a_{1,k}a_{1,π(k)}_{∏_{i=2}^{n} ; i≠k}a_{i,π(i)}.  (9)

To a fixed pair (π, k), π ∈ 𝔖̃_{n−1} and 2 ≤ k ≤ n, we now associate the permutation σ ∈ 𝔖_{n}, given by σ(k) = 1, σ(1) = π(k), and σ(i) = π(i) for all i ≠ 1, k. Thus we see that (7) and (9) multiplied by β are identical, which implies that the coefficient of λ^{1} on the left-hand side of (3) vanishes, as desired.

The remaining task is to show that all other terms in the sum of (5) and (6) cancel. The reader should note that these “other terms” in (5) and (6) are indexed by signed permutations (π, ε) in the union SP_{n−1}^{(1)} ∪ SP_{n−1}^{(2)}, where the vector ε has at least two components equal to −1. We show that these terms cancel by defining a sign-reversing involution i on the set of signed permutations in SP_{n−1}^{(1)} ∪ SP_{n−1}^{(2)}, where the vector ε has at least two components equal to −1. The map i will be defined separately on three disjoint subsets of this set.

Set 1. Consider all signed permutations (π, ε) in SP_{n−1}^{(1)} ∪ SP_{n−1}^{(2)} with the property that there are at least two even indices i_{1}, i_{2}, 2 ≤ i_{1} < i_{2} ≤ n, with ε_{i_{1}} = ε_{i_{2}} = −1. Let us call this property the property P1.

Given a signed permutation (π, ε) with property P1, let i_{1} and i_{2} be even integers such that ε_{i_{1}} = ε_{i_{2}} = −1, which are minimal with respect to this property. Then we define

i((π, ε)) := (π ∘ (i_{1}, i_{2}), ε).  (10)

(The permutation π ∘(i_{1}, i_{2}) is the composition of π and the transposition exchanging i_{1} and i_{2}.) Clearly, i((π, ε)) also has property P1 since the vector ε has not changed. Furthermore, if (π, ε) ∈ SP_{n−1}^{(1)}, then also i((π, ε)) ∈ SP_{n−1}^{(1)}, and similarly for SP_{n−1}^{(2)}. By definition, the weight of (π, ε) is

w(π, ε) = (−λa_{1,i_{1}}a_{1,π(i_{1})})(−λa_{1,i_{2}}a_{1,π(i_{2})})_{∏_{i=2}^{n} ; i≠i_{1},i_{2}}W_{i,π(i)},

while the weight of i((π, ε)) is

w(π ∘ (i_{1}, i_{2}), ε) = (−λa_{1,i_{1}}a_{1,π(i_{2})})(−λa_{1,i_{2}}a_{1,π(i_{1})})_{∏_{i=2}^{n} ; i≠i_{1},i_{2}}W_{i,π(i)},

which is equal to w(π, ε). In summary, we have established the relation

(sgn π) · w(π, ε) = −(sgn(π ∘ (i_{1}, i_{2}))) · w(π ∘ (i_{1}, i_{2}), ε).

Since, in addition, i is an involution, the terms in (5) indexed by signed permutations with property P1 cancel each other pairwise, and the same is true for the analogous terms in (6).

Set 2. Now we consider all signed permutations in SP_{n−1}^{(1)} ∪ SP_{n−1}^{(2)} which do not have property P1, but have the property that there are at least two odd indices i_{1}, i_{2}, 2 ≤ i_{1} < i_{2} ≤ n with ε_{i_{1}} = ε_{i_{2}} = −1. Let us call this property the property P2. Given a signed permutation (π, ε) with property P2, we define the map i by (10), as before. It is then easy to see that everything else is as in the previous case. In particular, the terms in (5) indexed by signed permutations with property P2 cancel each other pairwise, and the same is true for the analogous terms in (6).

Set 3. Finally, we consider the signed permutations (π, ε) in SP_{n−1}^{(1)} ∪ SP_{n−1}^{(2)} which have neither property P1 nor property P2. Since ε must have at least two components equal to −1, the only possibility is then that there is an even i_{1} and an odd i_{2} such that ε_{i_{1}} = ε_{i_{2}} = −1, and these are the only components of ε which are equal to −1. We define the map i again by (10). This time, if (π, ε) ∈ SP_{n−1}^{(1)}, then i((π, ε)) ∈ SP_{n−1}^{(2)}, and vice versa. However, all the other conclusions of the first case remain valid, and, thus, again the terms in the sum of the right-hand sides of (5) and (6) indexed by signed permutations in this subset cancel each other pairwise.

This completes the proof of (3). □

Corollary 4. Let (a_{i,j})_{1≤i,j≤n} be the doubly indexed sequence with the property that a_{i,j} = a_{j,i} and a_{i,i} = 2 for all i and j. Then, if the matrices A, B and C are defined as in Theorem 3 (with β = 1), we have

det A = det B + det C.

Proof. We set β = 1, a_{i,j} = a_{j,i} and a_{i,i} = 2 for all i and j in Theorem 3. Then a_{1,1} − 2β = 0, and, hence, the assertion is equivalent to Equation (3) with these specializations. □

Corollary 5. Let (a_{i,j})_{1≤i,j≤n} be the doubly indexed sequence with the property that a_{i,j} = −a_{j,i} for all i and j. Then, if the matrices A, B and C are defined as in Theorem 3 (with β = −1), for even n we have

det A + det B + det C = 0.

Proof. We set β = −1 and a_{i,j} = −a_{j,i} for all i and j in Theorem 3. Then the determinant on the right-hand side of (3) is the determinant of a skew-symmetric matrix of odd size and, hence, zero. The assertion is therefore equivalent to Equation (3) with these specializations. □

As it turns out, in the “skew-symmetric” case (that is, in the case of Corollary 5), the determinant of the matrix C factors into two big factors. These two factors can be described explicitly. They are the “even” and the “odd” parts of the Pfaffian of the skew-symmetric matrix (a_{i,j})_{1≤i,j≤n}. Recall that, by definition, for even n the Pfaffian of a skew-symmetric matrix A = (a_{i,j})_{1≤i,j≤n}, denoted Pf(A), is the square root of det A, where the sign is chosen so that the term a_{1,n}a_{2,n−1} ⋯ a_{n/2,n/2+1} occurs with coefficient +1. In combinatorial terms, the Pfaffian of A is (cf. [9, Sec. 2])

Pf(A) = ∑_{m} sgn m · ∏_{(i,j)∈m} a_{i,j},  (11)

where the sum is over all perfect matchings m on {1, 2, …, n}. Let Pf_{e}(A) denote the sum of all the terms appearing on the right-hand side of (11) which contain a_{1,k} for an even k. Similarly, we denote by Pf_{o}(A) the sum of all the terms appearing in Pf(A) which contain a_{1,k} for an odd k.

Theorem 6. Let n be even, and let A = (a_{i,j})_{1≤i,j≤n} be a skew-symmetric matrix, that is a_{i,j} = −a_{j,i} for all i and j. If C is defined as in Theorem 3 (with β = −1), that is,

C_{i,j} = \{ \begin{matrix}a_{i,j} & if i + j is even, \\ a_{i,j} − λa_{1,i}a_{1,j} & if i + j is odd, \end{matrix}

then we have

det C = −2λ Pf_{e}(A) Pf_{o}(A).

Proof. We expand the determinant det(C) as in the proof of Theorem 3, see (6). Clearly, in this expansion, all the contributions of signed permutations in SP_{n−1}^{(2)} for which all the ε_{i}’s are 1 cancel each other, because the sum of these contributions is simply det(a_{i,j})_{2≤i,j≤n}, the determinant of a skew-symmetric matrix of odd dimension. The arguments given in the proof of Theorem 3 for Sets 1 and 2 show in addition that the contributions of signed permutations in SP_{n−1}^{(2)} for which there exist i_{1} and i_{2}, both even or both odd, such that ε_{i_{1}} = ε_{i_{2}} = −1 cancel each other. However, this happens also for signed permutations in Set 3, i.e., for signed permutations in SP_{n−1}^{(2)} for which ε_{i_{1}} = ε_{i_{2}} = −1 for an even i_{1} and an odd i_{2}, and for which all other ε_{i}’s are 1. To see this, for fixed even i_{1} and odd i_{2}, let us consider all the signed permutations (π, ε) in SP_{n−1}^{(2)} with ε_{i_{1}} = ε_{i_{2}} = −1, ε_{i} = 1 otherwise, with a fixed value π(i_{1}) and a fixed value π(i_{2}). Their contribution to (6) is

λ^{2} sgn(i_{1}, i_{2}, π(i_{1}), π(i_{2})) · a_{1,i_{1}}a_{1,π(i_{1})}a_{1,i_{2}}a_{1,π(i_{2})} det A_{1,π(i_{1}),π(i_{2})}^{1,i_{1},i_{2}},  (12)

where A_{1,π(i_{1}),π(i_{2})}^{1,i_{1},i_{2}} is the submatrix of A which arises by deleting the rows numbered 1, i_{1} and i_{2} and the columns numbered 1, π(i_{1}) and π(i_{2}), and where sgn(i_{1}, i_{2}, π(i_{1}), π(i_{2})) is a certain sign. If we interchange the roles of i_{1} and π(i_{1}), and of i_{2} and π(i_{2}), and consider the analogous signed permutations in SP_{n−1}^{(2)}, then their contribution is

λ^{2} sgn(i_{1}, i_{2}, π(i_{1}), π(i_{2})) · a_{1,i_{1}}a_{1,π(i_{1})}a_{1,i_{2}}a_{1,π(i_{2})} det A_{1,i_{1},i_{2}}^{1,π(i_{1}),π(i_{2})}.  (13)

However, we have

A_{1,π(i_{1}),π(i_{2})}^{1,i_{1},i_{2}} = − (A_{1,i_{1},i_{2}}^{1,π(i_{1}),π(i_{2})})^{t} ,

which implies

det A_{1,π(i_{1}),π(i_{2})}^{1,i_{1},i_{2}} = − det A_{1,i_{1},i_{2}}^{1,π(i_{1}),π(i_{2})},

since these are determinants of matrices of dimension n − 3, which is odd. Thus, the sum of the terms (12) and (13) is zero.

In summary, the above arguments have shown that det C is equal to the contributions in (6) by signed permutations in SP_{n−1}^{(2)} with exactly one ε_{i} which is −1. To be precise, they show that (compare with expression (8))

det C = −λ ∑_{π∈𝔖̃_{n−1}} _{∑_{k=2}^{n} ; k+π(k) odd}(sgn π) · a_{1,k}a_{1,π(k)}_{∏_{i=2}^{n} ; i≠k}a_{i,π(i)}.

In fact, there is still cancellation in the expression on the right-hand side. If π ∈ 𝔖̃_{n−1} should have a cycle of odd length which does not contain k, then the permutation π̄ arising from π by reversing the orientation of the cycle has the same sign, but the product ∏_{i=2,i≠k}^{n}a_{i,π̄(i)} has sign opposite to ∏_{i=2,i≠k}^{n}a_{i,π(i)}. Thus, the contributions corresponding to π and π̄ cancel each other. An analogous argument shows that the same is true if the cycle of π containing k should have an even length. Thus,

det C = −λ ∑′_{∑_{k=2}^{n} ; k+π(k) odd}(sgn π) · a_{1,k}a_{1,π(k)}_{∏_{i=2}^{n} ; i≠k}a_{i,π(i)},  (14)

where the sum ∑ ′ is over all π ∈ 𝔖̃_{n−1} with only cycles of even length except that the cycle containing k has odd length.

To show that the expression (14) is equal to −2λ Pf_{e}(A) Pf_{o}(A), we construct a bijection between 𝔖̃_{n−1} and M_{e}×M_{o}×{1, −1}, where M_{e} denotes the set of all perfect matchings on {1, 2, …, n} with the property that 1 is matched to an even number, and where M_{o} is the analogous set of perfect matchings with the property that 1 is matched to an odd number. If π is mapped to (m_{1}, m_{2}, η) under this bijection, then this bijection will have the property that

sgn π · a_{1,k}a_{1,π(k)}_{∏_{i=2}^{n} ; i≠k}a_{i,π(i)} = −(sgn m_{1})(sgn m_{2}) ∏_{(i,j)∈m_{1}} a_{i,j} ∏_{(i,j)∈m_{2}} a_{i,j}.

Clearly, given such a bijection, the assertion of the theorem would be proved.

Let π ∈ 𝔖̃_{n−1}. Consider a cycle of π not containing k. Let i be the smallest number in the cycle. Then we match i to π(i) in m_{1}, π(i) to π^{2}(i) in m_{2}, π^{2}(i) to π^{3}(i) in m_{1}, π^{3}(i) to π^{4}(i) in m_{2}, etc. Considering the cycle containing k, we let η = 1 if k is even while we let η = −1 is k is odd. If k is even, then we match 1 to k in m_{1}, k to π(k) in m_{2}, π(k) to π^{2}(k) in m_{1}, etc., while if k is odd, we match 1 to k in m_{2}, k to π(k) in m_{1}, π(k) to π^{2}(k) in m_{2}, etc. It is obvious that this sets up a bijection. The fact that the sign behaves in the correct way under the bijection can be shown in a similar manner as in the proof of Proposition 2.2 in [9]. □

References

1. Fricke R., Klein F., Vorlesungen über die Theorie der automorphen Funktionen, I, (1897; reprint, Johnson Reprint Corp., New York, 1965), Teubner, Leipzig,.

2. Keen L., On Fricke moduli, Advances in the Theory of Riemann Surfaces (Proc. Conf., Stony Brook, N.Y., 1969), Princeton Univ. Press, Princeton, N.J., 1971, pp. 205–224; Ann. of Math. Studies, No. 66.

3. , A rough fundamental domain for Teichmüller spaces, Bull. Amer. Math. Soc. 83 (1977), 1199–1226.

4. Magnus W., Rings of Fricke Characters and Automorphism groups of free groups, Math. Zeit. 170 (1980), 91-103.

5. Okumura Y., Global real analytic angle parameters for Teichmüller spaces, J. Math. Soc. Japan 49 (1997), 213–229.

6. Roberts, John A. G.; Baake, Michael, Trace maps as 3D reversible dynamical systems with an invariant, J. Statist. Phys. 74 (1994), 829–888.

7. Saito, K, Character variety of representations of a finitely generated group in SL_{2}, Topology and Teichmüller spaces (Katinkulta, 1995), World Sci. Publishing, River Edge, NJ, 1996, pp. 253–264.

8. D. Stanton and D. White, Constructive Combinatorics, Undergraduate Texts in Math., Springer–Verlag, New York, Berlin Heidelberg, Tokyo, 1986.

9. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96–131.

10. Vogt, H., Sur les invariants fondamentaux des équations différentielles linéaires du second ordre, thèse, Paris, Ann. Sci. École Norm. Sup. 6 (1889), 3–72.

11. D. Zeilberger, A combinatorial approach to matrix algebra, Discrete Math. 56 (1985), 61–72.

Mathematics Department, Brigham Young University, Provo, UT 84602, USA. E-

mail: steve@math.byu.edu. WWW: http://www.math.byu.edu/~steve/.

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France. E-mail: kratt@euler.univ-lyon1.fr.

WWW: http://igd.univ-lyon1.fr/~kratt.