Association Schemes

Association Schemes

with Multiple Q -polynomial Structures

HIROSHI SUZUKI [email protected]

Department of Mathematics, International Christian University, 10-2, Osawa 3-chome, Mitaka-shi Tokyo 181, Japan

Received April 25, 1996; Revised January 13, 1997

Abstract. It is well known that an association schemeX= (X,{R_i}0≤i≤d)withk1>2has at most twoP- polynomial structures. The parametrical condition for an association scheme to have twoP-polynomial structures is also known. In this paper, we give a similar result forQ-polynomial association schemes. In fact, ifd >5, then we obtain exactly the same parametrical conditions for the dual intersection numbers or Krein parameters.

Keywords: Q-polynomial, association scheme, multipleQ-polynomial structure, Krein parameter, distance- regular graph, integrality of eigenvalue

1. Introduction

Ad-class symmetric association scheme is a pairX = (X,{R_i}0≤i≤d), whereXis a finite set, eachR_iis a nonempty subset ofX×Xfori= 0,1, . . . , dsatisfying the following.

(i) R0={(x, x)|x∈X}.

(ii) {R_i}0≤i≤dis a partition ofX×X, i.e.,

X×X =R₀∪R₁∪ · · · ∪R_d, R_i∩R_j =∅ifi6=j.

(iii) ^tR_i=R_ifori= 0,1, . . . , d, where^tR_i={(y, x)|(x, y)∈R_i}. (iv) There exist integersp^h_i,jsuch that for allx, y∈X with(x, y)∈Rh,

p^h_i,j=|{z∈X|(x, z)∈R_i, (z, y)∈R_j}|.

We refer toXas the vertex set ofX, and to the integersp^h_i,jas the intersection numbers ofX.

LetX = (X,{R_i}0≤i≤d)be a symmetric association scheme. LetMat_X(R)denote the algebra of matrices over the realsRwith rows and columns indexed byX. Thei-th adjacency matrixA_i∈Mat_X(R)ofXis defined by

(Ai)xy=

½1 if(x, y)∈Ri

0 otherwise (x, y∈X).

* This research was partially supported by the Grant-in-Aid for Scientific Research (No.06640075, No. 09640062), the Ministry of Education, Science and Culture, Japan.

From(i)−(iv)above, it is easy to see the following.

(i)⁰ A0=I.

(ii)⁰ A0+A1+· · ·+Ad =J, whereJ is the all-1s matrix, andAi◦Aj =δi,jAi for 0≤i, j≤d, where◦denotes the entry-wise matrix product.

(iii)^{0 t}Ai=Aifor0≤i≤d.

(iv)⁰ AiAj = Xd

h=0

p^h_i,jAhfor0≤i, j≤d.

By the Bose-Mesner algebra ofXwe mean the subalgebraMofMatX(R)generated by the adjacency matricesA0, A1, . . . , Ad. Observe by(iv)⁰above that the adjacency matrices form a basis forM. Moreover,Mconsists of symmetric matrices and it is closed under◦. In particular,Mis commutative in both multiplications.

Since the algebraMconsists of commutative symmetric matrices, there is a second basis E₀, E₁, . . . , E_dsatisfying the following.

(i)⁰⁰ E₀= 1

|X|J.

(ii)⁰⁰ E₀+E₁+· · ·+E_d=I, andE_iE_j=δ_i,jE_ifor0≤i, j≤d.

(iii)^{00 t}Ei=Eifor0≤i≤d.

(iv)⁰⁰ Ei◦Ej = 1

|X| Xd

h=0

q^h_i,jEh,(0≤i, j≤d)for some real numbersq^h_i,j.

E₀, E₁, . . . , E_dare the primitive idempotents of the Bose-Mesner algebra. The parameters q^h_i,jare called Krein parameters or dual intersection numbers.

Conventionally, we assumep^h_i,jandq_i,j^h are zero if one of the indicesh, i, jis out of range {0,1, . . . , d}otherwise mentioned clearly.

A symmetric association scheme X = (X,{R_i}0≤i≤d) with respect to the ordering R₀, R₁, . . . , R_dof the relations is called aP-polynomial association scheme if the following conditions are satisfied.

(P1) p^h_i,j= 0if one ofh, i, jis greater than the sum of the other two.

(P2) p^h_i,j6= 0if one ofh, i, jis equal to the sum of the other two for0≤h, i, j≤d.

