TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 000, Number 0, 0000

A COMBINATORIAL PROOF OF BASS’S EVALUATIONS OF THE IHARA-SELBERG ZETA FUNCTION FOR GRAPHS

DOMINIQUE FOATA AND DORON ZEILBERGER

This paper is dedicated to Gian-Carlo Rota, on his millionth_{2}’s birthday.

Abstract. We derive combinatorial proofs of the main two evaluations of the Ihara-Selberg Zeta function associated with a graph. We give three proofs of the first evaluation all based on the algebra of Lyndon words. In the third proof it is shown that the first evaluation is an immediate consequence of Amitsur’s identity on the characteristic polynomial of a sum of matrices. The second evaluation of the Ihara-Selberg Zeta function is first derived by means of a sign-changing involution technique. Our second approach makes use of a short matrix-algebra argument.

1. Introduction

We are pleased to dedicate the present paper to our bon maître Rota who has been a great promoter of combinatorial methods. Convinced that combinatorics was hidden in many branches of mathematics (see, e.g., [14]), he has successfully persuaded his followers to unearth its treasures, study them for their own sake and propose a fruitful symbiosis with the mainstream of mathematics.

Rota’s pioneering paper [13] made the Möbius function, and hence its associated zeta function, a central unifying concept in combinatorics and elsewhere. The present paper is devoted to the calculation of a zeta function, not of a partially ordered set, as it has been so successfully done in the past by Rota and his disciples (see, e.g., [17]), but of a tree lattice.

Digging out those combinatorial treasures is not always an easy task, since very often a language barrier has to be overcome. One such example, that we were fortunate to discover, is Bass’s [3] evaluation of the Ihara-Selberg zeta function for a graph. Thanks to his superb and very lucid talk (Temple Mathematics Colloquium, May 1995) we were introduced to the algebraic set-up of his derivation and led to the core of his paper. Of great help also have been his transparencies, copies of which he was kind enough to send us.

\begin{matrix}c \\ ◯ \end{matrix}0000 American Mathematical Society

0002-9947/00 $1.00 + $.25 per page

Received by the editors December 1, 1996.

1991 Mathematics Subject Classification. Primary: 05C05, 05C25, 05C50; Secondary: 11F72, 15A15, 16A27.

Key words and phrases. Ihara-Selberg zeta function, Lyndon words, Amitsur identity.

The second author was supported in part by N.S.F. and the first author as a consultant of Zeilberger on his grant.

In calculating the zeta function of a tree lattice Bass [4] was led to determine the following invariant for a finite connected unoriented graph G. To express his result he first transformed G into an oriented graph by letting each edge whose ends are vertices i and j give rise to two oriented edges going from i to j and from j to i. Let c_{0} (resp. 2 c_{1}) be the number of vertices (resp. of oriented edges). He then introduced the class R of prime, reduced cycles of G, a class that in general is infinite, and formed the product

(1.1)  η(u) = ∏_{γ∈R}(1 − u^{|γ|}),

where |γ| denotes the length of the cycle γ. The product η(u) is usually called the Ihara-Selberg function associated with the graph G.

His main result was to show that the expansion of η(u) as an infinite series is actually a polynomial in u giving two explicit formulas for it, first as the determinant of a matrix of order 2 c_{1} that depends on the successiveness of the edges (a notion that will be defined below), namely

(1.2)  η(u) = det(I − u T),

second, as a product

(1.3)  η(u) = (1 − u^{2})^{c_{1}−c_{0}} det Δ(u),

where Δ(u) is a matrix of order c_{0} that depends on the connectedness of the vertices. The definitions of T and Δ(u) will be given in full details later on.

To prove (1.2) and (1.3) Bass makes use of keen algebraic techniques. In particular, the Jacobi formula det exp A = exp tr A plays a key role in the derivation of (1.2). As this classical formula has been derived by combinatorial methods ([6], [20]), it was challenging to use those methods to find combinatorial proofs of both formulas (1.2) and (1.3). This is the purpose of the paper.

With the present combinatorial approach we can show that (1.2) can be derived in a more general context. Instead of counting the cycles by the counter u^{|γ|}, we can keep track of the successiveness property within each cycle γ by mapping γ onto a monomial β(γ) in the so-called successiveness variables b(e, e′). As we shall see, the determinantal expression (1.2) can be derived in three different manners, all based on the the algebra of Lyndon words.

The concept of Lyndon word has been crucial in the foundations of Free Differential Calculus, initiated by Chen, Fox and Lyndon [5] and pursued by Schützenberger [15], [16] and Viennot [19]. The standard material on the subject can be found in the book by Lothaire ([8], chap. 5). Hereafter we just recall a few basic properties

Start with a finite nonempty set X supposed to be totally ordered and consider the free monoid X^{∗} generated by X. Let < be the lexicographic order on X^{∗} derived from the total order on X. A Lyndon word is defined to be a nonempty word in X^{∗} which is prime, i.e., not the power l′^{r} of any other word l′ for any r ≥ 2, and which is also minimal in the class of its cyclic rearrangements. Let L denote the set of all Lyndon words. The following property, due to Lyndon, can be found in [8], p. 67 (Theorem 5.1.5):

(1.4) Each nonempty word w ∈ X^{∗} can be uniquely written as a nonincreasing juxtaposition product of Lyndon words:

w = l_{1}l_{2} … l_{n},  l_{k} ∈ L,  l_{1} ≥ l_{2} ≥ ⋯ ≥ l_{n}.

With each Lyndon word l let us associate a variable denoted by [l]. Assume that all those variables [l] are distinct and commute with each other. Furthermore, let B be a square matrix whose entries b(x, x′) (x, x′ ∈ X) form another set of commuting variables.

If w = x_{1}x_{2} … x_{m} is a nonempty word in X^{∗}, define

β_{circ}(w) := b(x_{1}, x_{2})b(x_{2}, x_{3}) … b(x_{m−1}, x_{m})b(x_{m}, x_{1})

and β_{circ}(w) = 1 if w is the empty word. Notice that all the words in the same cyclic class have the same β_{circ}-image. Also define

(1.5)  β([l]) := β_{circ}(l)

for each Lyndon word l. Now form the Z-algebras of formal power series in the variables [l] and in the variables b(x, x′), and by linearity make β to be a continuous homomorphism. It makes sense to consider the product

(1.6)  Λ := ∏_{l∈L}(1 − [l])

as well as its inverse Λ^{−1}. We can also consider the images of Λ and Λ^{−1} under β. We have

β(Λ) = ∏_{l∈L}(1 − β([l]));

and

β(Λ^{−1}) = (β(Λ))^{−1}.

We further define two maps β_{dec} and β_{vert} (“dec” for “decreasing” and “vert” for “vertical”) as follows. If (l_{1}, l_{2}, …, l_{n}) is the nonincreasing factorization of a word w in Lyndon words, as defined in (1.4), let

β_{dec}(w) := β_{circ}(l_{1}) β_{circ}(l_{2}) … β_{circ}(l_{n}).

