A NOTE ON ELEMENT CENTRALIZERS IN FINITE COXETER GROUPS.

MATJAŽ KONVALINKA, GÖTZ PFEIFFER, AND CLAAS E. RÖVER

Abstract. The normalizer N_{W} (W_{J}) of a standard parabolic subgroup W_{J} of a finite Coxeter group W splits over the parabolic subgroup with complement N_{J} consisting of certain minimal length coset representatives of W_{J} in W. In this note we show that (with the exception of a small number of cases arising from a situation in Coxeter groups of type D_{n}) the centralizer C_{W} (w) of an element w ∈ W is in a similar way a semidirect product of the centralizer of w in a suitable small parabolic subgroup W_{J} with complement isomorphic to the normalizer complement N_{J}. Then we use this result to give a new short proof of Solomon’s Character Formula and discuss its connection to MacMahon master theorem.

1. Introduction

Let W be a finite Coxeter group, generated by a set of simple reflections S with length function ℓ: W → ℕ∪{0}. Each subset J ⊆ S generates a so-called standard parabolic subgroup W_{J} = ⟨J⟩ of W. Conjugates of standard parabolic subgroups are called parabolic subgroups. These subgroups are themselves Coxeter groups and therefore play an important role in the structure theory of finite Coxeter groups. A well-known property of the cosets of a standard parabolic subgroup W_{J} in W is that each coset contains a unique element of minimal length. The subgroup W_{J} hence possesses a distinguished right transversal X_{J}, consisting of the minimal length coset representatives. Due to a theorem of Howlett [4] and later work of Brink and Howlett [1], it is known that and how the normalizer N_{W} (W_{J}) of the parabolic subgroup W_{J} is a semidirect product of W_{J} and a subgroup N_{J} consisting of precisely those minimal length coset representatives x ∈ X_{J} which leave J as subset of W invariant in the conjugation action of W on its subsets, i.e., N_{J} = {x ∈ X_{J} : J^{x} = J}.

In this note we show that most centralizers of elements in W enjoy a similar semidirect product decomposition. Pfeiffer and Röhrle [9] have shown, based on Richardson’s [10] characterization of involutions as central longest elements of parabolic subgroups of W, that if w ∈ W is an involution then its centralizer in W coincides with the normalizer of a parabolic subgroup, and as such is a semidirect product. This note can be regarded as a generalization of the result for involutions to all elements of W. Our results effectively reduce questions regarding the conjugacy classes of elements in a finite Coxeter group W to the cuspidal conjugacy classes, that is those conjugacy classes which are disjoint from any proper parabolic subgroup of W. Cuspidal conjugacy classes of elements of W play a central role in the algorithmic approach to the conjugacy classes of finite Coxeter groups in Chapter 3 of the book by Geck and Pfeiffer [3]. We refer the reader to this book as a general introduction to the theory of finite Coxeter groups.

Key words and phrases. Coxeter group, Solomon’s Character formula, MacMahon master theorem.

We will call certain conjugacy classes of elements of a finite Coxeter group W non-compliant; see Definition 4.6. Without exception, these are conjugacy classes of W which nontrivially intersect a parabolic subgroup of type D_{n} with n > 4. Hence, if W has no parabolic subgroups of type D, part (ii) of the following theorem applies without restrictions. We can now formulate our main theorem as follows.

Theorem 1.1. Let W be a finite Coxeter group and let w ∈ W. Let V be the smallest parabolic subgroup of W that contains w. Then the following hold.

(i) The centralizer C_{V} (w) = C_{W} (w)∩V is a normal subgroup of the centralizer C_{W} (w) with quotient C_{W} (w)/C_{V} (w) isomorphic to the normalizer quotient N_{W} (V)/V.

(ii) The centralizer C_{W} (w) splits over C_{V} (w) with complement isomorphic to N_{W} (V)/V unless w lies in a non-compliant conjugacy class of elements of W.

The parabolic subgroup V in the theorem is well-defined as the intersection of all parabolic subgroups of W that contain w, due to the fact that intersections of parabolic subgroups are parabolic subgroups, see Theorem 2.3 below. For the proof of the theorem, we will assume that w has minimal length in its conjugacy class in W. Then V is the standard parabolic subgroup W_{J} of W, where J = J(w), the set of generators occurring in a reduced expression for w. The proof of part (i) is carried out in Section 3. Part (ii) of the theorem is established case by case in Section 4. The results for the exceptional types of Coxeter groups have been obtained with the help of computer programs using the GAP [11] package CHEVIE [2]. These programs are available through the second author’s ZigZag [8] package. In Section 5, we use Theorem 1.1 to provide a new short proof of a theorem of Solomon, and then discuss its relation to MacMahon master theorem [5, page 98].

2. Preliminaries.

In this section we recall some results about distinguished coset representatives and conjugacy classes in a finite Coxeter group W, generated by a set of simple reflections S and with length function ℓ.

For w ∈ W, we set J(w) = {s_{1}, …, s_{l}} ⊆ S, if w = s_{1} … s_{l} is a reduced expression, i.e., if l = ℓ(w). As a consequence of Matsumoto’s theorem, J(w) does not depend on the choice of a reduced expression for w.

For w ∈ W, let

D(w) = {s ∈ S : ℓ(sw) < ℓ(w)}

be its descent set, and let

A(w) = {s ∈ S : ℓ(sw) > ℓ(w)} = S \ D(w)

be its ascent set. The set

X_{J} = {w ∈ W : J ⊆ A(w)}

is a right transversal for W_{J} in W, consisting of the elements of minimal length in each coset. For each element w ∈ W there are unique elements u ∈ W_{J} and x ∈ X_{J} such that w = u · x. Here the explicit multiplication dot indicates that the product ux is reduced, i.e., that ℓ(ux) = ℓ(u) + ℓ(x). An immediate consequence is the following lemma.

Lemma 2.1 ([3, Lemma 2.1.14]). Let J ⊆ S. Then ℓ(w^{x}) ≥ ℓ(w) for all w ∈ W_{J}, x ∈ X_{J}.

We denote the longest element of W by w_{0}. For J ⊆ S, we denote by w_{J} the longest element of the parabolic subgroup W_{J}.

Lemma 2.2. Let w ∈ W and let J = D(w). Then w = w_{J} · x for some x ∈ X_{J}.

Proof. This follows from [3, Lemma 1.5.2] and [3, Proposition 2.1.1] □

For J, K ⊆ S define X_{JK} = X_{J} ∩ X_{K}^{−1}. Then X_{JK} is a set of minimal length double coset representatives of W_{J} and W_{K} in W.

Theorem 2.3 ([3, Theorem 2.1.12]). Let J, K ⊆ S and let x ∈ X_{JK}. Then W_{J}^{x} ∩ W_{K} = W_{L}, where L = J^{x} ∩ K.

Theorem 2.4 ([3, Theorem 2.3.3]). Suppose J, K are conjugate subsets of S and that x ∈ X_{J} is such that J^{x} = K. If s ∈ D(x) then x = d · y, where d = w_{J}w_{L} for L = J ∪ {s}, and y ∈ X_{L}.

For the conjugacy classes of W, we are particularly interested in elements of minimal length. These elements have useful properties, such as the following.

