01_device


Kazanidis, P.A.

18

*Corresponding author

Science Diliman 20:1, 18-23

SOME IMPORTANT DEFINITIONS

Definition 1. Let Ω be any non-empty set. Let R be
a partition of Ω ×  Ω. (Ω,R) is a coherent
configuration if the following axioms are satisfied:

(a) The set {(α, α) | α ∈ Ω} is a union of some
elements of R. This set is called the diagonal.

(b) For each class C ∈ R, the transpose C* which
is defined as {(β, α) | (α, β) ∈ C} is a class in R.

(c) For all C
i
,C

j
 and C

k
 in R and for any (α, β) ∈

C
k
, there is a non-negative number pk

ij
 such that

the number of γ satisfying

(α, γ) ∈ C
i
 ∧ (γ, β) ∈ C

j
(1)

is equal to pk
ij
 . This number is independent of the

choice of (α, β) ∈ C
k
.

If G is a permutation group on Ω and R is the set of
orbitals then, (Ω, R) is called the coherent
configuration associated with G. The group G is said

Fission and fusion schemes and the action of
the diagonal group D(T, n)

Priscila Alejandro Kazanidis*
Institute of Mathematics, College of Science

University of the Philippines, Diliman, Quezon City
Email: cristyale35@yahoo.com

Date submitted: March 15, 2006; Date accepted: July 9, 2008

ABSTRACT

This  paper  is a closer look at associate classes of an association scheme.  The orbitals of a  subgroup
D(T, n)  of  the  full  automorphism   group of the association schemes served as building blocks for the
fusion schemes.

Keywords: association scheme, fusion and fission schemes, orbital, intersection number, permutation,
group action

to be generously transitive on Ω if given any (α, β)
∈ Ω ×  Ω, there is an element g ∈ G such that

(α, β)g = (β, α) (2)

Replace item (b) by

(b’) For each class C, C*= C.

With (b’), the coherent configuration is called
association scheme. If item (a) is replaced by

(a’) The diagonal is one class in R,

then, (Ω, R)  with R as a set of orbitals is called an
association scheme associated with the transitive
permutation group G. A group G with association
scheme (Ω, R) which is generously transitive is
necessarily transitive on the elements of Ω.

Some relations between association schemes are
defined here.

Definition 2. Consider the following association
schemes.

A1 = (Ω, R
1
) ∧ A

2
 = (Ω,R

2
) (3)



Fission and fusion schemes and the action of the diagonal group D(T; n)

19Science Diliman 20:1, 18-23

The association scheme A
1
 is finer than A

2
 if  for all

C
k
 ∈R

1
, there exists C

l
 ∈ R

2
 such that C

k
 ⊂ C

l
. Also,

A
2 

is said to be coarser than A
1
. The association

scheme A
1
 is fission scheme while A

2
 is called a

fusion scheme.

THE DIAGONAL GROUP

Diagonal groups were defined  by Cameron (Cameron,
1999) and the following are their  definition in terms of
generators (Alejandro, et al., 2003). A diagonal group
D(T, n) where T is a group and n a positive integer is a
permutation group acting on a non-empty set Ω given
by

Ω = {[x
1
, x

2
, . . . , x

n
]|x

i
 ∈ T} (4)

The following are the generators of D(T, n):

(a) the group Tn acting by right translation, that is the
permutations

      [x
1
, x

2
, . . . , x

n
]    [x

1
t
1
,  x

2
t
2
, . . . , x

n
t
n
] (5)

for t
1
, t

2
, . . . , t

n
 ∈ T;

(b) the automorphism group of T, acting coordinate-
wise, that is,

[x
1
, x

2
,..., x

n
]      [x

1
α, x

2
α, ... , x

n
α] (6)

for α ∈ Aut (T);

(c) the symmetric group S
n
, acting by permuting the

coordinates, that is,

[x
1
, x

2
,..., x

n
] �  [x1 , x2 , ..., xn  ] (7)

where π ∈ S
n
;

(d) the permutation τ  acting as follows:

[x
1
, x

2
,..., x

n
] �  [x1

−1, x
1

−1x
2
, ..., x

1
−1x

n
]. (8)

Another way of looking at diagonal groups is by their
action on the right cosets of a point-stabilizer. Define a
group G as follows:

G = Tn+1(Out(T) ×  Sn+1) (9)

Consider the subgroup