Now when the m letters of a word w = x_{1}x_{2} … x_{m} are rearranged in nondecreasing order, we obtain a word w̃ = x̃_{1}x̃_{2} … x̃_{m} called the nondecreasing rearrangement of w. Then define

β_{vert}(w) := b(x̃_{1}, x_{1})b(x̃_{2}, x_{2}) … b(x̃_{m}, x_{m}).

Also define β_{dec}(w) = β_{vert}(w) := 1 when w is the empty word.

By convention let X^{∗} denote the sum of all the words w (w ∈ X^{∗}) and use the notation

β_{dec}(X^{∗}) := ∑_{w∈X^{∗}} β_{dec}(w)

with an analogous notation for β_{vert}(X^{∗}).

Theorem 1.1. We have the identities

(1.7)  β(Λ^{−1}) = β_{dec}(X^{∗});
(1.8)  β_{dec}(X^{∗}) = β_{vert}(X^{∗});
(1.9)  β_{vert}(X^{∗}) = (det(I − B))^{−1};
(1.10)  β(Λ) = det(I − B).

Notice that the conjunction of (1.7), (1.8) and (1.9) implies the identity

(1.11)  β(Λ^{−1}) = (det(I − B))^{−1}

and therefore (1.10). The proofs of (1.7), (1.8) and (1.9) are given in section 2. As we shall see, they are all classical, or preexist in other contexts. The proof of (1.10) itself is given in section 4. Thus we already have two independent proofs of (1.10).

The direct proof of (1.10) heavily relies on the techniques developed (or not yet developed) in the algebra of Lyndon words. Section 3 is then devoted to recalling classical results on Lyndon words and proving new ones. Section 4 contains the construction of an involution of X^{∗} that shows that β(Λ) reduces to a finite sum β(G) that is easily expressible as det(I − B).

Our third proof of (1.10) was suggested to us by Jouanolou [7] after the first author had discussed the contents of a first version of the paper during the October 1996 session of the Séminaire Lotharingien. It is based on a specialization of Amitsur’s identity [2] on the characteristic polynomial of a finite sum of matrices A_{1} + ⋯ + A_{k}. For each Lyndon word l = i_{1}i_{2} … i_{p} whose letters belong to the set [k] = {1, 2, …, k} let A_{l} be the matrix product A_{l} := A_{i_{1}}A_{i_{2}} … A_{i_{p}}.

Then Amitsur’s identity can be stated as

(1.12)  det(I − (A_{1} + ⋯ + A_{k})) = ∏_{l∈L} det(I − A_{l}),

where the product is extended over all Lyndon words in the alphabet [k].

In section 5 we reproduce the (short) proof of Amitsur’s identity (1.12) due to Reutenauer and Schützenberger [12]. As will be seen, (1.10) is a mere consequence of (1.12). Thus the shortest proof of identity (1.10) has to be borrowed from Classical Matrix Algebra.

In section 6 we show how identity (1.2) fits into the present context. It is shown that when X is taken as the set E of all oriented edges of the graph G and each variable b(x, x′) is equal to 0 when the edge x′ is the reverse of x or is not the successor of x, and equal to u otherwise, identity (1.10) reduces to (1.2).

As named by Bass [3], the inverse of η(u), as given in (1.2), is the zeta function of the underlying tree lattice, so that η(u) itself may be called the Möbius function of the tree lattice. Accordingly, when proving (1.9) (resp. (1.10)) we calculate the zeta function (resp. the Möbius function) of the tree lattice.

There is a priori no extension of (1.3) in which the information on the edge successiveness can be kept other than a simple counting of the reduced prime cycles. We are then left to prove (1.3) itself, but we present two new proofs, one purely combinatorial derived in section 7, which is based on the constructions of several involutions on words. The second one is of matrix-algebra nature.

After submitting the present paper for publication in the Fall 1996 our attention was drawn by Ahumada (Mulhouse), who himself published an early paper on the subject [1]), to the paper by Stark and Terras that had just appeared [18]. The latter authors also have a proof of identity (1.10) when L is restricted to the set of reduced prime cycles. Finally, Stanton (Minneapolis) was kind enough to send us a preprint by Northshield [10] who also has elementary proofs of both identities (1.2) and (1.3).

2. The zeta function approach

When the infinite product Λ is developed as an infinite series in the variables [l], we get the sum of all the commuting monomials [l_{1}] [l_{2}] … [l_{n}], or, equivalently, the sum of the nonincreasing words [l_{i_{1}}] [l_{i_{2}}] … [l_{i_{n}}] (l_{i_{1}} ≥ l_{i_{2}} ≥ ⋯ ≥ l_{i_{n}}). Hence, as

β(Λ^{−1}) = ∑ β(l_{i_{1}}) β(l_{i_{2}}) … β(l_{i_{n}}) = ∑_{w∈X^{∗}} β_{dec}(w) = β_{dec}(X^{∗}),

because of Lyndon’s theorem (1.4) and by definition of β_{dec}, we obtain (1.7).

Let |w| denote the length of each word w ∈ X^{∗}. As both mappings β_{dec} and β_{vert} transform a word of length m into a monomial in the variables b(x, x′) of degree m, identity (1.7) is equivalent to

∑_{|w|=m} β_{dec}(w) = ∑_{|w|=m} β_{vert}(x)

for all m ≥ 0. Therefore (1.7) is proved if and only if the following proposition holds.

(2.1) There exists a bijection Φ of X^{∗} onto itself thaving the following property: if w = x_{1}x_{2} … x_{m} belongs to X^{∗}, then Φ(w) = w′ = x′_{1}x′_{2} … x′_{m} is a rearrangement of w and β_{vert}(w′) = β_{dec}(w).

The construction of such a bijection has been given in [4] (theorem 4.11) and also in [8] p. 198-199. However the construction must be slightly modified to fit in the present derivation. We illustrate the construction of the bijection with an example. Let X = {1, 2, …, 5 } and w = 3, 4, 5, 1, 2, 4, 2, 1, 2, 3, 1, 2, 4, 2. The factorization (l_{1}, l_{2}, …, l_{n}) of w as a nonincreasing sequence of Lyndon words (as defined in (1.5)) is (3, 4, 5; 1, 2, 4, 2; 1, 2, 3, 1, 2, 4, 2). For the construction of the bijection another factorization is used, the decreasing factorization (d_{1}, d_{2}, …, d_{r}) of w simply defined by cutting w before every letter x of w which is smaller than or equal to each letter to its left. With the working example (d_{1}, d_{2}, …, d_{r}) = (3, 4, 5; 1, 2, 4, 2; 1, 2, 3; 1, 2, 4, 2). Notice that each Lyndon word l_{i} is the juxtaposition product of contiguous factors d_{j}. Moreover

(2.2)  β_{dec}(w) = β_{circ}(l_{1}) β_{circ}(l_{2}) … β_{circ}(l_{n})
= β_{circ}(d_{1}) β_{circ}(d_{2}) … β_{circ}(d_{r}).

To obtain w′ we form the product of the so-called dominated circuits (see [8], chap. 10)