Proposition 2.5 ([3, Corollary 3.1.11]). Let C be a conjugcay class of W and let w, w′ be elements of minimal length in C. Then J(w′) = J(w)^{x} for some x ∈ X_{J(w),J(w′)}.

A conjugacy class C of elements of W is called a cuspidal class if C ∩ W_{J} = ∅ for all proper subsets J of S. Cuspidal classes never fuse in the following sense.

Theorem 2.6 ([3, Theorem 3.2.11]). Let J ⊆ S and let w ∈ W_{J} be such that the conjugacy class C_{J} of w in W_{J} is cuspidal in W_{J}. Then

C_{J} = C ∩ W_{J},

where C is the conjugacy class of w in W.

If w is of minimal length in its conjugacy class, then it is also of minimal length in its conjugacy class in the Coxeter group W_{J(w)}, which by [3, Proposition 3.2.12] is a cuspidal class of W_{J(w)}

Below, we review some basic facts about Coxeter groups of classical type, that is of type A, B or D. For a more detailed review of the combinatorics of the conjugacy classes of finite Coxeter groups of classical type we refer the reader to the description [7] of the implementation of the character tables of these groups in GAP.

2.1. Type A. Suppose W is a Coxeter group of type A_{n−1}. Then W is isomorphic to the symmetric group 𝔖_{n} on the n points [n] = {1, …, n}, with Coxeter generators s_{i} = (i, i + 1), i = 1, …, n − 1. The cycle type of a permutation w ∈ W is the partition of n, which contains a part l for each l-cycle of w, where fixed points count as 1-cycles. Since any two elements of w are conjugate in W if and only if they have the same cycle type, the conjugacy classes of elements of W are naturally parametrized by the partitions of n.

Here, it will be convenient to write partitions as weakly increasing sequences. Given a partition λ = (λ_{1}, …, λ_{t}) of n (that is a sequence of positive integers λ_{1} ≤ ⋯ ≤ λ_{t} with λ_{1} + ⋯ + λ_{t} = n), there is a corresponding parabolic subgroup W_{J} = 𝔖_{λ_{1}} × ⋯ × 𝔖_{λ_{t}} containing an element w with cycle type λ. A particular element of minimal length in this conjugacy class is the product w_{λ} of t disjoint cycles consisting of λ_{i} successive points, for i = 1, …, t. For example, a minimal length representative of the conjugacy class of elements with cycle structure 1124 in 𝔖_{8} is w_{1124} = (1)(2)(3, 4)(5, 6, 7, 8) = (3, 4)(5, 6, 7, 8).

Note that w_{λ} is a Coxeter element of W_{J}, the product

w_{λ} = ∏_{s_{i}∈J} s_{i} (2.1)

(in decreasing order) of all s_{i} ∈ J. For example, J(w_{1124}) = {s_{3}, s_{5}, s_{6}, s_{7}}, and w_{1124} = s_{7}s_{6}s_{5}s_{3}.

2.2. Type B. Suppose W is a Coxeter group of type B_{n}. Then W is isomorphic to the group of permutations on {−n, …, −1, 0, 1, …, n} satisfying w(−i) = −w(i). Alternatively, we can represent this group as the group of signed permutations, i.e. injective maps from [n] to [n] ∪ −[n] with precisely one of i and −i in the image. Since the elements are permutations, we can write them in cyclic form. We have two types of cycles: cycles which do not contain i and −i for any i, and cycles in which i is an element if and only if −i is an element. Cycles of the first type come in natural pairs, and instead of (i_{1}, i_{2}, …, i_{k})(−i_{1}, −i_{2}, …, −i_{k}), we write (i_{1}, i_{2}, …, i_{k}) and call it a positive cycle. Cycles of the second type are of the form (i_{1}, i_{2} …, i_{k}, −i_{1}, −i_{2}, …, −i_{k}). We shorten that to (i_{1}, i_{2}, …, i_{k})^{−} and call it a negative cycle. For example, the permutation

−4 ↦ −2, −3 ↦ 1, −2 ↦ 4, −1 ↦ 3, 0 ↦ 0, 1 ↦ −3, 2 ↦ −4, 3 ↦ −1, 4 ↦ 2

is written as (1, −3)(2, −4)^{−}. In this notation, every signed permutation looks like an ordinary permutation in cyclic form, except that every element and every cycle can have a minus sign. Note that we can change the sign of all elements in a cycle without changing the signed permutation. The Coxeter generators are t_{1} = (1)^{−} and s_{i} = (i, i + 1), i = 1, …, n − 1. We also set t_{i} = (i)^{−}, for i > 1.

An element w ∈ W (B_{n}) can also be represented in the form of a signed permutation matrix. This is an n × n matrix which acts on the standard basis {e_{1}, …, e_{n}} of ℝ^{n} in the same way as the permutation w acts on the points [n] = {1, …, n}, i.e., for i ∈ [n], it maps e_{i} to e_{|w(i)|} or its negative, depending on whether w(i) is positive or negative. We will briefly use this matrix representation of W (B_{n}) in Section 4.6.

Since conjugation on a signed permutation in cyclic form works in the same way as with usual permutations (if we conjugate with w, an element i of any cycle is replaced by w(i)), two signed permutations are conjugate if and only if they have the same number of negative cycles of every length, and the same number of positive cycles of every length. The cycle type of a permutation w ∈ W is a double partition λ = (λ^{+}, λ^{−}) with |λ^{+}| + |λ^{−}| = n, so that λ^{+} contains a part l for each positive l-cycle of w, and λ^{−} contains a part l for each negative l-cycle of w. Two elements of W are conjugate in W if and only if they have the same cycle type, and therefore the conjugacy classes of elements of W are naturally parametrized by the double partitions of n. For example, the conjugacy class of (1, 5, −2)(4, 7)(3)^{−}(6, −8)^{−} is (21, 32).

Take J ⊆ {t_{1}, s_{1}, s_{2}, …, s_{n−1}} and w ∈ W_{J}. If s_{i} ∉ J, the elements i + 1, …, n appear in positive cycles of w with all positive elements. Therefore, if we are given a double partition (λ^{+}, λ^{−}) of n, λ^{+} = (λ_{1}^{+}, …, λ_{t}^{+}), λ^{−} = (λ_{1}^{−}, …, λ_{s}^{−}), the smallest parabolic subgroup W_{J} that contains an element of cycle type (λ^{+}, λ^{−}) is of the form W (B_{|λ^{−}|}) × 𝔖_{λ_{1}^{+}} × ⋯ × 𝔖_{λ_{t}^{+}}. According to the description [3, 3.4.2] of conjugacy classes of W, there is a minimal length representative w_{λ} of the corresponding conjugacy class of the following form. The negative cycles contain 1, …, |λ^{−}|, and the positive cycles contain |λ^{−}| + 1, …, n; furthermore, each cycle contains only consecutive numbers in increasing order. For example, a minimal length representative of the conjugacy class corresponding to λ = (112, 23) is w_{λ} = (1, 2)^{−}(3, 4, 5)^{−}(6)(7)(8, 9).

