数理解析研究所講究録1109 巻 1999 年 196-200

196Classification of primitive association schemeswith small vertices
Akihide Hanaki (花木章秀、 信州大)Izumi Miyamoto (宮本泉、 山梨大)
After we intended to give a talk on this title, we have computed alittle more association
schemes, not only primitive association schemes but also all the association schemes withsmall vertices. The present result is as follows.

1

Association schemes with$n$vertices, $n\leq 23$

The number of the isomorphism classes of the association schemes.

,
be its adjacency matrix.
) be an association scheme. LetLet (X,$A_{k}(i,j)=1$$X=\{x_{1},x_{2},\cdots,x_{n}\}$, if,,ofbethesetvertices.
SoLet$\{\hslash\}_{0\leq i}\leq d$$A_{0},$$A_{1},$$\cdots$$A_{d}$$(X_{i}, x_{j})\in R_{k}$

$0$

197

otherwise.

The property of adjacency matrices
1.

has $\{0,1\}$ -entris and has constant collumn and row sum. The sum
its valency.
matrix.
$A_{i}$$v_{i}$

is called$A_{0}=\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{y}$2. $A_{0}+A_{1}+\cdots+A_{d}=J$ (3. For all there exists
$i$

4.

$i’$

$\mathrm{a}111$matrix)

such that$A_{i}A_{j}=\Sigma_{0\leq k\leq d}p_{ijk}A_{k}(A_{0},$${}^{t}A_{i}=A_{i’}$$A_{1},$$\cdots,A_{d}$themselves. )By an association schemetrix is . Let.

are a basis of the algebra generated by

we mean the associatin scheme of which relation ma. Let supp
for some $m\in$$\{0,1,2, \cdots d\}\}$ . An association scheme
is said to be connected with respect to , if
supp $(\langle 4\rangle)=\{0,1,2, \cdots d\}$ . An association scheme is primitive if and only if isconnected with respect tofor all $i\in\{1,2, \cdots d\}$ . Easy primitive association schemes
areassociation schemes of class 1 (association schemes with $d=1$ ),association schemes with prime vertices, especially, cyclotomic schemes with prime vertices,
association schemes defined from primitive permutation groups.
$A$$A$$A_{i}^{m}=\Sigma_{0\leq k\leq d}a_{i,k}^{[m1}A_{k}$$(\langle A_{i}\rangle)=\{k|a_{i}[,m_{k}]\neq 0$$A$$A_{i}$$A$$A$$A_{i}$

2

Primitive schemes with up to 24 vertices

Association schemes of class 1 and cyclotomic schemes with prime vertices always exist,
so we omit them. The names of primitive groups are in the library of GAP.

198

Computation, up to 19 vertices

3

We use group algorithm programming system GAP [7] to compute isomorphism classes ofis the list of valencies arranged in incleasing orderassociation schemes. Let$[1’,2’,\cdots, d’]$ indicates the numbers such that.
. The list
Here we note that always $v_{0}=1$ and $0’=0$ , so they are omitted in the lists. Letisbe the number of the vertices $|X|$ of an association scheme . Then$[1’,2’,\cdots,d’]$toouranda partition of $n-1$ . We input these two lists
computer program in order to make relation matrices. The following facts show some
impossible inputs.
$[v_{1},v_{2}, \cdots , v_{d}]$$A_{i’}={}^{t}A_{i}$$v_{1}\leq v_{2}\leq\cdots\leq v_{d}$$n$$A$$[v_{1},v_{2}, \cdots, v_{d}]$$[v_{1},v_{2}, \cdots,v_{d}]$Proposition 3.1 There enist no regular graphs of odd valencies with odd vertices, whichmeans that $if|X|$ is odd and $v_{i}=odd$ , then $i\neq i’$ .
Proposition 3.2 ([3]) Let be an association scheme on a vertex set X. Let $n=|X|$and let $m$ be the number of valencies such that $v_{i}=1$ . Then the adjacency matrices ofvalency 1 make a semiregular group on $X$ and $m$ divides .
$A$$n$

Proposition 3.3 ([3]) Let $m$ be the number of valencies equal to 1. If is the number.
of valencies equal to then$s$$mdi\dot{m}de\mathit{8}sl$$l_{2}$

Association schenes of all of its valencies equal to 1 are given by regular representation. So we omitted to compute this case and relied on the classificationof groupsof groups. Then we computed all the possible inputs by our GAP-programs to get
isomorphism classes of association schemes.
$(\mathrm{c}\mathrm{f}.[6])$Computation of primitive schemes

4The method of our computation was same as in up to 19 vertices. But we used thefollowing facts and we were able to compute all the possible inputs for the primitive
association schemes.

Proposition 4.1 (cf. [10, Theorem 1.4.2]) Let be a primitive association scheme.
Let be the minimal valency greater than 1. Then any prime factor of any valency isless than or equal to .
$\mathcal{X}$

$k$

$k$

Proposition 4.2 Let $E$ and be disjoint sets such that the union $E\cup F$ is the set ofthe valencies of an association scheme X. Let be maximal in and let be minimalin E. Suppose that any valency in $F$ satisfies one of the following.
(i)is coprime with any valency in $E$ and $v_{j}<v_{k}$ .
.
is greater than(ii)
If is not empty, then the association scheme X is not primitive.
$F$$v_{i}$$v_{k}$$v_{k}$$v_{k}$$F$$v_{i}v_{j}$$E$$v_{j}$

199

We note that many conditions for imprimitivity are given in [1], which are also sufficientfor our computation.
We have 271 inputs with 23 vertices. Among them Proposition 4.1 gives 36 inputs$[[v_{1,2}v, \cdots,v_{d}], [1’, 2^{;}, \cdots,d’]]$ for primitive schemes and Proposition
4.2 shows 16 of themimprimitive.
For some cases we applyed the following argument to prove the imprimitivity. For$\cdots,v_{d}|=[3,3,4,6,6]$ and [3, 3, 3, 3, 4, 6] imprimitive.
instance we have cases [[For any adjacency matrix , defineand$v_{1},v_{2},$$A_{i}^{[0\}}=A_{0}$$A_{i}$

if, if$A_{i}^{[]}n-1A_{i}$$A_{i}^{[n1}=\{$$A_{ii}^{[n}-11_{A}$is oddis even

$n$

$n$

Let
and let $\delta_{i}(j)=minimum\{n|a\mathrm{f}n1^{j},\neq 0\}$ orall (see [1] Section 5).
$\mathrm{A}^{[n]}=\Sigma a_{[n]},kA_{k}$$\delta_{i}(j)=\infty$

if $a_{[n])}j=0$ for$n$

Proposition 4.3 (cf. [1] Section 5)that and , the valencies of, are coprime mutually and that $\delta_{i}(j)=n$ . Thenfor some$\delta_{i}(k)=n-1_{y}$ whereor
if is even or odd respectively,$v_{i}v_{j}/(v_{i}-1)$ andequality
thelastthen.
if$Suppo\mathit{8}e$$v_{i}$$A_{j}$$v_{j\prime}$$A_{j}A_{\hat{i}}=p_{j,i_{)}k}\wedge A_{k}$$A_{\hat{i}}=A_{i}$$A_{i’}$

$k$

and
with

$v_{k}\geq v_{if}v_{k}\geq$$n$$holds_{J}$$A_{i}$$A_{k}\mathrm{A}_{i}\wedge,$$=p_{k,im}\wedge,,A_{m}+v_{i}A_{j}$Proving the above facts, the fundamental property $p_{ijk}v_{k}=pkj’ivi$ plays a most important role. We had not recognized this property well in our computer program.

5Computation, from 20 vertices

There is another fundamental property $p_{ijk}=pj^{l}i^{l}k’$ . These properties imply that incourse of constructing a relation matrix, if one
is determined, then at the same timeandare determined. We also have conditions thatandare integers. As we have checked
as soon as possible, this improved
our program.
$p_{ijk}$$p_{j’i’}k^{\prime,pki}\prime j’,$$p_{i’}kj,$$pjk’i^{l}$$p_{\dot{0}jk}v_{k}/v_{\dot{f}}$$p_{k\mathrm{i}’}i$$p_{ijk}v_{k}/v_{j}$$p_{ijk}$

Survey of related topics

6

Let be a transitive permutation group on $X$ . Then the orbits of on $X\cross X$ define
an association schene. For any association scheme , each adjacency matrix
can beseen an adjacency matrix of a regular graph, not necessarily connected..
A. Hulpke (1996) computed transitive groups up to degree 30. By Pentium PC, degree 8, 9, 10 take 2 or 3 minites, degree 12 half an hour, degree 18 or 20
one or 2 days. Up to degree 22 the list is in the library of GAP. (http:.
uk/\sim
Aulpke/publ.html)-and.
M. Meringer (1996) computed regular graphs by DEC-Alpha UNIX-Workstation andDEC-Station 5000/200. (http:)
$G$

$G$

$A$

$A_{i}$$133\mathrm{M}\mathrm{h}\mathrm{z}$$//\mathrm{w}\mathrm{w}\mathrm{w}- \mathrm{g}\mathrm{a}\mathrm{p}.\mathrm{d}_{\mathrm{C}}\mathrm{s}$$\mathrm{s}\mathrm{t}$$\mathrm{a}\mathrm{c}.$$//\mathrm{w}\mathrm{w}\mathrm{w}.\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{e}2.\mathrm{u}\mathrm{n}\mathrm{i}-\mathrm{b}\mathrm{a}\mathrm{y}\mathrm{r}\mathrm{e}\mathrm{u}\mathrm{t}\mathrm{h}.\mathrm{d}\mathrm{e}/\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{k}\mathrm{u}\mathrm{s}/\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h}_{\mathrm{S}}.\mathrm{h}\mathrm{t}\mathrm{m}1$

200

Acknowledgement
The authors wish to thank Dr. Mitsugu Hirasaka for his valuable advices.

References[1] Z. Arad, E. Fisman and M. Muzychuk, Generalized table algebras, to appear.
[2] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Menlo Park,, 1984.
CA:$\mathrm{B}\mathrm{e}\mathrm{n}\mathrm{j}\mathrm{a}\mathrm{m}\mathrm{i}\mathrm{n}/\mathrm{C}\mathrm{u}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}$[3] A. Hanaki and I. Miyamoto, Classification of association schemes with 16 and 17
vertice8, Kyushu J. Math. 52 (1998) 383-395.
[4] A. Hanaki and I. Miyamoto, ClaS8ification of as8ociation schemes with 18 and 19
vertices, Korean J. Comp. App. Math. 5 (1998) 543-551.

[5] M. Hirasaka, The classification of association scheme8 with 11 and 12 vertices,Kyushu J. Math. 51 (1997) 413-428.
[6] E. Nomiyama, Classification of association scheme8 with at most ten vertices,Kyushu J. Math. 49 (1995) 163-195.

[7] M. Schert, et.al. GAP
ematik, Rheinischtion, 1995.

, Algorithms, and Programming, Lehrstuhl Df MathTechnische Hochschule, Aachen, Germany, fifth edi-$-c_{r}oup\mathit{8}$$\mathrm{w}_{\mathrm{e}\mathrm{S}}\mathrm{t}\mathrm{f}\dot{\mathrm{a}}\mathrm{h}\mathrm{S}\mathrm{C}\mathrm{h}\mathrm{e}$schemes of small order, to appear in J. Statist.
[8] K. See and S. Y. Song,Plann. Inference. Bose Conference Issue (1998),$A_{\mathit{8}}sociation$[9] Y. Suga, Data of association schemes, pubhished at 珂 V 珂 V 珂珂 (July 4, 1996):. htm. math. kyushu-u.
http:$//\mathrm{g}\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{s}\mathrm{h}$$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\mathrm{S}\mathrm{u}\mathrm{g}\mathrm{a}/\mathrm{a}\mathrm{s}\mathrm{s}/\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}$[10] P.-H. Zieschang, An Algebraic Approach to Association Schemes, Springer, 1996.