Graphs and Combinatorics (2018) 34:863–877 https://doi.org/10.1007/s00373-018-1917-5 ORIGINAL PAPER

A Characterization of Q-Polynomial Distance-Regular Graphs Using the Intersection Numbers Supalak Sumalroj1 Received: 6 July 2017 / Revised: 3 June 2018 / Published online: 23 June 2018 © Springer Japan KK, part of Springer Nature 2018

Abstract We consider a primitive distance-regular graph Γ with diameter at least 3. We use the intersection numbers of Γ to find a positive semidefinite matrix G with integer entries. We show that G has determinant zero if and only if Γ is Q-polynomial. Keywords Distance-regular graph · Q-polynomial Mathematics Subject Classification 05E30

1 Introduction Let Γ denote a distance-regular graph with diameter D ≥ 3. In the literature there are a number of characterizations for the Q-polynomial condition on Γ . There is the balanced set characterization [7, Theorem 1.1], [8, Theorem 3.3]. There is a characterization involving the dual distance matrices [8, Theorem 3.3]. There is a characterization involving the intersection numbers ai [6, Theorem 3.8]; cf. [2, Theorem 5.1]. There is a characterization involving a tail in a representation diagram [3, Theorem 1.1]. There is a characterization involving a pair of primitive idempotents [4, Theorem 1.1]; cf. [5, Theorem 1.1]. In this paper we obtain the following characterization of the Q-polynomial property. Assume Γ is primitive. We use the intersection numbers of Γ to find a positive semidefinite matrix G with integer entries. We show that G has determinant zero if and only if Γ is Q-polynomial. Our main result is Theorem 2.