2.3. Type D. Suppose W is a Coxeter group of type D_{n}. Then W is isomorphic to the group of permutations on {−n, …, −1, 0, 1, …, n} satisfying w(−i) = −w(i) and with an even number of i > 0 satisfying w(i) < 0. Alternatively, we can represent this group as the group of signed permutations with an even number of i mapping to −[n]. These are precisely the signed permutations with an even number of negative cycles. The Coxeter generators are u = (1, −2) and s_{i} = (i, i + 1), i = 1, …, n − 1. The cycle type of a permutation w ∈ W is a double partition (λ^{+}, λ^{−}) with |λ^{+}| + |λ^{−}| = n, so that λ^{+} contains a part l for each positive l-cycle of w, and λ^{−} contains a part l for each negative l-cycle of w. If two elements of W are conjugate, they have the same cycle type. Having the same cycle type, however, is not a sufficient condition for conjugacy. For example, u and s_{1} have the same cycle type but are not conjugate. It is easy to see that if they have the same cycle type (λ^{+}, λ^{−}) and |λ^{−}| > 0 or λ^{+} contains an odd part, they are conjugate. If they have the same cycle type (λ^{+}, ∅), where λ^{+} contains only even parts, they are conjugate if and only if the number of negative numbers in their cycle decomposition has the same parity.

We call a partition even if it consists of even parts only. The conjugacy classes of elements of W are naturally parametrized by double partitions of n, where λ^{−} has an even number of parts, with two classes when λ^{−} = ∅ and λ^{+} is even. Given a double partition (λ^{+}, λ^{−}) of n, λ^{+} = (λ_{1}^{+}, …, λ_{t}^{+}), λ^{−} = (λ_{1}^{−}, …, λ_{s}^{−}), s even, the corresponding parabolic subgroup W_{J} is of the form W (D_{|λ^{−}|}) × 𝔖_{λ_{1}^{+}} × ⋯ × 𝔖_{λ_{t}^{+}}. Furthermore, there is a minimal length representative w_{λ} of the corresponding conjugacy class of the following form. The negative cycles contain 1, …, |λ^{−}|, the positive cycles contain |λ^{−}| + 1, …, n, and each cycle contains only consecutive numbers in increasing order. If λ^{−} = ∅ and λ^{+} has only even parts, then there is an extra representative w′_{λ} with the first positive cycle starting with −1 instead of 1. For example, for λ = (112, 23), we have w_{λ} = (1, 2)^{−}(3, 4, 5)^{−}(6)(7)(8, 9), and for (224, ∅), we have w_{λ} = (1, 2)(3, 4)(5, 6, 7, 8) and w′_{λ} = (−1, 2)(3, 4)(5, 6, 7, 8).

3. Centralizers.

In this section we prove a general theorem about the structure of element centralizers in finite Coxeter groups. It is shown to be a consequence of Theorem 2.6, which in the book [3] has been established by a careful case-by-case analysis. Without loss of generality, we may assume that w ∈ W is an element of minimal length in its conjugacy class in W.

Theorem 3.1. Suppose w ∈ W has minimal length in its conjugacy class in W and let J = J(w). Then C_{W} (w)W_{J} = N_{W} (W_{J}).

Clearly, part (i) of Theorem 1.1 follows from this result.

Proof. Denote by C the conjugacy class of w in W and by C_{J} its conjugacy class in W_{J}, which is cuspidal in W_{J}. By Theorem 2.6, C_{J} = C ∩ W_{J}, which implies that for every x ∈ N_{W} (W_{J}) there exists an element u ∈ W_{J} with w^{x} = w^{u}. So xu^{−1} ∈ C_{W} (w), i.e. x ∈ C_{W} (w)W_{J}, and hence N_{W} (W_{J}) ⊆ C_{W} (w)W_{J}.

Now it only remains to show that C_{W} (w) ⊆ N_{W} (W_{J}). Let y ∈ C_{W} (w) and write it as y = uxv^{−1} for u, v ∈ W_{J} and a double coset representative x ∈ X_{JJ}.

From w ∈ C_{J} ∩ C_{J}^{y} it then follows that w^{v} ∈ C_{J} ∩ C_{J}^{x} ⊆ W_{J} ∩ W_{J}^{x} = W_{J∩J^{x}}, by Theorem 2.3, and since C_{J} is a cuspidal class in W_{J}, we must have J ∩ J^{x} = J, whence x ∈ N_{J} ⊆ N_{W} (W_{J}) and thus y = uxv^{−1} ∈ N_{W} (W_{J}). □

The following additional results are of independent interest and will be used in the proof of Theorem 5.1 below.

Proposition 3.2. Suppose w ∈ W has minimal length in its conjugacy class in W and let J = J(w). Then the following hold.

(i) The conjugacy class of w in W is a disjoint union of conjugates of the conjugacy class of w in W_{J}.

(ii) If a ∈ C_{W} (w) and x ∈ X_{J} are such that C_{W_{J}} (w)a ⊆ W_{J}x, then x ∈ N_{J}. (iii) If x ∈ X_{J} is such that ℓ(w^{x}) = ℓ(w), then J(w^{x}) = J^{x}. (iv) If v ∈ W is such that ℓ(w^{v}) = ℓ(w), then J(w^{x}) = J^{x}, where v = u · x

with u ∈ W_{J} and x ∈ X_{J}.

Proof. (i) and (ii) follow from the proof of Theorem 3.1.

(iii) Let K = J(w^{x}). By Proposition 2.5, there exists an element y ∈ X_{KJ} such that K^{y} = J. Hence w^{xy} ∈ W_{J} and ℓ(w^{xy}) = ℓ(w^{x}) = ℓ(w) and (since C ∩ W_{J} = C_{J}) w^{xy} = w^{u} for some u ∈ W_{J}. Moreover, X_{K} = yX_{J}. Hence u^{−1}xy centralizes w^{u}, and if we write u^{−1}xy = a · z for a ∈ W_{J} and z ∈ X_{J} then, by (ii), z ∈ N_{J}. It follows that zy^{−1} ∈ X_{JK} is the unique minimal length representative of the coset W_{J}x, hence x = zy^{−1} and J^{x} = J(w^{x}).

(iv) We have w^{v} = (w^{u})^{x}. Conjugation with x does not decrease the length (Lemma 2.1), so ℓ(w) = ℓ(w^{v}) ≥ ℓ(w^{u}) and therefore ℓ(w^{u}) = ℓ(w). By (iii), with w replaced by w^{u}, we have J(w^{v}) = J(w^{u})^{x}, and J(w^{u}) = J(w), which finishes the proof. □

4. Complements.

In this section we prove part (ii) of Theorem 1.1 for each type of irreducible finite Coxeter group, case by case. We start with the general observation that part (ii) of the theorem is straightforward in the following situations.

Lemma 4.1. Let w ∈ W be an element of minimal length in its conjugacy class in W, and let J = J(w). If w is cuspidal in W or if C_{W_{J}} (w) = W_{J} then N_{J} is a complement of C_{W_{J}} (w) in C_{W} (w).

Proof. If w is cuspidal then W_{J} = W and both quotients N_{W} (W_{J})/W_{J} and C_{W} (w)/C_{W_{J}} (w) are trivial.

If C_{W_{J}} (w) = W_{J} then w = w_{J} and C_{W} (w) = N_{W} (W_{J}) [9, Proposition 2.2]. □