In this case we writec_i=pⁱ_i−1,1,a_i=pⁱ_i,1,b_i =pⁱ_i+1,1andk_i=p⁰_i,ifori= 0,1, . . . , d.

A symmetric association scheme X = (X,{R_i}0≤i≤d) with respect to the ordering E₀, E₁, . . . , E_d of the primitive idempotents of the Bose-Mesner algebra is called aQ- polynomial association scheme if the following conditions are satisfied.

(Q1) q^h_i,j= 0if one ofh, i, jis greater than the sum of the other two.

(Q2) q^h_i,j6= 0if one ofh, i, jis equal to the sum of the other two for0≤h, i, j≤d.

In this case we writec^∗_i =qⁱ_i−1,1,a^∗_i =q_i,1ⁱ ,b^∗_i =qⁱ_i+1,1andk_i^∗=q_i,i⁰ fori= 0,1, . . . , d.

IfX = (X,{Ri}0≤i≤d)is aP-polynomial association scheme with respect to the ordering R0, R1, . . . , Rd, then the graphΓ = (X, R1)with vertex setX, edge set defined byR1

becomes a distance-regular graph. In this case,

R_i={(x, y)∈X×X|∂(x, y) =i},

where∂(x, y)denotes the distance betweenxandy. Conversely, every distance-regular graph is obtained in this way.

Q-polynomial association schemes appear in design theory in connection with tight condi- tions, but it is not much studied compared withP-polynomial association schemes, though there are extensive studies ofP- andQ-polynomial association schemes.

Recently the author studied imprimitiveQ-polynomial association schemes and showed in [9] that ifd > 6andk₁^∗ >2, then imprimitiveQ-polynomial association schemes are either dual bipartite or dual antipodal, i.e., dual intersection numbers satisfy eithera^∗_i = 0 for alli, orb^∗_i =c^∗_d−ifor alli6= [d/2]. This is a continuation of the study ofQ-polynomial association schemes.

As is well known, the Bose-Mesner algebra of a symmetric association scheme be- comes a so-called C-algebra and satisfies Kawada-Delsarte duality, and by this duality Q-polynomial association schemes correspond to P-polynomial association schemes in

‘algebraic level’. On the other hand, the combinatorial properties of association schemes can be easily seen as those of distance-regular graphs forP-polynomial association schemes but theQ-polynomial property is not well understood. See [10, 11].

Some of the properties of P-polynomial association schemes are expected to hold in Q-polynomial association schemes as dual. But it is also true that some of the properties such as the unimodal property ofith valenciesk_i’s do not hold fork_i^∗’s inQ-polynomial association schemes. Until recently, there was no break through to replace the parametrical conditions obtained by combinatorial argument in distance-regular graphs by something in Q-polynomial association schemes.

Recently, Garth A. Dickie proved the following:

LetX = (X,{R_i}0≤i≤d)be aQ-polynomial association scheme. Then for eachi with0< i < d,qⁱ_1,i= 0implies thatq¹_1,1= 0.

The corresponding result forP-polynomial association scheme is easily shown by a simple combinatorial argument. Dickie substituted that part by matrix identities in [6], which is a part of [5, Chapter 4]. In [9], the author generalized Dickie’s result and obtained Proposition 2 and Corollary 1, which played the key roles in the proof of the main theorem in it.

In this paper, we prepare another identity using matrix identities to treat the problem to determine association schemes with multipleQ-polynomial structures.

The following is our main result in this paper.

Theorem 1 LetX = (X,{R_i}0≤i≤d)withk^∗₁>2be aQ-polynomial association scheme with respect to the orderingE₀, E₁, . . . , E_dof the primitive idempotents.

(1) SupposeX isQ-polynomial with respect to another ordering. Then the new ordering is one of the following:

(I) E₀, E₂, E₄, E₆, . . . , E₅, E₃, E₁,

(II) E₀, E_d, E₁, E_d−1, E₂, E_d−2, E₃, E_d−3, . . .,

(III) E0, Ed, E2, Ed−2, E4, Ed−4, . . . , Ed−5, E5, Ed−3, E3, Ed−1, E1, (IV) E₀, E_d−1, E₂, E_d−3, E₄, E_d−5, . . . , E₅, E_d−4, E₃, E_d−2, E₁, E_d, or

(V) d= 5andE₀, E₅, E₃, E₂, E₄, E₁.

(2) Xhas at most twoQ-polynomial structures.

