Dept. of Mathematics, Iowa State University

Fusion Relation in

Products of Association Schemes*

by

Dept. of Mathematics, Iowa State University,

Ames, IA 50011, U.S.A.

E-mail:

Abstract. Fusion relations between the association schemes obtained by direct product and wreath product are established via a study of their matrix representations. The character table of the scheme obtained by the wreath product is described and some algebraic properties of the products are derived.

Keywords: Commutative association schemes, character tables, fusion schemes.

______

* 1991 Mathematics Subject Classification. Primary 05E30; Secondary 05B99.

a Supported in part by- KOSEF, POSTECH, Korea

1.INTRODUCTION

One way to construct new association schemes is to form various products of smaller schemes. Two important constructions are the direct product and wreath product. The direct product of (symmetric) association schemes was first studied by Kusumoto [7], in connection with the construction of new incomplete block designs from a family of given designs. The concept of the wreath product is originated from the wreath product introduced by Weisfeiler [10, Section G, pp.43-45] in the study of cellular rings. Although the wreath product is a well-known standard construction in group theory, the concept of the wreath product is different from that of the wreath product in group theory and has almost no relevance.

Our aim is to develop some tools that can be used in the classification of association schemes. The current paper investigates the fusion relations between the association schemes that are obtained as the direct product and/or wreath product of smaller association schemes. The basic general definitions are given in section 2. The direct product and wreath product are examined in sections 3 and 4, respectively. Some algebraic properties of the direct product and wreath product operations are also discussed in these sections. Theorem 3.2 shows that the character table of a direct product of association schemes is the Kronecker product of the character tables of the direct factors. Theorem 4.1 shows that the wreath product of two association schemes is isomorphic to a fusion scheme of the direct product of the same two association schemes. Theorem 4.2 describes the character table of the wreath product explicitly in terms of the character tables of the factors. Theorem 4.5 shows the fusion relations between various mixed triple products.

2. ASSOCIATION SCHEMES AND THEIR FUSIONS

This section briefly describes the relevant terms and notational conventions which will be employed in future sections. For more elaborate explanations and a comprehensive treatment of the theory of association schemes, the reader is referred to [2][3][4]. Primarily, our discussion will focus on arbitrary association schemes (most often commutative ones).

Let X = (X,) be an association scheme of class d with |X| = u. The relations are conveniently described by their {0, 1}-adjacency matrices defined by if ; 0 otherwise. The intersection numbers are defined in terms of the relations for the scheme by the following formula:

= |{z : and }|

where (x, y) is a fixed member of the relation . The definition of an association scheme is equivalent to the following four axioms:

(1), (2), (3) for some , (4),

where and are the identity matrix and all-one matrix, respectively, and denotes the transpose of the matrix A. If the scheme is symmetric, then for all i. Commutativity of the scheme asserts that , and thus . If the scheme is commutative, the adjacency matrices generate a ()-dimensional commutative algebra over the complex field. This algebra is called the Bose-Mesner algebra of the scheme. The axioms of association schemes imply that the Bose-Mesner algebra is also closed under the Schur multiplication “” (also known as the Hadamard multiplication [2].) The Bose-Mesner algebra for a commutative association scheme, being semi-simple, admits precisely primitive idempotents . We can define the complex numbers according to the expressions . Thus, the number is characterized by the relation . That is, is the eigenvalue of , associated with the eigenspace spanned by the columns of , occuring with multiplicity = rank (). We define P to be the matrix whose ith- row and jth-column entry is . P is referred to as the character table (or first eigenmatrix) of association scheme X. We define the valencies of X by

.

We have the following formulas:

;, for i = 1, 2, . . ., d ; .

Given an association scheme X = (X,), it is sometimes convenient to represent the association scheme by its relation tableR(X), which is defined by the matrix R(X) =, where |X| = u. That is, the (x, y)-entry of R(X) is i if and only if (x, y) . (It is just one way to represent an association scheme. In algebraic point of view, it is only an element in the Bose-Mesner algebra and does not play any important role.)