Our general strategy in search of a centralizer complement for w will be to identify a complement M of W_{J} in its normalizer that centralizes w. More precisely, we have the following consequence of Theorem 3.1.

Proposition 4.2. Let w ∈ W be of minimal length in its conjugacy class, let J = J(w) and suppose that the normalizer complement N_{J} is generated by elements x_{1}, …, x_{r}. Let u_{1}, …, u_{r} ∈ W_{J} be such that u_{i}x_{i} ∈ C_{W} (w), i = 1, …, r, and set M = ⟨u_{1}x_{1}, …, u_{r}x_{r}⟩. Then M is a complement of C_{W_{J}} (w) in C_{W} (w) provided that M ∩ W_{J} = 1.

Proof. Clearly, W_{J}M = W_{J}N_{J} = N_{W} (W_{J}). From M ∩W_{J} = 1 it then follows that M is a complement of W_{J} in its normalizer. Moreover, M is a subgroup of C_{W} (w) since each of its generators centralizes w. From Theorem 3.1 it then follows that M is a complement of C_{W_{J}} (w) in C_{W} (w). □

4.1. Type A. Let λ = (1^{a_{1}}, 2^{a_{2}}, …, n^{a_{n}}) be a partition of n, let w_{λ} be as in (2.1) and let J = J(w_{λ}). Then W_{J} is a direct product

W_{J} = 𝔖_{1}^{a_{1}} × 𝔖_{2}^{a_{2}} × ⋯ × 𝔖_{n}^{a_{n}}

of symmetric groups, and its normalizer

N_{W} (W_{J}) = 𝔖_{1} ≀ 𝔖_{a_{1}} × 𝔖_{2} ≀ 𝔖_{a_{2}} × ⋯ × 𝔖_{n} ≀ 𝔖_{a_{n}}

is a direct product of wreath products of symmetric with symmetric groups. In a similar way, the centralizer

C_{W} (w_{λ}) = C_{1} ≀ 𝔖_{a_{1}} × C_{2} ≀ 𝔖_{a_{2}} × ⋯ × C_{n} ≀ 𝔖_{a_{n}}

is a direct product of wreath products of cyclic with symmetric groups, and the centralizer

C_{W_{J}} (w_{λ}) = C_{1}^{a_{1}} × C_{2}^{a_{2}} × ⋯ × C_{n}^{a_{n}}.

is a direct product of cyclic groups. Clearly, the quotients N_{W} (W_{J})/W_{J} and C_{W} (w_{λ})/C_{W_{J}} (w_{λ}) are both isomorphic to 𝔖_{a_{1}} × 𝔖_{a_{2}} × ⋯ × 𝔖_{a_{n}}. In order to show that the particular normalizer complement N_{J} is also a complement of C_{W_{J}} (w_{λ}) in C_{W} (w_{λ}), we introduce some notation. Let us define as

s(o, m) = (s_{o+1}s_{o+2} ⋯ s_{o+2m−1})^{m} = (o + 1, o + 2, …, o + 2m)^{m} (4.1)

the permutation that swaps, after an offset o, two adjacent blocks of m points {o+ 1, …, o + m} and {o + m + 1, …, o + 2m}. For example, s(2, 3) = (s_{3}s_{4}s_{5}s_{6}s_{7})^{3} = (3, 4, 5, 6, 7, 8)^{3} = (3, 6)(4, 7)(5, 8). And s_{i} = s(i − 1, 1). Then

N_{J} = 𝔖_{a_{1}} × 𝔖_{a_{2}} × ⋯ × 𝔖_{a_{n}}

is a direct product of symmetric groups 𝔖_{a_{m}}, with Coxeter generators s(o_{m}, m), s(o_{m}+m, m), …, s(o_{m}+(a_{m}−2)m, m), and offsets

o_{m} = a_{1} + 2a_{2} + ⋯ + (m − 1)a_{m−1}, (4.2)

for those m ∈ {1, …, n} with a_{m} > 0.

Proposition 4.3. Let λ be a partition of n, let w_{λ} be the permutation with cycle structure λ from (2.1) and let J = J(w_{λ}) be the corresponding subset of S. Then N_{J} is a complement of C_{W_{J}} (w_{λ}) in C_{W} (w_{λ}).

Proof. It suffices to consider the case λ = (m^{a}) since all of W_{J}, N_{W} (W_{J}), C_{W} (w_{λ}), C_{W_{J}} (w_{λ}), and N_{J} are subgroups of the direct product

𝔖_{1a_{1}} × 𝔖_{2a_{2}} × ⋯ × 𝔖_{na_{n}}

inside 𝔖_{n} and one can argue componentwise.

If λ = (m^{a}), then N_{J} is isomorphic to 𝔖_{a}, with a−1 Coxeter generators s(o, m), s(m, m), …, s((a−2)m, m), permuting the blocks of m points

{1, …, m}, {m+1, …, 2m}, …, {(a−1)m+1, …, am}.

Clearly

w_{λ} = (1, …, m)(m+1, …, 2m) ⋯ ((a−1)m+1, …, am)

is centralized by N_{J}. The claim now follows from Theorem 3.1. □

4.2. Type B. Let λ be a double partition of n with λ^{+} = (1^{a_{1}}, 2^{a_{2}}, …, n^{a_{n}}) and λ^{−} = (1^{b_{1}}, 2^{b_{2}}, …, n^{b_{n}}), let w_{λ} be as in Section 2.2, and let J = J(w_{λ}) be the corresponding subset of S. Then W_{J} is a direct product

W_{J} = W (B_{|λ^{−}|}) × 𝔖_{1}^{a_{1}} × 𝔖_{2}^{a_{2}} × ⋯ × 𝔖_{n}^{a_{n}}

and its normalizer

N_{W} (W_{J}) = W (B_{|λ^{−}|}) × 𝔖_{1} ≀ W (B_{a_{1}}) × 𝔖_{2} ≀ W (B_{a_{2}}) × ⋯ × 𝔖_{n} ≀ W (B_{a_{n}})

is a direct product of W (B_{|λ^{−}|}) with wreath products of symmetric groups and Coxeter groups of type B. In a similar way, the centralizer

C_{W} (w_{λ}) = C_{W (B_{|λ^{−}|})}(w_{λ}) × C_{1} ≀ W (B_{a_{1}}) × C_{2} ≀ W (B_{a_{2}}) × ⋯ × C_{n} ≀ W (B_{a_{n}})

is a direct product of C_{W (B_{|λ^{−}|})}(w_{λ}) and wreath products, and the centralizer

C_{W_{J}} (w_{λ}) = C_{W (B_{|λ^{−}|})}(w_{λ}) × C_{1}^{a_{1}} × C_{2}^{a_{2}} × ⋯ × C_{n}^{a_{n}}

is a direct product of C_{W (B_{|λ^{−}|})}(w_{λ}) and cyclic groups. Clearly, the quotients N_{W} (W_{J})/W_{J} and C_{W} (w_{λ})/C_{W_{J}} (w_{λ}) are both isomorphic to W (B_{a_{1}}) × W (B_{a_{2}}) × ⋯ × W (B_{a_{n}}). In order to show that a variant of the particular normalizer complement N_{J} is a complement of C_{W_{J}} (w_{λ}) in C_{W} (w_{λ}), we introduce some more notation.

