DOI 10.1007/s10801-010-0230-z
Classification of commutative association schemes with almost commutative Terwilliger algebras
Rie Tanaka
Received: 6 January 2010 / Accepted: 31 March 2010 / Published online: 21 April 2010
© Springer Science+Business Media, LLC 2010
Abstract We classify the commutative association schemes such that all non- primary irreducible modules of their Terwilliger algebras are one-dimensional.
Keywords Association scheme·Terwilliger algebra·Wreath product·Poset
1 Introduction
The Terwilliger algebra T =T(x)of an association scheme X =(X,{Ri}0≤i≤d) (x∈X)is introduced in [9]. The algebraT is a semisimpleC-algebra, and not com- mutative if|X|>1. It is important to determine the irreducibleT-modules for each Xand consider what combinatorial information onXcan be deduced from a property of its irreducibleT-modules.
In [4], the irreducible T-modules of a wreath product of 1-class association schemes are determined and it is shown that every non-primary irreducibleT-module is 1-dimensional. A semisimple algebra is commutative if all of its irreducible mod- ules are 1-dimensional. So we may sayT is almost commutative if all of its non- primary irreducibleT-modules are 1-dimensional. In this paper, we classify the com- mutative association schemes whose Terwilliger algebras are almost commutative.
In the classification, we first characterize such association schemes in terms of intersection numbersphij and Krein parametersqijh ofX.In the study of association schemes,phij andqijh play important roles. By considering vanishing conditions of phij,qijh, several important classes of association schemes such asP-polynomial and Q-polynomial schemes have been introduced [1, 3]. In this paper, we introduce a class of association schemes whose intersection numbers vanish in a drastic way.
R. Tanaka (
)Graduate School of Information Sciences, Tohoku University, Aramaki Aza-Aoba, Aoba-ku, Sendai 980-8579, Japan
e-mail:[email protected]
(B) For all distincth, i, there is exactly onej such thatpijh =0(0≤h, i, j≤d).
(B∗) For all distincth, i, there is exactly onej such thatqijh =0(0≤h, i, j≤d).
The following is the main theorem of this paper:
Theorem 1 LetX=(X,{Ri}0≤i≤d)be a commutative association scheme. The fol- lowing are equivalent:
(i) Every non-primary irreducibleT(x)-module is 1-dimensional for somex∈X.
(ii) Every non-primary irreducibleT(x)-module is 1-dimensional for allx∈X.
(iii) The intersection numbers ofX satisfy (B).
(iv) The Krein parameters ofX satisfy (B∗).
(v) X is a wreath product of association schemesX1,X2, . . . ,Xn where eachXi
is either a 1-class association scheme or the group scheme of a finite abelian group.
Moreover, if (i)–(v) hold,X is triply regular.
The paper is organized as follows: Sect.2reviews some basic properties of asso- ciation schemes and their Terwilliger algebras. In the proof of Theorem1, we will adopt the following strategy. In Sect.3, we will prove the equivalence of assertions (i)–(iv) from the theorem. In Sect.4, we will prove the equivalence of assertions (iii) and (v) from the theorem.
2 Preliminaries
For general introduction to association schemes and Terwilliger algebras, we refer the reader to [1,3,6,9].
LetXbe a finite nonempty set and MatX(C)the set of square complex matrices whose entries are indexed by the elements ofX. LetR0, R1, . . . , Rd be nonempty subsets ofX×X, and for each 0≤i≤d, letAi∈MatX(C)be the adjacency matrix ofRi:
(Ai)xy=
1 if(x, y)∈Ri, 0 otherwise.
The pairX=(X,{Ri}0≤i≤d)is called ad-class association scheme if the following (AS1)–(AS4) hold:
(AS1) A0=I, the identity matrix.
(AS2) A0+A1+ · · · +Ad=J, the all-one’s matrix.
(AS3) For 0≤i≤d, there is 0≤i≤dsuch thatAi=ATi , the transpose ofAi. (AS4) AiAjis a linear combination ofA0, A1, . . . , Adfor 0≤i, j≤d.
By (AS1) and (AS4),M:=Span{A0, A1, . . . , Ad}is a subalgebra of MatX(C);
this is the Bose–Mesner algebra ofX. By (AS2), theAiare linearly independent and thus form a basis forM.We sayX is commutative ifMis commutative.
Throughout the paper, we assumeXis commutative. By (AS3),Mis closed under conjugate-transposition. HenceMis a commutative semisimple algebra and has a basis{Ei:0≤i≤d}of primitive idempotents:
EiEj=δijEi; (1)
E0+E1+ · · · +Ed=I; (2) where we always setE0= |X|−1J.Note that for each 0≤i≤d, there is 0≤ ˆi≤d such thatEˆi=ETi . It also follows from (AS2) thatMis closed under entry-wise multiplication denoted◦.
The intersection numbers pijh and the Krein parameters qijh are defined by the following equations:
AiAj= d
h=0
pijhAh, Ei◦Ej= |X|−1 d
h=0
qijhEh (0≤i, j≤d). (3)
LetRi(x):= {y∈X:(x, y)∈Ri}(x∈X,0≤i≤d). By (3), phij = |Ri(x)∩ Rj(y)|where(x, y)∈Rh(x, y∈X). Clearly, thepijh are non-negative integers. In particular,ki :=pii0= |Ri(x)| =0.We can also verify that theqijh are non-negative real numbers andmi:=qiˆ0
i=trEi=0 [1,6]. Note that ki=
d
h=0
pjih (0≤i, j≤d); (4)
phij=0 ⇐⇒ phji =0 ⇐⇒ pjih=0; (5)
phij=phj i. (6)
Fixx ∈X. For each 0≤i≤d, let Ei∗=Ei∗(x), A∗i =A∗i(x) be the diagonal matrices in MatX(C)withyy-entries(Ei∗)yy=(Ai)xy,(A∗i)yy= |X|(Ei)xy.By def- inition, we have the following:
Ei∗Ej∗=δijE∗i (0≤i, j≤d); (7) E0∗+E∗1+ · · · +Ed∗=I. (8) We also have the following:
A∗0=I; (9)
A∗0+A∗1+ · · · +A∗d= |X|E0∗; (10)
A∗iA∗j = d
h=0
qijhA∗h (0≤i, j≤d). (11)
The Ei∗ and theA∗i form two bases for the dual Bose–Mesner algebra M∗= M∗(x)with respect tox. The Terwilliger algebraT =T(x)of X with respect to
x is the subalgebra of MatX(C)generated byMandM∗. SinceT is closed under conjugate-transposition, it is semisimple. It is easily shown thatT is not commutative if|X|>1. We can verify the following:
Lemma 2 ([9])
(i) Ei∗AjEh∗=0 if and only ifphij=0.
(ii) EiA∗jEh=0 if and only ifqijh=0.
Nonzero matrices amongEi∗AjEh∗(0≤h, i, j ≤d)form a basis ofM∗MM∗, andT is generated by M∗MM∗. When T coincides with M∗MM∗, X has a special regularity:
Definition 3 Xis called triply regular if for all 0≤h, i, j, l, m, n≤d, the size Rh(x)∩Ri(y)∩Rj(z)
is independent ofx, y, z∈Xwhere(x, y)∈Rl, (y, z)∈Rm, (x, z)∈Rn.
Proposition 4 ([7]) X is triply regular if and only ifT(x)=M∗(x)MM∗(x)for allx∈X.
The triple-regularity was first introduced in the study of spin models (see [5]).
LetCXbe the set of the complex column vectors with coordinates indexed byX, and observe that MatX(C)acts onCXfrom the left. We equipCXwith the Hermitian inner product,. Fory∈X,letyˆbe the vector inCXwith a 1 in coordinateyand 0 elsewhere. Then{ ˆy:y∈X}forms an orthonormal basis ofCX.
For aT-moduleW, its orthogonal complementW⊥is also aT-module sinceT is closed under conjugate-transposition. ThusCXis decomposed as a direct sum of irreducibleT-modules. Let 1:=
y∈Xyˆ∈CX.
Lemma 5 ([9]) The space Span{Ei∗1:0≤i≤d} =Span{Eixˆ :0≤i≤d}is an irreducibleT(x)-module of dimensiond+1.
TheT-module in Lemma5will be denotedW0=W0(x). ThisT-moduleW0is said to be primary.
Definition 6 LetX1=(X1,{R(1)i }0≤i≤d1),X2=(X2,{R(2)i }0≤i≤d2)be association schemes, andA(1)i (0≤i≤d1), A(2)i (0≤i≤d2)their adjacency matrices. LetX= X1×X2andRi (0≤i≤d1+d2)be subsets ofX×Xwhose adjacency matricesAi
are defined as follows:
Ai=A(1)i ⊗A(2)0 (0≤i≤d1), Ad1+i=J⊗A(2)i (1≤i≤d2),
where⊗denotes the Kronecker product. Then(X,{Ri}0≤i≤d1+d2)is an association scheme; this is called the wreath product ofX1andX2, denotedX1X2.
Definition 7 LetP,Qbe partially ordered sets (posets). The ordinal sumP⊕Qof PandQis the poset on the unionP∪Qsuch thatx≺yinP⊕Qif (a)x≺yinP, or (b)x≺yinQ, or (c)x∈P andy∈Q.
Basic concepts and properties of posets can be found in [8, Chap. 3].
3 Characterization
In this section, we prove the equivalence of (i)–(iv) in Theorem1. Fixx∈X. Let T =T(x)be the Terwilliger algebra ofXwith respect tox.
Lemma 8 The following are equivalent:
(i) CX=W0.
(ii) ki=1 for all 0≤i≤d.
(iii) mi=1 for all 0≤i≤d.
(iv) Xis the group association scheme of a finite abelian group.
Moreover, if (i)–(iv) hold, then (B) and (B∗) hold.
Proof Since 1=dimEi∗W0≤dimEi∗CX=ki, we have (i)⇔(ii). Similarly, we have (i)⇔ (iii). Obviously,Mis a group algebra if and only if (ii) holds. Since X is commutative, we have (ii)⇔(iv). The last assertion is clear.
See [1,2], for details of group association schemes.
Lemma 9 The following hold.
(i) (B) holds if and only ifEi∗AjEh∗= |X|E∗iE0Eh∗ for 0≤h, i, j ≤d withh=i andphij=0.
(ii) (B∗) holds if and only ifEiA∗jEh= |X|EiE0∗Eh for 0≤h, i, j ≤d withh=i andqijh =0.
Proof (i) Note that by (AS2), |X|E∗iE0Eh∗=Ei∗AjEh∗+
l=jE∗iAlEh∗.Suppose (B) holds. Letpijh =0 andh=i.By Lemma2and (B),Ei∗AlEh∗=0 only ifl=j. Thus|X|E∗iE0Eh∗=Ei∗AjEh∗.Conversely, supposeEi∗AjEh∗= |X|Ei∗E0E∗h.Then we have
l=jE∗iAlEh∗=0.Since theEi∗AlEh∗are linearly independent,Ei∗AlE∗h= 0 ifl=j,that is,pilh =0 only ifl=j.We obtain (B). (ii) By exchanging the roles of thephij, E∗i, Ai, (AS2) by those of theqijh, Ei, A∗i, (10), we obtain the assertion.
Proposition 10 If every non-primary irreducibleT-module is 1-dimensional, then (B), (B∗) hold.
Proof By Lemma 8, if CX=W0, (B), (B∗) hold. Suppose CX=W0. Since the nontrivial subspacesE∗hW0⊥are direct sums of non-primary irreducibleT-modules, they areT-modules. HenceEi∗AjEh∗W0⊥=0 ifh=i.Letpijh =0 andh=i.Let
u2, . . . , ukh be a basis of E∗hW0⊥. Then Eh∗1, u2, . . . , ukh form a basis of Eh∗CX. We have Ei∗AjEh∗1=pijhEi∗1 and|X|Ei∗E0Eh∗1=khE∗i1. Clearly, Ei∗AjEh∗ul =
|X|Ei∗E0Eh∗ul =0 (2≤l ≤kh). Hence kh·Ei∗AjEh∗=phij · |X|Ei∗E0E∗h. Since
|X|Ei∗E0Eh∗=d
l=0Ei∗AlEh∗ and the E∗iAlEh∗ are linearly independent, kh=phij and thusE∗iAjE∗h= |X|Ei∗E0Eh∗. By Lemma9, (B) holds. Similarly, exchanging the roles ofphij,E∗i,Ai, 1 by those of theqijh,Ei,A∗i,x, (Bˆ ∗) holds.
Lemma 11 The following hold.
(i) If (B) holds, thenEi∗MEi∗is a commutative algebra for 0≤i≤d.
(ii) If (B∗) holds, thenEiM∗Ei is a commutative algebra for 0≤i≤d.
Proof (i) By (7), (8) and Lemma9, forh, j (0≤h, j≤d)we have
Ei∗AhAjEi∗=Ei∗Ah
d
l=0
El∗
AjEi∗=Ei∗AhE∗iAjE∗i +
l=i
Ei∗AhE∗lAjE∗i
=Ei∗AhEi∗·E∗iAjE∗i +
l=i
Ei∗AhE∗l ·El∗AjE∗i
=Ei∗AhEi∗·E∗iAjE∗i +
l=i,pihl =0,pilj=0
|X|2Ei∗E0El∗E0Ei∗
=Ei∗AhEi∗·E∗iAjE∗i +
l=i,pihl =0,pilj=0
kl|X|Ei∗E0Ei∗.
Therefore
Ei∗AhEi∗·Ei∗AjEi∗=Ei∗AhAjEi∗−
l=i,pihl =0,plji=0
kl|X|Ei∗E0E∗i
= d
l=0
phjl Ei∗AlE∗i −
l=i,pihl =0,pilj=0
kl|X|Ei∗E0Ei∗. (12)
HenceEi∗MEi∗is closed under multiplication. SinceMis commutative, by (12), Ei∗ME∗i is commutative as well. (ii) Exchanging the roles of the phij, E∗i, Ai,M, (7), (8) by those of theqijh,Ei,A∗j,M∗, (1), (2), the assertion holds.
Lemma 12 The following hold.
(i) If (B) holds, thenT =M∗MM∗. (ii) If (B∗) holds, thenT =MM∗M.
Proof (i) Let U :=Span{Ei∗E0E∗h :h =i,0 ≤ h, i ≤ d}. By Lemma 9, U = Span{Ei∗AjEh∗:h=i,0≤h, i, j ≤d}.HenceM∗MM∗=(d
i=0Ei∗MEi∗)⊕U
(a direct sum). By Lemma11and calculations in its proof, theEi∗MEi∗andU are closed under multiplication. We can easily verify that theEi∗MEi∗ act onU from both the left and the right. ThusM∗MM∗forms an algebra, i.e.,T =M∗MM∗. (ii) Exchanging the roles of thepijh, Ei∗, Ai,Mby those of theqijh, Ei, A∗i,M∗, the
assertion holds.
Corollary 13 If (B) holds,X is triply regular.
Proof By Proposition4and Lemma12, the assertion holds.
Proposition 14 The following hold.
(i) If (B) holds, every non-primary irreducibleT-module is 1-dimensional.
(ii) If (B∗) holds, every non-primary irreducibleT-module is 1-dimensional.
Proof (i) By Lemma 11, E∗iMEi∗ is a commutative semisimple algebra. Hence Ei∗CX is decomposed as the direct sum of the common eigenspaces ofEi∗MEi∗. AssumeCX=W0.Letu∈(Ei∗CX)∩W0⊥be a common eigenvector ofEi∗MEi∗. Since Span{u}is closed under the action of M∗MM∗, by Lemma 12, it is aT- module. In this way,(Ei∗CX)∩W0⊥is decomposed as a direct sum of 1-dimensional irreducibleT-modules. The assertion is clear. (ii) Exchanging the roles of theEi∗,M
by those of theEi,M∗, the assertion holds.
Proof of Theorem1(i)⇔(ii)⇔(iii)⇔(iv) By Proposition10, we have (i)⇒(iii) and (i)⇒(iv). By Proposition14, we have (iii)⇒(ii) and (iv)⇒(ii). Obviously, (ii)
⇒(i).
4 Classification
In this section, we prove (iii)⇔(v) in Theorem1. Throughout the section, letX= (X,{Ri}0≤i≤d) be a commutative association scheme whose intersection numbers satisfy (B).
Lemma 15 Ifpijj =0 for 1≤i, j≤d,thenpjij=0, pjij=0 andpjij=0.
Proof By (5),pijj =0 and pijj =0. Again by (5),pjji =0, and by (6) we have
pjij=0.Again by (5),pijj=0.
Lemma 16 Ifpijj=0 for 1≤i, j≤d withi=j, thenAiAj=pijjAj.
Proof By (B),pijl=0 ifl=j.By (5),pjil=0 if and only ifpijl =0.Henceplij=0
ifl=j,and the assertion holds.
Let[i] = [i] := {i, i}for 1≤i≤d.
Lemma 17 Let≺be the relation on{[i] :1≤i≤d}defined as follows:[i] ≺ [j]if [i] = [j]orpijj =0. Then≺is a partial order.
Proof By Lemma15, the relation ≺ is well-defined. By definition,≺is reflexive.
Suppose [i] ≺ [j] and [j] ≺ [i]. Moreover suppose pijj =0 and pj ii =0. Since pjij =0,by (5),pijj =0.If i=j,by (B),pj li =0 only ifl=j.Since pij i=0, i=j.Thus[i] = [j]and≺is antisymmetric. Suppose[h] ≺ [i]and[i] ≺ [j]for distinct [h],[i],[j]. Since phii =0, pjij =0 and h=i, i=j, by Lemma 16, (AhAi)Aj=phii AiAj =phii pjijAj =0.On the other hand,Ah(AiAj)=pjijAhAj. ThereforeAhAj=pjhjAj=0 andpjhj =0. Hence[h] ≺ [j], and thus≺is transi-
tive.
For the rest of the section, letP:=({[i] :1≤i≤d},≺)be the poset defined in Lemma17.
Lemma 18 Let[i]be a minimal element ofP. Ifki≥2,then[i]is the minimum.
Proof Supposeki ≥2.Letx∈X.Take distincty, z∈Ri(x).Since[i]is minimal, (y, z)∈Ri ∪Ri. Let[j] ∈P \ {[i]} and w∈Rj(x). Since i=j, by (B),y, z∈ Rh(w)for some 1≤h≤d.Hencephih =pihh =0,and[i] ≺ [h].If[h] = [i],by the configuration ofx, y, w, we havepij i=0 orpij i=0,i.e.,[j] ≺ [i], contradicting[i] is minimal. Hence[h] = [i].By the configuration ofx, w, y, pj hi =pihj=0.Since [h] = [i]andpihh=0, h=j.So[h] = [j].Since[i] ≺ [h],we have[i] ≺ [j].
Lemma 19 The following hold.
(i) IfP is a singleton, then eitherd=1 orX is the group association scheme ofZ3. (ii) IfPis an antichain with at least 2 elements,X is the group association scheme
of a finite abelian group.
Proof (i) LetP= {[i]}.Supposeki≥2.Thenpiii =0.By (5), (6), we havepiii= piii=0. Ifi=i,by (B), (4),ki=d
l=0piil=piii=piii< pii0+piii≤d
l=0pili = ki, contradictingki=ki.Hencei=i,i.e.,d=1.Supposed=1. Thenki=ki=1 and by Lemma8,Xis the group association scheme ofZ3.(ii) By Lemma18,ki=1
for all[i] ∈P.By Lemma8, the assertion holds.
Lemma 20 Suppose P =P1⊕P2 for some subposets P1,P2 of P. Then R0∪ ( [i]∈P
1Ri)is an equivalence relation onX, i.e.,X is imprimitive. Moreover, Ai (1≤i≤d)can be written as follows:
Ai=Bi⊗Iq [i] ∈P1
; Ai=Jp⊗Ci
[i] ∈P2
;
whereB0=Ip,Bi ([i] ∈P1)are the adjacency matrices of the subschemeX1and C0=Iq,Ci ([i] ∈P2)are those of the quotient schemeX2=X/X1. In particular, X=X1X2.
Proof The first assertion is clear. By [1, Theorem II.9.3], the equations on Ai
([i] ∈P1)hold. Let ∼be the relation on{0,1, . . . , d}defined asi∼j ifpj αi =0 for someα∈ [α] ∈P1.Then∼is an equivalence relation. Clearly,{0} ∪ {i: [i] ∈P1} is an equivalence class. For[i] ∈P2,piαi=0 for allα∈ [α] ∈P1.Sincei=α,by (B),piαj=0 ifj=i.In particular, for[j] ∈P2,pj αi =pαji =0 ifj=i.Hence each i ([i] ∈P2)forms an equivalence class. By [1, Theorem II.9.4], the equations onAi ([i] ∈P2)hold. The last assertion is clear by Definition6.
Corollary 21 We keep the notation of Lemma20. BothX1andX2are commutative association schemes whose intersection numbers satisfy (B) and whose correspond- ing posets areP1andP2respectively.
For details of imprimitive association schemes, see [1, Sect. II.9].
Lemma 22 Suppose[i],[j] ∈P are incomparable. If[i] ≺ [h]for some[h] ∈P\ {[i],[j]},then[j] ≺ [h].
Proof Letx∈X. Takey∈Ri(x), z∈Rj(x)andw∈Rh(x).Since [i] ≺ [h],i.e., phih=0, by (B), phil=0 if l=h. So(y, w)∈Rh.Let(y, z)∈Rs and(z, w)∈Rt. By the configurations of 3 verticesx, z, wandy, z, w, we obtainphj t=ptjh =0 and phst =pt sh =0.Ift=h, by (B), we haves=j and by the configuration ofx, y, z, we havepijj =0 contradicting the assumption that[i],[j]are incomparable. Hence
t=handphj h=0, i.e.,[j] ≺ [h].
Proposition 23 Pis an ordinal sum of singletons and antichains.
Proof LetP1be the set of minimal elements ofP. Clearly,P1is either a singleton or an antichain. By Lemma22,P=P1⊕(P\P1). Next letP2be the set of minimal elements ofP\P1. Similarly we obtainP\P1=P2⊕(P\(P1⊕P2)).Repeating this process, we finally obtainP=P1⊕P2⊕ · · · ⊕Pm,wherePi (1≤i≤m)is
either a singleton or an antichain.
Proof of Theorem1(iii)⇔(v) By Proposition23,P=P1⊕P2⊕ · · · ⊕Pm,where Pl(1≤l≤m) is a singleton or an antichain. By Lemma20, the subposetP1induces the subschemeX1 of X, andX =X1Y1 whereY1 denotes the quotient scheme X/X1. By Corollary21,Y1satisfies (B) and corresponds to the posetP2⊕ · · · ⊕Pm. Again, the subposetP2induces the subschemeX2ofY1,andY1=X2Y2whereY2
denotes the quotient schemeY1/X2.Repeating this process, we finally obtainX= X1X2 · · · Xm,whereXl (1≤l≤m)corresponds to the posetPl. By Lemma19, Xl is a 1-class association scheme or the group association scheme of a finite abelian
group. This completes the proof.
Remark LetX be a symmetric association scheme. ThenX is a wreath product of 1-class association schemes if and only ifP is a chain.
Acknowledgements The author would like to thank Hajime Tanaka for valuable discussions and sug- gestions. She would also like to thank Paul Terwilliger for his careful reading of the manuscript.
References
1. Bannai, E., Ito, T.: Algebraic Combinatorics I. Benjamin/Cummings, Redwood City (1984)
2. Bannai, E., Munemasa, A.: The Terwilliger algebras of group association schemes. Kyushu J. Math.
49, 93–102 (1995)
3. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin, Heidelberg (1989)
4. Bhattacharyya, G., Song, S.-Y., Tanaka, R.: On Terwilliger algebras of wreath products of one-class association schemes. J. Algebr. Comb. 31, 455–466 (2010)
5. Jaeger, F.: On spin models, triply regular association schemes, and duality. J. Algebr. Comb. 4, 103–144 (1995)
6. Martin, W.J., Tanaka, H.: Commutative association schemes. Eur. J. Comb. 30, 1497–1525 (2009) 7. Munemasa, A.: An application of Terwilliger algebra. Unpublished preprint. Preprint found on:
http://www.math.is.tohoku.ac.jp/~munemasa/unpublished.html
8. Stanley, R.P.: Enumerative Combinatorics, vol. I. Cambridge Univ. Press, Cambridge (2002) 9. Terwilliger, P.: The subconstituent algebra of an association scheme (Part I). J. Algebr. Comb. 1, 363–
388 (1992). (Part II; III), J. Algebr. Comb. 2, 73–103; 177–210 (1993)