Δ(w) = (\begin{matrix}4 5 3 \\ 3 4 5 \end{matrix}| {2 4 2 1 \atop 1 2 4 2} |\begin{matrix}2 3 1 \\ 1 2 3 \end{matrix}| \begin{matrix}2 4 2 1 \\ 1 2 4 2 \end{matrix}) .

In Δ(w) the top word in each factor is obtained from the bottom factor d_{j} by making a right to left cyclic shift of d_{j}.

Next we reshuffle the columns of Δ(w) in such a way that the mutual order of two columns with the same top entry is not modified but the top row becomes nonincreasing:

(\begin{matrix}5 4 4 4 3 3 2 2 2 2 2 1 1 1 \\ 4 3 2 2 5 2 1 4 1 1 4 2 3 2 \end{matrix}) .

The resulting bottom word is the word Γ^{−1}(Δ(w)) as described in [8], p. 199, except the construction has been given with the reverse order of X.

Now exchange top and bottom words and rewrite the resulting biword from right to left:

(\begin{matrix}2 3 2 4 1 1 4 1 2 5 2 2 3 4 \\ 1 1 1 2 2 2 2 2 3 3 4 4 4 5 \end{matrix}) .

Finally, reshuffle the columns of the last biword so that the top word becomes nondecreasing, still keeping the mutual order of any two columns having the same top entry invariant:

w′ = (\begin{matrix}1 1 1 2 2 2 2 2 3 3 4 4 4 5 \\ 2 2 2 1 1 3 4 4 1 4 2 2 5 3 \end{matrix}) .

Then w′ is defined to be the bottom word of the above biword. Moreover

β_{dec}(w) = β_{vert}(w′).

With the working example the latter monomial is equal to b(1, 2)^{3} b(2, 1)^{2} b(2, 3) b(2, 4)^{2} b(3, 1) b(3, 4) b(4, 2)^{2} b(4, 5) b(5, 3).

Identity (1.9) is essentially the MacMahon Master Theorem identity (see [9], p. 93-96, or [4], chap. 5). This achieves the proof of (1.11). Notice that the combination of (1.7), (1.8) and (1.10) provides a new proof of the Master Theorem identity.

3. Lyndon and Donlyn words

As already defined in the introduction a Lyndon word is a nonempty word in X^{∗} which is prime and also minimal in its class of cyclic rearrangements. Let L denote the set of all Lyndon words. The following properties (3.1)–(3.3) can be found in [8], pp. 65 and 66 (Propositions 5.1.2 and 5.1.3):

(3.1) A nonempty word in X^{∗} is a Lyndon word if and only if it is strictly smaller that any of its proper right factors. (3.2) A nonempty word in X^{∗} is a Lyndon word if and only if it is of length one or the juxtaposition product lm of two Lyndon words l, m such that l < m.

Let l be a Lyndon word; if |l| ≥ 2 let m_{0} be the proper right factor of maximal length such that m_{0} ∈ L. Write l = l_{0}m_{0}. The factorization (l_{0}, m_{0}) of l is called the standard factorization of l.

(3.3) If (l_{0}, m_{0}) is the standard factorization of a Lyndon word l of length |l| ≥ 2, then l_{0} is also a Lyndon word and l_{0} < l_{0}m_{0} < m_{0}.

We will also need the following two properties, apparently not stated in the standard texts, but essential in our derivation.

(3.4) A factorization (l_{0}, m_{0}) of a Lyndon word l into two nonempty factors is the standard factorization of l if and only if m_{0}l_{0} is the second smallest cyclic rearrangement of l (the smallest one being l itself ).

For obvious reasons we shall call the word m_{0}l_{0} a Donlyn word. We reproduce the short proof kindly provided by Perrin [11].

Notice that if (l_{0}, m_{0}) is the standard factorization of l, then m_{0} is necessarily the smallest proper right factor of l. Let (l_{1}, m_{1}) be another factorization of l. Either m_{1} does not start with m_{0} and then m_{0}l_{0} < m_{1}l_{1}, or m_{1} = m_{0}m_{2} for some word m_{2}. In the latter case, as m_{2} is a proper right factor of l, we have l < m_{2} and then m_{0}l_{0} < m_{0}l < m_{0}m_{2}l_{1} = m_{1}l_{1}. The converse is immediate. □

(3.5) Let l, m be two Lyndon words such that l < m. Then (l, m) is the standard factorization of lm if and only if m is less than each of the cyclic rearrangements of l other than l.

Proof. Assume that (l, m) is the standard factorization of lm and let l = l′l′′ with both l′ and l′′ nonempty. If l′′ = mm′′, then m < l′′l′. If l′′ does not start with m, then m < l′′; otherwise, we would have l′′ < m and then l′′m < m which contradicts the fact that m is the smallest proper right factor of lm. Now if m = l′′m′, then l′′m′ = m < l′′m = l′′l′′m′ implies m′ < l′′m′ = m and this contradicts the fact that m is a Lyndon word. Accordingly, m cannot start with l′′ and the inequality m < l′′ implies m < l′′l′.

Conversely, suppose that m is less than each of the cyclic rearrangements of l other than l. If (l, m) is not the standard factorization of lm, then l = l′l′′, with l′, l′′ nonempty, l′′m ∈ L and l′′m < m. By assumption, we also have m < l′′l′. Therefore, l′′m < m < l′′l′. This implies that m = l′′m′ with m < m′ < l′, so that m < m′ < l′ < l. But the inequality m < l cannot hold as lm is a Lyndon word. □

4. The Möbius function approach

The content of a word w is defined as the set Cont(w) of all distinct letters occurring in w. A nonempty word of X^{∗} is said to be multilinear, if all its letters are distinct. Two words w and w′ are said to be disjoint, if they have no letter in common.

Denote by [L] the set of all commuting variables [l] associated with each Lyndon word l. If w is a prime word, it is the cyclic rearrangement of a unique Lyndon word l. We will also write [w] = [l], regarding each variable [l] as being associated with the class of cyclic rearrangements of the word l. We next form the free Abelian monoid Ab[L] generated by [L] and consider the following sequence Ab[L] ⊃ D ⊃ G defined as follows. Each monomial π = [l_{1}] [l_{2}] … [l_{r}] belongs to D, if and only if the Lyndon words l_{1}, l_{2}, …, l_{r} are all distinct. It belongs to G if furthermore every element x ∈ X occurs at most once in the set Cont(π) = Cont(l_{1}l_{2} … l_{r}). In such a case all the Lyndon words l_{k} are necessarily multilinear. As X is finite, the set G is necessarily finite. Moreover each element π ∈ G may be regarded as a permutation of the set Cont(π) ⊂ X. The number r of factors in π is called the degree of π and denoted by deg π.

The expansion of Λ (defined in (1.6)) is the infinite series

(4.1)  Λ = ∑_{π∈D}(−1)^{deg π}π.

We can also form the polynomial

(4.2)  G := ∑_{π∈G}(−1)^{deg π}π.

The definition of the homomorphism β was given in (1.5).

Theorem 4.1. We have the identity

(4.3)  β(Λ) = β(G),

so that β(Λ) is a polynomial.

The proof of Theorem 4.1 is based on an involution π ↦ π′ of D \ G such that deg π + deg π′ = 0 mod 2 that is defined as follows.