Denote by r(o, m) the permutation defined by

x.r(o, m) = \begin{cases}2o + m + 1 − x, & if o + 1 ≤ x ≤ o + m, \\ x, & otherwise. \end{cases}

In this way, r(o, m) = (o + 1, o + m)(o+2, o+m−1) ⋯ reverses the range {o + 1, …, o + m} and thus is the longest element of the symmetric group 𝔖_{{o+1,...,o+m}} with Coxeter generators s_{o+1}, …, s_{o+m−1}. For example, r(2, 5) = (3, 7)(4, 6).

Moreover, denote

t(o, m) = (o+1)^{−}(o+2)^{−} ⋯ (o+m)^{−},

which acts as −1 on the points {o+1, o+2, …, o+m} and as identity everywhere else.

If λ^{+} = (m^{a}) and λ^{−} = ∅, then W_{J} is a direct product of a copies of 𝔖_{m} and N_{J} is isomorphic to W (B_{a}), with Coxeter generators

r(0, m) t(0, m) and s(0, m), s(m, m), …, s((a−2)m, m).

In general, if λ^{+} = (1^{a_{1}}, 2^{a_{2}}, …, n^{a_{n}}), then W_{J} is a direct product of W (B_{|λ^{−}|}) and direct products of isomorphic symmetric groups 𝔖_{m} and N_{J} is a direct product of groups W (B_{a_{m}}), with Coxeter generators

r(o_{m}, m) t(o_{m}, m) and s(o_{m}, m), s(o_{m} + m, m), …, s(o_{m} + (a_{m}−2)m, m) and offsets

o_{m} = |λ^{−}| + a_{1} + 2a_{2} + ⋯ + (m − 1)a_{m−1}, (4.3)

for those m ∈ {1, …, n} with a_{m} > 0. Unfortunately, this group N_{J} usually does not centralize w_{λ}. However, if we define a group N_{λ} as the subgroup of W generated by the same elements as N_{J}, with t(o_{m}, m) in place of r(o_{m}, m) t(o_{m}, m), then N_{λ} is a centralizing complement.

Proposition 4.4. Let λ be a double partition of n, let w_{λ} be as in Section 2.2, and let J = J(w_{λ}) be the corresponding subset of S. Then

N_{λ} = ⟨t(o_{m}, m), s(o_{m}+km, m) | k = 0, …, a_{m}−2, m = 1, …, n, a_{m} > 0⟩

is a complement of C_{W_{J}} (w_{λ}) in C_{W} (w_{λ}).

Proof. Clearly, N_{λ} centralizes w_{λ} since its generators t(o_{m}, m) and s(o_{m}+km, m) do. The statement now follows with Proposition 4.2 from the fact that N_{λ} is a complement of W_{J} in its normalizer in W. □

4.3. Type D. The case of Coxeter groups of type D_{n} is best dealt with by comparing it to the situation in type B_{n}. Throughout this section, we assume n ≥ 4, denote by W the Coxeter group of type B_{n} with Coxeter generators S, as described in Section 2.2, and by W^{+} the Coxeter group of type D_{n} with Coxeter generators S^{+}, consisting of the signed permutations with an even number of negative cycles as described in Section 2.3.

The following properties are easy to establish and we leave their proofs to the reader.

Lemma 4.5. Let w ∈ W be an element of cycle type λ = (λ^{+}, λ^{−}) such that λ^{−} has an even number of parts and that w has minimal length in its conjugacy class in W. Also let J = J(w). Then the following hold.

(i) w has minimal length in its class in W^{+}.

(ii) If λ^{−} = ∅ and λ^{+} is even then C_{W^{+}}(w) = C_{W} (w), otherwise C_{W^{+}}(w) has

index 2 in C_{W} (w). (iii) If J^{+} = S^{+} ∩ W_{J} then W_{J^{+}}^{+} is the smallest parabolic subgroup of W^{+}

containing w.

(iv) If λ^{−} = ∅ then J^{+} = J, otherwise W_{J^{+}}^{+} = W_{J} ∩W^{+} is a subgroup of index

2 in W_{J}

(v) C_{W_{J^{+}}^{+}}(w) = C_{W_{J}} (w) ∩ W^{+} is a subgroup of index 2 in C_{W_{J}} (w) unless λ^{−} = ∅.

(vi) If λ^{+} is not even and λ^{−} = ∅ then N_{J^{+}}^{+} = N_{J} ∩ W^{+} is a subgroup of index 2 in N_{J}, otherwise N_{J} ≅ N_{J^{+}}^{+}.

The parabolic subgroup W_{J^{+}}^{+} is of the form D_{|λ^{−}|} × 𝔖_{λ_{1}^{+}} × ⋯ × 𝔖_{λ_{t}^{+}}, where D_{m} is the subgroup of W^{+} generated by {u, s_{1}, …, s_{m−1}}, for m = 2, …, n.

Definition 4.6. We call a double partition λ = (λ^{+}, λ^{−}) a non-compliant double partition if λ^{+} consists of a single odd part m and λ^{−} is a nonempty even partition of even length.

We call a conjugacy class C of W a non-compliant class, if, for some odd n > 4, there is a non-compliant double partition λ of n and a parabolic subgroup W_{M} of W which has an irreducible component W_{K} of type D_{n}, such that C contains an element of W_{M} whose projection on W_{K} has cycle type λ.

For example, the elements of W = W (D_{5}) with cycle type (1, 22) form a noncompliant class. For another example, the elements of W = W (D_{7}) of cycle type (21, 22) form a non-compliant class, as some of them lie in a parabolic subgroup W_{M} of type D_{5} × A_{1}, with D_{5}-part of cycle type (1, 22).

Lemma 4.7. An element w ∈ W (D_{n}) of cycle type λ = (λ^{+}, λ^{−}) lies in a noncompliant class if and only if λ^{+} is not even and λ^{−} is nonempty and even.

The next result shows that, in a Coxeter group W^{+} of type D_{n}, the centralizer C_{W^{+}}(w) splits over C_{W_{J}^{+}}(w), unless the class of w ∈ W^{+} is non-compliant. Here, we write J^{+}(w) ⊆ S^{+} for the set of generators occurring in a reduced expression of w when considered as an element of W^{+}, in order to distinguish it from the set J(w) ⊆ S of generators in a reduced expression of w ∈ W.

Proposition 4.8. Let λ = (λ^{+}, λ^{−}) be a double partition of n be such that ℓ(λ^{−}) is even. Let w_{λ} and N_{λ} be as in Proposition 4.4 and let J^{+} = J^{+}(w_{λ}) be the corresponding subset of S^{+}. Then the following hold.

(i) If λ^{+} is even then N_{λ} is a complement of C_{W_{J^{+}}^{+}}(w_{λ}) in C_{W^{+}}(w_{λ}).

(ii) If λ^{+} is not even and λ^{−} = ∅ then N_{λ} ∩ W^{+} is a subgroup of index 2 in N_{λ} and a complement of C_{W_{J^{+}}^{+}}(w_{λ}) in C_{W^{+}}(w_{λ}).