Two association schemes X = (X,) and Y of class d are isomorphic if there is a bijection f from X to Y and a permutation of the index set such that whenever ,for each i = 1, 2, . . ., d. In this case, we write X Y.

Let X = (X,) be an association scheme of class d. An e-class association scheme Y = (X,) with is called a fusion scheme of X if each relation of Y is a nonempty union of some relations of X. In this case the association scheme X is called a fission scheme of Y. It is not hard to verify that:

Lemma 2.1.Let X = be an association scheme of class d. A partition of the index set {0, 1, . . ., d} with , gives rise to a fusion scheme G = with the relations defined by , = 0, 1, . . ., e, if and only if (1) for some {0, 1, . . ., e}, and

(2) for any {0, 1, . . ., e}, and any

.

The sum of the equality in (2) turns out to be the intersection number for G. For a commutative association scheme, a criterion for the existence of a fusion scheme in terms of its character table is given as follows [1] [5] [9].

Lemma 2.2.For a given commutative association scheme X = with its character table P, a partition of {0, 1, . . ., d} with , gives rise to a e-class fusion scheme G = with the relations defined by if and only if there exists a partition of {0, 1, . . ., d} with such that -block of P has constant row sum. The constant row sum turns out to be the -entry of the character table of the fusion scheme.

3. DIRECT PRODUCT

This section recalls the definition of the direct product of association schemes and describes the association relations in terms of its adjacency matrices, relation table and character table.

Let X = (X,) and Y = (Y,) be association schemes with |X| = u and |Y| = v. The direct productX  Y consists of relations including the diagonal relation on . The relation between the two ordered pairs and in is determined by the association relations between the first coordinates and in X and between the second coordinates and in Y. The h-th relation of X  Y, which we will denote , for h = i(e+1) + j (0id, 0je, ), is defined by

= {((x, y), (z, w)) | (x, z), (y, w)}.

Then, the reader can easily verify that X  Y is an association scheme. Furthermore, X  Y is commutative (resp. symmetric) if and only if X and Y are commutative (resp. symmetric). Let the adjacency matrices of X be and those of Y be . Then, with the above ordering of the relations, the h-th adjacency matrix of the direct product X  Y is given by for h. Here “” denotes the Kronecker product of two matrices and B. So the Bose-Mesner algebra of X  Y is generated by the set { | 0id, 0je} with the usual matrix operations: ,

, , etc. (To see the connection to the products of distance-regular graphs, we refer to [4, Section 12.4], where the notation X Y has been used instead of X  Y.)

Now the relation table of the direct product can be described by

R(X  Y ) =R(X) + R(Y).

By the definition of the direct product, YX is defined by the set of adjacency matrices . The relation table of YX is given by

R(YX) = R(Y)+ R(X).

This has the following consequence:

Lemma 3.1. X  Y YX.

Proof. Let be the permutation matrix which represents the permutation

The statement follows the fact that , thus the relation tables R(XY) and R(Y  X) are identical up to a permutation of the set. Hence X  Y is isomorphic to Y X.

The character table of a direct product is also the Kronecker product of the character tables of the direct factors.

Theorem 3.2.Let X and Y be commutative association schemes with respective character tables P(X) and P(Y). Then X  Y has the character table P(X Y) = P(X) P(Y).

Proof: Let P(X) = () and P(Y) = (). The Bose-Mesner algebras of X and Y which are generated by {} and {}, admit another bases and of orthogonal idempotents, related to the original bases by coefficients and, with and . The Bose-Mesner algebra of the direct product X  Y is spanned by the set of adjacency matrices. The set of orthogonal idempotents is a second basis for the Bose-Mesner algebra for the direct product X  Y with

=.

Let P(X  Y) be the character table of X  Y.Then by the above identity,

, for , .

Thus P(X Y) = P(X) P(Y), as required.

Remark. It is well known that the character table of the direct product of two groups is the tensor product of the character tables of the direct factors (as representations of direct product are tensor products of representations of the factors). In the development of a combinatorial character theory of quasigroups, Johnson and Smith [6, Sections 2 and 3] show that this result is still true for loops (nonassociative groups) but not for quasigroups in general. They proved this by using the centralizer ring of (i.e., the Bose-Mesner algebra of the association scheme coming from) the permutation action of the direct product of multiplication groups on the direct product of loops, as the group theoretic proof using representations is no longer available for loops.

