Classification of primitive association schemes with small vertices

Akihide Hanaki and Izumi Miyamoto

In this paper, we classify all primitive association schemes with up to 22 vertices and all commutative association schemes with 23 vertices. The classification of association schemes is obtained up to 19 vertices ([2], [3], [4], [6], and [9], see also [8]), but it seems to very hard to classify association schemes with more than 20 vertices even if we use computers. So we treat only primitive cases here. Primitive association schemes are very important like as simple groups in finite groups. Our method is same as in [2] and [3], and uses GAP [7].

Notations are same as in [2] and [3]. To describe association schemes we use the relation matrices. For definitions and terminologies, we refer to [1].

We already know some classes of primitive association schemes. First examples are association schemes of class 1. In this case, all diagonal entries of the relation matrix are 0 and other entries are 1. Second examples are association schemes with prime vertices. Especially, cyclotomic schemes exist always. Third examples are defined from primitive permutation groups. But if a permutation group is doubly transitive, then it defines the class 1 scheme.

1 Primitive schemes with up to 22 vertices

Association schemes of class 1 and cyclotomic schemes with prime vertices always exist, so we omit them.

The next table contains all primitive schemes with up to 22 vertices, except cyclotomic schemes with prime vertices and class 1 schemes. The names of primitive groups are in the library of GAP.

number of vertices valencies primitive permutation group

     9  1, 4, 4  3^2:4, 3^2:D8
     10  1, 3, 6  A(5), S(5)
     15  1, 6, 8  A(6), S(6)

1, 7, 7  non (prim15)

     16  1, 5, 10  (2^4:5).4, 2^4:A 5, 2^4:S 5
                         1, 6, 9  (A 4xA 4):2, 2^4.3^2:4,

                                   2^4.S 3xS 3, (S 4xS 4):2

1, 6, 9  non (prim16 1)

                         1, 5, 5, 5 2^4:5, 2^4:D 10

1, 5, 5, 5 non (prim16 2)
19 1, 9, 9 non (prim19)
21  1, 10, 10 A(7), S(7)

                         1, 4, 8, 8 PGL(2,7)

The relation matrices of non group cases are described in Appendix.

The method of our computation is same as in [2] and [3]. But to use the primitivity assumption, we use the following fact.

Proposition 1.1. Let X be a primitive association scheme. Let k be the minimal valency greater than 1. Then any prime factor of any valency is less than or equal to k.

Proof. Direct consequence from [11, Theorem 1.4.2].

This is very effective for our calculations. Also we used that if there exists a relation of valency 2 then the association scheme must be obtained by a polygon with prime vertices. Note that there exists no non-trivial primitive scheme with 20 or 22 vertices.

2 Commutative association schemes with 23 vertices

First we get the fact that there exist 19 schemes of valencies {1, 11, 11}, one of them is cyclotomic and other schemes can not be obtained from transitive permutation groups. Next we tried to classify all association schemes with 23 vertices, but it was very hard. We calculated only symmetric association schemes, and get the fact that symmetric association schemes with 23 vertices are the class 1 scheme and the cyclotomic scheme of class 11. This fact says the following.

Theorem 2.1. Commutative association schemes with 23 vertices are 19 schemes with valency {1, 11, 11} and cyclotomic schemes of class 1 and 11.

Proof. A commutative association scheme has the symmetrization, and it must be the class 1 scheme or the cyclotomic scheme of class 11.

Note that if we consider only commutative primitive schemes then we can apply results in [10] and [5]. Also note that no non-commutative association scheme with 23 vertices is known.

Acknowledgement

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

References

[1] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Menlo Park, CA: Benjamin/Cummings, 1984.

[2] A. Hanaki and I. Miyamoto, Classification of association schemes with 16 and 17 vertices, to appear in Kyushu J. Math.

[3] A. Hanaki and I. Miyamoto, Classification of association schemes with 18 and 19 vertices, to appear in Korean J. Comp. App. Math.

[4] M. Hirasaka, The classification of association schemes with 11 and 12 vertices, Kyushu J. Math. 51 (1997) 413-428.

[5] M. Hirasaka, On association schemes with a nonsymmetric relation of valency 4, preprint.

[6] E. Nomiyama, Classification of association schemes with at most ten vertices, Kyushu J. Math. 49 (1995) 163-195.

[7] M. Schert, et.al. GAP – Groups, Algorithms, and Programming, Lehrstuhl D f Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, fifth edition, 1995.

[8] K. See and S. Y. Song, Association schemes of small order, to appear in J. Statist. Plann. Inference. Bose Conference Issue (1998),

[9] Y. Suga, Data of association schemes, published at WWW (July 4, 1996): http://goldenfish.math.kyushu-u.ac.jp/Suga/ass/class.htm

[10] N. Yamazaki, On symmetric association schemes with k_{1} = 3, preprint.

[11] P.–H. Zieschang, An Algebraic Approach to Association Schemes, Springer, 1996.

Akihide Hanaki Faculty of Science, Shinshu University, Matsumoto 390-8621, Japan Izumi Miyamoto Faculty of Engineering, Yamanashi University, Kofu 400-8511, Japan

Appendix

