Algebraic Combinatorics -- The Decomposition Theorem

The Decomposition Theorem

The Decomposition Theorem

Redfield's theorem allows to express the solutions of many enumeration problems as cap products of cycle indicator polynomials. We consider a few examples.

Lemma: The number of orbits of H^G on n_iⁿ, where H,G <= S_n , is equal to the cap-product
C(H,n)ÇC(G,n).

Proof: The set of bijections n_iⁿ can be identified with the set M_c of classes of column equivalent 2´n-matrices containing injective n-tuples over n as rows, so that Redfield's theorem yields the statement.

Noticing that bijections are permutations, we can reformulate this lemma as follows:

Corollary: The cap product C(H,n)ÇC(G,n) is equal to the number of classes of elements sÎS_n with respect to the following equivalence relation:
s₁~s₂ iff $pÎH,rÎG: s₁=ps₂r^-1.
In other words, this cap product is equal to the number of (H,G)-double cosets in S_n . More explicitly, in terms of intersections of conjugacy classes C^a of the symmetric group S_n with H and G, this cap product is equal to
(1)/( | H | | G | )å_{a|¾| n} | C^aÇH | | C^aÇG | Õ_k a_k!k^a_k

=(n!)/( | H | | G | ) å_{a|¾| n}( | C^aÇH | | C^aÇG | )/( | C^a | ).

An expression for the number of graphs can also be obtained from Redfield's Counting Theorem as follows. A labelled graph with v vertices and e edges can be considered as an injective mapping f from [v choose 2] to [v choose 2], where the i-th pair of vertices is connected by an edge if and only if f(i) <= e. This together with the lemma above gives:

Corollary: The number of graphs with v vertices and e edges is equal to the cap product
C(S_v ,[v choose 2])ÇC(S_e ÅS_{[v choose 2]\e}).

More generally we obtain for the number of G-classes on nⁿ, which consist of mappings with prescribed content the following result:

Corollary: The number of G-classes of content (b₁, ...,b_m) on mⁿ is equal to the cap product
C(G,n)ÇC(S_b₁Å...ÅS_{b_m},n).

We shall return to this later. Tools from linear representation theory will allow a further elucidation of Redfield's methods and results. Furthermore we can derive an algorithm for a redundancy free construction of representatives of the G-classes on Y^X from the last corollary.

Besides this useful cap operation Redfield introduced a cup operation È, defined to be the linear extension of the following operation on monomials:

Y^cÈ...ÈY^d:=(Y^cÇ...ÇY^d)Y^d.

It clearly has the following property:

Lemma: The cap product C(H,n)ÇC(G,n) is equal to the sum of the coefficients in the cup product C(H,n)ÈC(G,n).

This shows that it should be useful to examine cup products of cycle indicator polynomials. In fact it is possible to write each such cup product as a sum of cycle indicators of stabilizers. We shall prove this result of Redfield with the aid of the following lemma:

Redfield's Lemma Let _GX be a finite action, w₁,...,w_r its orbits, x_iÎw_i and c:G -> Q[Y] a class function. Then we have for the stabilizers G_i:=G_{x_i} of these representatives that
(1)/( | G | )å_gÎGc(g) | X_g | =å_i=1^r (1)/( | G_i | )å_{gÎG_i}c(g).

Proof:

| G | å_i(1)/( | G_i | )å_{gÎG_i}c(g)= å_i | w_i | å_{gÎG_i}c(g)

=å_xÎXå_{gÎG_x} c(g)=å_gc(g) | X_g | .

We are now in a position to prove the main theorem of Redfield's first paper:

Redfield's Decomposition Theorem Assume that we are given subgroups H₁,...,H_m of S_n and an action of ´_iH_i on M_c. Let w₁,...,w_r denote the orbits, choose representatives A_iÎw_i, and denote by G_i their stabilizers. Then each G_i is conjugate in ´^mS_n to a subgroup of the diagonal D(´^mS_n ), and the cup product of the cycle indicator polynomials of the H_i can be decomposed with the aid of the G_i as follows:
C(H₁,n)È...ÈC(H_m,n)=å_i=1^r(1)/( | G_i | ) å_{(p₁,...,p_m)ÎG_i}Õ_k=1ⁿy_k^a_k(p₁).

Proof: Recall the action in question:

(´_i H_i)´M_c -> M_c:((p₁,...,p_m),(a_ik)_c) -> (p_ia_ik)_c.

Then A is a matrix, the rows of which are injective n-tuples over n, i.e. they can be identified with elements of S_n , and hence M can be identified with ´^mS_n . The equivalence relation ~_c can therefore be expressed in group theoretical terms as follows. If AÎM is identified with (r₁,...,r_m), BÎM with (r₁',...,r_m'), then

A~_c B iff $sÎS_n : (r₁',...,r_m')= (r₁s,...,r_ms).

Thus the equivalence class A_c can be identified with the following left coset of the diagonal subgroup:

{(r₁s,...,r_ms) | sÎS_n }=(r₁,..., r_m)D(´^mS_n ).

Analogously we can rewrite Redfield's action of ´_iH_i on M_c as follows:

((p₁,...,p_m),(r₁,..., r_m)_c) -> (p₁r₁,...,p_mr_m)_c.

The stabilizer of A_c=(r₁,...,r_m)_c is the subgroup

H₁´...´H_mÇ(r₁,...,r_m)D(´^mS_n ) (r₁, ...,r_m)^-1,

and hence is conjugate to a subgroup of the diagonal, as is claimed.

In order to prove the second part of the assertion, we first of all note that by the definition of the cup operation we have that

È_i=1^mC(H_i,n)=(1)/(Õ_i | H_i | ) å(Õ_ka_k!k^a_k)^m-1 Õ_ky_k^a_k,

where

(Õ_ka_k!k^a_k)^m-1=a₁((p₁,..., p_m))

where the sum is taken over all the (p,...,p_m)Î´_iH_i such that a(p₁)=...=a(p_m)=(a₁,...,a_n). In order to show that this cup product can be decomposed as claimed, we apply Redfield's Lemma. We therefore introduce the class function c:´_iH_i -> Q[Y], defined by

c((p₁,...,p_m)):=Õ_ky_k^a_k for each i Îm: a(p_i)=(a₁,...,a_n),

c((p₁,...,p_m)):=0 otherwise.

Then the cup operation together with Redfield's Lemma yields the statement.

Putting m:=1, we obtain the following decomposition of the cycle indicator polynomial according to the stabilizers of the orbits:

Corollary: Consider H£S_n with orbits w₁,..., w_r on Y^X, representatives f_iÎw_i and stabilizers G_i of these representatives. Then the cycle indicator polynomial C(H,n) is equal to the following sum:
C(H,n)=å_i=1^r(1)/( | G_i | )å_{pÎG_i}Õ_k=1ⁿ y_k^a_k(p).

Examples: Let us also consider a few examples of the particular case m:=2. Redfield's Decomposition Theorem yields
C(H₁,n)ÈC(H₂,n)=å_i=1(1)/( | G_i | ) å_{(p₁,p₂)ÎG_i}Õ_ky_k^a_k(p₁).
The mapping
j:M_c -> S_n :(r₁,r₂)_c -> r₁r₂^-1
is clearly a bijection, and it has the property
j((p₁,p₂)(r₁,r₂)_c)=p₁r₁r₂^-1p₂^-1,
which means that the orbit of (r₁,r₂)_c is mapped onto the (H₁,H₂)-double coset H₁r₁r₂^-1H₂. The stabilizer of (r,1)_c,rÎS_n , is conjugate to the intersection (r^-1H₁r´H₂)ÇD(S_n ´S_n ), and we have obtained:
Corollary: If {p₁,...,p_r} is a transversal of the (H₁,H₂)-double cosets of S_n , then, by Redfield's Decomposition Theorem, we have
C(H₁,n)ÈC(H₂,n)=å_i=1^rC(p_i^-1H₁p_iÇH₂,n).

Special cases are
C(A_n,n)ÈC(A_n,n)= | A_n\S_n /A_n | ·C(A_n,n),
and (exercise)
C(S_n-1,n)ÈC(S_n-1,n)= C(S_n-1,n)+C(S_n-2,n).

Redfield's Decomposition Theorem shows that a good knowledge of the conjugacy classes of subgroups of D(´^mS_n ) is important. We can obtain the desired information from a transversal of the left cosets of the normalizer of D(´^mS_n ) in ´^mS_n . In order to get such a transversal we derive the following theorem which describes, for an arbitrary finite G, the lattice of subgroups in between D(´^m G) and ´^mG. Then we shall evaluate, for particular cases, the normalizer of D(´^mG) and consider applications.