It is well known thatQ-polynomial association schemes withk₁^∗= 2are the association schemes attached to ordinaryn-gons as distance-regular graphs. We also give parametrical conditions in each of the cases in the theorem above. See Theorem 2. Association schemes with multipleP-polynomial structures were studied by Eiichi Bannai and Etsuko Bannai in [1], see also [2, 3, 7]. On the other hand, the corresponding problem forQ-polynomial association schemes was raised by Eiichi Bannai and Tatsuro Ito in [2, Sections III.4, III.7]

in connection with the integrality condition of the eigenvalues ofP- andQ-polynomial association schemes. In his thesis [5], Garth A. Dickie classifiedP-polynomial association schemes with multipleQ-polynomial structures. Our result in this paper is a generalization of a part of his result and actually it can substitute a part of his proof. It is worth noting that Dickie’s proof uses the additional conditionP-polynomial property fully. He proves first that the association schemes in question is thin in Terwilliger’s terminology. This part can be seen without difficulty as a corollary of our result.

The author believes thatP-polynomial association schemes andQ-polynomial association schemes share many more properties which cannot be seen atC-algebra level. That means we may be able to expect higher duality between these types of schemes. On the other hand, each of these classes of association schemes should be studied separately to understand their peculiarity. Just as the graph theoretical arguments developed in distance-regular graphs have successfully applied in the study of association schemes, the representation theory in Q-polynomial association schemes should shed light from different direction.

2. Basic Properties ofQ-polynomial Schemes

In this section, we collect the properties of Krein parametersq^h_i,j which are derived al- gebraically from the conditions of P-polynomial C-algebra with nonnegative structure constants. See the definitions and the proofs in [9].

