A modular absolute bound condition for primitive association schemes

DOI 10.1007/s10801-008-0145-0

A modular absolute bound condition for primitive association schemes

Akihide Hanaki·Ilia Ponomarenko

Received: 29 September 2007 / Accepted: 12 June 2008 / Published online: 5 July 2008

© Springer Science+Business Media, LLC 2008

Abstract The well-known absolute bound condition for a primitive symmetric asso- ciation scheme(X, S)gives an upper bound for|X|in terms of|S|and the minimal non-principal multiplicity of the scheme. In this paper we prove another upper bounds for|X|for an arbitrary primitive scheme(X, S). They do not depend on|S|but de- pend on some invariants of its adjacency algebraKSwhereKis an algebraic number field or a finite field.

Keywords Association scheme·Adjacency algebra

1 Introduction

Let(X, S)be an association scheme (for a background on association scheme theory we refer to [1,10] and Appendix). Denote byF Sits adjacency algebra over a fieldF. As usual we considerF Sas a subalgebra of the full matrix algebra MatX(F ). Set

rkmin(F, S)= min

A∈F S\F Jrk(A)

whereJ is the all-one matrix inF S and rk(A)is the rank of a matrix A. One can see that in the commutative case the number rkmin(C, S)coincides with the mini- mal multiplicitym_minof a non-principal irreducible representation of the algebraCS (see (1)).

Partially supported by RFBR grants 07-01-00485, 08-01-00379 and 08-01-00640. The paper was done during the stay of the author at the Faculty of Science of Shinshu University.

A. Hanaki

Faculty of Science, Shinshu University, Matsumoto 390-8621, Japan e-mail:[email protected]

