A Note on Thin P-Polynomial and Dual-Thin Q-Polynomial Symmetric Association Schemes

(1)

P1: PMR

Journal of Algebraic Combinatorics KL507-01-Dickie November 6, 1997 13:58

Journal of Algebraic Combinatorics 7 (1998), 5–15

°c 1998 Kluwer Academic Publishers. Manufactured in The Netherlands.

A Note on Thin P-Polynomial and Dual-Thin Q-Polynomial Symmetric Association Schemes

GARTH A. DICKIE [email protected]

University of Technology, Discrete Mathematics HG 9.53, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

PAUL M. TERWILLIGER [email protected]

Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison WI 53706 Received December 18, 1995

Abstract. Let Y denote a d-class symmetric association scheme, with d ≥3. We show the following: If Y admits a P-polynomial structure with intersection numbers p^h_{i j}and Y is 1-thin with respect to at least one vertex, then

p₁₁¹ =0⇒ pⁱ_1i=0 1≤i≤d−1.

If Y admits a Q-polynomial structure with Krein parameters q_{i j}^h, and Y is dual 1-thin with respect to at least one vertex, then

q₁₁¹ =0⇒q_1iⁱ =0 1≤i≤d−1.

Keywords: Association scheme, distance-regular graph, intersection number, Q-polynomial

1. Introduction

Let Y denote a d-class symmetric association scheme, with d ≥3. It is well-known that if Y admits a P-polynomial structure with intersection numbers p_{i j}^h, then

p¹₁₁6=0 ⇒ p_1iⁱ 6=0 1≤i≤d−1 (1)

[1, Theorem 5.5.1]. The first author shows in [3] that if Y admits a Q-polynomial structure with Krein parameters q_{i j}^h, then

q₁₁¹ 6=0 ⇒ q_1iⁱ 6=0 1≤i ≤d−1. (2)

In the present paper we show the following: If Y admits a P-polynomial structure with intersection numbers p^h_{i j}, and Y is 1-thin with respect to at least one vertex, then

p¹₁₁=0 ⇒ p_1iⁱ =0 1≤i≤d−1. (3)

If Y admits a Q-polynomial structure with Krein parameters q_{i j}^h, and Y is dual 1-thin with respect to at least one vertex, then

q₁₁¹ =0 ⇒ q_1iⁱ =0 1≤i ≤d−1. (4)

(2)

P1: PMR

6 DICKIE AND TERWILLIGER

The 1-thin and dual 1-thin conditions are defined in Section 1.4. Our main results are in Theorems 2.1 and 2.2.

In the following sections we introduce notation and recall basic results, following [1, Section 2.1] and [4, Section 3].

1.1. Symmetric association schemes

By a d-class symmetric association scheme we mean a pair Y =(X,{R_i}0≤i≤d), where X is a non-empty finite set, and where

(i) {Ri}0≤i≤dis a partition of X×X ; (ii) R0= {x x |x∈X};

(iii) R_i =R_i^tfor 0≤i ≤d, where R_i^t = {yx |x y∈R_i};

(iv) there exist integers p_{i j}^h such that for all integers h with 0 ≤ h ≤ d and all vertices x,y∈ X with x y∈ R_h,

p_{i j}^h = |{z∈ X |x z∈ Ri, yz∈ Rj}| 0≤i, j ≤d. (5) We refer to X as the vertex set of Y , and refer to the integers p^h_{i j}as the intersection numbers of Y . Abbreviate ki = p_ii⁰, and observe ki is non-zero for 0≤i ≤d.

1.2. The Bose-Mesner algebra

Let Y =(X,{Ri}0≤i≤d)denote a symmetric association scheme. Let MatX(R)denote the algebra of matrices overRwith rows and columns indexed by X . The associate matrices for Y are the matrices A0, . . . ,Ad∈MatX(R)defined by

(Ai)x y =