Construction of the involution. Say that π = [l_{1}] [l_{2}] … [l_{r}] is a good companion if it belongs to G. If π = [l_{1}] [l_{2}] … [l_{n}] is a bad companion (an element of D \ G), let x be the smallest letter that occurs more than once in l_{1}l_{2} … l_{r}. If l_{i} contains x, let xu_{1}, xu_{2}, …, xu_{s} be the list of all cyclic rearrangements of l_{i} that start with x. Write such a list for each of the words l_{1}, l_{2}, …, l_{r} and combine all those lists. It is essential to notice that all the elements in the list are distinct, because it is so for all the cyclic rearrangements of a Lyndon word and by assumption all the Lyndon words l_{1}, l_{2}, …, l_{r} are themselves distinct.

Now choose a total order on X such that x = min X and consider the lexicographic order on X^{∗} with respect to that total order. Furthermore, write the previous list in increasing order

(4.4)  List(π) = (xu_{1}, xu_{2}, xu_{3}, …)

and consider the smallest two elements xu_{1}, xu_{2}. Either they come from the same factor l_{i} (case (i)), or from two different factors (case (ii)).

In case (i) write xu_{1} = xvxw, xu_{2} = xwxv (v, w ∈ X^{∗}) so that [l_{i}] = [xvxw] = [xwxv]. Then define

π = [l_{1}] [l_{2}] … [l_{r}] ↦ π′ = [l_{1}] … [l_{i−1}] [xv] [xw] [l_{i+1}] … [l_{r}].

In case (ii) suppose [xu_{1}] = [l_{1}], [xu_{2}] = [l_{2}]. Then define

π = [l_{1}] [l_{2}] … [l_{r}] ↦ π′ = [xu_{1}xu_{2}] [l_{3}] … [l_{r}].

In case (i) the word xu_{1} = xvxw that is first in List(π) is necessarily a Lyndon word (with respect to the latter total order on X). Furthermore, the pair (xv, xw) is the standard factorization of xvxw by Property (3.4). Therefore, both xv, xw are Lyndon words and accordingly prime by Property (3.3).

On the other hand, as xvxw and xwxv are the smallest two elements in List(π) and since xv < xvxw < xw < xwxv < xu_{3} < ⋯, both xv and xw are smaller than all the other words xu_{k} for each k ≥ 3. It also follows from Property (3.4) that xw is less than all the cyclic rearrangements of xv other than xv. Accordingly, the smallest two elements in List(π′) are xv and xw. Consequently, (π′)′ = π.

In case (ii) the two words xu_{1} and xu_{2} coming from two different factors are necessarily Lyndon words. As xu_{1} < xu_{2}, Property (3.2) implies that xu_{1}xu_{2} is also a Lyndon word and therefore is prime. On the other hand, as xu_{1} < xu_{1}xu_{2} < xu_{2}, the word xu_{1}xu_{2} is less than all cyclic rearrangements of xu_{1} that may occur in List(π) other than all the words xu_{k} for each k ≥ 3, in particular it is less than all cyclic rearrangements of xu_{1} that may occur in List(π) other than xu_{1}. It follows from Property (3.5) that (xu_{1}, xu_{2}) is the standard factorization of xu_{1}xu_{2}. Accordingly, xu_{1}xu_{2} and xu_{2}xu_{1} are the smallest two elements in List(π′). Hence (π′)′ = π.

This shows that π ↦ π′ is a well defined involution of D \G. Moreover it satisfies

β(π) = β(π′).

Therefore (4.3) holds. □

Let π = [l_{1}] [l_{2}] … [l_{r}] be a monomial belonging to G. As noted before, π may be regarded as a permutation of Cont(π). The set G is then the set of all permutations of subsets of X. The summand (−1)^{deg π}β(π) in β(G) is then the term in the expansion of det(I − B) associated with the permutation π (see, e.g., [20], § 1). Thus

(4.5)  β(G) = ∑_{π∈G}(−1)^{deg π} β(π) = det(I − B).

This yields identity (1.10) in view of Theorem 4.1.

5. Amitsur’s identity

Reutenauer and Schützenberger [12] gave the following short proof of the Amitsur identity (1.12): Lyndon’s factorization theorem (1.4) may be expressed as ∏_{l}(1 − l)^{−1} = X^{∗} = (∑_{w} w) (w ∈ X^{∗}) where the product is taken over all Lyndon words in nonincreasing order. As X^{∗} = (1 − X)^{−1} = (∑_{w} w) (w ∈ X^{∗}), we can deduce (1 − X)^{−1} = ∏_{l}(1 − l)^{−1}. Now form the inverse of the latter identity and replace X by a set of matrices {A_{1}, …, A_{k}}. Taking the determinant of both sides yields identity (1.12).

Next Amitsur’s identity (1.12) specializes into (1.10) in the following manner. Let N = 2c_{1}, k = N × N and consider the lexicographic order on the pairs (i, j) (1 ≤ i, j ≤ N). If (i, j) is the m-th pair, let A_{m} be the matrix whose entries are all null except the (i, j)-entry which is equal to b(i, j). Then A_{1} + ⋯ + A_{k} = B.

Consider a word l = (i_{1}, j_{1})(i_{2}, j_{2}) … (i_{p}, j_{p}) in the alphabet {(1, 1), …, (N, N)}. If j_{1} = i_{2}, j_{2} = i_{3}, …, j_{p−1} = i_{p}, then A_{l} is the matrix whose all entries are null except the (i_{1}, j_{p})-entry which is equal to b(i_{1}, i_{2})b(i_{2}, i_{3}) ⋯ b(i_{p−1}, i_{p})b(i_{p}, j_{p}). If the above contiguity relations for the entries b(i, j) do not hold, A_{l} is zero.

Now remember that det(I − A_{l}) is the alternating sum of the diagonal minors of the matrix A_{l}. Accordingly, when the word l satisfies the above contiguity relations and j_{p} = i_{1}, we have

det(I − A_{l}) = 1 − b(i_{1}, i_{2})b(i_{2}, i_{3}) ⋯ b(i_{p−1}, i_{p})b(i_{p}, i_{1}).

In the other cases, det(I − A_{l}) = 1.

The infinite product in (1.12) can then be restricted to the Lyndon words l = (i_{1}, j_{1})(i_{2}, j_{2}) … (i_{p}, j_{p}) in the alphabet {(1, 1), …, (N, N)} satisfying j_{1} = i_{2}, j_{2} = i_{3}, …, j_{p−1} = i_{p} et j_{p} = i_{1}. But those words are in bijection with the Lyndon words i_{1}i_{2} … i_{p} in the alphabet [N]. This proves identity (1.10).

6. Bass’s results

As said in the introduction Bass’s calculations deal with an oriented graph having c_{0} vertices labelled 1, 2, …, c_{0} and 2 c_{1} oriented edges. Notice that each loop around vertex i in the original unoriented graph gives rise to two oriented loops around i in the oriented graph. Each oriented edge e going from vertex i, called the origin of e, to vertex j, called the end of e, has a unique reverse edge going from j to i that will be denoted by J(e) or by \overline{e}. Let V be the set of vertices and E be the set of oriented edges so that #V = c_{0} and #E = 2c_{1}.