Electronic supplementary material The online version of this article (https://doi.org/10.1007/s00373018-1917-5) contains supplementary material, which is available to authorized users.

B 1

Supalak Sumalroj [email protected] Nakhon Pathom Rajabhat University, Nakhon Pathom, Thailand

123

864

Graphs and Combinatorics (2018) 34:863–877

2 Preliminaries Let X denote a nonempty finite set. Let Mat X (C) denote the C-algebra consisting of the matrices whose rows and columns are indexed by X and whose entries are in C. When X = {0, 1, . . . , D}, we use the notation Mat D+1 (C) = Mat X (C). For B ∈ Mat X (C) let B and B t denote the complex conjugate and the transpose of B, respectively. Let V = C X denote the vector space over C consisting of column vectors with coordinates indexed by X and entries in C. Observe that Mat X (C) acts on V by left multiplication. We endow V with the Hermitean inner product ( , ) such that (u, v) = u t v for all u, v ∈ V . The inner product ( , ) is positive definite. For B ∈ Mat X (C) we obtain t (u, Bv) = (B u, v) for all u, v ∈ V . We endow Mat X (C) with the Hermitean inner product  ,  such that R, S = tr (R t S) for all R, S ∈ Mat X (C). The inner product  ,  is positive definite. Let Γ = (X , R) denote a finite, undirected, connected graph, without loops or multiple edges, with vertex set X and edge set R. Let ∂ denote the shortest pathlength distance function for Γ . Define the diameter D := max{∂(x, y)|x, y ∈ X }. For a vertex x ∈ X and an integer i ≥ 0 define Γi (x) = {y ∈ X |∂(x, y) = i}. For notational convenience abbreviate Γ (x) = Γ1 (x). For an integer k ≥ 0, we call the graph Γ regular with valency k whenever |Γ (x)| = k for all x ∈ X . We say that Γ is distance-regular whenever for all integers h, i, j (0 ≤ h, i, j ≤ D) and for all x, y ∈ X with ∂(x, y) = h, the number pihj := |Γi (x) ∩ Γ j (y)| is independent of x and y. The integers pihj are called the intersection numbers of Γ . From now on we assume Γ is distance-regular with diameter D ≥ 3. We abbreviate i i (0 ≤ i ≤ D), b := p i (1 ≤ i ≤ D), ai := p1i ci := p1,i−1 i 1,i+1 (0 ≤ i ≤ D − 1), 0 ki := pii (0 ≤ i ≤ D), and c0 = 0, b D = 0. Observe that Γ is regular with valency k = b0 and ci + ai + bi = k (0 ≤ i ≤ D). By [1, p. 127] the following holds for 0 ≤ h, i, j ≤ D: (i) pihj = 0 if one of h, i, j is greater than the sum of the other two; and (ii) pihj = 0 if one of h, i, j equals the sum of the other two. For 0 ≤ i ≤ D, let Ai denote the matrix in Mat X (C) with (x, y)-entry  (Ai )x y =

1 if ∂(x, y) = i, 0 if ∂(x, y) = i,

x, y ∈ X .

We call Ai the i-th distance matrix of Γ . We call A = A1 the adjacency matrix of Γ . Observe that Ai is real and symmetric  D for 0 ≤ i ≤ D. Note that A0 = I , where I Ai = J , where J is the all-ones matrix in is the identity matrix. Observe that i=0 D Mat X (C). Observe that for 0 ≤ i, j ≤ D, Ai A j = h=0 pihj Ah . For integers h, i, j (0 ≤ h, i, j ≤ D) we have

123

Graphs and Combinatorics (2018) 34:863–877

865

p0h j = δh j pi0j pihj

(1)

= δi j ki

(2)

= p hji

kh pihj

=

ki phi j

(3) =

j k j pi h .

(4)

For 0 ≤ i, j ≤ D we have (A Ai )A j = A(Ai A j ). This gives a recursion h−1 h h h ci+1 pi+1, + ah pihj + bh pih+1 j + ai pi j + bi−1 pi−1, j = ch pi j j

(5)

that can be used to compute the intersection numbers. Let M denote the subalgebra of Mat X (C) generated by A. By [1, p. 127] the matrices Γ . By [1, A0 , A1 , . . . , A D form a basis for M. We call M the Bose–Mesner algebra of D Ei = I ; p. 45], M has a basis E 0 , E 1 , . . . , E D such that (i) E 0 = |X |−1 J ; (ii) i=0 (iii) E it = E i (0 ≤ i ≤ D); (iv) E i = E i (0 ≤ i ≤ D); (v) E i E j = δi j E i (0 ≤ i, j ≤ D). The matrices E 0 , E 1 , . . . , E D are called the primitive idempotents of Γ , and E 0 is called the trivial idempotent. For 0 ≤ i ≤ D let m i denote the rank D+1 in C[λ] by v0 = 1, of E i . Let λ denote an indeterminate. Define polynomials {vi }i=0 v1 = λ, and λvi = ci+1 vi+1 + ai vi + bi−1 vi−1 (1 ≤ i ≤ D), where c D+1 := 1. By [1, p. 128] and [9, Lemma 3.8], the following hold: (i) deg vi = i (0 ≤ i ≤ D + 1); (ii) the coefficient of λi in vi is (c1 c2 . . . ci )−1 (0 ≤ i ≤ D + 1); (iii) vi (A) = Ai (0 ≤ i ≤ D); (iv) v D+1 (A) = 0; (v) the distinct eigenvalues of Γ are precisely the zeros of v D+1 ; call these θ0 , θ1 , . . . , θ D . Define a matrix B ∈ Mat D+1 (C) as follows: ⎤ a0 b0 0 ⎥ ⎢ c1 a1 b1 ⎥ ⎢ ⎥ ⎢ .. ⎥. . c a B=⎢ 2 2 ⎥ ⎢ ⎥ ⎢ . . .. .. b ⎦ ⎣ D−1 0 cD aD ⎡

We call B the intersection matrix of Γ . Note that A has the same minimal polynomial as B. Moreover the minimal polynomial of B is the characteristic polynomial of B. For an eigenvalue θ of B we have v B = θ v where v is a row vector D in C[λ] by u = 1, v = (v0 (θ ), v1 (θ ), . . . , v D (θ )). Define polynomials {u i }i=0 0 u 1 = λ/k, and λu i = ci u i−1 + ai u i + bi u i+1 (1 ≤ i ≤ D − 1).

123

866

Graphs and Combinatorics (2018) 34:863–877

Observe that u i = vi /ki (0 ≤ i ≤ D). For an eigenvalue θ of B we have Bu = θ u where u is a column vector u = (u 0 (θ ), u 1 (θ ), . . . , u D (θ ))t . By [1, p. 131, 132], Aj =

D

v j (θi )E i (0 ≤ j ≤ D),

(6)

i=0

E j = |X |

−1

mj

D

u i (θ j )Ai (0 ≤ j ≤ D).

(7)

i=0

Since E i E j = δi j E i and by (6), (7) we have A j E i = E i A j (0 ≤ i, j ≤ D). For 1 ≤ i ≤ D let Γi denote the graph with vertex set X where vertices are adjacent in Γi whenever they are at distance i in Γ . We observe that Γ1 = Γ . The graph Γ is said to be primitive whenever Γi is connected for 1 ≤ i ≤ D. Lemma 1 (See [1, Proposition 4.4.7]) Assume Γ is primitive. Then u i (θ j ) = 1 for 1 ≤ i, j ≤ D. We now define a matrix S ∈ Mat D+1 (C). D Definition 1 Let S ∈ Mat D+1 (C) denote the transition matrix from the basis {Ai }i=0 D of M to the basis {E i }i=0 of M. Thus

Ej =

D

Si j Ai (0 ≤ j ≤ D),

i=0

Aj =

D

(S −1 )i j E i (0 ≤ j ≤ D). i=0

Lemma 2 The entries of S and S −1 are given below. For 0 ≤ i, j ≤ D, Si j = |X |−1 m j u i (θ j ), (S −1 )i j = v j (θi ). Proof Immediate from Definition 1 and (6), (7).



We recall the Q-polynomial property. Let ◦ denote the entry-wise multiplication in Mat X (C). Note that Ai ◦ A j = δi j Ai for 0 ≤ i, j ≤ D. So M is closed under ◦. By [9, p. 377], there exist scalars qihj ∈ C such that E i ◦ E j = |X |

−1

D

qihj E h (0 ≤ i, j ≤ D).

(8)

h=0

We call the qihj the Krein parameters of Γ . By [1, p. 48, 49], these parameters are real and nonnegative for 0 ≤ h, i, j ≤ D. The graph Γ is said to be Q-polynomial with respect to the ordering E 0 , E 1 , . . . , E D whenever the following hold for 0 ≤

123

Graphs and Combinatorics (2018) 34:863–877

867

h, i, j ≤ D: (i) qihj = 0 if one of h, i, j is greater than the sum of the other two; and (ii) qihj = 0 if one of h, i, j equals the sum of the other two. Let E denote a primitive idempotent of Γ . We say that Γ is Q-polynomial with respect to E whenever there exists a Q-polynomial ordering E 0 , E 1 , . . . , E D of the primitive idempotents such that E = E 1 . We recall the dual Bose–Mesner algebra of Γ . Fix a vertex x ∈ X . For 0 ≤ i ≤ D let E i∗ = E i∗ (x) denote the diagonal matrix in Mat X (C) with (y, y)-entry  (E i∗ ) yy

=

1 if ∂(x, y) = i, 0 if ∂(x, y) = i,

y ∈ X.

D E i∗ = We call E i∗ the i-th dual idempotent of Γ with respect to x. Observe that (i) i=0 I ; (ii) E i∗t = E i∗ (0 ≤ i ≤ D); (iii) E i∗ = E i∗ (0 ≤ i ≤ D); (iv) E i∗ E ∗j = δi j E i∗ (0 ≤ i, j ≤ D). By construction E 0∗ , E 1∗ , . . . , E ∗D are linearly independent. Let M ∗ = M ∗ (x) denote the subalgebra of Mat X (C) with basis E 0∗ , E 1∗ , . . . , E ∗D . We call M ∗ the dual Bose–Mesner algebra of Γ with respect to x. We now recall the dual distance matrices of Γ . For 0 ≤ i ≤ D let Ai∗ = Ai∗ (x) denote the diagonal matrix in Mat X (C) with (y, y)-entry (Ai∗ ) yy = |X |(E i )x y y ∈ X .

(9)

We call Ai∗ the dual distance matrix of Γ with respect to x and E i . By [9, p. 379], the matrices A∗0 , A∗1 , . . . , A∗D form a basis for M ∗ . Observe that (i) A∗0 = I ; (ii) D ∗ = |X |E ∗ ; (iii) A∗t = A∗ (0 ≤ i ≤ D); (iv) A∗ = A∗ (0 ≤ i ≤ D); (v) i=0 Ai  0 i i i i D Ai∗ A∗j = h=0 qihj A∗h (0 ≤ i, j ≤ D). From (6) and (7) we have A∗j = m j

D

u i (θ j )E i∗ (0 ≤ j ≤ D),

(10)

i=0

E ∗j = |X |−1

D

v j (θi )Ai∗ (0 ≤ j ≤ D).

(11)

i=0 D of M ∗ to Lemma 3 The matrix |X |S is the transition matrix from the basis {E i∗ }i=0 D of M ∗ . Thus the basis {Ai∗ }i=0

A∗j = |X |

D

Si j E i∗ (0 ≤ j ≤ D),

i=0

E ∗j = |X |−1

D

(S −1 )i j Ai∗ (0 ≤ j ≤ D). i=0

Proof Immediate from Lemma 2 and (10), (11).



123

868

Graphs and Combinatorics (2018) 34:863–877

3 The Matrices Salt , (S−1 )alt , S Recall the matrix S from Definition 1. We now modify the matrices S, S −1 to obtain D × D matrices S alt , (S −1 )alt as follows: (S alt )i j = Si j − S0 j (1 ≤ i, j ≤ D), (S −1 )ialt j

= (S

−1

)i j (1 ≤ i, j ≤ D).

(12) (13)

Lemma 4 The following (i)–(iv) hold. (i) (S −1 )alt and S alt are inverses. D to {A A∗ A − (ii) S alt is the transition matrix from {|X |(A2 E i∗ A − AE i∗ A2 )}i=1 2 i ∗ D A Ai A2 }i=1 . D to {A A∗ − A∗ A } D . (iii) S alt is the transition matrix from {|X |(A3 E i∗ − E i∗ A3 )}i=1 3 i i 3 i=1 ∗ ∗ D D . alt (iv) S is the transition matrix from {|X |(A2 E i − E i A2 )}i=1 to {A2 Ai∗ − Ai∗ A2 }i=1 D to {A A∗ − A∗ A} D . (v) S alt is the transition matrix from {|X |(AE i∗ − E i∗ A)}i=1 i i i=1 Proof (i) By (12) and (13), for 1 ≤ i, j ≤ D (S

alt

(S

−1 alt

) )i j =

D

=1

alt −1 alt Si (S ) j

D

= (Si − S0 )(S −1 ) j =1

= (SS −1 )i j − (SS −1 )0 j = Ii j − I 0 j = Ii j . (ii) For 1 ≤ j ≤ D we write A2 A∗j A − A A∗j A2 in terms D E i∗ = I , we have By Lemma 3 and (12) and since i=0 A2 A∗j A − A A∗j A2 = |X |

D

D . of {A2 E i∗ A − AE i∗ A2 }i=1

(A2 E i∗ A − AE i∗ A2 )Si j

i=0

= |X |(A2 E 0∗ A − AE 0∗ A2 )S0 j + |X | = |X |(A2 (I − (E 1∗ + · · · + E ∗D ))A

D

(A2 E i∗ A − AE i∗ A2 )Si j i=1

− A(I − (E 1∗ + · · · + E ∗D ))A2 )S0 j

+ |X |

D

(A2 E i∗ A − AE i∗ A2 )Si j

i=1

= |X |

D

i=1

123

(A2 E i∗ A − AE i∗ A2 )(Si j − S0 j )

Graphs and Combinatorics (2018) 34:863–877

= |X |

D

869

(A2 E i∗ A − AE i∗ A2 )(S alt )i j .

i=1



(iii)–(v) Similar to the proof of (ii). Define a matrix ⎡ ⎢ S = ⎢ ⎣

S alt

0 S alt S alt

⎤ ⎥ ⎥, ⎦

S alt

0

where S alt is from (12). Observe that S is 4D × 4D. Lemma 5 det(S ) = (det(S alt ))4 . Moreover S is invertible. Proof Immediate from the construction of S .



Corollary 1 The matrix S is the transition matrix from D D {|X |(A2 E i∗ A − AE i∗ A2 )}i=1 , {|X |(A3 E i∗ − E i∗ A3 )}i=1 , D D {|X |(A2 E i∗ − E i∗ A2 )}i=1 , {|X |(AE i∗ − E i∗ A)}i=1

to D D {A2 Ai∗ A − A Ai∗ A2 }i=1 , {A3 Ai∗ − Ai∗ A3 }i=1 , D D {A2 Ai∗ − Ai∗ A2 }i=1 , {A Ai∗ − Ai∗ A}i=1 .

Proof Immediate from Lemma 4.



4 The Bilinear Form  ,  Recall the positive definite Hermitean bilinear form  ,  on Mat X (C). Lemma 6 (See [9, Lemma 3.2]) For 0 ≤ h, i, j, r , s, t ≤ D, (i) E i∗ A j E h∗ , Er∗ As E t∗  = δir δ js δht kh pihj , (ii) E i A∗j E h , Er A∗s E t  = δir δ js δht m h qihj . Corollary 2 (See [9, Lemma 3.2]) For 0 ≤ h, i, j ≤ D, (i) E i∗ A j E h∗ = 0 if and only if pihj = 0, (ii) E i A∗j E h = 0 if and only if qihj = 0. Lemma 7 For 0 ≤ h, i, j, r , s, t ≤ D we have Ai E ∗j Ah , Ar E s∗ At  =

D

   k pir p js pht .

=0

123

870

Graphs and Combinatorics (2018) 34:863–877

D h ∗ ∗ ∗ Proof Since Ai A j = h=0 pi j A h and E i E j = δi j E i (0 ≤ i, j ≤ D) and by Lemma 6(i) and (4), we obtain Ai E ∗j Ah , Ar E s∗ At  = tr ((Ai E ∗j Ah )t (Ar E s∗ At )) = tr (Ah E ∗j Ai Ar E s∗ At ) =

D

 pir tr (Ah E ∗j A E s∗ At )

=0

=

D

 pir tr (E ∗j A E s∗ At Ah )

=0

=

D D



 w pir pht tr (E ∗j A E s∗ Aw )

=0 w=0

=

D

D

 w pir pht tr (E ∗j E ∗j A E s∗ E s∗ Aw )

=0 w=0

=

D D



 w pir pht tr (E ∗j A E s∗ E s∗ Aw E ∗j )

=0 w=0

=

D

D

 w pir pht tr ((E s∗ A E ∗j )t (E s∗ Aw E ∗j ))

=0 w=0

=

D

D

 w pir pht E s∗ A E ∗j , E s∗ Aw E ∗j 

=0 w=0

=

D

D

 w δw pir pht ps k j j

=0 w=0

=

D

   k pir p js pht .

=0

Definition 2 Let G denote the matrix of inner products for A2 E i∗ A − AE i∗ A2 ,

A3 E i∗ − E i∗ A3 ,

A2 E i∗ − E i∗ A2 ,

AE i∗ − E i∗ A,

where 1 ≤ i ≤ D. Thus the matrix G is 4D × 4D. Theorem 1 The entries of G are as follows: For 1 ≤ i, j ≤ D, where φ/2 is a weighted sum involving the following terms and coefficients:

123

Graphs and Combinatorics (2018) 34:863–877

871

, 

A2 E ∗j A − AE ∗j A2

A3 E ∗j − E ∗j A3

A2 E ∗j − E ∗j A2

AE ∗j − E ∗j A

A2 E i∗ A − AE i∗ A2 A3 E i∗ − E i∗ A3 A2 E i∗ − E i∗ A2 AE i∗ − E i∗ A

φ 2k2 b2 ( pi1j − pi2j ) 2k2 a2 ( pi1j − pi2j ) 2k2 c2 ( pi1j − pi2j )

2k2 b2 ( pi1j − pi2j ) 2k3 (δi j ki − pi3j ) 0 0

2k2 a2 ( pi1j − pi2j ) 0 2k2 (δi j ki − pi2j ) 0

2k2 c2 ( pi1j − pi2j ) 0 0 2k(δi j ki − pi1j )

Term

Coefficient

pi0j pi1j pi2j pi3j

kk2 k2 a1 a2 − kb12 k2 (c2 (b1 − 1) − a2 (a1 + 1) + b2 (c3 − 1)) −k3 c32

Proof By Lemma 7 and using (1)–(5), we obtain A2 E i∗ A − AE i∗ A2 , A2 E ∗j A − AE ∗j A2  = A2 E i∗ A, A2 E ∗j A − A2 E i∗ A, AE ∗j A2  − AE i∗ A2 , A2 E ∗j A + AE i∗ A2 , AE ∗j A2  =

D

α α α kα p22 pi j p11 −

α=0

⎛

= 2⎝

D

β

β

β

kβ p21 pi j p12 −

β=0 2

α α α kα p22 pi j p11 −

α=0

D

γ

γ

γ

kγ p12 pi j p21 +

γ =0

3

η

η

η

kη p11 pi j p22

η=0

⎞ β

D

β

kβ ( p12 )2 pi j ⎠

β=1

0 0 0 1 1 1 = 2(k0 p22 pi j p11 + k1 p22 pi j p11 2 2 2 3 2 3 − k2 ( p12 ) pi j − k3 ( p12 ) pi j ) = 2(kk2 pi0j + (k2 a1 a2 − kb12 ) pi1j

2 2 2 1 2 1 + k2 p22 pi j p11 − k1 ( p12 ) pi j

+ k2 (c2 (b1 − 1) − a2 (a1 + 1)

+ b2 (c3 − 1)) pi2j − k3 c32 pi3j ).

(14)

Similarly, for 1 ≤ h ≤ 3, Ah E i∗ − E i∗ Ah , A2 E ∗j A − AE ∗j A2  = Ah E i∗ , A2 E ∗j A − Ah E i∗ , AE ∗j A2  − E i∗ Ah , A2 E ∗j A + E i∗ Ah , AE ∗j A2  = Ah E i∗ A0 , A2 E ∗j A − Ah E i∗ A0 , AE ∗j A2  − A0 E i∗ Ah , A2 E ∗j A + A0 E i∗ Ah , AE ∗j A2  =

D

α=0

α α α kα ph2 pi j p01 −

D

β=0

β

β

β

kβ ph1 pi j p02 −

D

γ =0

γ

γ

γ

kγ p02 pi j ph1 +

D

η

η

η

kη p01 pi j ph2

η=0

1 1 2 2 = 2(kph2 pi j − k2 ph1 pi j )

123

872

Graphs and Combinatorics (2018) 34:863–877 2 1 2 2 = 2(k2 p1h pi j − k2 p1h pi j ) 2 = 2k2 p1h ( pi1j − pi2j ).

(15)

Similarly, for 1 ≤ h,  ≤ 3, Ah E i∗ − E i∗ Ah , A E ∗j − E ∗j A  = Ah E i∗ , A E ∗j  − Ah E i∗ , E ∗j A  − E i∗ Ah , A E ∗j  + E i∗ Ah , E ∗j A  = Ah E i∗ A0 , A E ∗j A0  − Ah E i∗ A0 , A0 E ∗j A  − A0 E i∗ Ah , A E ∗j A0  + A0 E i∗ Ah , A0 E ∗j A  =

D

α α α kα ph pi j p00 −

α=0

= = =

D

β

β

β

kβ ph0 pi j p0 −

β=0

D

γ

γ

γ

kγ p0 pi j ph0 +

γ =0

D

η

η

η

kη p00 pi j ph

η=0

− δh kh pihj ) 2(δh δi j kh ki − δh kh pihj ) 2δh kh (δi j ki − pihj ). 0 0 2(k0 ph pi j

(16)



The result follows. In Appendix 2, we give the matrix G for D = 3. Definition 3 For 1 ≤ i ≤ D let Bi denote the matrix of inner products for A2 Ai∗ A − A Ai∗ A2 ,

A3 Ai∗ − Ai∗ A3 ,

A2 Ai∗ − Ai∗ A2 ,

A Ai∗ − Ai∗ A.

So the matrix Bi is 4 × 4.  denote the matrix of inner products for Definition 4 Let G A2 Ai∗ A − A Ai∗ A2 ,

A3 Ai∗ − Ai∗ A3 ,

A2 Ai∗ − Ai∗ A2 ,

A Ai∗ − Ai∗ A,

 is 4D × 4D. where 1 ≤ i ≤ D. Thus the matrix G  has the form Lemma 8 The matrix G ⎡ ⎢ =⎢ G ⎢ ⎣

B1

0 B2

..

0

.

⎤ ⎥ ⎥ ⎥, ⎦

BD

where B1 , B2 , . . . , B D are from Definition 3. Proof Recall that A∗0 , A∗1 , . . . , A∗D form a basis for M ∗ . Therefore the sum M M ∗ M = D ∗ i=0 M Ai M is direct. The summands are mutually orthogonal by Lemma 6(ii). The result follows.



123

Graphs and Combinatorics (2018) 34:863–877

 = Lemma 9 det(G)

873

D

i=1 det(Bi ).

Proof Immediate from Lemma 8.



5 The Main Result In this section we obtain our main result, which is Theorem 2. Lemma 10 The following (i)–(iii) hold. (i) (ii) (iii)

 = |X |2 (S )t G S . G  det(G) = |X |−8D (det(S ))−2 det( G). D −8D alt −8 (det(S )) det(G) = |X | i=1 det(Bi ).

Proof (i) Immediate from Definitions 2, 4, and Corollary 1. (ii) Follows from (i). (iii) Follows from (ii) and Lemmas 5, 9.



Lemma 11 If Γ is primitive, then for t (1 ≤ t ≤ D), A A∗t A2 − A2 A∗t A, A∗t A2 − A2 A∗t , A∗t A − A A∗t are linearly independent. Proof Assume Γ is primitive. We want to show that for t (1 ≤ t ≤ D), A A∗t A2 − A2 A∗t A, A∗t A2 − A2 A∗t , A∗t A − A A∗t are linearly independent. Suppose not. Then there exist scalars a, b, c, not all zero, such that a(A A∗t A2 − A2 A∗t A) + b(A∗t A2 − A2 A∗t ) + c(A∗t A − A A∗t ) = 0. Abbreviate θi∗ = m t u i (θt ) (0 ≤ i ≤ D). So A∗t =

D

∗ ∗ i=0 θi E i .

θi∗ = θ0∗ (1 ≤ i ≤ D).

(17)

By Lemma 1, (18)

For 1 ≤ h ≤ 3 pick z ∈ X such that ∂(x, z) = h. Compute the (x, z)-entry in (17). For h = 3 we get ac3 (θ1∗ − θ2∗ ) = 0. For h = 2 we get aa2 (θ1∗ − θ2∗ ) + b(θ0∗ − θ2∗ ) = 0. For h = 1 we get ab1 (θ1∗ − θ2∗ ) + c(θ0∗ − θ1∗ ) = 0. Solving these equations we obtain a(θ1∗ − θ2∗ ) = 0 and b = 0, c = 0. Recall that a, b, c are not all zero, so a = 0 and θ1∗ = θ2∗ . Now (17) becomes A A∗t A2 − A2 A∗t A = 0. Recall c2 A2 = A2 − a1 A − k I . We have A A∗t A2 + k A∗t A = A2 A∗t A + k A A∗t . Thus [A, A A∗t A + k A∗t ] = 0. For 0 ≤ i, j ≤ D such that i = j we have E i A∗t E j (θi θ j + k) = 0 since each primitive idempotent is a polynomial in A. By Corollary 2, E i A∗t E j = 0 if and only if qit j = 0, t = 1 and θ = k, we have kθ + k = 0 and and in this case θi θ j + k = 0. Since q0t 0 t hence θt = −1. Define a diagram with nodes 0, 1, . . . , D. There exists an arc between nodes i, j if and only if i = j and qit j = 0. Observe that node 0 is connected to node t and no other nodes. By [1, Proposition 2.11.1] and Lemma 1, the diagram is connected. Thus there exists a node s with s = 0 and s = t that is connected to node t by an arc. In other words qstt = 0. So

θs θt + k = 0 and hence θs = k, a contradiction. The result follows.

123

874

Graphs and Combinatorics (2018) 34:863–877

Theorem 2 Let Γ denote a primitive distance-regular graph with diameter D ≥ 3. Then Γ is Q-polynomial if and only if det(G) = 0. Proof To prove the theorem in one direction, assume that Γ is Q-polynomial with respect to the ordering E 0 , E 1 , . . . , E D . Write A∗ = A∗1 . By [8, Theorem 3.3] and Lemma 1, we obtain A∗ A3 − A3 A∗ ∈ Span{A A∗ A2 −A2 A∗ A, A∗ A2 − A2 A∗ , A∗ A− A A∗ }. Thus A A∗ A2 − A2 A∗ A, A∗ A3 − A3 A∗ , A∗ A2 − A2 A∗ , A∗ A− A A∗ are linearly dependent. Now the matrix B1 from Definition 3 has determinant zero. Now det(G) = 0 by Lemma 10(iii). For the other direction, assume det(G) = 0. By Lemma 10(iii) and since S alt is invertible, there exists an integer t (1 ≤ t ≤ D) such that det(Bt ) = 0. Now A A∗t A2 − A2 A∗t A, A∗t A3 − A3 A∗t , A∗t A2 − A2 A∗t , A∗t A − A A∗t are linearly dependent. By Lemma 11, we have A A∗t A2 − A2 A∗t A, A∗t A2 − A2 A∗t , A∗t A − A A∗t are linearly independent. So A∗t A3 − A3 A∗t ∈ Span{A A∗t A2 − A2 A∗t A, A∗t A2 − A2 A∗t , A∗t A − A A∗t }. Now by [8, Theorem 3.3] and (18), Γ is a Q-polynomial with respect to E = E t .

Acknowledgements The author would like to thank Professor Paul Terwilliger for many valuable ideas and suggestions. This paper was written while the author was an Honorary Fellow at the University of Wisconsin-Madison supported by the Development and Promotion of Science and Technology Talents (DPST) Project, Thailand.

6 Appendix 1 Recall the distance-regular graph Γ with diameter D. Recall for 0 ≤ h ≤ D h p1,h−1 = ch , k h ch 1 ph,h−1 = , k

h =a , p1h h k h ah 1 phh = , k

h p1,h+1 = bh , k h bh 1 ph,h+1 = . k

We now give p2h j for h − 2 ≤ j ≤ h + 2. ch−1 ch , c2 ch (ah−1 + ah − a1 ) h p2,h−1 = , c2 ch (bh−1 − 1) + ah (ah − a1 − 1) + bh (ch+1 − 1) h = , p2h c2 bh (ah+1 + ah − a1 ) h p2,h+1 = , c2 bh bh+1 h p2,h+2 = . c2

h p2,h−2 =

123

Graphs and Combinatorics (2018) 34:863–877

875

We now give p3h j for h − 3 ≤ j ≤ h + 3. h = p3,h−3 h = p3,h−2 h p3,h−1 =

h = p3h

h p3,h+1 =

h p3,h+2 = h p3,h+3 =

ch−2 ch−1 ch , c2 c3 (ah − a2 )ch−1 ch ch−1 ch (ah−2 + ah−1 − a1 ) + , c2 c3 c2 c3 ch−1 ch (bh−2 − 1) + ch ah−1 (ah−1 − a1 − 1) + ch bh−1 (ch − 1) c2 c3 ch (ah − a2 )(ah−1 + ah − a1 ) bh ch ch+1 b1 ch + + − , c2 c3 c2 c3 c3 ch bh−1 (ah + ah−1 − a1 ) c2 c3 (ah − a2 )(ch (bh−1 − 1) + ah (ah − a1 − 1) + bh (ch+1 − 1)) + c2 c3 bh ch+1 (ah + ah+1 − a1 ) b1 ah + − , c2 c3 c3 ch bh−1 bh bh (ah − a2 )(ah+1 + ah − a1 ) + c2 c3 c2 c3 bh (ch+1 (bh − 1) + ah+1 (ah+1 − a1 − 1) + bh+1 (ch+2 − 1)) b1 bh + − , c2 c3 c3 (ah − a2 )bh bh+1 bh bh+1 (ah+2 + ah+1 − a1 ) + , c2 c3 c2 c3 bh bh+1 bh+2 . c2 c3

7 Appendix 2 Recall the matrix G from Theorem 1. In this appendix we give G for D = 3. Example 1 Assume D = 3. The rows and columns of G are indexed by the following matrices, in the specified order: Block 1 Block 2 Block 3 Block 4

A3 E 1∗ − E 1∗ A3 A2 E 1∗ − E 1∗ A2 AE 1∗ − E 1∗ A A2 E 1∗ A − AE 1∗ A2

A3 E 2∗ − E 2∗ A3 A2 E 2∗ − E 2∗ A2 AE 2∗ − E 2∗ A A2 E 2∗ A − AE 2∗ A2

A3 E 3∗ − E 3∗ A3 A2 E 3∗ − E 3∗ A2 AE 3∗ − E 3∗ A A2 E 3∗ A − AE 3∗ A2 .

So the matrix G is 12 × 12. G has the form ⎡

X 0 0 ⎢0 Y 0 G=⎢ ⎣0 0 Z S1 S2 S3

⎤ S1 S2 ⎥ ⎥, S3 ⎦ W

123

876

Graphs and Combinatorics (2018) 34:863–877

where each block is a 3 × 3 symmetric matrix as shown below. ⎡

X=

Y=

Z=

S=

⎤ 2k3 k −2k3 c3 −2k3 a3 3 ⎣ −2k3 c3 2k3 (k2 − p 3 ) ⎦, −2k3 p23 22 3 3 −2k3 a3 −2k3 p23 2k3 (k3 − p33 ) ⎤ ⎡ −2k2 a2 −2k2 b2 2k2 (k − c2 ) 2 ) 2 ⎦, ⎣ −2k2 a2 2k2 (k2 − p22 −2k2 p23 2 2 −2k2 b2 −2k2 p23 2k2 (k3 − p33 ) ⎤ ⎡ −2kb1 0 2k(k − a1 ) 1 ) 1 ⎦, ⎣ −2kb1 2k(k2 − p22 −2kp23 1 1 ) 0 −2kp23 2k(k3 − p33 ⎡ ⎤ a1 − c2 b1 − a2 −b2 1 − p2 1 − p2 ⎦ , p23 2k2 ⎣ b1 − a2 p22 22 23 1 2 1 − p2 −b2 p23 − p23 p33 33

S1 = b2 S, S2 = a2 S and S3 = c2 S. The matrix W is symmetric with entries W11 = 2(k 2 k2 + (k2 a1 a2 − kb12 )a1 + (k2 (c2 (b1 − 1) + a2 (a2 − a1 − 1) + b2 (c3 − 1)) − k2 a22 )c2 ), W12 = 2((k2 a1 a2 − kb12 )b1 + (k2 (c2 (b1 − 1) + a2 (a2 − a1 − 1) W13

+ b2 (c3 − 1)) − k2 a22 )a2 − k3 c33 ), = 2((k2 (c2 (b1 − 1) + a2 (a2 − a1 − 1) + b2 (c3 − 1)) − k2 a22 )b2 − k3 c32 a3 ),

1 W22 = 2(kk22 + (k2 a1 a2 − kb12 ) p22 + (k2 (c2 (b1 − 1) + a2 (a2 − a1 − 1) 2 3 + b2 (c3 − 1)) − k2 a22 ) p22 − k3 c32 p22 ), 1 W23 = 2((k2 a1 a2 − kb12 ) p23 + (k2 (c2 (b1 − 1) + a2 (a2 − a1 − 1) 2 2 3 + b2 (c3 − 1)) − k2 a2 ) p23 − k3 c32 p23 ), 1 W33 = 2(kk2 k3 + (k2 a1 a2 − kb12 ) p33 + (k2 (c2 (b1 − 1) + a2 (a2 − a1 − 1) 2 2 3 + b2 (c3 − 1)) − k2 a2 ) p33 − k3 c32 p33 ).

From Appendix 1, we find 1 p22 = 3 p22 = 1 = p23 3 p23 = 1 p33 =

123

k 2 a2 c2 (b1 − 1) + a2 (a2 − a1 − 1) + b2 (c3 − 1) 2 , p22 = , k c2 c3 (a2 + a3 − a1 ) , c2 k2 b2 b2 (a3 + a2 − a1 ) 2 , p23 = , k c2 c3 (b2 − 1) + a3 (a3 − a1 − 1) − b3 , c2 k 3 a3 b2 (c3 (b2 − 1) + a3 (a3 − a1 − 1) − b3 ) 2 = , , p33 k c2 c3

Graphs and Combinatorics (2018) 34:863–877 3 p33 =

877

c3 b2 (a3 + a2 − a1 ) (a3 − a2 )(c3 (b2 − 1) + a3 (a3 − a1 − 1) − b3 ) + c2 c3 c2 c3 b1 a3 − . c3

References 1. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin (1989) d . Linear Algebra Appl. 2. Hanson, E.: A characterization of Leonard pairs using the parameters {ai }i=0 438, 2289–2305 (2013) 3. Juriši´c, A., Terwilliger, P., Žitnik, A.: The Q-polynomial idempotents of a distance-regular graph. J. Comb. Theory Ser. B 100, 683–690 (2010) 4. Kurihara, H., Nozaki, H.: A characterization of Q-polynomial association schemes. J. Comb. Theory Ser. A 119, 57–62 (2012) 5. Nomura, K., Terwilliger, P.: Tridiagonal matrices with nonnegative entries. Linear Algebra Appl. 434, 2527–2538 (2011) 6. Pascasio, A.A.: A characterization of Q-polynomial distance-regular graphs. Discret. Math. 308, 3090– 3096 (2008) 7. Terwilliger, P.: A characterization of P- and Q-polynomial association schemes. J. Comb. Theory Ser. A 45, 8–26 (1987) 8. Terwilliger, P.: A new inequality for distance-regular graphs. Discret. Math. 137, 319–332 (1995) 9. Terwilliger, P.: The subconstituent algebra of an association scheme I. J. Algebraic Comb. 1, 363–388 (1992)

123