An Inequality Involving the Local Eigenvalues of a Distance-Regular Graph
PAUL TERWILLIGER [email protected]
Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison Wisconsin, 53706, USA Received October 10, 2000; Revised March 24, 2003; Accepted April 15, 2003
Abstract. Letdenote a distance-regular graph with diameterD≥3, valencyk, and intersection numbers ai,bi,ci. LetXdenote the vertex set ofand fixx∈X. Letdenote the vertex-subgraph ofinduced on the set of vertices inXadjacentx. Observehaskvertices and is regular with valencya1. Letη1≥η2≥ · · · ≥ηk denote the eigenvalues ofand observeη1=a1. Letdenote the set of distinct scalars amongη2, η3, . . . , ηk. Forη∈let multηdenote the number of timesηappears amongη2, η3, . . . , ηk. Letλdenote an indeterminate, and letp0,p1, . . . ,pDdenote the polynomials inR[λ] satisfyingp0=1 and
λpi=ci+1pi+1+(ai−ci+1+ci)pi+bipi−1 (0≤i≤D−1),
wherep−1=0.We show
1+
η=−1η∈
pi−1( ˜η)
pi( ˜η)(1+η˜)multη≤ k bi
(1≤i≤D−1),
where we abbreviate ˜η= −1−b1(1+η)−1. Concerning the case of equality we obtain the following result. LetT= T(x) denote the subalgebra of MatX(C) generated byA,E∗0,E1∗, . . . ,E∗D, whereAdenotes the adjacency matrix of andEi∗denotes the projection onto theith subconstituent ofwith respect tox.Tis called the subconstituent algebra or the Terwilliger algebra. An irreducibleT-moduleW is said to bethinwhenever dimEi∗W ≤1 for 0≤i≤D. By theendpointofWwe mean min{i|E∗iW=0}. We show the following are equivalent: (i) Equality holds in the above inequality for 1≤i≤D−1; (ii) Equality holds in the above inequality fori =D−1; (iii) Every irreducibleT-module with endpoint 1 is thin.
Keywords: distance-regular graph, association scheme, Terwilliger algebra, subconstituent algebra 2000 Mathematics Subject Classification: Primary 05E30; Secondary 05E35, 05C50
1. Introduction
In this paper will denote a distance-regular graph with diameter D ≥ 3, valency k, and intersection numbers ai,bi,ci (see Section 2 for formal definitions). We recall the subconstituent algebra of . Let X denote the vertex set of and fix a “base vertex”
x∈ X. LetT =T(x) denote the subalgebra of MatX(C) generated byA,E0∗,E∗1, . . . ,E∗D, where Adenotes the adjacency matrix of and Ei∗ denotes the projection onto theith subconstituent ofwith respect tox. The algebraT is called thesubconstituent algebra(or Terwilliger algebra) ofwith respect tox[28]. ObserveThas finite dimension. Moreover
T is semi-simple; the reason is each ofA,E0∗,E1∗, . . . ,E∗Dis symmetric with real entries, soTis closed under the conjugate-transpose map [16, p. 157]. SinceTis semi-simple, each T-module is a direct sum of irreducibleT-modules.
In this paper, we are concerned with the irreducible T-modules that possess a certain property. In order to define this property we make a few observations. LetW denote an irre- ducibleT-module. ThenWis the direct sum of the nonzero spaces amongE0∗W,E1∗W, . . . , E∗DW. There is a second decomposition of interest. To obtain it we make a definition. Let k =θ0 > θ1 >· · ·> θDdenote the distinct eigenvalues of A, and for 0≤ i ≤ DletEi
denote the primitive idempotent of Aassociated withθi. ThenW is the direct sum of the nonzero spaces among E0W,E1W, . . . ,EDW. If the dimension of E∗iW is at most 1 for 0 ≤ i ≤ Dthen the dimension of EiW is at most 1 for 0 ≤ i ≤ D[28, Lemma 3.9]; in this case we sayW isthin. LetW denote an irreducibleT-module. By theendpointofW we mean min{i|0≤i≤ D, E∗iW =0}. There exists a unique irreducibleT-module with endpoint 0 [19, Proposition 8.4]. We call this moduleV0. The moduleV0is thin; in factEi∗V0
andEiV0have dimension 1 for 0≤i ≤ D[28, Lemma 3.6]. For a detailed description of V0 see [9, 19]. In this paper, we are concerned with the thin irreducibleT-modules with endpoint 1.
In order to describe the thin irreducible T-modules with endpoint 1 we define some parameters. Let=(x) denote the vertex-subgraph ofinduced on the set of vertices inXadjacentx. The graphhaskvertices and is regular with valencya1. Letη1 ≥η2≥
· · · ≥ηk denote the eigenvalues of the adjacency matrix of. We callη1, η2, . . . , ηkthe local eigenvaluesofwith respect tox. We mentionedis regular with valencya1 so η1=a1andηk≥ −a1[3, Proposition 3.1]. The eigenvaluesη2, η3, . . . , ηksatisfy another bound. To give the bound we use the following notation. For any real numberηother than
−1 we define
η˜= −1−b1(1+η)−1.
By [27, Theorem 1] we have ˜θ1≤ηi ≤θ˜Dfor 2≤i≤k. We remark ˜θ1<−1 and ˜θD≥0, sinceθ1 >−1 anda1−k ≤θD <−1 [25, Lemma 2.6]. LetW denote a thin irreducible T-module with endpoint 1. ObserveE1∗W is a 1-dimensional eigenspace forE1∗AE1∗; letη denote the corresponding eigenvalue. As we will see,ηis one ofη2, η3, . . . , ηk. We callη thelocal eigenvalue ofW. LetWdenote an irreducibleT-module. ThenWandW are isomorphic asT-modules if and only ifWis thin with endpoint 1 and local eigenvalueη [31, Theorem 12.1].
LetW denote a thin irreducibleT-module with endpoint 1 and local eigenvalueη. The structure of W is described as follows [22, 31]. First assumeη = θ˜j, where j = 1 or j = D. Then the dimension ofW isD−1. For 0≤ i ≤ D,Ei∗W is zero ifi ∈ {0,D}, and has dimension 1 ifi ∈ {0,D}. MoreoverEiW is zero ifi ∈ {0,j}, and has dimension 1 ifi ∈ {0,j}. Next assumeηis not one of ˜θ1, ˜θD. Then the dimension ofW is D. For 0 ≤i ≤ D,Ei∗W is zero ifi =0, and has dimension 1 if 1≤i ≤ D. Moreover EiW is zero ifi =0, and has dimension 1 if 1≤i ≤ D. For a more complete description of the thin irreducibleT-modules with endpoint 1 we refer the reader to [22, 31]. More general information onT and its modules can be found in [6–10, 12–14, 17–21, 24, 26, 28, 32].
In the present paper we obtain a finite sequence of inequalities involving the intersection numbers and local eigenvalues of. We show equality is attained in each inequality if and only if every irreducibleT-module with endpoint 1 is thin. We now state our inequalities. To do this we define some polynomials. Letλdenote an indeterminate, and letR[λ] denote the R-algebra consisting of all polynomials inλthat have real coefficients. Let p0,p1, . . . ,pD
denote the polynomials in R[λ] satisfying p0=1 and
λpi =ci+1pi+1+(ai−ci+1+ci)pi+bipi−1 (0≤i≤ D−1), wherep−1=0.One significance of these polynomials is that
pi(A)=A0+A1+ · · · +Ai (0≤i ≤ D),
whereA0,A1, . . . ,ADare the distance matrices of. Letdenote the set of distinct scalars amongη2, η3, . . . , ηk. Forη∈ , let multη denote the number of timesηappears among η2, η3, . . . , ηk. We show
1+
η∈
multη =k, 1+
η=−1η∈
multη 1+η˜ =0,
1+
η=−1η∈
multη (1+η)˜ 2 = k
b1.
Our first main result is the inequality
1+
η=−1η∈
pi−1( ˜η)
pi( ˜η)(1+η)˜ multη≤ k bi
(1)
for 1≤i ≤D−1. We remark on the terms in (1). Letηdenote an element inother than
−1. We mentioned above that ˜θ1≤η≤θ˜D. If ˜θ1 ≤η <−1 then ˜η≥θ1, and in this case pi( ˜η)>0 for 0≤i ≤ D−1 [31, Lemma 4.5]. If−1< η≤θ˜Dthen ˜η≤θD, and in this case (−1)ipi( ˜η)>0 for 0≤i ≤D−1 [31, Lemma 4.5]. In either case, the coefficient of multηin (1) is positive for 1≤i≤ D−1.
Our second main result concerns the case of equality in (1). We prove the following are equivalent: (i) Equality holds in (1) for 1≤ i ≤ D−1; (ii) Equality holds in (1) for i =D−1; (iii) Every irreducibleT-module with endpoint 1 is thin.
Our two main results are found in Theorems 13.5 and 13.6.
2. Preliminaries concerning distance-regular graphs
In this section we review some definitions and basic concepts concerning distance-regular graphs. For more background information we refer the reader to [1, 4, 23] or [28].
Let X denote a nonempty finite set. Let MatX(C) denote theC-algebra consisting of all matrices whose rows and columns are indexed by X and whose entries are in C. Let V =CX denote the vector space overCconsisting of column vectors whose coordinates are indexed by X and whose entries are in C. We observe MatX(C) acts on V by left multiplication. We endowV with the Hermitean inner product,defined by
u, v =utv¯ (u, v∈V), (2)
wheret denotes transpose and−denotes complex conjugation. As usual, we abbreviate u 2 = u,ufor allu∈V.For ally∈ X,let ˆydenote the element ofV with a 1 in they coordinate and 0 in all other coordinates. We observe{yˆ | y∈ X}is an orthonormal basis forV.The following formula will be useful. For allB∈MatX(C) and for allu, v∈V,
Bu, v = u,B¯tv. (3)
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 path-length distance function for , and set D = max{∂(x,y)|x,y ∈ X}. We refer to D as thediameter of . Let x,ydenote vertices of. We sayx,yareadjacentwheneverx yis an edge. Letkdenote a nonnegative integer. We sayisregularwithvalency kwhenever each vertex ofis adjacent to exactlykdistinct vertices of. We sayisdistance-regularwhenever for all integers h,i,j (0 ≤ h,i,j ≤ D) and for all vertices x,y ∈ X with∂(x,y) = h,the number
pi jh = |{z∈ X |∂(x,z)=i, ∂(z,y)= j}| (4) is independent ofxandy.The integersphi jare called theintersection numbersof.We ab- breviateci = p1ii−1 (1≤i≤ D), ai = pi1i (0≤i ≤D), andbi =pi1i+1(0≤i ≤D−1).
For notational convenience, we definec0 =0 andbD=0.We notea0 =0 andc1=1.
For the rest of this paper we assumeis distance-regular with diameterD≥3.
By (4) and the triangle inequality,
p1hj =0 if |h− j|>1 (0≤h,j ≤ D). (5) Observeis regular with valencyk = b0,and thatci +ai +bi = k for 0 ≤ i ≤ D.
Moreoverbi >0 (0≤i ≤ D−1) andci >0 (1≤i ≤ D).For 0≤i≤ Dwe abbreviate ki = p0ii,and observe
ki = |{z∈ X|∂(x,z)=i}|, (6) wherexis any vertex inX. Apparentlyk0=1 andk1=k.By [1, p. 195] we have
ki =b0b1· · ·bi−1
c1c2· · ·ci
(0≤i ≤D). (7)
The following formula will be useful [4, Lemma 4.1.7]:
pi1,i+1= b1b2· · ·bi
c1c2· · ·ci
(0≤i ≤D−1). (8)
We recall the Bose-Mesner algebra of.For 0≤i ≤ DletAidenote the matrix in MatX(C) withx yentry
(Ai)x y =
1, if∂(x,y)=i
0, if∂(x,y)=i (x,y∈ X).
We call Ai theithdistance matrixof.For notational convenience we defineAi =0 for i < 0 andi > D.We abbreviate A = A1 and call this theadjacency matrixof. We observe
A0 =I, (9)
D i=0
Ai =J, (10)
A¯i =Ai (0≤i≤ D), (11)
Ati =Ai (0≤i≤ D), AiAj =
D h=0
phi jAh (0≤i,j ≤D), (12)
where I denotes the identity matrix and J denotes the all 1’s matrix. Let M denote the subalgebra of MatX(C) generated by A.We refer toMas theBose-Mesner algebraof. Using (9) and (12) one can readily showA0,A1, . . . ,ADform a basis forM.By [4, p. 45], M has a second basisE0,E1, . . . ,EDsuch that
E0 = |X|−1J, (13)
D i=0
Ei =I, (14)
E¯i =Ei (0≤i≤ D), (15)
Eit =Ei (0≤i≤ D), (16)
EiEj =δi jEi (0≤i,j ≤ D). (17)
We refer to E0,E1, . . . ,ED as the primitive idempotents of . We call E0 the trivial idempotentof.
We recall the eigenvalues of. Since E0,E1, . . . ,EDform a basis for M,there exist complex scalarsθ0, θ1, . . . , θDsuch thatA=D
i=0θiEi. Combining this with (17) we find AEi = EiA = θiEi for 0 ≤ i ≤ D. Using (11), (15) we find θ0, θ1, . . . , θD are inR.
Observeθ0, θ1, . . . , θDare distinct since Agenerates M.By [3, Proposition 3.1],θ0 =k
and−k ≤θi ≤kfor 0≤ i ≤ D.Throughout this paper we assume E0,E1, . . . ,EDare indexed so thatθ0 > θ1 >· · ·> θD.We refer toθias theeigenvalueofassociated with Ei.We callθ0thetrivial eigenvalueof.For 0≤i ≤ Dletmi denote the rank ofEi. We refer tomi as themultiplicityofEi (or θi). By (13) we findm0 =1. Using (14)–(17) we readily find
V =E0V +E1V + · · · +EDV (orthogonal direct sum). (18) For 0≤i ≤ D,the spaceEiV is the eigenspace ofAassociated withθi. We observe the dimension of EiV is equal tomi.
We record a fact about the eigenvaluesθ1, θD.
Lemma 2.1([25,Lemma 2.6]) Let = (X,R) denote a distance-regular graph with diameter D≥3and eigenvaluesθ0> θ1>· · ·> θD.Then
(i) −1< θ1<k, (ii) a1−k≤θD<−1.
Later in this paper we will discuss polynomials in one variable. We will use the following notation. We letλdenote an indeterminate, and we letR[λ] denote theR-algebra consisting of all polynomials inλthat have coefficients inR.
3. Two families of polynomials
Let=(X,R) denote a distance-regular graph with diameter D≥ 3.In this section we recall two families of polynomials associated with. To motivate things, we recall by (5) and (12) that
A Ai =bi−1Ai−1+aiAi+ci+1Ai+1 (0≤i ≤ D), (19) whereb−1=0 andcD+1=0. Let f0,f1, . . . ,fDdenote the polynomials inR[λ] satisfying
f0=1 and
λfi =bi−1fi−1+aifi+ci+1fi+1 (0≤i≤ D−1), (20) where f−1=0. Letidenote an integer (0≤i ≤ D). The polynomial fihas degreei, and the coefficient ofλiis (c1c2· · ·ci)−1.Comparing (19) and (20) we find fi(A)= Ai.
We now recall some polynomials related to the fi. Letp0,p1, . . . ,pDdenote the poly- nomials inR[λ] satisfying
pi = f0+ f1+ · · · + fi (0≤i≤ D). (21) Leti denote an integer (0 ≤i ≤ D). The polynomial pi has degreei, and the coefficient ofλiis (c1c2· · ·ci)−1. Moreover pi(A)= A0+A1+ · · · +Ai. Settingi =Din this and using (10) we find pD(A)=J.
We record several facts for later use.
Lemma 3.1([22,Theorem3.2])Let = (X,R)denote a distance-regular graph with diameter D≥3.Let the polynomials p0,p1, . . . ,pDbe from(21). Then p0=1and
λpi =ci+1pi+1+(ai−ci+1+ci)pi+bipi−1 (0≤i≤ D−1), where p−1=0.
Lemma 3.2([31, Lemma 4.5])Let = (X,R) denote a distance-regular graph with diameter D≥3and eigenvaluesθ0> θ1>· · ·> θD. Let the polynomials pibe from(21).
Then the following(i)–(iv)hold for allθ∈R.
(i) Ifθ > θ1then pi(θ)>0for0≤i ≤D.
(ii) Ifθ=θ1then pi(θ)>0for0≤i ≤D−1and pD(θ)=0.
(iii) Ifθ < θDthen(−1)ipi(θ)>0for0≤i ≤D.
(iv) Ifθ=θDthen(−1)ipi(θ)>0for0≤i ≤D−1and pD(θ)=0.
4. The subconstituent algebra and its modules
In this section we recall some definitions and basic concepts concerning the subconstituent algebra and its modules. For more information we refer the reader to [6, 9, 10, 21, 22, 24, 28].
Let=(X,R) denote a distance-regular graph with diameterD≥3.We recall the dual Bose-Mesner algebra of.For the rest of this section, fix a vertexx∈ X.For 0≤i ≤ D we letEi∗=Ei∗(x) denote the diagonal matrix in MatX(C) withyyentry
(Ei∗)yy =
1, if∂(x,y)=i
0, if∂(x,y)=i (y∈X). (22)
We callE∗i theithdual idempotent ofwith respect to x.We observe D
i=0
Ei∗ =I, (23)
E¯i∗ =Ei∗ (0≤i ≤ D), (24)
E∗it =Ei∗ (0≤i ≤ D), (25)
Ei∗E∗j =δi jEi∗ (0≤i,j ≤D). (26) Using (23), (26), we find E0∗,E1∗, . . . ,E∗D form a basis for a commutative subalgebra M∗ =M∗(x) of MatX(C).We callM∗thedual Bose-Mesner algebra ofwith respect to x.We recall the subconstituents of. From (22) we find
Ei∗V =span{ˆy|y∈X, ∂(x,y)=i} (0≤i ≤D). (27)
By (27) and since{yˆ |y∈ X}is an orthonormal basis forV we find
V =E∗0V +E∗1V + · · · +E∗DV (orthogonal direct sum). (28) Combining (27) and (6) we find
dimE∗iV =ki (0≤i ≤D). (29)
We callE∗iV theithsubconstituent ofwith respect to x.
We recall howMandM∗are related. By [28, Lemma 3.2] we find
Eh∗AiE∗j =0 if and only if pi jh =0 (0≤h,i,j ≤D). (30) Combining (30) and (5) we find
Ei∗AE∗j =0 if|i−j|>1 (0≤i,j ≤D), (31) Ei∗AjE1∗=0 if|i−j|>1 (0≤i,j ≤D). (32) LetT =T(x) denote the subalgebra of MatX(C) generated by M andM∗. We callT the subconstituent algebra of with respect to x [28]. We observeT has finite dimension.
MoreoverT is semi-simple; the reason isT is closed under the conjugate-transponse map [16, p. 157].
We now consider the modules forT.By aT-modulewe mean a subspaceW ⊆V such that BW ⊆ W for allB ∈ T.We refer toV itself as thestandard moduleforT.LetW denote aT-module. ThenWis said to beirreduciblewheneverWis nonzero andWcontains noT-modules other than 0 andW.LetW,WdenoteT-modules. By anisomorphism of T -modulesfromW toWwe mean an isomorphism of vector spacesσ : W → Wsuch that
(σB−Bσ)W =0 for allB∈T. (33)
The modules W,W are said to be isomorphic as T -modules whenever there exists an isomorphism ofT-modules fromW toW.
LetW denote aT-module and letWdenote aT-module contained inW. Using (3) we find the orthogonal complement ofWinW is aT-module. It follows that eachT-module is an orthogonal direct sum of irreducibleT-modules. We mention any two nonisomorphic irreducibleT-modules are orthogonal [9, Lemma 3.3].
LetW denote an irreducibleT-module. Using (23)–(26) we findW is the direct sum of the nonzero spaces among E0∗W,E1∗W, . . . ,E∗DW. Similarly using (14)–(17) we findW is the direct sum of the nonzero spaces amongE0W,E1W, . . . ,EDW. If the dimension of Ei∗W is at most 1 for 0≤i ≤ Dthen the dimension ofEiW is at most 1 for 0≤i ≤ D [28, Lemma 3.9]; in this case we say W isthin. LetW denote an irreducibleT-module.
By theendpointof W we mean min{i|0 ≤i ≤ D, E∗iW =0}. We adopt the following notational convention.
Definition 4.1 Throughout the rest of this paper we let = (X,R) denote a distance- regular graph with diameterD≥3, valencyk, intersection numbersai,bi,ci, Bose-Mesner algebra M, and eigenvaluesθ0 > θ1 >· · · > θD. For 0 ≤ i ≤ Dwe let Ei denote the primitive idempotent ofassociated withθi. We letV denote the standard module for. We fixx∈ Xand abbreviateEi∗ =Ei∗(x) (0≤i ≤D),M∗=M∗(x),T =T(x). We define
si =
∂(x,y)=iy∈X
ˆ
y (0≤i ≤ D). (34)
5. TheT-moduleV0
With reference to Definition 4.1, there exists a unique irreducibleT-module with endpoint 0 [19, Proposition 8.4]. We call this moduleV0. The moduleV0is described in [9, 19]. We summarize some details below in order to motivate the results that follow.
The moduleV0is thin. In fact each ofEiV0,Ei∗V0has dimension 1 for 0≤i ≤ D. We give two bases forV0. The vectorsE0xˆ,E1xˆ, . . . ,EDxˆ form a basis forV0. These vectors are mutually orthogonal and Eixˆ 2 =mi|X|−1for 0 ≤ i ≤ D. To motivate the second basis we make some comments. For 0≤i ≤ Dwe havesi = Aix, whereˆ si is from (34).
Moreoversi = Ei∗δ, whereδ =
y∈Xy. The vectorsˆ s0,s1, . . . ,sDform a basis forV0. These vectors are mutually orthogonal and si 2=ki for 0≤i ≤ D. With respect to the basiss0,s1, . . . ,sDthe matrix representingAis
a0 b0 0
c1 a1 b1 c2 · ·
· · ·
· · bD−1
0 cD aD
. (35)
The basis E0xˆ,E1xˆ, . . . ,EDxˆ and the basiss0,s1, . . . ,sDare related as follows. For 0≤ i ≤Dwe havesi =D
h=0 fi(θh)Ehxˆ,where the fiare from (20).
We define the matrixϕ0. LetV0⊥denote the orthogonal complement ofV0inV. Observe V =V0+V0⊥ (orthogonal direct sum).
Letϕ0 denote the matrix in MatX(C) such thatϕ0 −I vanishes onV0 and such thatϕ0
vanishes on V0⊥. In other wordsϕ0 is the orthogonal projection fromV ontoV0. For all y∈ Xwe have
ϕ0yˆ =k−1i si, (36)
wherei =∂(x,y). To see (36) observek−1i si is contained inV0. Moreover ˆy−ki−1si is orthogonal to each ofs0,s1, . . . ,sDand hence is contained inV0⊥.
6. The local eigenvalues
A bit later in this paper we will consider the thin irreducibleT-modules with endpoint 1.
In order to discuss these we recall some parameters known as the local eigenvalues.
Definition 6.1 With reference to Definition 4.1, we let=(x) denote the graph ( ˘X,R),˘ where
X˘ = {y∈X |∂(x,y)=1}, R˘ = {yz| y,z∈X˘, yz∈ R}.
We observeis the vertex-subgraph ofinduced on the set of vertices inXadjacentx. The graphhas exactlykvertices, wherekis the valency of.Also,is regular with valency a1. We let ˘Adenote the adjacency matrix of. The matrix ˘Ais symmetric with real entries;
therefore ˘Ais diagonalizable with all eigenvalues real. We letη1 ≥η2 ≥ · · · ≥ηkdenote the eigenvalues of ˘A. We mentionedis regular with valencya1soη1=a1andηk≥ −a1
[3, Proposition 3.1]. We call η1, η2, . . . , ηk the local eigenvalues of with respect to x.
For notational convenience we make the following definition.
Definition 6.2 With reference to Definition 4.1, we letdenote the set of distinct scalars amongη2, η3, . . . , ηk, where theηiare from Definition 6.1. Forη∈Rwe let multηdenote the number of timesηappears amongη2, η3, . . . , ηk. We observe multη =0 if and only if η∈.
With reference to Definition 4.1, we consider the first subconstituent E1∗V. By (29) the dimension ofE∗1Visk. ObserveE∗1Vis invariant under the action ofE1∗AE∗1. To illuminate this action we observe that for an appropriate ordering of the vertices of,
E1∗AE∗1 = A˘ 0
0 0
,
where ˘Ais from Definition 6.1. Apparently the action ofE∗1AE1∗onE1∗V is essentially the adjacency map for . In particular the action ofE1∗AE1∗ onE1∗V is diagonalizable with eigenvaluesη1, η2, . . . , ηk. We observe the vectors1from (34) is contained inE∗1V. Using (35) we finds1is an eigenvector for E1∗AE1∗with eigenvaluea1. Letvdenote a vector in E1∗V. We observe the following are equivalent: (i)vis orthogonal tos1; (ii)Jv=0; (iii) E0v =0; (iv)E0∗Av=0; (v)ϕ0v =0. LetU denote the orthogonal complement ofs1in E1∗V. We observeUhas dimensionk−1. Using (3) we findUis invariant underE1∗AE∗1. Apparently the restriction ofE1∗AE∗1toUis diagonalizable with eigenvaluesη2, η3, . . . , ηk.
Forη∈ RletUηdenote the set consisting of those vectors inU that are eigenvectors for E1∗AE∗1 with eigenvalueη. We observeUη is a subspace ofU with dimension multη. We emphasize the following are equivalent: (i) multη =0; (ii)Uη =0; (iii)η∈. By (3) and sinceE1∗AE1∗is symmetric with real entries we find
U =
η∈
Uη (orthogonal direct sum). (37)
In Definition 6.1 we mentioned η1 = a1 and ηk ≥ −a1. We now recall some addi- tional bounds satisfied by the local eigenvalues. To state the result we use the following notation.
Definition 6.3 With reference to Definition 4.1, for allz∈R∪ ∞we define
˜ z=
−1− b1
1+z, if z= −1,z= ∞
∞, if z= −1
−1, if z= ∞.
(38)
We observe ˜˜z =zfor allz∈ R∪ ∞. By Lemma 2.1 neither ofθ1, θDis equal to−1, so θ˜1= −1−b1(1+θ1)−1and ˜θD= −1−b1(1+θD)−1. By the data in Lemma 2.1 we have θ˜1<−1 and ˜θD≥0.
Lemma 6.4 ([27,Theorem1])With reference to Definitions4.1and6.1,we haveθ˜1 ≤ ηi ≤θ˜Dfor2≤i ≤k.
We remark on the case of equality in the above lemma.
Lemma 6.5([5,Theorem5.4, 22,Theorem8.5]) With reference to Definition 4.1,letv denote a nonzero vector in U . Then(i)–(iii)hold below.
(i) The vector E0vis zero and each of E2v,E3v, . . . ,ED−1vis nonzero.
(ii) E1v=0if and only ifv∈Uθ˜1. (iii) EDv =0if and only ifv∈Uθ˜D.
Corollary 6.6 With reference to Definition4.1,letvdenote a nonzero vector in U . Then (i), (ii)hold below.
(i) Ifv∈Uθ˜1orv∈Uθ˜D then Mvhas dimension D−1.
(ii) Ifv /∈Uθ˜1andv /∈Uθ˜D then Mvhas dimension D.
Proof: By (18) and sinceE0,E1, . . . ,EDform a basis forM, we findMvhas an orthog- onal basis consisting of the nonvanishing vectors among E0v,E1v, . . . ,EDv. Applying Lemma 6.5 we find that in case (i) exactly two of these vectors are zero. Similarly in case (ii) exactly one of these vectors is zero. The result follows.
The following equations will be useful.
Lemma 6.7 With reference to Definition4.1,the following(i)–(iii)hold.
(i) 1+
η∈multη=k.
(ii) 1+
η∈,η=−1 multη
1+˜η =0.
(iii) 1+
η∈,η=−1 multη (1+η˜)2 = bk1. Proof:
(i) There arek−1 elements in the sequenceη2, η3, . . . , ηk.
(ii) Each diagonal entry of ˘A is zero so the trace of ˘A is zero. Recall η1, η2, . . . , ηk
are the eigenvalues of ˘A so k
i=1ηi = 0. By this and since η1 = a1 we have a1 +
η∈ηmultη=0. In this equation, write eachηin terms of ˜ηusing Definition 6.3 to obtain the result.
(iii) Recallis regular with valencya1, so each diagonal entry of ˘A2 isa1. Apparently the trace of ˘A2 is ka1, so k
i=1η2i = ka1. By this and since η1 = a1 we have a12 +
η∈η2multη=ka1. Proceeding as in (ii) above we obtain the result.
7. The local eigenvalue of a thin irreducibleT-module with endpoint 1
In this section we make some comments concerning the thin irreducibleT-modules with endpoint 1 and the local eigenvalues.
Definition 7.1 With reference to Definition 4.1, letW denote a thin irreducibleT-module with endpoint 1. Observe E1∗W is a 1-dimensional eigenspace for E1∗AE1∗; letηdenote the corresponding eigenvalue. We observe E∗1W is contained in E1∗V and orthogonal to s1, so E1∗W ⊆Uη. ApparentlyUη = 0 soη ∈ . We refer toηas thelocal eigenvalue ofW.
Lemma 7.2([31,Theorem12.1])With reference to Definition 4.1,let W denote a thin irreducible T -module with endpoint1and local eigenvalueη. Let Wdenote an irreducible T -module. Then the following(i), (ii)are equivalent.
(i) W and Ware isomorphic as T -modules.
(ii) Wis thin with endpoint1and local eigenvalueη.
Lemma 7.3 With reference to Definition4.1,for allη∈Rwe have
Uη⊇E1∗Hη, (39)
where Hη denotes the subspace of V spanned by all the thin irreducible T -modules with endpoint1and local eigenvalueη.
Proof: ObserveE1∗Hη is spanned by theE1∗W, whereW ranges over all thin irreducible T-modules with endpoint 1 and local eigenvalue η. For all such W the space E1∗W is contained inUηby Definition 7.1. The result follows.
We remark on the dimension of the right-hand side in (39). To do this we make a definition.
Definition 7.4 With reference to Definition 4.1, and from our discussion below (33), the standard moduleV can be decomposed into an orthogonal direct sum of irreducible T- modules. LetWdenote an irreducibleT-module. By themultiplicity with which W appears in V, we mean the number of irreducibleT-modules in the above decomposition which are isomorphic toW. We remark that this number is independent of the decomposition.
Definition 7.5 With reference to Definition 4.1, for all η ∈ R we let µη denote the multiplicity with which W appears in the standard module V, where W denotes a thin irreducibleT-module with endpoint 1 and local eigenvalueη. If no suchW exists we set µη=0.
Theorem 7.6([31,Theorem12.6]) With reference to Definition4.1,for all η ∈ Rthe following scalars are equal:
(i) The scalarµηfrom Definition7.5.
(ii) The dimension of E1∗Hη,where Hη is from Lemma7.3.
Moreover
multη≥µη. (40)
We consider the case of equality in (39) and (40).
Theorem 7.7([31,Theorem12.9])With reference to Definition4.1,the following(i)–(iii) are equivalent.
(i) Equality holds in(39)for allη∈R. (ii) Equality holds in(40)for allη∈R.
(iii) Every irreducible T -module with endpoint1is thin.
In summary we have the following.
Corollary 7.8 With reference to Definition4.1,suppose every irreducible T -module with endpoint1is thin. Then for allη∈there exists a thin irreducible T -module with endpoint 1and local eigenvalueη. The multiplicity with which this module appears in V is equal to multη. Up to isomorphism there are no further irreducible T -modules with endpoint1.
8. The spaceMvforv∈ E1∗V
With reference to Definition 4.1, letηdenote a scalar inand letvdenote a nonzero vector inUη. We seek a criterion which determines whenvis contained inE1∗Hη, whereHηis from Lemma 7.3. Our criterion is Corollary 12.6. In order to develop this criterion we consider the spaceMv. We begin by constructing a useful orthogonal basis forMv.
As we proceed in this section, we will encounter scalars of the form pi( ˜η) appearing in the denominator of some rational expressions. To make it clear these scalars are nonzero, we begin with the following result.
Lemma 8.1 With reference to Definition4.1,letηdenote a real number.
(i) Ifθ˜1 < η <−1thenη > θ˜ 1. If−1< η <θ˜Dthenη < θ˜ D. In either case pi( ˜η)=0 for0≤i ≤D.
(ii) Ifη=θ˜1thenη˜ =θ1. Ifη=θ˜Dthenη˜=θD. In either case pi( ˜η)=0for0≤i ≤ D−1 and pD( ˜η)=0.
Proof: Combine Definition 6.3 and Lemma 3.2.
Definition 8.2 With reference to Definition 4.1, letηdenote a real number ( ˜θ1≤η≤θ˜D) and letvdenote a vector inUη. We define the vectorsv0, v1, . . . , vD−1as follows.
(i) Supposeη= −1. Then vi =
i h=0
ph( ˜η) pi( ˜η)
kibi
khbh
ph(A)v (0≤i ≤ D−1). (41)
(ii) Supposeη= −1. Then
vi =pi(A)v (0≤i ≤D−1). (42)
(The polynomials piare from (21).)
Theorem 8.3 With reference to Definition4.1,letηdenote a scalar inand letvdenote a nonzero vector in Uη. First assumeη =θ˜1, η =θ˜D. Then the vectorsv0, v1, . . . , vD−1
from Definition8.2form a basis for Mv. Next assumeη=θ˜1orη=θ˜D. ThenvD−1=0 andv0, v1, . . . , vD−2form a basis for Mv.
Proof: For 0≤h ≤Dthe polynomialphhas degree exactlyh. By this and Definition 8.2 we find that for 0≤i ≤D−1 the vectorvi =gi(A)v, wheregiis a polynomial of degree exactlyi. First assumeη=θ˜1,η=θ˜D. We showv0, v1, . . . , vD−1form a basis forMv. By Corollary 6.6(ii) we findMvhas dimensionD. From this and sinceAgeneratesM, we find v,Av,A2v, . . . ,AD−1vform a basis for Mv. By this and our initial comment the vectors v0, v1, . . . , vD−1form a basis forMv. Next assumeη=θ˜1orη=θ˜D. ThenvD−1 =0 by [22, Theorem 9.6]. We showv0, v1, . . . , vD−2form a basis forMv. By Corollary 6.6(i) the space Mvhas dimension D−1, sov,Av,A2v, . . . ,AD−2vform a basis for Mv. By this and our initial commentv0, v1, . . . , vD−2form a basis forMv.
The vectorsvi from Definition 8.2 are investigated in [22, 31] and a number of results are obtained. One result we will use is the following.
Theorem 8.4([22,Lemma10.5, 31,Theorem10.7])With reference to Definition4.1,let ηdenote a real number( ˜θ1 ≤ η≤ θ˜D)and letvdenote a vector in Uη. Then the vectors v0, v1, . . . , vD−1from Definition8.2are mutually orthogonal. Moreover the square-norms of these vectors are given as follows.
(i) Supposeη= −1. Then
vi 2= pi+1( ˜η)ci+1
pi( ˜η)( ˜η+1)
b1b2· · ·bi
c1c2· · ·ci
v 2 (0≤i ≤ D−1). (43)
(ii) Supposeη= −1. Then
vi 2=b1b2· · ·bi
c1c2· · ·ci v 2 (0≤i≤ D−1).
9. The spaceMv, continued
With reference to Definition 4.1, letηdenote an element inand letvdenote a vector in Uη. In the last section we usedvto define some vectorsvi. In this section we consider the vi from a different point of view.
Lemma 9.1 With reference to Definition4.1,letvdenote a vector in E∗1V . Then Ei∗Ajv=0 if|i−j|>1 (0≤i,j ≤D).
Proof: Leti,j be given and assume|i − j| > 1. Observe Ei∗AjE1∗ = 0 by (32) so Ei∗AjE1∗v=0. ObserveE1∗v=vsoEi∗Ajv=0.
Lemma 9.2 With reference to Definition 4.1, let v denote a vector in E1∗V which is orthogonal to s1. ThenD
j=0Ei∗Ajv=0for0≤i≤ D.
Proof: ObserveJv =0 so Ei∗Jv =0. EliminateJ in this expression using (10) to get the result.
Lemma 9.3 With reference to Definition 4.1, let v denote a vector in E1∗V which is orthogonal to s1. Then
pi(A)v=Ei∗+1Aiv−Ei∗Ai+1v (0≤i ≤ D−1). (44) Moreover pD(A)v=0.