(iii) If λ^{+} = (1^{a_{1}}, …, n^{a_{n}}) and λ^{−} = (λ_{1}^{−}, …, λ_{s}^{−}) is not even then there is an index j ≤ s such that k = λ_{1}^{−} + ⋯ + λ_{j}^{−} is odd, and the subgroup

N_{λ}^{+} = ⟨t(0, k)^{m} t(o_{m}, m), s(o_{m}+im, m) | i = 0, …, a_{m}−2, m = 1, …, n, a_{m} > 0⟩

is a complement of C_{W_{J^{+}}^{+}}(w_{λ}) in C_{W^{+}}(w_{λ}).

Note that t(0, k)^{m} = 1 if m is even and t(0, k)^{m} = t(0, k) if m is odd.

Proof. Let J = J(w_{λ}) be the subset of S corresponding to λ. In all three cases it suffices to find a complement N^{∗} of W_{J} in its normalizer in W that centralizes w_{λ} such that |N^{∗} ∩ W^{+}| = |N_{J^{+}}^{+}|. For then N^{∗} ∩ W_{J^{+}}^{+} = 1 and N_{W^{+}}(W_{J^{+}}^{+}) ⊆ N_{W} (W_{J}) = W_{J}N^{∗} imply that N^{∗} ∩ W^{+} is a complement of W_{J^{+}}^{+} in its normalizer in W^{+} that centralizes w_{λ}, and the claim follows with Proposition 4.2.

(i) If λ^{+} is even then N_{λ} is contained in W^{+} and N^{∗} = N_{λ} will do.

(ii) If λ^{−} = ∅ and λ^{+} is not even then J^{+} = J but N_{J^{+}} is subgroup of index 2 in N_{J} and N^{∗} = N_{λ} ∩ W^{+} will do.

(iii) If λ^{−} is not even then N_{λ}^{+} is a complement of W_{J} in its normalizer in W that is contained in W^{+} and centralizes w_{λ}, whence N^{∗} = N_{λ}^{+} will do. □

4.4. Type I. Suppose W is a Coxeter group of type I_{2}(m). Then W is the group generated by generators s_{1} and s_{2} satisfying (s_{1}s_{2})^{m} = (s_{2}s_{1})^{m}. Each element of W is either cuspidal or an involution. Hence the theorem for this type follows from Lemma 4.1.

4.5. Exceptional Types. Although in type A each conjugacy class contains an element w such that the normalizer complement N_{J} is also a centralizer complement, this cannot be expected in general to be the case. However, from the preceding examples one sees that it is frequently possible to construct from N_{J} an isomorphic copy N_{J}^{∗} which is a centralizer complement. In each of the above examples, N_{J}^{∗} is obtained from N_{J} by replacing generators x_{i} of N_{J} by products w_{L}x_{i} for suitable subsets L ⊆ J.

Based on this observation, we formulate an algorithm, which in practice always finds a centralizer complement, except for elements of non-compliant classes.

Algorithm CentralizerComplement. Input: A finite Coxeter group W and an element w of minimal length in its conjugacy class in W. Output: a centralizer complement for w, or fail if none exists.

1. set J ← J(w).

2. find involutions x_{1}, …, x_{r} generating the normalizer complement N_{J}.

3. for each element v of minimal length in the W_{J}-conjugacy class of w do

the following: • let u ∈ W_{J} be such that v^{u} = w;

• for each i = 1, …, r, set

Y_{i} ← \begin{cases}\{x_{i}\}, & if v^{x_{i}} = v, \\ \{w_{L}x_{i} : L ⊆ J, x_{i}^{w_{L}} = x_{i}, v^{w_{L}} = v^{x_{i}}\}, & otherwise. \end{cases}

• if there are elements y_{i} ∈ Y_{i}, i = 1, …, r, such that M = ⟨y_{1}, …, y_{r}⟩

satisfies M ∩ W_{J} = 1 then return M^{u}.

4. return fail (if we ever get here).

Note that, by Proposition 4.2, any group M found in this way is necessarily a complement of the centralizer of w in W_{J}.

For W irreducible of exceptional type, the algorithm produces a centralizer complement in all but seven cases. Each case corresponds to a non-compliant class from the following table. In this table we list, for each non-compliant class C of W, its position i in CHEVIE’s list of conjugacy classes of W, its name, a reduced expression for a representative w of minimal length, the set J(w), a set M ⊇ J(w), the type of W_{M} exhibiting a direct factor of type D_{2l+1}, and the label λ of the conjugacy class of W (D_{2l+1}) containing the projection of w.

W i  name  w ∈ C J(w)  M  type  λ
E_{6} 7  D_{4}(a_{1})  _{342345} 2345 12345  D_{5}  (1, 22)
E_{7} 9  D_{4}(a_{1})  _{425423} 2345 12345  D_{5}  (1, 22)
42 D_{4}(a_{1}) + A_{1} _{4254237} 23457 123457 D_{5} × A_{1} (1, 22)
E_{8} 16  D_{4}(a_{1})  _{242345} 2345 12345  D_{5}  (1, 22)
44  D_{6}(a_{1})  _{24234567} 234567 2345678  D_{7}  (1, 42)
53 D_{4}(a_{1}) + A_{2} _{34234578} 234578 1234578 D_{5} × A_{2} (1, 22)
73 D_{4}(a_{1}) + A_{1} _{3542348} 23458 123458 D_{5} × A_{1} (1, 22)

In the next section we show that in all of these cases, and indeed whenever w lies in a non-compliant class, no complement exists.

4.6. Non-compliance. The class of W (D_{5}) with label λ = (1, 22) contains the element

w_{λ} = ts_{1}s_{2}s_{1}ts_{1}s_{2}s_{3} = (ts_{1}t)s_{2}(ts_{1}t)s_{1}s_{2}s_{3} = us_{2}us_{1}s_{2}s_{3},

which lies in the parabolic subgroup W_{J} of type D_{4}. Its centralizer C_{W_{J}} (w) in W (D_{4}) has order 16 and its centralizer C_{W} (w) in W (D_{5}) has order 32. However, C_{W_{J}} (w) has no complement in C_{W} (w), since the coset C_{W} (w) \ C_{W_{J}} (w) contains no element of order 2 (as a straightforward computation in GAP will confirm).

The next result shows that this is indeed always the case, when the cycle type of w ∈ W (D_{n}) is a non-compliant double partition of n.

Proposition 4.9. Suppose that W is of type D_{n} and let w ∈ W be an element of minimal length in its conjugacy class with J(w) = J. If the cycle type of w ∈ W is a non-compliant double partition of n then the centralizer C_{W_{J}} (w) has no complement in C_{W} (w).

Proof. Recall from Section 2.2 that elements of W (B_{n}) can be represented as signed permutation matrices, i.e., matrices with exactly one non-zero entry 1 or −1 in each row and column. Such an element lies in W (D_{n}) if and only if its matrix has an even number of entries −1, and it is an involution if and only if the matrix is symmetric.

Now suppose that n = m + k is odd and that w ∈ W = W (D_{n}) is an element of minimal length in a conjugacy class with cycle type λ = (λ^{+}, λ^{−}) where the partition λ^{+} consists of a single odd part m and λ^{−} is a nontrivial partition of an even number k, consisting of an even number of even parts. Then W_{J} for J = J(w) has type D_{k} × A_{m−1} and, by the description of N_{J} in Section 4.2 and Lemma 4.5(vi), its normalizer N_{W} (W_{J}) has a complement of order 2 (and of type B_{1}), generated by the quotient w_{J}w_{0}.