prim15 = [ \begin{matrix}0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 0 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 2 & 2 & 2 \\ 2 & 2 & 0 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 \\ 2 & 2 & 2 & 0 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 2 \\ 2 & 2 & 2 & 2 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 2 & 1 & 2 & 1 & 2 & 0 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 1 \\ 2 & 1 & 1 & 2 & 2 & 2 & 0 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 1 \\ 2 & 1 & 1 & 2 & 2 & 1 & 2 & 0 & 2 & 1 & 2 & 1 & 1 & 1 & 2 \\ 1 & 2 & 2 & 1 & 2 & 1 & 2 & 1 & 0 & 2 & 1 & 1 & 2 & 1 & 2 \\ 1 & 2 & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 0 & 1 & 2 & 1 & 2 & 2 \\ 1 & 2 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 0 & 1 & 1 & 2 & 1 \\ 1 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 0 & 2 & 1 & 1 \\ 1 & 1 & 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 2 & 1 & 0 & 1 & 2 \\ 1 & 1 & 2 & 2 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 2 & 2 & 0 & 1 \\ 1 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 0 \end{matrix} ]

prim16 1 = [ \begin{matrix}0 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 1 & 0 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 \\ 1 & 1 & 0 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 1 & 2 & 2 & 2 & 2 \\ 1 & 1 & 2 & 0 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 2 & 2 \\ 1 & 2 & 1 & 2 & 0 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 1 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 1 & 2 & 1 \\ 1 & 2 & 2 & 2 & 1 & 1 & 0 & 2 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 1 \\ 2 & 1 & 1 & 2 & 2 & 2 & 2 & 0 & 2 & 1 & 2 & 1 & 2 & 1 & 1 & 2 \\ 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 0 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 2 & 1 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 0 & 2 & 2 & 2 & 2 & 1 & 1 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 1 & 2 & 2 & 1 \\ 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 & 2 & 2 & 1 & 0 & 2 & 1 & 2 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 2 & 0 & 1 & 1 & 2 \\ 2 & 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 0 & 1 & 2 \\ 2 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 1 & 0 & 2 \\ 2 & 2 & 2 & 2 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 0 \end{matrix} ]

prim16 2 = [ \begin{matrix}0 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 3 \\ 1 & 0 & 2 & 2 & 3 & 3 & 1 & 1 & 2 & 2 & 3 & 1 & 1 & 2 & 3 & 3 \\ 1 & 2 & 0 & 3 & 2 & 3 & 1 & 2 & 1 & 3 & 2 & 2 & 3 & 1 & 1 & 3 \\ 1 & 2 & 3 & 0 & 3 & 2 & 2 & 1 & 3 & 1 & 2 & 3 & 2 & 1 & 3 & 1 \\ 1 & 3 & 2 & 3 & 0 & 2 & 2 & 3 & 2 & 1 & 1 & 1 & 3 & 3 & 1 & 2 \\ 1 & 3 & 3 & 2 & 2 & 0 & 3 & 2 & 1 & 2 & 1 & 3 & 1 & 3 & 2 & 1 \\ 2 & 1 & 1 & 2 & 2 & 3 & 0 & 3 & 3 & 1 & 1 & 2 & 3 & 2 & 3 & 1 \\ 2 & 1 & 2 & 1 & 3 & 2 & 3 & 0 & 1 & 3 & 1 & 3 & 2 & 2 & 1 & 3 \\ 2 & 2 & 1 & 3 & 2 & 1 & 3 & 1 & 0 & 1 & 3 & 1 & 2 & 3 & 2 & 3 \\ 2 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 1 & 0 & 3 & 2 & 1 & 3 & 3 & 2 \\ 2 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 3 & 3 & 0 & 3 & 3 & 1 & 2 & 2 \\ 3 & 1 & 2 & 3 & 1 & 3 & 2 & 3 & 1 & 2 & 3 & 0 & 2 & 1 & 2 & 1 \\ 3 & 1 & 3 & 2 & 3 & 1 & 3 & 2 & 2 & 1 & 3 & 2 & 0 & 1 & 1 & 2 \\ 3 & 2 & 1 & 1 & 3 & 3 & 2 & 2 & 3 & 3 & 1 & 1 & 1 & 0 & 2 & 2 \\ 3 & 3 & 1 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 2 & 2 & 1 & 2 & 0 & 1 \\ 3 & 3 & 3 & 1 & 2 & 1 & 1 & 3 & 3 & 2 & 2 & 1 & 2 & 2 & 1 & 0 \end{matrix} ]

prim19 = [ \begin{matrix}0 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 2 \\ 2 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 \\ 2 & 2 & 0 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 \\ 2 & 2 & 1 & 0 & 2 & 2 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 2 & 1 \\ 1 & 2 & 2 & 1 & 0 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 1 \\ 1 & 2 & 2 & 1 & 2 & 0 & 2 & 1 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 2 & 1 & 1 & 0 & 1 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 \\ 2 & 2 & 2 & 2 & 1 & 2 & 2 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 1 & 2 & 2 \\ 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 0 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 2 \\ 2 & 1 & 2 & 1 & 1 & 2 & 1 & 2 & 1 & 0 & 2 & 2 & 1 & 1 & 2 & 2 & 2 & 1 & 1 \\ 1 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 0 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 1 \\ 1 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 0 & 2 & 1 & 2 & 1 & 1 & 2 & 2 \\ 1 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 & 1 & 0 & 1 & 2 & 2 & 2 & 2 & 1 \\ 2 & 1 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 0 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 0 & 2 & 1 & 1 & 2 \\ 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 2 & 1 & 2 & 1 & 0 & 2 & 2 & 1 \\ 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 0 & 1 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 0 & 2 \\ 1 & 1 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 & 1 & 0 \end{matrix} ]