Lemma 1 LetX = (X,{R_i}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE₀, E₁, . . . , E_dof primitive idempotents. Letk_i^∗=q_i,i⁰ . Then the following hold.

(1) q^h_i+1,jc^∗_i+1 =q^h_i,j−1b^∗_j−1+q_i,j^h (a^∗_j−a^∗_i) +q^h_i,j+1c^∗_j+1−q^h_i−1,jb^∗_i−1.

(2) k^∗_hq_i,j^h =k^∗_iqⁱ_j,handk^∗_i >0fori= 0,1, . . . , d. In particular,q^h_i,j 6= 0if and only if qⁱ_j,h6= 0.

(3) q^i+h_i,h+1c^∗_h+1=q_i,h^i+h(a^∗_i +· · ·+a^∗_i+h−a^∗₁− · · · −a^∗_h).

Well known Krein condition asserts that Krein parametersq_i,j^h are all nonnegative, and we can derive some more properties of them using this condition.

Lemma 2 LetX = (X,{Ri}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE₀, E₁, . . . , E_dof primitive idempotents. Thenq^h_i,j≥0for all0≤h, i, j≤d and the following hold.

(1) Ifq_i+1,j^h ₋₁=q^h_i+1,j =q_i+1,j+1^h = 0for0≤i < d, thenq^h_i,j=q^h_i+2,j = 0.

(2) If q^h_l,j−l+i = q_l,j−l+i+1^h = · · · = q^h_l,j+l−i = 0for i ≤ l and 0 ≤ i < d, then q^h_i,j=q_2l^h_−i,j = 0.

(3) For alli, jwith0≤i, h, i+h≤d,a^∗_i =a^∗_i+1=· · ·=a^∗_i+h= 0impliesa^∗₁=· · ·= a^∗_h= 0.

(4) For allhandiwith0≤h, i, i+h≤d, the following hold.

(i) Ifq_i,i+h−1^h = 0, thena^∗_i ≤a^∗_i+h. Moreover ifa^∗_i =a^∗_i+h, thenq_i+1,i+h^h = 0.

(ii) Ifq_i+1,i+h^h = 0, thena^∗_i ≥a^∗_i+h. Moreover ifa^∗_i =a^∗_i+h, thenq_i,i+h^h ₋₁= 0.

(iii) Ifq_i,i+h−1^h =q_i+1,i+h^h = 0, thena^∗_i =a^∗_i+h. (5) For allhandiwith0≤i≤h≤d, the following hold.

(i) Ifq_i,h−i+1^h = 0, thena^∗_i ≤a^∗_h−i. Moreover ifa^∗_i =a^∗_h−i, thenq_i+1,h−i^h = 0.

(ii) Ifq_i+1,h^h _−i= 0, thena^∗_i ≥a^∗_h−i. Moreover ifa^∗_i =a^∗_h−i, thenq_i,h^h _−i+1= 0.

(iii) Ifq_i,h^h _−i+1=q_i+1,h^h _−i = 0, thena^∗_i =a^∗_h−i.

3. New Conditions on Krein Parameters

Only a few restrictions of the Krein parametersq_i,j^h of symmetric association schemes are known except those derived algebraically using Lemma 1 or Krein conditions in Lemma 2.

We list other restrictions on Krein parameters. The first one is shown in [4]. See also [2, Theorem 2.3.8, Proposition 2.8.3]. This is the key to connect the conditions on Krein parameters with representations or matrix identities. Actually, all the rest follow from this identity.

Proposition 1 Let X = (X,{Ri}0≤i≤d) be a symmetric association scheme. Let E0, E1, . . . , Ed be primitive idempotents and letq^h_i,jbe the Krein parameters. Then for 0≤h, i, j ≤d, we have

q_i,j^h = 0⇔ X

u∈X

(Eh)ux(Ei)uy(Ej)uz= 0for allx, y, z∈X.

The following three results are proved in [9]. Proposition 2 is shown by Lemma 3 and Corollary 1 is a direct consequence of Proposition 2.

Lemma 3 LetX = (X,{R_i}0≤i≤d)be a symmetric association scheme. Let

E0, E1, . . . , Ed be primitive idempotents and letq^h_i,j be the Krein parameters. Suppose {i |q_j,kⁱ qⁱ_l,m 6= 0} ⊂ {h}. Then for all integers0 ≤h, i, j, k, l, m ≤dand the vertices a, a⁰, b, b⁰, the following hold.

(1) X

e∈X

(Ej)ea(Ek)ea⁰(El)eb(Em)eb=q_l,m^h

|X| X

e∈X

(Ej)ea(Ek)ea⁰(Eh)eb.

(2) X

e∈X

(E_j)_ea(E_k)_ea0(E_l)_eb(E_m)_eb0 = X

e,e⁰∈X

(E_j)_ea(E_k)_ea0(E_h)_ee0(E_l)_e0b(E_m)_e0b⁰.

Proposition 2 Let X = (X,{R_i}0≤i≤d) be a Q-polynomial association scheme with respect to the orderingE0, E1, . . . , Edof primitive idempotents. Suppose that

{l|q^l_j,h+iq^l_i−j,h+j 6= 0} ⊂ {h+i−j}.

Then forh≥0,i≥j ≥1withh+i+j≤d,q_i,h+j^h+i = 0 implies that q_j,h+j^h+j = 0.

Corollary 1 LetX = (X,{R_i}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE₀, E₁, . . . , E_dof primitive idempotents.

(1) Forh≥0,i≥1withh+i+ 1≤d,

q_i,h+1^h+i =q^h+i_1,h+i= 0 implies that q_1,h+1^h+1 = 0.

(2) Forh≥0,i≥2withh+i+ 2≤d,

q_i,h+2^h+i =q_2,h+i^h+i =q^h+i_2,h+i−1= 0 implies that q^h+2_2,h+2= 0.

By settingh = 0 in Corollary 1, we have the main result in [6], i.e.,a^∗_i = 0implies a^∗₁= 0for all1≤i≤d−1.

We give another application of the matrix identities, which gives a basic tool to handle Krein parameters of association schemes.

Proposition 3 LetX = (X,{R_i}0≤i≤d)be a symmetric association scheme. Suppose the following.

(1){t|q^t_i,kq^t_h,m6= 0} ⊂ {l}, (2){t|q^t_j,kq_h,l^t 6= 0} ⊂ {m}.

Thenq_i,j^h 6= 0implies thatq_k,lⁱ =q_k,m^j .

Proof: LetX(h, i, j, k, l, m)be the following sum.

X

w,x,y,z∈X

(Eh)w,x(Ei)w,y(Ej)w,z(Ek)y,z(El)x,y(Em)x,z.

We evaluateX(h, i, j, k, l, m)using Lemma 3 under our assumption.

Rearranging first the order of the product and apply Lemma 3(2)by our assumption(1), we have the following.

X(h, i, j, k, l, m)

= X

w,z∈X

(E_j)_w,z X

x,y∈X

(E_i)_y,w(E_k)_y,z(E_l)_y,x(E_h)_x,w(E_m)_x,z

= X

w,z∈X

(E_j)_w,zX

x∈X

(E_i)_x,w(E_k)_x,z(E_h)_x,w(E_m)_x,z

= X

w,x∈X

(E_i)_x,w(E_h)_x,wX

z∈X

(E_k)_x,z(E_m)_x,z(E_j)_w,z

= X

w,x∈X

(E_i)_x,w(E_h)_x,wX

z∈X

(E_k◦E_m)_x,z(E_j)_z,w

= X

w,x∈X

(E_i)_x,w(E_h)_x,w((E_k◦E_m)E_j)_x,w

= q^j_k,m

|X| X

w,x∈X

(E_i)_x,w(E_h)_x,w(E_j)_x,w

= q^j_k,m

|X| X

w∈X

X

x∈X

(E_i◦E_j)_w,x(E_h)_x,w

= q^j_k,m

|X|

X

w∈X

((Ei◦Ej)Eh)w,w

= q^j_k,m

|X|

q_i,j^h

|X| X

w∈X

(E_h)_w,w

= q^j_k,mq_i,j^h

|X|² k^∗_h.

Now by symmetry we swapiwithj, andlwithmto obtain the following.

X(h, i, j, k, l, m) =qⁱ_k,lq_i,j^h

|X|² k^∗_h. Therefore ifq_i,j^h 6= 0, we haveq_k,lⁱ =q^j_k,mas desired.

Corollary 2 LetX = (X,{Ri}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE0, E1, . . . , Ed of primitive idempotents. Ifq_i,j^h 6= 0, then the following hold.

(1) Ifq_i−1,j^h =q_i−1,j−1^h =q^h_i,j+1=q_i+1,j+1^h = 0, thenc^∗_i =b^∗_j.

(2) Ifq_i^h_−1,j =q_i^h_−1,j+1=q^h_i,j−1=q_i+1,j^h ₋₁= 0, thenc^∗_i =c^∗_j.

(3) Ifq_i^h_−1,j+1=q^h_i,j+1=q_i+1,j^h ₋₁=q_i+1,j^h = 0, thenb^∗_i =b^∗_j.

Proof: It is easy to check each of the following.

(1) {t|q_i,1^t q_h,j+1^t 6= 0} ⊂ {i−1}, and{t|q^t_j,1q_h,i−1^t 6= 0} ⊂ {j+ 1}. (2) {t|q_i,1^t q_h,j^t ₋₁6= 0} ⊂ {i−1}, and{t|q^t_j,1q^t_h,i−16= 0} ⊂ {j−1}. (3) {t|q_i,1^t q_h,j+1^t 6= 0} ⊂ {i+ 1}, and{t|q^t_j,1q_h,i+1^t 6= 0} ⊂ {j+ 1}. Hence we have the assertions as direct consequences of the previous proposition.

Corollary 3 LetX = (X,{Ri}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE₀, E₁, . . . , E_dof primitive idempotents. Ifk^∗₁>2, then the following hold.

(1) Ifq_2,h^h =q_1,h^h =q_2,h−1^h = 0with2≤h≤d, thenh=d.

(2) Ifq_2,h^h =q_1,h^h =q_2,h+1^h = 0with2≤h≤d, thenh=d.

Proof: (1)By Corollary 2,b^∗₁=c^∗_h−1,c^∗₁=c^∗_h+1. Supposeh < d. Thenq_h+1,h² ₋₁6= 0 andq²_h,h−1 = q_h,h² = 0by our assumption. Hence by Corollary 2,c^∗_h+1 = c^∗_h−1. Thus b^∗₁=c^∗₁= 1. This impliesk₁^∗= 2, becausea^∗_h=q^h_1,h= 0impliesa^∗₁= 0by Corollary 1.

This is not the case. Thereforeh=d.

(2)In this case, we haveb^∗₁ =b^∗_h+1andc^∗₁ =b^∗_h−1. Similarly, ifh < d, then we have b^∗_h+1=b^∗_h−1andk₁^∗= 2. This is a contradiction.

4. MultipleQ-polynomial Structures

In this section and the next, we prove the following result. It is obvious that Theorem 1 is a direct consequence of it.

Theorem 2 LetX = (X,{R_i}0≤i≤d)withk^∗₁>2be aQ-polynomial association scheme with respect to the orderingE₀, E₁, . . . , E_dof the primitive idempotents.

(1) SupposeX isQ-polynomial with respect to another ordering. Then the new ordering is one of the following:

(I) E₀, E₂, E₄, E₆, . . . , E₅, E₃, E₁,

(II) E₀, E_d, E₁, E_d−1, E₂, E_d−2, E₃, E_d−3, . . .,

(III) E0, Ed, E2, Ed−2, E4, Ed−4, . . . , Ed−5, E5, Ed−3, E3, Ed−1, E1, (IV) E0, Ed−1, E2, Ed−3, E4, Ed−5, . . . , E5, Ed−4, E3, Ed−2, E1, Ed, or

(V) d= 5andE₀, E₅, E₃, E₂, E₄, E₁.

(2) Letq_i,j^h be the Krein parameters with respect to the original ordering. Supposed≥3.

Then,

(I) holds if and only ifq_1,1¹ =· · ·=q_1,d−1^d−1 = 06=q_1,d^d . (II) holds if and only ifq_1,d^d 6= 0 =q^d_2,d=· · ·=q_d,d^d . (III) holds if and only if one of the following holds:

(i) d= 3, andq_1,3³ = 06=q_2,3³ ,

(ii) d= 4,q_1,4⁴ =q⁴_3,4= 0, andq⁴_2,46= 06=q⁴_2,3, or

(iii) d≥5,q_2,d^d 6= 0 =q_1,d^d =q^d_3,d=· · ·=q^d_d,d. Moreover ifd= 2e−1, then q_1,j^j 6= 0impliesj=eand ifd= 2e, thenq^j_1,j 6= 0if and only ifj=e, e+ 1.

(IV) holds if and only if one of the following holds:

(i) d= 3,q_1,2² 6= 0 =q_3,2² , or

(ii) d≥4,q_2,d^d−1 =· · · =q^d−1_d,d = 0. Moreover, ifd= 2e, thenq_1,j^j 6= 0implies j=eand ifd= 2e+ 1, thenq_1,j^j 6= 0if and only ifj=e, e+ 1.

(V) holds if and only ifq_1,5⁵ =q_2,5⁵ =q⁵_4,5=q⁵_5,5= 06=q⁵_3,5andq⁵_3,4= 0.

(3) Xhas at most twoQ-polynomial structures.

Before we start the proof, we prepare some lemmas to illustrate the structures ofQ- polynomial association schemes appeared in the theorem above.

Lemma 4 LetX = (X,{R_i}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE₀, E₁, . . . , E_dof primitive idempotents. For3 ≤m≤d, the following are equivalent.

(1) a^∗₁=a^∗₂=· · ·=a^∗_m−1= 06=a^∗_m.

(2) q²_1,2=q_2,3² =· · ·=q²_m−2,m−1= 06=q²_m−1,m.

Proof: Suppose(1)holds. Sincem ≥3,a^∗₂ =q_1,2² = 0. Now by induction, we have q²_i,i+1 = 0for i = 1,2, . . . , m−2from Lemma 2(4)(i). Moreover q_m−1,m² 6= 0by Lemma 2(4)(iii).

Conversely, suppose(2). Then by Corollary 1(1),a^∗₁= 0asd≥3. Now we have(1) by Lemma 2(4)(i),(iii).

Lemma 5 LetX = (X,{Ri}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE0, E1, . . . , Edof primitive idempotents. Suppose

q_1,d^d 6= 0 =q^d_2,d=· · ·=q_d,d^d . Then the following hold.

(1) For0≤i, j≤d,q^d_i,j6= 0if and only if0≤i+j−d≤1.

(2) If, in addition,q¹_1,1=· · ·=q^d_1,d⁻¹₋₁= 06=q^d_1,d, thenk^∗₁= 2.

Proof: (1)This is a direct consequence of Lemma 2(2).

(2)We first observe the following:

1. q^d_i,d−i6= 0fori= 1, . . . , d−1,{t|q^t_i,1q_d,d^t _−i+16= 0} ⊂ {i−1}and {t|q^t_d−i,1q^t_d,i−16= 0} ⊂ {d−i+ 1}.

2. q^d_i+1,d−i6= 0fori= 1, . . . , d−1,{t|q_i+1,1^t q_d,d^t _−i+16= 0} ⊂ {i}and {t|q^t_d−i,1q^t_d,i6= 0} ⊂ {d−i+ 1}.

Now we apply Proposition 3. We obtainc^∗_i =b^∗_d−ifori= 1, . . . , d−1from the first set of conditions, andc^∗_i+1=b^∗_d−ifori= 1, . . . , d−1from the second set of conditions. Thus

1 =c^∗₁=b^∗_d−1=c^∗₂=b^∗_d−2=· · ·=c^∗_d−1=b^∗₁=c^∗_d.

Sincea^∗₁= 0, we havek^∗₁=c^∗₁+a^∗₁+b^∗₁= 2as desired.

Lemma 6 LetX = (X,{Ri}0≤i≤d)be aQ-polynomial association scheme with respect to the orderingE0, E1, . . . , Edof primitive idempotents. Suppose

q^d_2,d⁻¹=· · ·=q^d_d,d⁻¹= 0.

Then the following hold.

(1) For0≤i, j≤d,q_i,j^d−16= 0only if0≤i+j−(d−1)≤2. Moreover, ifi+j−(d−1)∈ {0,2},q^d_i,j⁻¹6= 0.

(2) Supposed≥3. Then, for0≤i, j≤d,q_i,j^d 6= 0if and only ifi+j=d.

(3) Ifd≥3, thenb^∗_i =c^∗_d−ifori= 0,1, . . . , d, i.e.,Xis dual antipodal2-cover.

Proof: (1)This is a direct consequence of Lemma 2(2).

(2)By the assumption,q_2,d^d ₋₁=· · ·=q_d,d^d ₋₁ = 0. Sinced≥3,q_d^d_−1,d−1=q^d_d−1,d= 0. Henceq^d_d,d= 0, by Lemma 2(1). Now by induction oniin reverse order,q^d_i,d= 0for 1≤i≤d, asq^d_i+1,d=q_i+1,d−1^d = 0.

(3)By(2), we can apply Corollary 2(1)by settingh=d,j=d−ifori= 0,1, . . . , d.

From now on assume the following:

X = (X,{Ri}0≤i≤d)is aQ-polynomial association scheme with respect to the ordering E0, E1, . . . , Ed of the primitive idempotents. Let q^h_i,j’s (and c^∗_i’s, a^∗_i’s, b^∗_i’s) be Krein parameters or dual intersection numbers with respect to this ordering of the primitive idempotents. Supposek^∗₁>2.

Let∆ = ∆^(h)be a graph on the vertex setV∆ ={0,1, . . . , d}such thatiis adjacent to j, ori ∼j, if and only ifq^h_i,j 6= 0. Hence for this particular graph, we allow loops. Let

∂(i, j)denote the distance betweeniandjin this graph and∆_l(i) ={j|∂(i, j) =l}. Let

∆(i) = ∆₁(i), and∆^∗(i) = ∆(i)− {i}.

It is easy to see that∆^(h)is a path graph, if and only ifXisQ-polynomial with respect to the orderingE0, Eh, . . .of the primitive idempotents. Here by a path graph we mean a path which may include some loops.

We prove Theorem 2 in a series of lemmas. In Lemma 7, we check that if the parameters satisfy one of the conditions in(2)thenXisQ-polynomial with respect to the corresponding ordering. In Lemma 8, we show(3) assuming that (1) and(2) are valid. In the next section we show the main part, i.e., ifXhas differentQ-polynomial ordering of primitive idempotents then the ordering is the one listed in(1)and the parameters satisfy the conditions in(2).

Lemma 7 If Krein parametersq^h_i,j’s satisfy the conditions of one of the cases in Theorem 2 (2), thenX isQ-polynomial with respect to the corresponding ordering.

Proof: It suffices to show that the graph∆ = ∆^(h)is a path graph, whereh= 2in(I), h=din(II),(III),h=d−1in(IV), andh= 5in(V).

Suppose the condition in(I)holds, i.e.,q¹_1,1 = · · · = q_1,d−1^d−1 = 0 6= q^d_1,d. Then by Lemma 4, we have that

q_1,2² =q²_2,3=· · ·=q_d²_−2,d−1= 06=q_d²_−1,d.

Sinceq_i,i+2² 6= 0fori= 0,1, . . . , d−2, we have∆^∗(i) ={i−2, i+2}fori= 2, . . . , d−2,

∆^∗(d−1) ={d−3, d}and∆^∗(d) ={d−2, d−1}. Therefore, it is easy to check that

∆ = ∆⁽²⁾is a path graph

0∼2∼4∼6∼ · · · ∼5∼3∼1.

Suppose the condition in(II)holds. Then by Lemma 5(1)we have thatq_i,j^d 6= 0if and only if0≤i+j−d≤1. It is easy to check that∆is a path graph

0∼d∼1∼d−1∼2∼d−2∼3∼d−3∼ · · ·.

Suppose the condition in(III)holds. The assertions are easily checked for the cases d <5from the conditions in(i),(ii). Supposed≥5. Then by Lemma 2(2),q_i,j^d = 0if i+j−d >2andq_i,j^d 6= 0ifi+j−d= 2for0≤i, j≤d. The additional conditions on q^j_1,j’s imply the following by Lemma 2(5)(i)and(iii).

1. Ifd= 2e−1, thenq_i,d−i+1^d 6= 0implies thati=e.

2. Ifd= 2e, thenq_i,d−i+1^d 6= 0if and only ifi∈ {e, e+ 1}. Now it is easy to check that∆is a path graph

0∼d∼2∼d−2∼4∼d−4∼ · · · ∼d−5∼5∼d−3∼3∼d−1∼1.

Suppose the condition in(IV)holds. The assertion is trivial ifd= 3. Supposed≥4.

Then by Lemma 6(1),q^d_i,j⁻¹ = 0ifi+j > d+ 1andq_i,j^d−1 6= 0ifi+j = d+ 1for 0≤i, j ≤d. The additional conditions onq_1,j^j ’s imply the following by Lemma 2(5)(i) and(iii).

1. Ifd= 2e, thenq_i,d−i^d−1 6= 0implies thati=e.

2. Ifd= 2e+ 1, thenq_i,d^d−₋¹_i 6= 0if and only ifi∈ {e, e+ 1}. Now it is easy to check that∆is a path graph

0∼d−1∼2∼d−3∼4∼d−5∼ · · · ∼5∼d−4∼3∼d−2∼1∼d.

Finally if the condition in(V)holds, then∆is a path graph 0∼5∼3∼2∼4∼1.

Note that q_2,4⁵ 6= 0 follows from Lemma 2 (1) as q_3,5⁵ 6= 0 while q_2,6⁵ = q_2,5⁵ = 0.

Lemma 8 X has at most twoQ-polynomial structures.

Proof: It suffices to show that no two of the sets of parametrical conditions of Theorem 2 (2)hold simultaneously. We may assumed≥3.

Suppose(I)holds. Thena^∗₁ =· · ·=a^∗_d−1 = 06=a^∗_d. Sincea^∗_d 6= 0anda^∗₂ = 0, the only possible case is(II). Now by Lemma 5(2), we havek^∗₁ = 2, which contradicts our assumption.

Suppose(II)holds. Thena^∗_d 6= 0andq³_2,2 6= 0ifd= 3by Lemma 5(1). Hence none of the other cases can occur.

Suppose(III)holds. Ifd = 3, thenq_1,3³ = 0 6= q_2,3³ . Hence if(IV)holds as well, q³_2,2= 0. By Lemma 1(1)withh= 3, i= 3, j = 2, we haveq_3,2³ a^∗₂+q_3,3³ c^∗₃= 0. Thus a^∗₂=q_1,2² = 0, which is not the case in(IV). Ifd≥4, thenq_2,d^d 6= 0. Hence(V)cannot occur.(IV)does not occur either, asXis dual antipodal 2-cover by Lemma 6.

(IV)and(V)cannot occur simultaneously, asq_3,5⁵ 6= 0in the case(V), whileq_3,5⁵ = 0 in the case(IV)as it is dual antipodal 2-cover.

ThereforeXhas at most twoQ-polynomial structures.

5. Proof of Main Theorem

SupposeX = (X,{Ri}0≤i≤d)has anotherQ-polynomial structure, i.e.,XisQ-polynomial with respect to another orderingE0, Ei1, Ei2, . . . , Eid of primitive idempotents. Just to simplify the notation, leti1 = h, andi2 = i. We may assume thatd > 2andh > 1.

We determine the order 0, i1, i2, . . . and the conditions ofq^h_l,m’s in the following. Let

∆ = ∆^(h). By our assumption,∆is a path graph. One of the keys is that for eachlwith 1≤l≤d,|∆(l)| ≤3or|∆^∗(l)| ≤2.

In Lemma 9, we show that the first member in the new orderingh= 2,d−1ord. In Lemma 10, we treat the case whenh = 2and show that we have(I)or(IV)(i)in the theorem. Lemma 11 is for the case whenh=d−1and we show that(IV)occurs. The case whenh = drequires a little more work. In Lemma 12, we determine the second memberiin the new ordering to showi= 1or2with an exception when we have(V). In Lemmas 13 and 14, we determine the case wheni= 1and2respectively by showing that we have either the case(II)or(III)respectively.