Say that an oriented edge e′ is a successor of an oriented edge e, if the end of e and the origin of e′ coincide. An oriented path from vertex i to vertex j is a linear sequence of oriented edges e_{1}e_{2} … e_{m} (m ≥ 1) such that for every k = 1, 2, …, m−1 the edge e_{k+1} is a sucessor of e_{k}; moreover the origin of e_{1} is i while the end of e_{m} is j. The integer m is the length of the oriented path. It will be convenient to consider the free monoid E^{∗} generated by the edge set E and see the oriented paths as particular elements of E^{∗}.

When j = i the oriented path is called a pointed cycle. The oriented path e_{1}e_{2} … e_{m} is said to be reduced, if J(e_{1}) ≠ e_{2}, J(e_{2}) ≠ e_{3}, …, J(e_{m−1}) ≠ e_{m}, J(e_{m}) ≠ e_{1}. A pointed cycle is said to be prime, if it cannot be expressed as the product δ^{r} of a given pointed cycle δ for any r ≥ 2.

Two pointed cycles δ and δ′ are said to be (cyclically) equivalent, if they are cyclic rearrangements of each other, i.e., if they can be expressed as words δ = e_{1}e_{2} … e_{m} and δ′ = e_{k}e_{k+1} … e_{m}e_{1} … e_{k−1} in E^{∗} for some k (1 ≤ k ≤ m). Each equivalence class is called a cycle. The cycle containing the pointed cycle δ will be denoted by [δ]. This notation will not conflict with our previous notation for the variables [l] as we shall see.

If a pointed cycle is prime (resp. reduced, resp. of length m), all the elements in its equivalence class are prime (resp. reduced, resp. of length m). We can then speak of prime, reduced cycles. The length of a cycle γ will be denoted by |γ|. Let P (resp. R) denote the set of all prime (resp. prime and reduced) cycles. The ingredients of (1.1) are then fully defined.

The further notions introduced by Bass are the following.

(i) For each i = 1, 2, …, c_{0} let E_{i} (resp. L(E_{i})) be the set of the oriented edges going out of vertex i (resp. the vector space spanned by the basis E_{i}). The outer degree of vertex i is the number of oriented edges going out of i. Let Q(i) be equal to that outer degree minus one, so that, as the graph is assumed to be connected, Q(i) ≥ 0. Let Q be the diagonal matrix diag(Q(1), …, Q(c_{0})). With those notations we have: dim L(E_{i}) = Q(i) + 1. The direct sum of all the L(E_{i})’s

will be denoted by L(E), so that dim L(E) = ∑_{i=1}^{n}(Q(i) + 1) = 2 c_{1}.

(ii) The successiveness map “Succ” is defined as follows: let e be an oriented edge going from vertex i to vertex j. Then

(6.1)  Succ(e) := ∑_{e′∈E_{j}} e′.

In other words, Succ(e) is the sum of all the successors of e. The mappings Succ and the reverse map J may be regarded as endomorphisms of L(E). Then T = Succ−J is the endomorphism occurring in formula (1.2).

(iii) The connectedness matrix K = (K(i, j)) (1 ≤ i, j ≤ c_{0}). Let E_{i,j} be the set of all oriented edges going from vertex i to vertex j. Then K(i, j) := |E_{i,j}|. Notice that K(j, i) = K(i, j) and K(i, i) ≥ 2 if there is a loop around i. The matrix Δ(u) occurring in (1.3) is the matrix

(6.2)  Δ(u) = I − u K + u^{2} Q.

To recover the first evaluation (1.2) we have to take the following ingredients:

(i) X = E, the set of oriented edges;

(ii) ignore each variable b(e, e′) when e′ is not a successor of e or when e′ = J(e) (mapping it to 0) and make all the other variables equal to u. Call β_{u} the corresponding homomorphism β.

If a cycle is prime, it contains a unique pointed cycle which is also a Lyndon word l. We then denote the cycle by [l]. We have