We may assume that J = S \ {s_{k+1}}, so that, as signed permutation on the set {1, …, n}, the element w induces an even number of negative cycles on the k points {1, …, k} and a positive m-cycle on the m points {k + 1, …, n}. The centralizer C_{W} (w) cannot move points from outside the m-cycle into the m-cycle and thus consists of block diagonal matrices

diag(A, B) = [ \begin{matrix}A & 0 \\ 0 & B \end{matrix} ] ,

of a k × k matrix A and an m × m-matrix B, which modulo 2 have the same number of entries −1 since C_{W} (w) is a subgroup of W (D_{n}). Moreover, for each element diag(A, B) in C_{W} (w) the number of entries −1 on the diagonal of A, is even, since with every point in {1, …, k} being mapped to its negative, the entire cycle which contains it must be negated.

The centralizer of w in W_{J} consists precisely of those elements diag(A, B) ∈ C_{W} (w) which have an even number of entries −1 in both A and B, since A is the matrix of an element in W (D_{k}).

Let u be an involution in C_{W} (w). Then its matrix diag(A, B) is symmetric, and an even number of entries −1 on the diagonal of A implies that both A and B have an even number of entries −1 and thus u ∈ C_{W_{J}} (w).

It follows that C_{W_{J}} (w) has no complement in C_{W} (w). □

More generally, if w lies in a non-compliant class of a finite Coxeter group W, then its centralizer has no complement.

Theorem 4.10. Let W be a finite Coxeter group. Suppose w is an element of minimal length in a non-compliant conjugacy class of W with J(w) = J. Then the centralizer C_{W_{J}} (w) has no complement in C_{W} (w).

Proof. Suppose first that W is a direct product W_{1} × W_{2} of nontrivial standard parabolic subgroups W_{1} and W_{2}, that w = w_{1}w_{2} with w_{1} ∈ W_{1} and w_{2} ∈ W_{2}, and that w_{1} lies in a non-compliant class of W_{1}. Then W_{J} = W_{J_{1}} × W_{J_{2}} for certain subsets J_{1} ⊆ W_{1} ∩S and J_{2} ⊆ W_{2} ∩S. If C_{W_{J_{1}}}(w_{1}) has no complement in C_{W_{1}}(w_{1}) then C_{W_{J}} (w) cannot have a complement in C_{W} (w) = C_{W_{1}}(w_{1}) × C(w_{2}).

Next, suppose that w ∈ W_{L} for some L ⊆ S and that w lies in a non-compliant class of W_{L}. Suppose N is a complement of C_{W_{J}} (w) in C_{W} (w), that is C_{W} (w) = C_{W_{J}} (w) ⋊ N. Then the centralizer of w in W_{L},

C_{W_{L}}(w) = C_{W} (w) ∩ W_{L} = (C_{W_{J}} (w) ⋊ N) ∩ W_{L} = C_{W_{J}} (w) ⋊ (N ∩ W_{L}),

in contradiction to our assumption that w lies in a non-compliant class. The theorem now follows from Definition 4.6 and Proposition 4.9. □

5. Applications.

In this section we first use Theorem 1.1 to prove a result about minimal length representatives of conjugacy classes. Then we show how it implies the celebrated Solomon’s character formula. Finally, we discuss the interpretation of Solomon’s theorem as a Coxeter group analogue of MacMahon master theorem.

Theorem 5.1. Assume w has minimal length in its conjugacy class in W. Then the following hold for any v ∈ W:

(i) J(w^{v}) = D(v^{−1}) ⟺ v = w_{J(w)};

(ii) J(w^{v}) = A(v^{−1}) ⟺ v = w_{J(w)}w_{0}.

Proof. Let L = D(v^{−1}). Then v^{−1} = w_{L} · x for some x ∈ X_{L}, by Lemma 2.2. Clearly ℓ((w^{v})^{w_{L}}) = ℓ(w^{v}), since J(w^{v}) = L. By Lemma 2.1, conjugation by the coset representative x does not decrease the length, hence ℓ(w^{v}) = ℓ((w^{v})^{w_{L}}) ≤ ℓ((w^{v})^{w_{L}x}) = ℓ(w) and it follows that w^{v} has minimal length in its conjugacy class as well. By Proposition 2.5, L = J(w^{v}) and J(w) are conjugate subsets of S. Proposition 3.2 (iv) says more precisely that x is a conjugating element, i.e., L^{x} = J(w).

Assume that ℓ(x) > 0 and let s ∈ D(x). Then s ∉ L, since x ∈ X_{L}; denote L ∪ {s} by M. By Theorem 2.4, x is a reduced product x = d · y with y ∈ X_{M} and d = w_{L}w_{M}, the longest coset representative of W_{L} in W_{M}. It follows that v^{−1} = w_{L} · x = w_{M} · y, whence M ⊆ D(v^{−1}) = L ⊊ M. The contradiction shows that x = 1, and therefore v = w_{L} and L = J(w).

(ii) Note that J(w^{w_{0}}) = J(w)^{w_{0}}, D(x^{w_{0}}) = D(x)^{w_{0}}, and A(x) = D(xw_{0}) for all x ∈ W, whence D(x)^{w_{0}} = A(w_{0}x). Therefore, it follows from (i) that

J(w^{xw_{0}}) = J(w^{x})^{w_{0}} = D(x^{−1})^{w_{0}} = A((xw_{0})^{−1}) ⟺ x = w_{J(w)},

as desired, for v = xw_{0}. □

The following formula, first proved by Solomon [12] in 1966, is an easy consequence of the previous result.

Theorem 5.2 (Solomon’s theorem). For J ⊆ S, let π_{J} denote the permutation character of the action of W on the cosets of W_{J} defined by π_{J}(w) = |Fix_{W/W_{J}} (w)|, and let ϵ be the sign character of W, defined by ϵ(w) = (−1)^{ℓ(w)} for w ∈ W. Then

∑_{J⊆S}(−1)^{|J|}π_{J} = ϵ.

Proof. The formula follows if we can show that ∑_{J⊆S}(−1)^{|J|}π_{J}(w) = ϵ(w) for all w ∈ W. We have W_{J}xw = W_{J}x ⟺ xwx^{−1} ∈ W_{J}, so

∑_{J⊆S}(−1)^{|J|}π_{J}(w) = ∑_{J⊆S}(−1)^{|J|} ∑_{\begin{matrix}x∈X_{J} \\ xwx^{−1}∈W_{J} \end{matrix}} 1 = ∑_{x∈W} ∑_{J(xwx^{−1})⊆J⊆A(x)}(−1)^{|J|},

where we reversed the order of summation and used the facts that x ∈ X_{J} ⟺ J ⊆ A(x) and xwx^{−1} ∈ W_{J} ⟺ J(xwx^{−1}) ⊆ J. The Binomial Theorem implies that

∑_{A⊆J⊆B}(−1)^{|J|} = (−1)^{|A|} ∑_{I⊆B\A}(−1)^{|I|} = \begin{cases}(−1)^{|A|} & if A = B, \\ 0 & otherwise. \end{cases}