H = Aut(T) ×  Sn+1 (10)

The inner automorphisms are identified with the diagonal
subgroup

{(t, t, ..., t)⏐t ∈ T} (11)

of Tn+1. This is how diagonal groups are described in
the O’Nan-Scott Theorem. Each right coset of H in G
has a unique coset representative (1, x

1
, ... , x

n
) ∈

Tn+1. This representative is denoted [x
1
, ... , x

n
]. Now,

let us observe the action of G on the coset
representatives:

[x
1
, ... , x

n
](1, t

1
, ...,  t

n
) = H(1, x

1
, ... , x

n
) (1, t

1
, ..., t

n
)

         = H(1, x
1
t,1 ..., x

n
t
n
)

        = [x
1
t
1
, ...,  x

n
t
n
]. (12)

Thus we obtain the permutations in (a). A conjugation
by an element t ∈ T is uniquely a product of an element
of Tn+1 with first coordinate 1 and the diagonal element
(t, ..., t) as seen below:

      [x
1
, ...,  x

n
](t, ..., t) = H(1, x

1
, ...,  x

n
)(t, ..., t)

= H(t, x
1
t, ..., x

n
t)

= H(1, t-1x
1
t, ..., t-1x

n
t)

= [t-1x
1
t, ..., t-1x

n
t] (13)

Hence, Inn(T) is a subset of Tn+1. The remaining
automorphisms in (b) are exactly the outer
automorphisms of T. Observe the following action of
τ:

         [x
1
, ...,  x

n
]τ  = H(1, x

1
, ..., x

n
)τ

     = H(x
1
,1, x

2
, ..., x

n
)

     = H(1, x
1

-1, x
2
, ..., x

1
-1x

n
)

     = [x
1
-1, x

1
-1x

2
, ..., x

1
-1x

n
] (14)

The symmetric group S
n+1

 is generated by the symmetric
group  S

n
  in  (c)  and  the  transposition  τ  =  (1, 2)  in  (d).

Diagonal groups D(T, n) where n ≥ 8 and T abelian are
generously transitive permutation groups. All orbitals
in Orbl(Ω, D(T, n)) are symmetric and this gives a
commutative association scheme. Some association
schemes result from fission schemes. For the case of
Orbl(Ω, D(T, n)), a fission scheme is formed by looking

→

→

  π   π      π



Kazanidis, P.A.

20 Science Diliman 20:1, 18-23

at a proper subgroup K of D(T, n). A special set of
generators is used to construct the subgroup K. By
taking union of elements of Orbl(Ω, K), the association
scheme from Orbl(Ω, D(T, n)), is obtained. The
character tables corresponding to the basis algebra of
Orbl(Ω, K) and Orbl(Ω, D(T, n)) will be investigated
by making each entry a function of T and n.

THE ORBITALS

Let T be a permutation group acting on itself by right
translation. Let AutT be the automorphism group of T
acting on the elements of T naturally. The semi-direct
product T2 × OutT acts on T the following way:

        x((t1,t2),γ) = (t
1
-1 xt

2
)γ (15)

for all x ∈ T and for all  (t
1

, t
2
)γ ∈ T2 × AutT.

The orbitals of T2 acting on T is the set of orbits resulting
from the induced action of T2 on T × T. The orbitals of
OutT in T is defined similarly. The two actions are
shown below:

(x
1
, x

2
)(t1,t2) = (t

1
-1 x

1
t
2
, t

1
-1 x

2
 . t

2
)

 (x
1
,  x

2
)γ = (xγ

1
, xγ

2
) (16)

The discussion below shows that the orbitals of T2 ×
OutT can be computed using the above orbitals.

The following is a detailed discussion of an important
part of the proposition. Let (α

1
, β

1
) be any element of

(Ω × Ω). Suppose that for some γ  ∈ AutT, (α
1
, β

1
)γ =

(α, β). Also, for some (t
1
, t

2
) ∈ T × T (α, β)(t1, t2 ) = (α2, β2).

Then, (α2, β2)  is in a T
2-orbital containing an image of

(α1, β1) under an automorphism γ.

Proposition 1. Let T be a group and OutT its outer
automorphism group. Then, an orbital O of T2 × OutT
containing the element (α1, β1) in Ω × Ω in the
action previously defined is the union of all T2-
orbitals and all AutT-orbitals containing images of
(α1, β1).