I. Ponomarenko (

Petersburg Department of V.A.Steklov Institute of Mathematics, St. Petersburg 191023, Russia e-mail:[email protected]

It is a well-known fact (see [1, Theorem 4.9]) that given a primitive symmetric scheme(X, S) the number|X| can not be arbitrarily large when|S| andm_min are bounded. It was asked there about a reasonable absolute bound condition for an arbi- trary primitive commutative scheme. The main goal of this paper is to use the modu- lar representation theory for schemes to get another upper bound for|X|without the assumption of commutativity. Our first result gives the following modular absolute bound condition for primitive schemes.

Theorem 1.1 Let(X, S)be a primitive scheme and letq be a prime power. Setr= rkmin(Fq, S). Then

|X| ≤q^r−1 q−1

wheneverr >1. Ifr=1, then|X|< q and(X, S)is a thin scheme of prime order.

We have examples for which the equality holds in Theorem1.1.

Example 1.2 Let(X, S)be the cyclotomic scheme over a prime fieldFpcorrespond- ing to its multiplicative subgroup of order r. Suppose that there exists a prime q such that p=(q^r −1)/(q−1). Then rkmin(Fq, S)=r and the equality in The- orem 1.1 holds. We omit the proof of this fact, but one can easily check it for (p, r, q)=(31,5,2)or(31,3,5).

Given a scheme(X, S)denote byP=P(CS)the set of all central primitive idem- potents of the algebraCS. ForP∈Psetm_P to be the multiplicity of the irreducible representation ofCScorresponding toP in the standard representation (given by the standardCS-moduleCX). Put

mmin= min

P∈P\{P0}mP (1)

whereP0=(1/|X|)J is the principal idempotent ofCS. If(X, S)is primitive and mmin=1, then it is a thin scheme of prime order (Theorem2.2). So we may omit this case. Set

Q(X, S)=Q({Px,y:P ∈P, x, y∈X}).

It is not necessarily a splitting field of QS, but it is a Galois extension and every P ∈P belongs to the adjacency algebraQ(X, S)S.

Theorem 1.3 Let(X, S)be a primitive scheme. Suppose thatpis a prime which does not divide the Frame number of this scheme (see (A4)) andm_min>1. Then

|X| ≤q^mmin−1

q−1 . (2)

whereq=p^|Q(X,S):Q|.

Remark 1.4 The proof of Theorem1.3given in Section3shows that the upper bound in (2) can be reduced. For an appropriateP ∈P, the bound is

|X| ≤q^mP −1 q−1 whereq=p^{|Q({Px,y:x,y∈X}):Q|}.

We do not know any primitive scheme for which the upper bound in (2) is tight.

However, there are examples where this bound is less than one given by the absolute bound condition (e.g. for some amorphic primitive schemes(X, S)such that|X| =q² and|S| =(q+1)/2 whereqis a prime andq≡1 (mod 3); in this caseQ(X, S)=Q and one can takep=3). On the other hand, one can use inequality (2) to prove the finiteness of some classes of rational primitive schemes (here a scheme is called rational ifQis a splitting field of its adjacency algebra). In this case, we can apply Theorem1.3to any primitivep-scheme, that is, a scheme such that the primepdoes divide neither|X|nor the valency of an element fromS.

Corollary 1.5 Given a primepand a positive integerr the set of rational primitive p-schemes for whichmmin≤r, is finite.

The class ofp-schemes withp=2 consists of odd schemes, i.e. those for which only symmetric basis relation of it is a reflexive one. Theorem1.3shows that for a fixedr a splitting field of an odd primitive scheme withm_min≤r grows when|X| grows.

The assumptions of Theorem1.3mean that the adjacency algebra of(X, S)over a field of characteristicpis semisimple. Non-semisimple case seems to be much more difficult (see [6,8]).

The proofs of Theorems1.1and1.3are given in Sections 2and3respectively.

To make the paper self-contained we put in Appendix the notation and definitions concerning schemes and their adjacency algebras.

Notation As usual byQ,Cand Fq we denote the fields of rational and complex numbers and a finite field with q elements respectively. Throughout the paper X denotes a finite set. The diagonal of the setX×X is denoted by . The algebra of all matrices whose entries belong to a fieldF and whose rows and columns are indexed by the elements ofXis denoted by MatX(F ), the identity matrix byIand the all-one matrix byJ.GivenA∈MatX(F )andx, y∈X, we denote byAx,ythe(x, y)- entry ofA. The Hadamard (componentwise) product of matricesA, B∈MatX(F )is denoted byA◦B. The adjacency matrix of a binary relationr⊂X×Xis denoted by A_r(this is a {0,1}-matrix of MatX(F )such that(A_r)_x,y=1 if and only if(x, y)∈r).

The left standard module of the algebra MatX(F )is denoted byF X. We will identify the elements ofXwith the standard basis vectors ofF X.

2 Combinatorics in the adjacency algebra

First we prove that with any matrix of the adjacency algebra of a scheme one can associate some special relations which are unions of basis relations (a special case of our result also follows from [4, Lemma 4.1]). Namely, letF be a field. Given a matrixA∈MatX(F )and an elementλ∈F we define a binary relation

e_λ(A)= {(x, y)∈X×X: λAx=Ay}

on the setX. Clearly,e1(A)is a nonempty equivalence relation onX ande_λ(A)∩ e_μ(A)= ∅ for all nonzero elementsλ=μ. Besides, e0(A)= ∅if and only if the matrixAhas no zero columns. In the latter case, the relation

e(A)=

λ∈F

eλ(A) (3)

is also an equivalence relation onX. Note thatAxbeing thexth column of the matrix Acan be considered as an element ofF X. So(x, y)∈e(A)if and only if the vectors Ax, Ay∈F Xare linearly dependent.

In [4, Lemma 4.1] it was proved that given a scheme(X, S)and a matrixA∈CS the relationeλ(A)withλ=1 belongs to the setS^∗of all unions of relations fromS.

The following statement generalizes this result for an arbitrary field and allλ’s. Below we denote by A_e andA_λ the adjacency matrices of the relationse(A) ande_λ(A) respectively. In the first part of the proof we follow [3, Lemma 1.42].

Theorem 2.1 Let(X, S)be a scheme and letF be a field. Thene_λ(A)∈S^∗for all A∈F Sandλ∈F.

Proof Without loss of generality we assume thatA=0. First we suppose thatF=C. SinceA∈CS, we also haveA^∗∈CSwhereA^∗is the Hermitian conjugate ofA. This implies thatA^∗A∈CS. So givenx∈Xthe number(A^∗A)_x,xequals to the coefficient of the identity matrixI =Ain the decomposition of the matrixA^∗Aby the matrices As,s∈S. Denote it byd. Then by the Cauchy-Schwarz inequality we conclude that

|(A^∗A)x,y| = |Ax, Ay| ≤ Ax · Ay =d (4) where ·, · and · are the inner product and the Euclidean norm inCXrespec- tively. Moreover, the equality in (4) is attained if and only if the vectorsAx andAy are linearly dependent. Thus|(A^∗A)_x,y| =dif and only if(x, y)∈e(A). Due to (A2) this shows thatA_e∈CSand soe(A)∈S^∗. On the other hand, given(x, y)∈e_λ(A) the number

(A^∗A)_x,y= Ax, Ay = Ax, λAx =λAx, Ax =λd.

does not depend on(x, y). By (3) this means that (A^∗A)◦A_e=d

λ∈

λA_λ

where= {λ∈C: e_λ(A)= ∅}. Since the matricesA^∗AandA_ebelong toCS, we conclude by (A2) thatA_λ∈CSand hencee_λ(A)∈S^∗.

LetF be an arbitrary field. SinceA∈F S, any two columns ofAconsist of the same elements ofF. Denote the set of all of them byM. Then

Mλ=M, λ∈, (5)

where= {λ∈F : eλ(A)= ∅}. Easily we can see thatis a finite subgroup of the multiplicative groupF^×, and sois cyclic. Take an injection and a group monomor- phism

f :M→C, μ→μ, ϕ:→C^×, λ→λ

such that the permutation groups induced by the actions of onM, and of= Im(ϕ)onM=Im(f )are equivalent. Then it is easy to see that

λAx=Ay ⇔ λAx=Ay, x, y∈X,

whereA∈MatX(C)is the complex matrix with entriesA_x,y=(A_x,y)^f for allx, y.

Soe(A)=e(A)and we are done by the first part of the proof.

It was proved in [9, p. 71] that any primitive scheme having a nonreflexive basis relation of valency 1 is a thin scheme of prime order. The following theorem gives a

“dual” version of this result.

Theorem 2.2 Let(X, S) be a primitive scheme and letF be a field. Suppose that rkmin(F, S)=1. Then(X, S)is a thin scheme of prime order.

Proof Since rkmin(F, S)=1, there exists a rank 1 matrixA∈F S\F J. This implies that any two columns ofA are linear dependent. Soe(A)=X×X. On the other hand,e1(A)∈S^∗by Theorem2.1. Due to the primitivity of(X, S)this implies that e₁(A)∈ {, X×X}. Moreover, since A /∈F J, we see that e₁(A)=. Thus by formula (3) we conclude that

A=

x∈X

λ_xA_λx

for someλ_x∈F such thatλ_x=λ_yfor allx=y. Soe_λx(A)∈S and the valency of eλ_x(A)equals 1 for allx∈X(see (A2)). This shows that the scheme(X, S)is thin.

To complete the proof it suffices to note that any primitive thin scheme is of prime

order.

Now we can prove Theorem1.1.

Proof of Theorem1.1 From the hypothesis it follows that there exists a rankrmatrix A∈FqS\FqJ. By Theorem2.1we know thate(A), e1(A)∈S^∗. Since the scheme (X, S)is primitive, this implies that

e(A), e₁(A)∈ {, X×X}.

However, sinceAis not a multiple ofJ, it follows thate₁(A)=, and hence

|X| = |{Ax: x∈X}|. (6) On the other hand, ife(A)=X×X, then any two vectorsAx andAy are linearly dependent. Sor=rk(A)=1 and|{Ax: x∈X}| ≤ |F_q^×| =q−1. By (6) this proves the second part of the theorem. Thus without loss of generality we can assume that e(A)=. Then any two distinct vectorsAx andAy are linearly independent. This means thatr=rk(A) >1 and

|{Ax: x∈X}| ≤q^r−1 q−1,

and we are done by (6).

3 Matrix rank in the adjacency algebra

In this section we deduce Theorem1.3from Theorem1.1. To do this, we will consider adjacency algebras over an algebraic number field and its ring of integers. We refer to [7] for standard facts from algebraic number theory. For the rest of the section we fix a scheme(X, S), an algebraic number fieldKand a rational prime numberp.

Denote byRthe ring of integers ofK. Take its prime idealPlying abovepZand setf to be the degree ofP. Then

f≤ |K:Q| (7)

and the quotient ringR/Pis isomorphic to the fieldFq whereq =p^f. Denote by K_PandR_PtheP-adic field and the ring ofP-adic integers respectively. Then

R_P= {a∈K_P:ν_P(a)≥0} (8) whereν_P is theP-valuation onK_P. Hereν_P(a)= ∞if and only ifa=0. Since RP/PRP∼=R/P, the ring epimorphismR→Fqinduces the epimorphismRP→ Fq, a→a, and hence the epimorphism

R_PS→FqS,

s∈S

a_sA_s→

s∈S

a_sA_s (9)

where we use the natural identification of {0,1}-matrices inR_PSandFqS. The image ofA∈RPSis denoted byA.

Lemma 3.1 SupposeFqSis semisimple. Then every central idempotent ofKPSbe- longs toR_PS.

Proof LetP be a central idempotent ofK_PS. Without loss of generality we assume thatP =0. Then due to (8) it suffices to verify that ν(P )=0 where ν=ν_P and given an elementA=

s∈Sa_sA_sof the algebraK_PSwe set ν(A)=min

s∈Sν(a_s). (10)

Clearly,ν(AB)≥ν(A)+ν(B)andν(aA)=ν(a)+ν(A)for allA, B∈KPSand a∈KP. So

ν(P )=ν(P²)≥ν(P )+ν(P )

whence it follows that ν(P )≤0 (here ν(P ) <∞ because P =0). Suppose that ν(P ) <0. SetQ=aPwhereais an element ofK_Psuch thatν(Q)=ν(a)+ν(P )= 0. ThenQ=0 (see (9)) and

ν(Q²)=ν(a²P )=ν(a)+(ν(a)+ν(P ))=ν(a)= −ν(Q) >0.

SoQ²=0. SinceQis in the center of the algebra FqS, the setQ(FqS) is a non- zero proper nilpotent ideal of it. However, this contradicts the assumption thatFqSis

semisimple.

Remark 3.2 In the proof of Lemma3.1we extended the valuationν_P to the adja- cency algebraK_PSof a scheme(X, S)(see (10)). This extensionν has properties:

ν(A)= ∞iffA=0,ν(A+B)≥min(ν(A), ν(B))andν(AB)≥ν(A)+ν(B).

LetP ∈P(CS)be a central primitive idempotent ofCS. Then every entry ofP is an algebraic number. If the fieldKcontains all entries ofP, thenP ∈KSandKcan be embedded into bothCandK_P. Through these embeddings, we can regardP as an element ofK_PS.

Lemma 3.3 SupposeFqS is semisimple and the field K contains all entries of a matrixP∈P(CS). Then the following statements hold:

(1) P ∈R_PS; in particular, the elementP is defined and belongs toP(FqS), (2) P (FqS)∼=Matn(Fq)for somen, the irreducible representation ofFqS defined

byP is absolutely irreducible, and the degree and the multiplicity of it in the standard representation ofFqScoincide withn_P andm_P respectively (see (A3)).

Proof The first part of statement (1) immediately follows from Lemma3.1. By [2, Proposition 1.12], we can see thatP is primitive. Statement (1) is completely proved.

Next, sinceP is primitive inCS,P is primitive in the adjacency algebra over any extension fieldEofFq, and thenP (ES)is a simple algebra. Since any finite division ring is a field, the Wedderburn theorem shows thatP (FqS)∼=Matn(F )for some nand some finite extension F ofFq, and P (F S)is also a simple algebra. By the separability ofF overFq, we have

P (F S)∼=F ⊗_FqP (FqS)∼=F ⊗_Fq Matn(F )∼=Matn(F⊗_FqF )

∼=Matn(|F :Fq|F )∼= |F :Fq|Matn(F ).

Due to the simplicity ofP (F S)we have|F :Fq| =1 and henceF =Fq. This means that the irreducible representation defined byP is absolutely irreducible.

Besides, the ranks of the modules

K_PS=P (K_PS)⊕(I−P )(K_PS), FqS=P (FqS)⊕(I−P )(FqS) are the same. Since obviously the ranks ofP (KPS)and(I−P )(KPS)do not exceed the ranks ofP (FqS)and(I−P )(FqS), respectively, it follows that they are equal.

Thus the degrees of irreducible representations corresponding toP andP are the same. Also comparing the dimensions of the decompositions of standard modules K_PX andFqX, we see that the multiplicities of irreducible representations in the standard representations corresponding toP andP are the same.

Lemma 3.4 SupposeFqSis semisimple and the fieldKcontains all entries ofP ∈ P(CS). Then there existsE∈FqSsuch that rk(E)=m_P.

Proof From Lemma3.3(2), we haveP (FqS)∼=Matn_P(Fq). Choose an elementE∈ P (FqS)corresponding to a diagonal matrix unit in MatnP(Fq). Since the irreducible representation corresponding toP appearsmP times in the standard representation,

we have that rk(E)=mP.

Now we give a proof of Theorem1.3.

Proof of Theorem1.3 Suppose p is not a divisor of the Frame number Fr(X, S).

Then the adjacency algebra of(X, S)over a field of characteristicp is semisimple (see Appendix). Since the fieldK=Q(X, S)satisfies the condition of Lemma3.4 for allP ∈P(CS), one can find a matrixE∈FqS such that rk(E)=mmin. Since m_min>1, we see thatE /∈FqJ. By Theorem1.1and inequality (7) we have

|X| ≤q^mP−1

q−1 =p^mPf −1

p^f−1 ≤p^|K:Q|mP−1 p^|K:Q|−1

and we are done.

Appendix: Association schemes

LetXbe a finite set andSa partition ofX×Xclosed with respect to the transpose.

A pair(X, S)is called an association scheme or scheme if the reflexive relation belongs to the setSand givenr, s, t∈S, the number

c_r,s^t = |{z∈X:(x, z)∈r, (z, y)∈s}| (A1) does not depend on the choice of(x, y)∈t. The elements ofS and the number|X| are called the basis relations and the order of the scheme. The set of unions of all

subsets ofSis denoted byS^∗. The numberd_r =c_r,r∗ wherer^∗is the transpose ofr, is called the valency ofr. The scheme(X, S)of order≥2 is called primitive if any equivalence relation onXbelonging toS^∗coincides with eitherorX×X.

Given a fieldF the linear spanF S of the set{A_s : s∈S}forms a subalgebra of the algebra MatX(F )(see (A1)). This subalgebra is called the adjacency algebra of the scheme(X, S)overF. From the definition it follows that F S is closed with respect to the transpose and the Hadamard multiplication. In particular,

a∈F, A∈F S ⇒ A^(a)∈F S (A2) whereA^(a)is a {0,1}-matrix in MatX(F )such thatA^(a)_x,y=1 if and only ifA_x,y=a.

One can see that any {0,1}-matrix belonging toF Sis of the formA_sfor somes∈S^∗. The set of all central primitive idempotents of the algebraF Sis denoted byP(F S).

The adjacency algebraCSof the scheme(X, S)over the complex number fieldC is semisimple. So by the Wedderburn theorem its standard moduleCXis completely reducible. For an irreducible submoduleLofCXcorresponding to a central primitive idempotentP of the algebraCS, we set

n_P =dim_C(L), m_P=rk(P )/nP, (A3) thusm_P andn_P are the multiplicity and the degree of the corresponding irreducible representation ofCS. It is known thatm_P ≥n_P for allP [4]. Obviously, for the principal central primitive idempotent P =(1/|X|)J of the algebra CS we have m_P =n_P =1.

For an arbitrary fieldF, the semisimplicity of the algebraF Swas studied in [5].

It was proved that it is semisimple if and only if the characteristic of the fieldF does not divide the number

Fr(X, S)= |X|^|S|

r∈Sd_r

P∈Pmⁿ

2 P

P

(A4) whereP is the set of all non-principal central primitive idempotents of the alge- braCS. This number is called the Frame number of the scheme(X, S).

A scheme(X, S)is called thin, if d_r =1 for all r∈S. In this case there exists a regular groupG≤Sym(X)such thatS coincides with the 2-orbits ofG, i.e. the orbits of the componentwise action ofGon the setX×X. (In this case the setsXand Gcan be naturally identified and the algebraF S becomes the group algebraF G.) Exactly the same construction produces a scheme(X, S) for an arbitrary transitive groupG≤Sym(X). One can prove that such a scheme is primitive if and only if the groupGis primitive.

References

1. Bannai, E., Ito, T.: Algebraic Combinatorics. I. Benjamin-Cummings, Menlo Park (1984)

2. Dade, E.C.: Block extensions. Ill. J. Math. 17, 198–272 (1973)

3. Evdokimov, S.A.: Schurity and separability of associative schemes. Doctor of Sciences Thesis, St.

Petersburg State University (2005)

4. Evdokimov, S., Ponomarenko, I.: Two inequalities for the parameters of a cellular algebra. Zap.

Nauchnykh Seminarov POMI 240, 82–95 (1997). English translation: J. Math. Sci., New York 96(5), 3496–3504 (1999)

5. Hanaki, A.: Semisimplicity of adjacency algebras of association schemes. J. Algebra 225, 124–129 (2000)

6. Hanaki, A., Yoshikawa, M.: On modular standard modules of association schemes. J. Algebraic Com- bin. 21, 269–279 (2005)

7. Narkiewicz, W.: Elementary and Analytic Theory of Algebraic Numbers. Springer Monographs in Mathematics. Springer, Berlin (2004)

8. Peeters, R.: On thep-ranks of the adjacency matrices of distance-regular graphs. J. Algebraic Combin.

15, 127–149 (2002)

9. Weisfeiler, B. (ed.): On Construction and Identification of Graphs. Lecture Notes in Mathematics, vol. 558. Springer, Berlin (1976)

10. Zieschang, P.-H.: Theory of Association Schemes. Springer Monographs in Mathematics. Springer, Berlin (2005)