Theorem: Let G be a finite group and lÎN^*. The lattice of subgroups of ´^lG, the normalizer of which contains D(´^lG), is isomorphic to the lattice of subgroups in between D(´^l+1G) and ´^l+1G. A lattice isomorphism is provided by the mapping
U -> (U | G):={(u₁g,...,u_lg,g) | (u₁,...,u_l) ÎU,gÎG}.

Proof: It is easy to check that U -> (U | G) is of the desired form and injective. We have to show that it is surjective and that it respects the lattice operations. In order to do this we consider the action of (´^l+1G) on ´(´^lG), defined by

((g₁,...,g_l+1), (g₁',...,g_l')) -> (...,g_ig_i'g_l+1^-1,...).

This action is clearly transitive, and the stabilizer of the identity element 1 is D(´^l+1G). Consider a subgroup H, where

D(´^l+1G) <= H <= ´^l+1G,

and the orbit w of 1 under H, i.e. consider w:=H((1,...,1)). For any (g₁',...,g_l')Îw there exists an element (h₁,..., h_l+1)ÎH such that (g₁',...,g_l')=(h₁h_l+1^-1,...,h_l h_l+1^-1). And as H contains the diagonal subgroup D(´^l+1G), we have that

(h₁,...,h_l,1)ÎH iff (h₁,...,h_l)Îw.

Using this remark it is easy to check that w is a subgroup of ´^lG, the normalizer of which in ´^lG contains the diagonal of ´^lG, and that furthermore H=(w | G) holds. Hence the mapping U -> (U | G) is not only injective but also surjective and compatible with the lattice structure.

This theorem has the following consequence:

Corollary: The lattice of subgroups in between D(G´G) and G´G, where G is a finite group, is isomorphic to the lattice of normal subgroups of G.

Recall now the definition of Z(G), the center of G:

Z(G):={hÎG | hg=gh, for each gÎG}.

One easily checks that

Z(´^m G)=´^mZ(G).

Theorem: The normalizer of D(´^l+1G) in ´^l+1G is the subgroup
(Z(´^lG) | G)={(g₁g,...,g_lg,g) | g_iÎZ(G),gÎG}.

Proof: It is obvious, that (Z(´^lG) | G) is a subgroup of the normalizer. Consider (h₁,...,h_l) not ÎZ(´^lG). There exist iÎl and gÎG such that h_igh_i^-1 not = g. The last component of

h^*:=(h₁,...,h_l,1)(g,...,g)(h₁,...,h_l,1)^-1

shows that h^* not ÎD(´^l+1G). But each subgroup between D(´^l+1G) and ´^l+1G is of the form (U | G) described in the last theorem. In particular the normalizer of D(´^l+1G) has this form, and therefore it is the normalizer of a subgroup of (Z(´^lG) | G).

As the normalizer N_G(U) of U <= G is the stabilizer of U under the conjugation operation of G on the subgroup lattice L(G), a knowledge of a transversal of the left cosets of N_G(U) in G suffices to describe the conjugacy class of U. If {g₁,...,g_r} is such a transversal, then

[~U] ={g₁Ug₁^-1,...,g_rUg_r^-1}.

Consider, for example, the symmetric group S_n . For n>2, the center of S_n consists of 1 only, so that the diagonal subgroup D(´^l+1S_n ) is equal to its normalizer in ´^l+1S_n . A transversal of the left cosets of the diagonal subgroup of ´^l+1S_n is

{(p₁,...,p_l,1) | (p₁,...,p_l)Î´^lS_n }.

Exercises

E: Prove the formula for cup products of symmetric groups.

E: Prove that the cup product of m factors of C(S_n-1 is given by:
C(S_n-1,n)È...ÈC(S_n-1,n)=å_k=1^mS(m,k) C(S_n-k,n),
where S(m,k) denotes a Stirling number of the second kind.
Hint: Prove first the following result of Foulkes: For each subgroup H <= S_n
C(H,n)È...ÈC(H,n)=(1)/(n!)å_{a|¾| n} ((n! | C^aÇH | )/( | H | | C^a | ))^m Õ_kx_k^a_k.
holds. Use the fact that x^m=å_k=0^mS(m,k)(x)_k.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

The Decomposition Theorem