But then

∑_{J⊆S}(−1)^{|J|}π_{J}(w) = ∑_{\begin{matrix}x∈W \\ J(xwx^{−1})=A(x) \end{matrix}}(−1)^{|A(x)|}.

Since ∑_{J⊆S}(−1)^{|J|}π_{J} is a class function, it is enough to choose w with minimal length in its conjugacy class. By Theorem 5.1(ii), this sum then consists only of the one term for x^{−1} = w_{J(w)}w_{0}, and we have

∑_{J⊆S}(−1)^{|J|}π_{J}(w) = (−1)^{|A(w_{0}w_{J(w)})|}.

But |A(w_{0}w_{J(w)})| = |D(w_{J(w)})^{w_{0}} | = |D(w_{J(w)})| = |J(w)| and then the claim follows from the fact that (−1)^{|J(w)|} = (−1)^{ℓ(w)} [3, Exercise 3.17]. □

Solomon proves this formula generically for all types of finite Coxeter groups, and he has published three different versions of the proof. His original proof [12] depends on an application the Hopf trace formula to the Coxeter complex of the finite Coxeter group W, a later proof (of a more general statement) uses a decomposition of the group algebra of W. The third version of the proof [14] is based on properties of a homomorphism of the descent algebra of W into the character ring of W (see also [3, Exercise 3.15]). None of these proofs have the combinatorial flavor of the above proof.

Finally, let us explain how to interpret Solomon’s theorem as a generalization of a special case of the celebrated MacMahon master theorem. For a connection with a different result due to MacMahon, see [13, §6].

MacMahon’s master theorem states that for a matrix X = (x_{ij})_{n×n}, the functions

(5.1)  \frac{1}{det(Id − X)},

where Id denotes the n × n-identity matrix, and

∑_{w} x_{v_{1}w_{1}}x_{v_{2}w_{2}} ⋯ x_{v_{m}w_{m}},

where w = w_{1}w_{2} ⋯ w_{m} runs over all words in {1, 2, …, n} and v = v_{1}v_{2} ⋯ v_{m} is the weakly increasing rearrangement of w, are equal. In particular, for any permutation w ∈ S_{n}, the coefficient of x_{1w(1)} ⋯ x_{nw(n)} in (5.1) is equal to 1. For I ⊆ [n], denote by X_{I} the submatrix (x_{ij})_{i,j∈I}. We have

\frac{1}{det(Id − X)} = \frac{1}{∑_{I⊆[n]}(−1)^{|I|} det X_{I}} = \frac{1}{1 − ∑_{∅≠I⊆[n]}(−1)^{|I|−1} det X_{I}}

= ∑_{k≥0}( ∑_{∅≠I⊆[n]}(−1)^{|I|−1} det X_{I})^{k} = ∑_{k≥0} ∑(−1)^{|I_{1}|−1+...+|I_{k}|−1} det X_{I_{1}} ⋯ det X_{I_{k}},

where the last sum runs over all k-tuples (I_{1}, …, I_{k}) of non-empty subsets of [n]. Since we are interested in the coefficient of x_{1w(1)} ⋯ x_{nw(n)} (in which all indices are represented, and each index is represented only twice, once as a first index and once as a second index), we can limit the sum to ordered set partitions (I_{1}, …, I_{k}) of the set [n]. Note that we have (−1)^{|I_{1}|−1+...+|I_{k}|−1} = (−1)^{n−k}.

Recall that the symmetric group S_{n} is a Coxeter group W of type A_{n−1} with Coxeter generators S = {s_{1}, …, s_{n−1}}, s_{i} = (i, i + 1). Choose a composition λ ⊢ n. By Merris-Watkins formula [6] (and not hard to prove independently), the coefficient of x_{1w(1)} ⋯ x_{nw(n)} in

∑ det X_{I_{1}} ⋯ det X_{I_{k}},

where the sum runs over all ordered set partitions (I_{1}, …, I_{k}) of [n] with |I_{j}| = λ_{j} for all j, is equal to (−1)^{ℓ(w)}π_{J}(w), where J is the subset of S that corresponds to the composition λ. This means that

∑(−1)^{n−|λ|}(−1)^{ℓ(w)}π_{J}(w) = 1,

where the sum runs over all subsets J of S. This is obviously equivalent to Solomon’s theorem.

Acknowledgement. The second author wishes to acknowledge support from Science Foundation Ireland.

References

[1] Brigitte Brink and Robert B. Howlett, Normalizers of parabolic subgroups in Coxeter groups, Invent. Math. 136 (1999), 323–351.

[2] Meinolf Geck, Gerhard Hiß, Frank Lübeck, Gunter Malle, and Götz Pfeiffer, CHEVIE — A system for computing and processing generic character tables, Appl. Algebra Engrg. Comm. Comput. 7 (1996), 175–210.

[3] Meinolf Geck and Götz Pfeiffer, Characters of finite Coxeter groups and Iwahori-Hecke algebras, London Mathematical Society Monographs. New Series, vol. 21, Oxford University Press, New York, 2000.

[4] Robert. B. Howlett, Normalizers of parabolic subgroups of reflection groups, J. London Math. Soc. (2) 21 (1980), 62–80.

[5] P. A. MacMahon, Combinatory analysis, 2 vols., Cambridge University Press, 1915-1916, reprinted in one volume by Chelsea, New York, 1960.

[6] Russell Merris and William Watkins, Inequalities and identities for generalized matrix functions, Linear Algebra Appl. 64 (1985), 223–242.

[7] Götz Pfeiffer, Character tables of Weyl groups in GAP, Bayreuth. Math. Schr. (1994), no. 47, 165–222.

[8] Götz Pfeiffer, ZigZag — A GAP3 Package for Descent Algebras of Finite Coxeter Groups, 2010, Version 0.77, electronically available at http://schmidt.nuigalway.ie/zigzag.

[9] Götz Pfeiffer and Gerhard Röhrle, Special involutions and bulky parabolic subgroups in finite Coxeter groups, J. Aust. Math. Soc. 79 (2005), no. 1, 141–147.

[10] R. W. Richardson, Conjugacy classes of involutions in Coxeter groups, Bull. Austral. Math. Soc. 26 (1982), 1–15.

[11] Martin Schönert et al., GAP – Groups, Algorithms, and Programming, Lehrstuhl D für Mathematik, RWTH Aachen, fifth ed., 1995, Home page: http://www.gap-system.org.

[12] Louis Solomon, The orders of the finite Chevalley groups, J. Algebra 3 (1966), 376–393.

[13] , A decomposition of the group algebra of a finite Coxeter group, J. Algebra 9 (1968), 220–239.

[14] , A Mackey formula in the group ring of a Coxeter group, J. Algebra 41 (1976), 255–268.

M.K.: Department of Mathematics, Vanderbilt University, Nashville TN, USA

E-mail address: matjaz.konvalinka@vanderbilt.edu

G.P., C.E.R.: School of Mathematics, Statistics and Applied Mathematics, NUI Galway, University Road, Galway, Ireland

E-mail address: goetz.pfeiffer@nuigalway.ie, claas.roever@nuigalway.ie