(1 if x y ∈R_i,

0 otherwise x,y∈X. (6)

From (i)–(iv) above we obtain

A₀+ · · · +A_d = J, (7)

Ai◦ Aj = δi jAi 0≤i, j ≤d, (8)

A₀ = I, (9)

Ai = A^t_i 0≤i ≤d, (10)

AiAj = Xd h=0

p^h_{i j}Ah 0≤i, j ≤d, (11)

where J is the all-1s matrix and◦denotes the entry-wise matrix product.

By the Bose-Mesner algebra of Y we mean the subalgebra M of Mat_X(R)generated by the associate matrices A₀, . . . ,A_d. Observe by (8) and (11) that the associate matrices form a basis for M. In particular, M is symmetric and closed under◦.

(3)

P1: PMR

THIN P-POLYNOMIAL AND DUAL-THIN Q-POLYNOMIAL 7 The algebra M has a second basis E0, . . . ,Ed such that

E0+ · · · +Ed = I, (12)

EiEj = δi jEi 0≤i, j ≤d, (13)

E0 = 1

|X|J, (14)

E_i = E_i^t 0≤i≤d, (15)

[1, Theorem 2.6.1]. We refer to E₀, . . . ,E_d as the primitive idempotents of Y . Since M is closed under◦, there exist real numbers q_{i j}^h satisfying

Ei◦Ej = 1

|X| Xd h=0

q_{i j}^hEh 0≤i, j ≤d. (16)

The numbers q_{i j}^h are the Krein parameters for Y . Abbreviate k_i^∗=q_{i i}⁰ for 0≤i ≤d.

By (8), (9), and the fact that A₀, . . . ,A_dis a basis for M, the primitive idempotents have constant diagonal; in fact

(Ei)x x= k^∗_i

|X| 0≤i≤d, x∈ X (17)

and k_i^∗6=0 [1, p. 45]. We apply (17) in the proof of Lemma 4.1.

1.3. The dual Bose-Mesner algebra

Let Y denote a d-class symmetric association scheme with vertex set X , associate matrices A0, . . . ,Ad, primitive idempotents E0, . . . ,Ed, and Bose-Mesner algebra M. Fix a vertex x∈ X .

For each integer i with 0≤i ≤d let A^∗_i =A^∗_i(x)denote the diagonal matrix in Mat_X(R) defined by

(A^∗_i)yy= |X|(E_i)x y y∈ X. (18)

We refer to A^∗₀, . . . ,A^∗_d as the dual associate matrices for Y with respect to x. Let M^∗=M^∗(x)denote the subalgebra of Mat_X(R)generated by the dual associate matrices.

We refer to M^∗as the dual Bose-Mesner algebra for Y with respect to x. From (16) we obtain

A^∗_iA^∗_j= Xd h=0

q_{i j}^hA^∗_h 0≤i, j ≤d. (19)

In particular, the dual associate matrices form a basis for M^∗.

(4)

P1: PMR

For each integer i with 0≤i ≤d let E_i^∗=E^∗_i(x)denote the diagonal matrix in MatX(R) defined by

(E_i^∗)yy =(Ai)x y y∈ X. (20)

From (7), (8) we obtain

E^∗₀+ · · · +E_d^∗ = I, (21)

E^∗_iE^∗_j = δi jE_i^∗ 0≤i, j≤d. (22) We refer to E₀^∗, . . . ,E^∗_d as the dual idempotents for Y with respect to x. Note that the dual idempotents form a second basis for M^∗.

1.4. The thin and dual-thin conditions

Let Y denote a d-class symmetric association scheme with vertex set X . Fix a vertex x ∈ X , and write M^∗ =M^∗(x).

Let T =T(x)denote the subalgebra of Mat_X(R)generated by M and M^∗. We refer to T as the subconstituent algebra for Y with respect to x. By a T -module we mean a subspace of the standard module V =R^X which is closed under multiplication by T . A T -module is said to be irreducible if it properly contains no T -modules other than 0. Recall that T is semi-simple, so that V may be decomposed as a direct sum of irreducible T -modules [4, Lemma 3.4].

An irreducible T -module W is said to be thin if

dim E_i^∗W ≤1 0≤i ≤d, (23)

and dual thin if

dim EiW ≤1 0≤i≤d. (24)

We say Y is i -thin with respect to x if every irreducible T -module W with E_i^∗W 6=0 is thin. We say Y is dual i -thin with respect to x if every irreducible T -module W with EiW 6=0 is dual thin.

1.5. P- and Q-polynomial structures

Let Y denote a d-class symmetric association scheme, with vertex set X , intersection numbers p_{i j}^h, and Krein parameters q_{i j}^h. We say that an ordering A0, . . . ,Adof the associate matrices is a P-polynomial structure for Y whenever

p_{i j}^h = 0 if one of h,i,j is greater than the sum of the other two, (25) p_{i j}^h 6= 0 if one of h,i,j is equal to the sum of the other two (26)

(5)

P1: PMR

THIN P-POLYNOMIAL AND DUAL-THIN Q-POLYNOMIAL 9 for 0≤ h,i,j ≤d. Recall that if A0, . . . ,Ad is a P-polynomial structure for Y , then A1

generates M [4, Lemma 3.8].

We say that an ordering E₀, . . . ,E_d of the primitive idempotents is a Q-polynomial structure for Y whenever

q_{i j}^h = 0 if one of h,i,j is greater than the sum of the other two, (27) q_{i j}^h 6= 0 if one of h,i,j is equal to the sum of the other two (28) for 0≤h,i,j ≤d. Recall that if E₀, . . . ,E_d is a Q-polynomial structure for Y , then for each x ∈X the dual associate matrix A^∗₁(x)generates M^∗(x)[4, Lemma 3.11].

2. Results

Our main results are the following:

Theorem 2.1 Let Y denote a d-class symmetric association scheme,with d≥3. Suppose A0, . . . ,Ad is a P-polynomial structure for Y with intersection numbers p_{i j}^h,and suppose Y is 1-thin with respect to at least one vertex. Then

p¹₁₁=0 ⇒ p_1iⁱ =0 1≤i≤d−1. (29)

We prove Theorem 2.1 in Section 3.

Theorem 2.2 Let Y denote a d-class symmetric association scheme,with d≥3. Suppose E0, . . . ,Edis a Q-polynomial structure for Y with Krein parameters q_{i j}^h,and suppose Y is dual 1-thin with respect to at least one vertex. Then

q₁₁¹ =0 ⇒ q_1iⁱ =0 1≤i ≤d−1. (30)

We prove Theorem 2.2 in Section 4.

3. Proof of Theorem 2.1

Define a symmetric bilinear form on MatX(R)(where X is any set) by

hB,Ci =tr(B^tC) B,C∈MatX(R). (31) Observe thathB,Ciis just the sum of the entries of B◦C. In particular, the form is positive definite.

Lemma 3.1 (Terwilliger [4]) Let Y=(X,{R_i}0≤i≤d)denote a symmetric association scheme with associate matrices A₀, . . . ,A_d and intersection numbers p_{i j}^h. Fix a vertex x∈ X,and write E_i^∗=E_i^∗(x)for 0≤i ≤d. Then:

(6)

P1: PMR

(i) for 0≤h,h⁰,i,i⁰,j,j⁰≤d,

hE_i^∗AhE^∗_j,E_i^∗0Ah⁰E^∗_j0i =δhh⁰δi i⁰δj j⁰khp_{i j}^h; (32) (ii) for 0≤h,i,j ≤d,

E_h^∗AiE^∗_j =0 ⇔ p^h_{i j}=0. (33)

Proof of (i): Observe

(E_i^∗AhE^∗_j)yz =(E_i^∗)yy(Ah)yz(E^∗_j)zz (34)

=(A_i)x y(A_h)yz(A_j)x z, (35) so that(E_i^∗AhE^∗_j)yz6=0 if and only if x y∈ Ri, yz∈ Rh, and x z∈ Rj. Since the relations R0, . . . ,Rd are disjoint, the matrices E_i^∗AhE^∗_j and E_i^∗0Ah⁰E^∗_j0 have no non-zero entries in common unless h = h⁰,i = i⁰,j = j⁰. In this case there are precisely k_hp_{i j}^h non-zero entries, each equal to 1. The result follows.

Proof of (ii): Immediate from (i). 2

Let Y denote a d-class symmetric association scheme, with vertex set X . Suppose A₀, . . . ,A_d is a P-polynomial structure for Y , with intersection numbers p^h_{i j}. Fix a vertex x∈ X , and write T =T(x), M^∗=M^∗(x), and E^∗_i =E_i^∗(x)for 0≤i≤d.

There are three matrices in T which are of particular interest to us (their duals will be used in Section 4). These are the lowering matrix L = L(x), the flat matrix F = F(x), and the raising matrix R=R(x), defined by

L = Xd

i=1

E_i^∗₋₁A1E_i^∗, (36)

F = Xd

i=0

E_i^∗A₁E_i^∗, (37)

R=

d−1

X

i=0

E_i^∗₊₁A1E_i^∗. (38)

It is easily shown using (25), (21), and (33) that

A1=L+F+R. (39)

Recall that A1generates the Bose-Mesner algebra M, so that A1and E₀^∗, . . . ,E_d^∗generate T . In particular, L, F , R, and E^∗₀, . . . ,E_d^∗generate T by (39).

Lemma 3.2 Let Y denote a d-class symmetric association scheme,with vertex set X . Suppose A0, . . . ,Adis a P-polynomial structure for Y,with intersection numbers p_{i j}^h. Fix

(7)

P1: PMR

THIN P-POLYNOMIAL AND DUAL-THIN Q-POLYNOMIAL 11 a vertex x∈ X,and write T =T(x),L =L(x),and E_i^∗ =E^∗_i(x)for 0≤i ≤d. If Y is 1-thin with respect to x,then:

(i) for any irreducible T -module W with E₁^∗W 6=0,

L E^∗_iW =0 ⇒ E_i^∗W =0 2≤i ≤d; (40)

(ii) forw∈T E₁^∗V,

L E^∗_iw=0 ⇒ E^∗_iw=0 2≤i ≤d; (41)

(iii) for B∈T E^∗₁,

L E^∗_iB=0 ⇒ E_i^∗B=0 2≤i ≤d. (42)

Proof of (i): Let W be given. Fix an integer i with 2≤i ≤d, and suppose L E_i^∗W =0.

Let W⁰denote the subspace of W defined by

W⁰=E_i^∗W + · · · +E_d^∗W. (43) Observe by (36)–(38) and (13) that W⁰is closed under multiplication by L, F , R, and E^∗₀, . . . ,E_d^∗. Since T is generated by these matrices, W⁰is a T -module. Since E^∗₁W⁰=0 and E₁^∗W 6= 0, W⁰is a proper submodule of W . Since W is irreducible, we now have W⁰=0, and E_i^∗W ⊆W⁰is zero as desired.

Proof of (ii): Since V may be decomposed into a direct sum of irreducible T -modules, it suffices to show that the result holds forw∈T E^∗₁W where W is an irreducible T -module.

Fix an integer i with 2≤i ≤d and an irreducible T -module W , and supposew∈T E₁^∗W has L E^∗_iw=0.

Suppose E_i^∗w6=0. Observe E₁^∗W 6=0, since 06=E_i^∗w∈ E_i^∗T E₁^∗W . Since Y is 1-thin with respect to x, W is thin and dim E_i^∗W ≤1. In particular, E_i^∗w∈ E_i^∗W spans E_i^∗W , and L E_i^∗W =0. By (i) we have E_i^∗W =0, and E^∗_iw=0 for a contradiction. Thus E^∗_iw=0 as desired.

Proof of (iii): Immediate from (ii). 2

Lemma 3.3 Let Y denote a d-class symmetric association scheme,with vertex set X . Suppose A0, . . . ,Adis a P-polynomial structure for Y,with intersection numbers p_{i j}^h. Fix a vertex x ∈X,and write L=L(x)and E_i^∗=E^∗_i(x)for 0≤i ≤d. Then:

(i) for 1≤i≤d−1,

L E^∗_iAi+1E₁^∗= p₁ⁱ_,_i₊₁E^∗_i₋₁AiE₁^∗; (44) (ii) for 1≤i ≤d,if p₁ⁱ⁻_,_i¹₋₁=0 then

L E^∗_iA_iE₁^∗=pⁱ_1iE_i^∗₋₁A_iE^∗₁. (45)

(8)

P1: PMR

Proof of (i): Let i be given. Observe by (22), (25), (33), (21), and (11) that

L E_i^∗Ai+1E^∗₁ =E_i^∗₋₁AE_i^∗Ai+1E₁^∗ (46)

=E_i^∗₋₁A Ã _d

X

h=0

E_h^∗

!

Ai+1E₁^∗ (47)

=E_i^∗₋₁A Ai+1E₁^∗ (48)

=E_i^∗₋₁ ÃXd

h=0

p^h₁_,_i₊₁Ah

!

E₁^∗ (49)

= p₁ⁱ_,_i₊₁E^∗_i₋₁AiE₁^∗, (50) as desired.

Proof of (ii): Let i be given, with pⁱ₁⁻_,_i¹₋₁=0. Observe as in (i) that

L E_i^∗A_iE₁^∗ =E_i^∗₋₁AE_i^∗A_iE₁^∗ (51)

=E_i^∗₋₁A Ã _d

X

h=0

E^∗_h

!

A_iE^∗₁ (52)

=E_i^∗₋₁A AiE^∗₁ (53)

=E_i^∗₋₁ Ã _d

X

h=0

p_1i^hAh

!

E₁^∗ (54)

=pⁱ_1iE_i^∗₋₁AiE^∗₁, (55)

as desired. 2

Proof of Theorem 2.1: Suppose Y is 1-thin with respect to x, and write L =L(x)and E^∗_i =E_i^∗(x)for 0≤i≤d. Suppose p₁₁¹ =0, and suppose for a contradiction that pⁱ_1i 6=0 for some i with 2≤i ≤d−1. Fix i ≥2 minimal with pⁱ_1i 6=0. Then by Lemma 3.3,

0=L¡

pⁱ_1iE_i^∗Ai+1E₁^∗−p₁ⁱ_,_i₊₁E_i^∗AiE₁^∗¢

, (56)

and by Lemma 3.2(iii),

0= p_1iⁱ E_i^∗A_i₊₁E^∗₁−pⁱ₁_,_i₊₁E_i^∗A_iE₁^∗. (57) The summands in (57) are nonzero by (33) and orthogonal by (32), for a contradiction.

Thus pⁱ_1i =0 for 2≤i ≤d−1, as desired. 2

4. Proof of Theorem 2.2

Our proof is based upon the following result:

(9)

P1: PMR

THIN P-POLYNOMIAL AND DUAL-THIN Q-POLYNOMIAL 13 Lemma 4.1 (Cameron, Goethals, Seidel [2]) Let Y denote a d-class symmetric associ- ation scheme,with vertex set X,primitive idempotents E0, . . . ,Ed,and Krein parameters q_{i j}^h. Fix a vertex x∈ X,and write A^∗_i = A^∗_i(x)for 0≤i≤d. Then:

(i) for 0≤h,h⁰,i,i⁰,j,j⁰≤d,

hE_iA^∗_hE_j,E_i0A^∗_h0E_j0i =δhh⁰δi i⁰δj j⁰k^∗_hq_{i j}^h; (58) (ii) for 0≤h,i,j ≤d,

EhA^∗_iEj =0 ⇔ q_{i j}^h =0. (59)

Proof of (i): Recall tr(BC)=tr(C B), and observe by (15), (13), (18), (16), and (17) that hE_iA^∗_hE_j,E_i0A^∗_h₀E_j0i = tr(E_jA^∗_hE_iE_i0A^∗_h₀E_j0) (60)

= tr(Ej⁰EjA^∗_hEiEi⁰A^∗_h0) (61)

= δii⁰δj j⁰tr(E_jA^∗_hE_iA^∗_h0) (62)

= δii⁰δj j⁰

X

y,z∈X

(Ej)yz(A^∗_h)zz(Ei)zy(A^∗_h0)yy (63)

= δii⁰δj j⁰|X|² X

y,z∈X

(E_j)yz(E_h)x z(E_i)zy(E_h0)x y (64)

= δii⁰δj j⁰|X|²X

y∈X

((Ei◦Ej)Eh)yx(Eh⁰)x y (65)

= δii⁰δj j⁰|X|q_{i j}^hX

y∈X

(Eh)yx(Eh⁰)x y (66)

= δii⁰δj j⁰|X|q_{i j}^h(E_h0E_h)x x (67)

= δhh⁰δii⁰δj j⁰|X|q_{i j}^h(Eh)x x (68)

= δhh⁰δii⁰δj j⁰k^∗_hq_{i j}^h, (69) as desired.

Proof of (ii): Immediate from (i). 2

Let Y denote a d-class symmetric association scheme, with vertex set X . Suppose E0, . . . ,Ed is a Q-polynomial structure for Y , with Krein parameters q_{i j}^h. Fix a vertex x∈ X , and write T =T(x), M^∗=M^∗(x), and A^∗_i =A^∗_i(x)for 0≤i ≤d.

The dual lowering matrix L^∗ = L^∗(x), the dual flat matrix F^∗ =F^∗(x), and the dual raising matrix R^∗=R^∗(x)are defined by

L^∗ = Xd

i=1

Ei−1A^∗₁Ei, (70)

(10)

P1: PMR

F^∗ = Xd

i=0

EiA^∗₁Ei, (71)

R^∗ =

d−1

X

i=0

E_i₊₁A^∗₁E_i. (72)

It is easily shown using (27), (12), and (59) that

A^∗₁=L^∗+F^∗+R^∗. (73)

Recall that A^∗₁ generates the dual Bose-Mesner algebra M^∗, so that A^∗₁ and E0, . . . ,Ed

generate T . In particular, L^∗, F^∗, R^∗, and E^∗₀, . . . ,E_d^∗generate T by (73).

Lemma 4.2 Let Y denote a d-class symmetric association scheme,with vertex set X . Suppose E0, . . . ,Ed is a Q-polynomial structure for Y,with Krein parameters q_{i j}^h. Fix a vertex x ∈ X,and write T =T(x),L^∗ =L^∗(x),and A^∗_i = A^∗_i(x)for 0≤i ≤d. If Y is dual 1-thin with respect to x,then:

(i) for any irreducible T -module W with E₁W 6=0,

L^∗EiW =0 ⇒ EiW =0 2≤i ≤d; (74)

(ii) forw∈T E1V,

L^∗Eiw=0 ⇒ Eiw=0 2≤i ≤d; (75)

(iii) for B∈T E1,

L^∗EiB=0 ⇒ EiB=0 2≤i ≤d. (76)

Proof: Similar to the proof of Lemma 3.2. 2

Lemma 4.3 Let Y denote a d-class symmetric association scheme,with vertex set X . Suppose E0, . . . ,Ed is a Q-polynomial structure for Y,with Krein parameters q_{i j}^h. Fix a vertex x∈ X,and write L^∗ =L^∗(x)and A^∗_i =A^∗_i(x)for 0≤i ≤d. Then:

(i) for 1≤i ≤d,

L^∗EiA^∗_i₊₁E1=q₁ⁱ_,_i₊₁Ei−1A^∗_iE1; (77) (ii) for 1≤i ≤d,if q₁ⁱ⁻_,_i₋¹₁=0 then

L^∗E_iA^∗_iE₁=q_1iⁱ E_i₋₁A^∗_iE₁. (78)

Proof: Similar to the proof of Lemma 3.3. 2

Proof of Theorem 2.2: Similar to the proof of Theorem 2.1. 2

(11)

P1: PMR

THIN P-POLYNOMIAL AND DUAL-THIN Q-POLYNOMIAL 15 References

1. A.E. Brouwer, A.M. Cohen, and A. Neumaier. Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.

2. P. Cameron, J. Goethals, and J. Seidel, “The Krein condition, spherical designs, Norton algebras, and permu- tation groups,” Indag. Math. 40 (1978), 196–206.

3. G. Dickie. “A note on Q-polynomial association schemes,” J. Alg. Combin. Submitted.

4. P. Terwilliger. “The subconstituent algebra of an association scheme. I,” J. Alg. Combin. 1(4) (1992), 363–388.