4. WREATH PRODUCT

We describe next the wreath product X wrY which is a bit complicated to define abstractly. (A different description, in connection with graphs and cellular rings, can be found in [10, pp. 43-45].) Let X = () and Y = () be association schemes of order |X| = u and |Y| = v. The wreath product of X and Y is defined on the set ; but we take Y= {}, and regard as the disjoint union of v copies of X, where . The relations on are definedby the following rule:

(1) For any j, the relations between the elements of are determined by the

association relations between the first coordinates in X.

(2) The relations between the elements that belong to two different sets, say

and , are determined by the association relation of the second coordinates

and in Y and the relation is independent from the first coordinates.

That is, the relations of X wrY are defined by

, for ; and, for .

Then, it is easy to see that X wr Y is an association scheme. As in the direct product, X wr Y is commutative (resp. symmetric) if and only if X and Y are.

Let the adjacency matrices of X be and those of Y be . Then the adjacency matrices of X wr Y are given by

.

With this ordering of the relations, the relation matrix of the wreath product is described by

R(X wr Y)=R(X) + {R(Y) }.

By the definition, it is clear that X wr Y is not isomorphic to Y wr X in general. It is also clear that the adjacency matrices of X wr Y are among those of YX, while for each j, is a sum of adjacency matrices of Y X. Thus, each association relation of X wr Y can be obtained from the relations of Y X, by fusion. This proves the following important theorem:

Theorem 4.1. Let X and Y be arbitrary association schemes. Then X wr Y is a fusion scheme of YX. In particular, the ()-dimensional Bose-Mesner algebra of the wreath product X wr Y is a subalgebra of the Bose-Mesner algebra of Y  X.

The character table of the wreath product of two association schemes is now described by the following:

Theorem 4.2. Let X and Y be commutative association schemes with respective character tables P(X) and P(Y). Then the character table P(X wrY) of X wr Y, which is augmented by an additional column with the multiplicities of the idempotents corresponding to the rows, is given by

P(X wrY) =

where and are the principal submatrices of the character tables P(X) andP(Y) described as follows:

P(X) =, P(Y) =.

Proof. Let be primitive idempotents of X and Y, respectively. It is easy to check that is the set of primitive idempotents of the Bose-Mesner algebra of X wr Y. Note that , , and thus

and

.

Since , the multiplicities are and . This completes the proof.

Note that the character table of X wr Y is easily obtained from that of YX by applying Lemma 2.2 as follows. First, we obtain the character table of YX by taking the Kronecker product of P(Y) and P(X). Secondly, we add together all columns of P(YX) which correspond to a single relation of X wr Y. This is done for all classes , . We call the resulting matrix M. Finally, we delete all repetitive rows of M, leaving a square matrix P which turns out to be the character table of X wr Y.

Remark. The character tables of direct products of groups are obtained from those of direct products of association schemes attached to the groups. The character tables of direct products in two contexts are essentially the same (cf. [6] or [11]). However one can not obtain the character tables of wreath products of groups as an application of the results of this section. Unfortunately, they share the same name, but the wreath products in two contexts are hardly related. (For the character tables of wreath products of groups we refer to [8].)

Lemma 4.3.Let X and Y be schemes of class d and e with orders u and v, respectively. Let G be a fusion scheme of X and H a fusion scheme of Y. Then

(1)G H is a fusion scheme of X Y

(2)G wr H is a fusion scheme of X wr Y.

Proof. Let and be the respective adjacency matrices of X and Y. Let {} and {} be the partitions of and which describe the fusion relations for G and H. Then statement (1) follows from the fact that

, for each and i;

, for each j and .

Similarly, (2) follows from the formulas , for each , and

, for each , where and . This completes the proof.