Proof. Let O be an orbital of T2 × AutT containing (α1,
β1). Suppose that (α2, β2) is an element of O satisfying
the following:

(a) For ι ∈ AutT
(α1, β1)

((t1, t2),ι)  = (t
1

-1 α1t2, t1
-1 β

1
t
2
)

           =  (α2, β2) (17)
(b) For t ∈ T

(α1, β1)
((1,1),γ) =  (α1

γ, β1
γ)

=   (α2, β2) (18)

(c) For some non-identity elements t
1
, t

2
 ∈ T and also

non-identity auto-morphism γ ∈ AutT

            (α1, β1)
((t1,t2),γ) = ((t

1
-1 α1t2)

γ, (t
1
-1 β1t2)

γ)
                                 = (α2, β2) (19)

In case (a) (α2, β2) is trivially in the T
2-orbital containing

(α1, β1). In case (b) (α2, β2) is again trivially in the
AutT-orbital containing (α1, β1). For case (c), let α : = α1

γ,
β : = β1

γ, t
1
 = t

1
γ  and t

2
 : = t

2
γ. Then

(α2, β2) =  (t1
-1 αt

2
, t

1
-1βt) (20)

This proves that (α2, β2) is in the T
2-orbital containing

(α, β) which in turn is the image of (α1, β1) under γ.

The three cases cover all possible images of (α1, β1)
under the induced action of the semi-direct product T2

× AutT.

Therefore,

      ( ∪ OT ) ∪ ( ∪ OAutT ) ⊂  O (21)

where the union is taken over all orbitals containing
images of (α1, β1).                                                   �

As a remark, to get the orbital O containing (α1, β1)
under the semi-direct product T2 × AutT, all AutT-orbitals
containing all elements of the T2-orbital must be listed.
Additionally, all T2-orbitals containing all elements of
the AutT-orbital containing (α1, β1) must also be listed.
This result was used in a GAP program (The GAP
Group, GAP- Groups, Algorithms and Programming,
Version 4, http://www.gap-system.org) implemented to
compute fission and fusion schemes.

THE SET OF ORBITALS AS THE FINEST
ASSOCIATION SCHEME

The fusion schemes will be constructed based on the
fact that the finest association scheme preserved by

γ γ



Fission and fusion schemes and the action of the diagonal group D(T; n)

21Science Diliman 20:1, 18-23

Tn+1 × OutT is its set of orbitals resulting from its action
on T.

Recall that an automorphism of an association scheme
is a permutation of the set of points Ω which preserves
associate class C

i
 for each i = 0, 1,  ..., m where m is

the number of associate classes.

The set of all orbitals O forms association scheme as
discussed here. Consider the orbitals O

i
, O

j
 and O

k

which are not necessarily distinct. Let (α, β) ∈ O
k
. It

can be shown that the intersection number pk
ij
 is

independent of the choice of (α, β). Denote by G the
group Tn+1 × OutT . Suppose that pk

ij
 is the non-negative

number which gives the cardinality of the set

{γ⏐(α, γ) ∈ O
i ∧ (γ, β) ∈ Οj} (22)

Let (δ,λ) ∈ O
k
. It can be shown that (δ,λ) has the

same intersection number. Let g ∈ G such that (δ,λ) =
(α, β)g. Then {γg⏐(αg, γg) ∈ O

i ∧ (γ
g, β) ∈ Ο

j
} =

{γg⏐(δ, γg) ∈ O
i ∧ (γ

g, λ) ∈ Ο
j
}. Since g is a

permutation of T, the cardinality of this set is constant
given by pk

ij 
. This means that the intersection number

is independent of the choice of (α, β).

The set of orbitals O is the finest association scheme
preserved by the the permutation group G. The
following is an explanation. Suppose that there is a finer
association scheme preserved by G. Let Õ

i 
be an

associate class of a finer one which is properly
contained in orbital O

i
. For some g ∈ G, Õ

i
g ≠ Õi

because the group G is transitive on the elements of its
orbitals. Therefore, Õ

i
 is not preserved by G. This

contradicts our assumption that the finer association
scheme is preserved by the group G.

The associate classes of fusion schemes are union of
orbitals of Tn+1 × OutT acting on the elements of T.
The group Tn+1 × OutT preserves these associate
classes because it preserves its orbitals. Hence, it is a
subgroup of the full automorphism group of the fusion
scheme.

INTERSECTION NUMBERS AND
INCIDENCE MATRICES

The last axiom of the definition of association scheme
deals with intersection numbers. This section discusses
intersection numbers and its relation to the product of
incidence matrices.

The incidence matrix A
i 
corresponding to the associate

class C
i
 will be constructed by using the elements of Ω

as the row and column indices. The matrix A
i
 is defined

as follows:
       1 if (α, β) ∈ C

i

 A
i
(α, β) =

       0 otherwise (23)

If A
i
, A

j
 and A

k
 are respectively the incidence matrices

of associate classes C
i
, C

j
 and C

k
, then the product

A
i
  ⋅ Aj can be written as

        A
i
 ⋅ A

j
  = p0

ij
 ⋅ A

0
 +p1

ij
 ⋅ A

1
 + ⋅⋅⋅ +pm

ij
 ⋅ A

m

                  = Σ k=mpk
ij
A

k
(24)

where m is the number of associate classes. The
(α, β)-entry of the product A

i
 ⋅ A

j
 is non-zero if and

only if there is at least one γ such that (α, γ)-entry of A
i

and (γ, β)-entry of A
j
 are both 1. This is equivalent in

saying that there is at least one γ such that (α, γ) ∈ C
i

and (γ, β) ∈ C
j 
. The intersection number pk

ij
 gives the

number of such γ if and only if (α, β) ∈ C
k
. Hence, the

intersection number pk
ij
 is the coefficient of A

k
 in the

linear expansion of A
i
 ⋅ A

j
 .

FUSION SCHEMES FROM GROUPS ISO-
MORPHIC TO Z

P

Proposition 2. The semi-direct product T2 × AutT is
sharply 2-transitive on Ω where T ≅  Zp for some
prime number p.

Proof. Let ρ be a generator of the group Z
p
. Consider

the following arbitrary pairs of distinct elements of
Z

p
 × Z

p
.

       (ρa, ρb) ^ (ρc, ρd) (25)

 

k=1



Kazanidis, P.A.

22

where a, b, c, d ∈ {0, 1, ... , p - 1}. Since we would
like to prove sharp 2-transitivity, we shall consider
ordered pairs whose first component is distinct from
the second component. Hence, the following conditions
are satisfied.

a ≡ b mod p and c ≡ d mod p (26)

Consequently,

a - b ≡ 0 mod p and c - d ≡ 0 mod p (27)

We shall find an element ((t
1
, t

2
), γ) ∈ T2 × AutT such

that

(ρa, ρb)((t1, t2),γ) = (ρc, ρd) (28)

There is an element (ρv1, ρv2) ∈ T × T such that

(ρa, ρb)((ρv1, ρv2 ),ι)  = (ρ-v1+a+v2 ,  ρ0)
 = (ρw, ρ0) (29)

From above, we deduce the following equation:

b ≡ (v
1
 - v

2
) mod p (30)

The element w of Z
p
 satisfy the following:

w ≡ (a - b) mod p (31)

There is an ordered pair (d
1
,d

2
) where d

1
,d

2
∈{0, 1,⋅⋅⋅,p- 1}

such that

d ≡ (-d
1
 + d

2
) mod p (32)

Now, let x ∈ {0, 1, ⋅⋅⋅ , p - 1} such that

x ≡ (c - d) mod p (33)

Then, using the assumptions above, we have

w ≡ 0 mod p and x ≡ 0 mod p (34)

It is known that the full automorphism group AutT of T
is transitive on its non-identity elements. Hence, there
exists γ ∈ AutT such that (ρw)γ = ρx. Thus,

(ρa, ρb)((ρv1, ρv2 ),ι), ((ρ0, ρ0),γ) = (ρx, ρ0) (35)

Applying ((ρd1,  ρd2),ι), we get

(ρx, ρ0)((ρd1, ρd2 ),ι)   = (ρx-d1+d2, ρ-d1+d2)
 = (ρc, ρd) (36)

Therefore, the element ((t
1
, t

2
),γ) will be the product

of the three elements of T2 × AutT given below:

     ((ρ(v1, ρv2),ι)((ρ0, ρ0), γ)((ρ-d1+d2, ρ-d1+d2),ι) (37)

Hence, the semi-direct product T2 × AutT is sharply 2-
transitive on T.                                                      �

Corollary 1. If T ≅  Zp where p is a prime number,
then the semi-direct product T2 × AutT is generously
transitive in its action on T.

Proof. Take the two ordered pairs of distinct elements
in the proposition above to be (ρa, ρb) and (ρb, ρa).�

These results explain why there is only one fusion
scheme for the case when the group T is isomorphic to
the cyclic group Z

p
 of prime order. Such fusion schemes

are the set of orbitals {C
0
, C

1
} where C

0
 is the diagonal

orbital and C
1
 is its complement in Ω × Ω.

It can also be observed that for all the T considered,
the orbitals are all symmetric. This implies that the semi-
direct product T2 × AutT for these groups T are
generously transitive in its action on the elements of T.
The following is a discussion of commutativity of
incidence matrices of these orbitals. Let A

i
 and A

j
 be

arbitrary incidence matrices. Recall the following
equation

A
i 
⋅ A

j
 = p0

ij 
⋅ A

0
 +p1

ij
 ⋅ A

1
 + ⋅⋅⋅ +pm

ij
 ⋅ A

m

where m is the number of associate classes. The (α, β)-
entry of the product A

i
  A

j
 depends on the associate

class where (α, β) belongs. It is pk
ij
 if (α, β) ∈ C

k
.

Since C
k
 is symmetric and pk

ij
 is independent of the

choice of (α, β) by axiom (c) of the definition, the (β,
α)-entry of the product is also pk

ij
. This means that the

product of incidence matrices A
i
 and A

j
 for i, j ∈{0, 1,

⋅⋅⋅ , m} is symmetric. This implies that the algebra of

Science Diliman 20:1, 18-23

∼ ∼

∼

Σ pkijAk=
k=m
k=1

(38)

•



Fission and fusion schemes and the action of the diagonal group D(T; n)

23

matrices over the set of reals ℜ generated by A
0
, A

1
,

⋅⋅⋅ , A
m
 is a commutative algebra.

THE DIAGONAL GROUP AND THE FUSION
SCHEMES

The diagonal group D(T, n) contains Tn+1 × OutT as a
proper subgroup for n ≥ 1. If an association scheme is
preserved by D(T, n), then it is also preserved by every
subgroup of D(T, n). As a consequence, the fusion
schemes preserved by Tn+1 × OutT are candidate
association schemes preserved by D(T, n). A complete
list of all possible association schemes preserved by
D(T, n) can be derived from the fusion schemes
preserved by Tn+1 × OutT . This claim is shown in the
following result:

Corollary 2. All association schemes preserved by
D(T, n) have associate classes which are union of
orbitals of Tn+1 × OutT

Proof. Let C be an associate class in an association
scheme preserved by D(T, n). Suppose that C is not a
union of orbitals of Tn+1 × OutT . Then there exists an
orbital  Oi  of  Tn+1  ×  OutT  and  O

ic
  ⊂   Oi  such  that

O
ic
 = C ∩ O

i
. Consider x ∈ O

ic
 and y ∈ O

i 
- O

ic
 . There

exists  g  ∈  Tn+1  ×  OutT  such  that  xg  =  y and hence
Cg ≠ C. This is a contradiction because C is an
associate class for D(T, n). �

Association schemes preserved by D(T, n) are coarser
as compared with the association schemes preserved
by Tn+1 × OutT .

For the case when n = 1 and T ≅  Zp for some prime
number p, only the trivial association scheme is
preserved by D(T, n). The generous transitivity of T2 ×
OutT on Ω implies that of the diagonal group.

DISCUSSION

The automorphism groups of finitely generated groups
can further be studied to characterize the resulting
orbitals in the action of T2 × OutT. A diagonal group
D(T, n) is isomorphic to (Tn+1 × OutT ) o S

n+1
. The

generators are as enumerated in the introductory section
of diagonal groups. The GAP algorithm may further
be implemented for those cases when n ≥ 2.

ACKNOWLEDGEMENTS

This research was funded by the Natural Science
Research Institute, University of the Philippines,
Diliman.

REFERENCES

Alejandro, P.P., Bailey, R.A. and Cameron, P.J., 2003.
Permutation Groups and Association Schemes. Discrete
Mathematics 266, 47-67.

Cameron, P.J. 1999.  Permutation Groups.  Cambridge
University Press.

Dixon, J.D.  and Mortimer, B. 1996.  Permutation Groups.
Springer-Verlag, New York.

Science Diliman 20:1, 18-23