β_{u}([l]) = \{ \begin{matrix}u^{|l|}, & if [l] is reduced; \\ 0, & otherwise; \end{matrix}

and then

β_{u}(Λ) = ∏_{γ∈R}(1 − u^{|γ|}).

Also if π = [l_{1}] [l_{2}] … [l_{r}] is a monomial whose components are prime reduced cycles, we have β_{u}(π) = u^{| Cont π|}. Let H be the set of the monomials π = [l_{1}] [l_{2}] … [l_{r}] such that each [l_{k}] is a prime reduced cycle and every edge occurs at most once in l_{1}l_{2} … l_{r} and let

H := ∑_{π∈H}(−1)^{deg π}π.

Then

β_{u}(G) = β_{u}(H).

so that (4.3) becomes (6.3) β_{u}(Λ) = β_{u}(H). As det(I − B) reduces to det(I − u T), formula (4.5) becomes

(6.4)  β_{u}(H) = ∑_{π∈H}(−1)^{deg π}u^{| Cont π|} = det(I − u T).

7. A Purely Combinatorial Proof of Formula (1.3)

Our purpose is to give a combinatorial proof of the identity

(7.1)  (1 − u^{2})^{\frac{1}{2} |E|+|V |}β_{u}(H) = (1 − u^{2})^{|E|} det Δ(u),

which is obviously equivalent to (1.3) because of (6.4). The determinant Δ(u) was defined in (6.2).

Our strategy will be to introduce a class of permutation graphs with colored edges, called chaps and consider the sum of the weights of all those chaps. That sum will be computed in two different ways. We will soon define polite chaps and later good chaps. It will be shown that the weighted sum of the impolite chaps is zero, as well as the weighted sum of the bad chaps. This is achieved by defining appropriate involutions that will partition all the impolite chaps into pairs each of whose members’ weight is the negative of the other, and similarly for the bad chaps. It will then follow that the sum of the weights of the polite chaps equals the sum of the weights of the good chaps. The former will turn out to be the right side of (7.1) while the latter will turn out to be the left side of (7.1).

7.1. Introducing Chaps. Suppose that the set E of all oriented edges of G is totally ordered. A chap may be seen as a permutation graph Ch (i.e., a collection of disjoint cycles) whose vertices — call them supervertices — are the vertices and the edges of the original graph, i.e., the elements of V ∪ E, and whose edges — call them superedges — are colored in the following sense. Let e, e′ be two oriented edges (not necessarily distinct) going out of the same vertex i, let j be the end of e and let e′′ be a successor of e (its origin is then vertex j). By definition the only possible colored superedges of a chap are the following

i ⟶^{1} i; i ⟶^{2} e; e ⟶^{3a} i; e ⟶^{3b} i;

e ⟶^{4a} j; e ⟶^{4b} j; e ⟶^{5} e; e ⟶^{6} e′; e ⟶^{7} e′′.

With each of the nine colors is associated a weight as shown in the next table:

Color  1  2  3a 3b 4a 4b  5  6 7
Weight 1 − u^{2} u(1 − u^{2}) u −u 1 −1 1 − u^{2} u^{2} −u

The weight of a chap is defined to be the product of the weights of the superedges times the sign of the graph permutation.

A chap is polite if its superedges are of the form:

i ⟶^{1} i; i ⟶^{2} e; e ⟶^{3b} i; e ⟶^{4a} j; e ⟶^{5} e;

where e is an edge of origin i and end j. A chap that is not polite will be called impolite. If a chap is impolite, there exists a vertex i such that one of the following conditions holds from some edges e, e′, e′′: (A) e ⟶^{3a} i, e ∈ E_{i}; (B) e ⟶^{4b} j, e ∈ E_{i}; (C) e ⟶^{6} e′, e ∈ E_{i}; (D) e ⟶^{7} e′′, e ∈ E_{i}. Denote by i the smallest such a vertex and let e be the smallest oriented edge in E_{i} which is the origin of a superedge colored 3a, 4b, 6 or 7. Accordingly, one the following six conditions holds:

(1) e ⟶^{3a} i ⟶^{2} e′;

(2) e ⟶^{4b} j ⟶^{2} e′;

(3) e ⟶^{6} e′, i ⟶^{1} i;

(3′) e ⟶^{6} e′, e′′ ⟶^{x} i ⟶^{2} e′′′ with x = 3a, 3b, 4a or 4b.

(4) e ⟶^{7} e′, j ⟶^{1} j, e′ ∈ E_{j} ;

(4′) e ⟶^{7} e′, e′′ ⟶^{x} j ⟶^{2} e′′′, e′ ∈ E_{j} with x = 3a, 3b, 4a or 4b.

If (1) (resp. (2)) occurs within an impolite chap Ch, transform Ch into another (impolite) chap Ch′ by replacing occurrence (1) (resp. (2)) by occurrence (3) (resp. (4)) and conversely. Finally, if (3′) occurs, perform the change: e ⟶^{6} e′′′, e′′ ⟶^{x} i ⟶^{2} e′ and if (4′) occurs, perform the change e ⟶^{7} e′′′ and e′′ ⟶^{x} j ⟶^{2} e′. Those changes preserve the absolute value of the weight and reverse its sign.

It follows that the sum of the weights of all impolite chaps is zero. Hence the sum of the weights of all chaps equals the sum of the weights of the polite chaps. We will now proceed to compute it.

7.2. The sum of the weights of the polite chaps. Each polite chap consists of cycles where superedges 2 and 4a intertwine

i_{1} ⟶^{2} e_{1} ⟶^{4a} i_{2} ⟶^{2} e_{2} ⟶^{4a} i_{3} ⋯ i_{k} ⟶^{2} e_{k} ⟶^{4a} i_{1}

as well as 2-cycles of the form i ⟶^{2} e ⟶^{3b} i, the other vertices and edges being fixed points: i ⟶^{1} i, e ⟶^{5} e.

A cycle of the first kind has weight u^{k}(1 − u^{2})^{k}, while a cycle of the second kind has weight −u^{2}(1 − u^{2}). To the product of all these cycles we must multiply by (1 − u^{2}) raised to the power of the number of remaining edges and vertices. Let V_{1} (resp. V_{2}, resp. V_{3}) be the set of vertices belonging to the cycles of the first kind (resp. of the second kind, resp. of the form e ⟶^{5} e). Since each cycle of the first kind has the same number of vertices and edges, and each cycle of the second kind has one vertex and one edge, the total weight is

(1 − u^{2})^{|E|} × u^{|V_{1}|} × (−u^{2})^{|V_{2}|} × (1 − u^{2})^{|V_{3}|}.

This is the same as (1 − u^{2})^{|E|+|V |} × (u/(1 − u^{2}))^{|V_{1}|} × (−u^{2}/(1 − u^{2}))^{|V_{2}|}.

Remember that E_{i,j} denote the set of all oriented edges in the graph G going from vertex i to vertex j and |E_{i,j}| = K(i, j). A polite chap Ch is then characterized by a sequence (V_{1}, V_{2}, V_{3}, σ, f, g), where

(i) (V_{1}, V_{2}, V_{3}) is a partition of the vertex set V in disjoint subsets;

(ii) σ is a permutation of V_{1};

(iii) f : V_{1} → E is a mapping such that [σ(i) = j] ⇒ [f(i) ∈ E_{i,j}];

(iv) g : V_{2} → E is a mapping such that g(i) ∈ E_{i}. Write α = u/(1 − u^{2}) and β = −u^{2}/(1 − u^{2}). As the sign of π is given by ε(σ) (−1)^{|V_{1}|+|V_{2}|}, the sum of the weights of the polite chaps is equal to

(1 − u^{2})^{|E|+|V |} ∑ ε(σ)(−α)^{|V_{1}|}(−β)^{|V_{2}|},

extended over all sequences (V_{1}, V_{2}, V_{3}, σ, f, g). Now the last summation, say, S is equal to

S = ∑_{((V_{1},V_{2},V_{3}),σ)} ε(σ) (−α)^{|V_{1}|}(−β)^{|V_{2}|} ∏_{i∈V_{1}} K(i, σ(i)) × ∏_{j∈V_{2}} deg j

= ∑_{(V_{1},V_{2},V_{3})} det(−α K(i, j))_{(i,j∈V_{1})} × (−β)^{|V_{2}|} ∏_{j∈V_{2}} deg j

= det(I − β(I + Q) − α K),

where Q and K are the two matrix ingredients of the matrix Δ(u) defined in section 6. Hence the sum of all the weights of the polite chaps (and hence the sum of the weights of all chaps) equals

(1 − u^{2})^{|E|+|V |} det(I + \frac{u^{2}}{1 − u^{2}} (I + Q) − \frac{u}{1 − u^{2}} K)

= (1 − u^{2})^{|E|} det(I − u K + u^{2} Q)
= (1 − u^{2})^{|E|} det Δ(u),

the right side of (7.1).

7.3. Good and Bad Chaps. A chap is hopelessly bad if it contains superedges colored 3a, 3b, 4a, or 4b. It is immediate that the sum of all the weights of the hopelessly bad chaps is zero since superedges colored 3a and 3b annihilate each other, as do those colored 4a and 4b. It is also clear that if a superedge 2 is present, then the chap must be a hopelessly bad chap, since whenever a vertex goes to an edge, some edge must go to a vertex through a superedge necessarily colored 3a, 3b, 4a, 4b. For the remaining chaps, the only way a vertex can be mapped onto is onto itself (superedge 1), that explains the factor of (1 − u^{2})^{|V |} on the left side of (7.2). We can now forget about the vertices and focus on the interaction of the edges.

Having purged the hopelessly bad chaps, we can only have chaps with superedges colored 5, 6, 7, that we shall further split into:

e ⟶^{5a} e with weight 1;

e ⟶^{5b} e with weight −u^{2};

e ⟶^{6a} e′ (e′ having the same origin as e) with weight u^{2};

e ⟶^{6b} e′ (e′ having the same origin as e but e′ ≠ e) with weight u^{2};

e ⟶^{7a} \overline{e} (\overline{e} = J(e)) with weight −u;

e ⟶^{7b} e′ (e′ a successor of e but different from \overline{e}) with weight −u. A not hopelessly bad chap is nevertheless very bad if it contains superedges colored 5b or 6a. These two cases annihilate each other so we can easily execute all the very bad chaps. It follows that a chap is not very bad if it contains superedges colored 5a, 6b, 7a, 7b.

Finally, a chap Ch is a bad chap if one of the three properties takes place:

(i) there is an edge e such that e ⟶^{5a} e and \overline{e} ⟶^{6b} e′ occur for some e′; (ii) there is an edge e such that e ⟶^{6b} e′ and \overline{e} ⟶^{7b} e′′ occur for some e′, e′′ ; (iii) there is an edge e such that the sequence e ⟶^{7a} \overline{e} ⟶^{7b} e′′ occurs for some e′′.

If Ch is a bad chap let e be the smallest offending edge. We define Ch′ by making the obvious transposition, i.e., by replacing the occurrence in case (i) by the occurrence in case (iii) and conversely, and replacing (ii) by e ⟶^{6b} e′′ and \overline{e} ⟶^{7b} e′. It is clear that Ch ↦ Ch′ is an involution of the set of the not very bad chaps that reverses the sign and preserves the absolute value of the weight.

A non-bad chap will be called a good chap. It is then a chap containing superedges colored 5a, 6b, 7a, 7b and having the following properties:

(i) whenever e ⟶^{5a} e occurs, then either \overline{e} ⟶^{5a} \overline{e}, or \overline{e} ⟶^{7b} e′ occurs;

(ii) whenever e ⟶^{6b} e′ occurs, then either \overline{e} ⟶^{7a} e or \overline{e} ⟶^{6b} e′′ occurs; (iii) whenever e ⟶^{7a} \overline{e} occurs, then either \overline{e} ⟶^{6b} e′ or \overline{e} ⟶^{7a} e occurs.

7.4. Enumerating the good chaps. Referring to the left side of (7.1) we are left to prove that the weighted sum of all the good chaps is equal to

β_{u}(H) × (1 − u^{2})^{|E|/2} = ∑_{π∈H}(−1)^{deg π}u^{| Cont(π)|} × (1 − u^{2})^{|E|/2}.

Say that τ is a back-track involution, if there exists a subset F (τ) of the edge set E such that J(F (τ)) = F (τ) and τ is the restriction of J to F (τ). Let T denote the set of all back-track involutions. (Notice that T ⊂ G.) With those notations we have

(1 − u^{2})^{|E|/2} = ∑_{τ∈T}(−1)^{deg τ} u^{|F (τ)|}.

Denote by w(Ch) and ε(Ch) the weight and the sign of a (good) chap Ch, respectively. We are left to prove the identity

∑_{Ch good chap} ε(Ch) w(Ch) = ∑_{π∈H}(−1)^{deg π}u^{| Cont(π)|} × ∑_{τ∈T}(−1)^{deg τ} u^{|F (τ)|}.

Construction of a bijection Ch ↦ (π, τ) of the set of good chaps onto H × T . The definition of a good chap shows that there are six cases to consider depending on the colors of superedges going out of each pair e, \overline{e}. The bijection is shown in the next table.

\begin{aligned}& Ch & π & τ \\ (1) & e ⟶^{5a} e \\ \overline{e} & ⟶^{5a} & \overline{e} \\ (2) & e ⟶^{5a} e & \overline{e} ⟶ e′ \\ & \overline{e} ⟶^{7b} e′ \\ (3) & e ⟶^{6b} e′ & \overline{e} ⟶ e′ & e ⟶ \overline{e} \\ & \overline{e} ⟶^{7a} e & & \overline{e} ⟶ e \end{aligned}  \begin{aligned}& Ch & π & τ \\ (4) & e ⟶^{6b} e′ & e ⟶ e′′ & e ⟶ \overline{e} \\ & \overline{e} ⟶^{6b} e′′ & \overline{e} ⟶ e′ & \overline{e} ⟶ e \\ (5) & e ⟶^{7a} \overline{e} & & e ⟶ \overline{e} \\ & \overline{e} ⟶^{7a} e & & \overline{e} ⟶ e \\ (6) & e ⟶^{7b} e′ & e ⟶ e′ \\ & \overline{e} ⟶^{7b} e′′ & \overline{e} ⟶ e′′ \end{aligned}

For instance, in case (2) we define π(\overline{e}) = e′; furthermore e ∉ Cont(π) and e, \overline{e} ∉ F (τ). The definition of τ is straightforward. To obtain π we start with the cycles of Ch and make the local modifications indicated.

In the construction of π no edge e is mapped onto its reverse \overline{e}, so that π ∈ H. The inverse bijection is described by means of the same table.

What remains to be proved is the identity

(7.2)  ε(Ch)w(Ch) = (−1)^{deg π} u^{| Cont(π)|} (−1)^{deg τ} u^{|F (τ)|}.

In cases (1), (2) and (6) there is no modification in the composition of the cycles when we go from Ch to π. In case (3) the supervertex e is deleted from the cycle containing \overline{e}, but the transposition e ↔ \overline{e} occurs in τ. In case (4) two cycles of π are made out of a single one, or a single cycle is made out of two existing ones. Therefore the sign changes, but again e ↔ \overline{e} occurs in τ. Finally, in case (5) the transposition e ⟷^{7b} \overline{e} is transformed into the transposition e ↔ \overline{e} in τ. Hence

ε(h) = ε(π) ε(τ)

For each i = 1, …, 6 let n_{i} be the number of pairs (e, \overline{e}) falling into case (i). The weight of Ch (not counting the contribution due to the vertices) is equal to

w(Ch) = (−u)^{n_{2}}u^{2n_{3}}(−u)^{n_{3}}u^{4n_{4}}(−u)^{2n_{5}}(−u)^{2n_{6}}
= (−u)^{n_{2}+n_{3}+2n_{4}+2n_{6}} (−u)^{2n_{3}+2n_{4}+2n_{5}}
= (−u)^{| Cont(π)|} (−u)^{|F (τ)|}.

Altogether

ε(Ch)w(Ch) = ε(π) (−u)^{| Cont(π)|} ε(τ) (−u)^{|F (τ)|}
= (−1)^{deg π} u^{| Cont(π)|} (−1)^{deg τ} u^{|F (τ)|}.

8. A matrix-algebraic proof of (1.3)

Let (u(i, j)) (1 ≤ i, j ≤ c_{0}) and (v(i)) (1 ≤ i ≤ c_{0}) be two sets of commuting variables. Introduce the common origin map “Com” as follows: if e is an oriented edge that goes from vertex i to vertex j, define:

(8.1)  Com(e) := ∑_{e′∈E_{i}, e′≠e} e′;
(8.2)  Com(v)(e) := v(i) Com(e).

Thus Com(e) is the sum of all edges, other than e, that have the same origin as e. Keeping the same notations we further define

(8.3) Succ(u)(e) := u(i, j) Succ(e), so that (8.4) A := I + Succ(u) + Com(v)

is an endomorphism of L(E). Finally, for each i = 1, 2, …, c_{0} let Δ(i, i) := 1 + K(i, i)u(i, i) + Q(i)v(i) and form the matrix

Δ = (\begin{matrix}Δ(1, 1) & K(1, 2)u(1, 2) & … & K(1, c_{0})u(1, c_{0}) \\ K(1, 2)u(1, 2) & Δ(2, 2) & … & K(2, c_{0})u(2, c_{0}) \\ ⋮ & ⋮ & ... & ⋮ \\ K(c_{0}, 1)u(c_{0}, 1) & K(c_{0}, 2)u(c_{0}, 2) & … & Δ(c_{0}, c_{0}) \end{matrix}) .

Proposition 8.1. The determinant of A factorizes as

(8.5)  det A = det Δ × ∏_{i=1}^{c_{0}}(1 − v(i))^{Q(i)}.

Proof. There is no confusion in denoting both the endomorphism and its corresponding matrix by the same symbol. For each i, j = 1, 2, …, c_{0} let A(i, j) be the linear map, induced by A, that maps the space L(E_{j}) into L(E_{i}). Its corresponding matrix is of dimention (Q(i)+1)×(Q(j)+1). The matrix A itself is fully described by the contents of all the blocks A(i, j) (i, j = 1, 2, …, c_{0}).

If B is a matrix of order n × m, denote by B_{1,•}, B_{2,•}, …, B_{n,•} its n rows (from top to bottom) and by B_{•,1}, B_{•,2}, …, B_{•,m} its m columns (from left to right). Next define σ B to be the matrix whose rows are B_{1,•}, B_{2,•} −B_{1,•}, …, B_{n,•} −B_{1,•}. Also let α B be the matrix whose rows are B_{•,1} +B_{•,1} +⋯+B_{•,m}, B_{•,2}, …, B_{•,n}.

First apply σ α to the blocks A(i, j) (i > j) below the diagonal of the matrix A and α σ to the other blocks A(i, j) (i ≤ j). It is easily seen that those transformations keep invariant the value of the determinant. Its value does not change either if we further make the following shift of rows and columns in the resulting matrix: 1 → 1, Q(1) + 2 → 2, Q(1) + Q(2) + 3 → 3, …, Q(1) + ⋯ + Q(c_{0} − 1) + c_{0} → c_{0}. We obtain the matrix

D = (\begin{matrix}Δ & ⋆ & … & ⋆ \\ 0 & (1 − v(1))I_{Q(1)} & … & ⋆ \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & (1 − v(c_{0}))I_{Q(c_{0})} \end{matrix})

where Δ is the matrix defined above. Hence

det A = det D = det Δ × ∏_{i=1}^{c_{0}}(1 − v(i))^{Q(i)}.□

Using the endomorphism T = Succ − J defined in section 6, we have Com = T J. Accordingly, if we let v(i) = u^{2} for all i and replace all the u(i, j) by −u in the definition of A, we get A = I −u(T +J)+u^{2}T J = (I −uT)(I −uJ). But det(I −uJ)

is clearly equal to (1 − u^{2})^{c_{1}}. Hence det Δ ∏_{i=1}^{n}(1 − u^{2})^{Q(i)} = det Δ(1 − u^{2})^{2c_{1}−c_{0}} =

det(1 − uT) det(I − uJ), so that det(I − uT) = det Δ(1 − u^{2})^{c_{1}−c_{0}}, which is Bass’s identity (1.3).

Acknowledgements. The authors are thankful to Jean-Pierre Jouanolou who convinced them that the first evaluation of the Ihara-Selberg zeta function could be derived from Amitsur’s identity and to Jiang Zeng who drew their attentions to the paper by Reutenauer and Schützenberger. They finally thank Phil Hanlon who made several suggestions that improved the presentation of the paper.

References

1. Guido Ahumada, Fonctions périodiques et formule des traces de Selberg sur les arbres, C. R. Acad. Sci. Paris 305 (1987), 709-712.

2. S. A. Amitsur, On the Characteristic Polynomial of a Sum of Matrices, Linear and Multilinear Algebra 9 (1980), 177–182.

3. Hyman Bass, The Ihara-Selberg Zeta Function of a Tree Lattice, Internat. J. Math. 3 (1992), 717-797.

4. Pierre Cartier and Dominique Foata, Problèmes combinatoires de commutation et réarrangements, Springer-Verlag (Lecture Notes in Math., vol. 85), Berlin, 1969.

5. K.T. Chen, R.H. Fox and R.C. Lyndon, Free differential calculus, IV. The quotient groups of the lower central series, Ann. Math. 68 (1958), 81-95.

6. Dominique Foata, A combinatorial proof of Jacobi’s identity, Ann. Discrete Math. 6 (1980), 125-135.

7. Jean-Pierre Jouanolou, Personal communication (1996).

8. M. Lothaire, Combinatorics on Words, Addison-Wesley (Encyclopedia of Math. and its Appl., vol. 17), Reading, Mass., 1983.

9. (Major) P.A. MacMahon, Combinatory Analysis, vol. 1, Cambridge Univ. Press (Reprinted by Chelsea, New York, 1955), Cambridge, 1915.

10. Sam Northshield, Proofs of Ihara’s Theorem for Regular and Irregular Graphs, Proc. I.M.A. Workshop “Emerging Applications of Number Theory” (submitted) (1996).

11. Dominique Perrin, Personal communication (1996).

12. Christophe Reutenauer and Marcel-Paul Schützenberger, A Formula for the Determinant of a Sum of Matrices, Letters of Math. Physics 13 (1987), 299–302.

13. Gian-Carlo Rota, On the Foundations of Combinatorial Theory. I Theory of Möbius Function, Z. Wahrscheinlichkeitstheorie 2 (1964), 340–368.

14. Gian-Carlo Rota, Report on the present state of combinatorics (Inaugural address delivered at the 5th Formal Power Series and Algebraic Combinatorics Conference, Florence, 21 June 1993), Discrete Math. 153 (1996), 289–303.

15. Marcel-Paul Schützenberger, Sur une propriété combinatoire des algèbres de Lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire d’algèbre et de théorie des nombres [P. Dubreil, M.-L. Dubreil-Jacotin, C. Pisot, 1958-59], Secrétariat Mathématique, 11, rue Pierre-Curie, F-75005, 1960, pp. 1-01–1-13.

16. Marcel-Paul Schützenberger, On a factorization of free monoids, Proc. Amer. Math. Soc. 16 (1965), 21-24.

17. Richard P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks, Monterey, 1986.

18. H. M. Stark and A. A. Terras, Zeta Functions of Finite Graphs and Coverings, Adv. in Math. 121 (1996), 124-165.

19. Gérard Viennot, Algèbres de Lie libres et monoïdes libres, Springer-Verlag (Lecture Notes in Math., vol. 691), Berlin, 1978.

20. Doron Zeilberger, A Combinatorial Approach to Matrix Algebra, Discrete Math. 56 (1985), 61-72.

Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France

E-mail address: foata@math.u-strasbg.fr

Department of mathematics, Temple University, Philadelphia, Pennsylvania 19122

E-mail address: zeilberg@math.temple.edu