Remark. Let denote the one-class association scheme of order u. Then wr is a (symmetric) two-class fusion scheme of X wr Y, for every association scheme X of order u and every association scheme Y of order v. This is one way to see that X wr Y is always imprimitive. Note that wr is the imprimitive association scheme coming from the completely multipartite strongly regular graph . Also, the primitivity is a monotone property with respect to fusion, i.e., all fission schemes of an imprimitive association scheme is necessarily imprimitive, and all fusion schemes of primitive schemes are primitive.

From the associativity of the Kronecker product of matrices, we find that the associative property holds for both product operations in the family of association schemes.

Lemma 4.4.For any schemes X, Y, and Z,

(1) (XY)ZX(YZ)

(2) (X wr Y) wr ZX wr (Y wr Z).

Proof. Let {| },{| , and {| be the sets of the respective adjacency matrices of X, Y and Z with respective orders u, v, and w. The set of adjacency matrices of (X wr Y) wr Z is given by

since , while that of X wr (Y wr Z) is given by

.

So, by the associativity of the Kronecker product, we see that the two schemes have the same set of adjacency matrices, and thus, (2) follows. It is easy to see that the two schemes in (1) also have the same adjacency matrices. This completes the proof.

Theorem 4.5. For any schemes X, Y, Z, the following hold:

(1) Xwr (YZ) (X wr Y)Z ; Xwr (YZ) (X wr Z)Y

(2) (XY) wr ZX(Y wr Z) ; (XY) wr Z Y(X wr Z)

where “ZX” denotes Z as isomorphic to a fusion scheme of X.

Proof. Let {| },{| , and {| be the sets of respective adjacency matrices of X, Y and Z. Then, the set of adjacency matrices of Xwr(ZY) is described by the union of three sets,, and with J =; while the number of classes of Z(X wr Y) is , and the set of adjacency matrices of Z (X wr Y) is the union of , and. Since the Kronecker product is associative and , for each it is clear that Xwr(Z Y) is a fusion scheme of Z(X wr Y). Since the direct product is commutative up to isomorphism, Xwr(YZ) is a fusion of(X wr Y)Z and a fusion of (XwrZ)Y simultaneously. Similarly, the statement (2) is proved.

5. EXAMPLE

Now we present the Hasse diagram of the partially ordered set of triple products of order 12 that are fusion schemes of , as an illustration of the constructions considered in this paper. The construction of this poset can be generalized to the products of four or more association schemes of higher order in an obvious manner.

(FIGURE GOES HERE)

Acknowledgement. The author is indebted to an anonymous referee who provided the complete proof of Theorem 4.2.

Figure: The Hasse diagram of the poset of triple product association schemes of order 12 that are fusion schemes of .

Class dAssociation schemes

11

8

7

6

5

4

3

REFERENCES

1. E. Bannai, Subschemes of some association schemes, J. Algebra144 (1991), 167-188.

2. E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Mathematics

Lecture Note Series No. 58, Benjamin/Cummings, Menlo Park, CA, 1984.

3. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-

Verlag, Berlin, 1989.

4. C. D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, NY, 1993.

5. K. W. Johnson and J. D. H. Smith, Characters of finite quasigroups III: Quotients and

fusion, European J. Combinatorics, 9 (1989), 47-56.

6. K. W. Johnson and J. D. H. Smith, Characters of finite quasigroups IV: Products and

superschemes, European J. Combinatorics, 10 (1989), 257-263.

7. K. Kusumoto, Association schemes of new types and necessary conditions for existence

of regular and symmetrical PBIB designs with those association schemes, Ann. Inst. Stat.

Math.19 (1967), 73-100.

8. S. Mattarei, On character tables of wreath products, J. Algebra, 175 (1995), 157-178.

9. M. E. Muzichuk, Subcells of the symmetric cells, in “Algebraic Structures and Their

Applications”, pp. 172-174, Kiev, 1988. [in Russian].

10. B. Weisfeiler (Ed.), On Construction and Identification of Graphs, Springer-Verlag,

Berlin, 1976.

11. A. Woldar, A combinatorial approach to the character theory of split metabelian groups.

J. Combin. Theory, Ser. A 50 (1989), no. 1, 100-109.

1