ISSN 2590-9770
The Art of Discrete and Applied Mathematics 3 (2020) #P2.04
https://doi.org/10.26493/2590-9770.1271.e54
(Also available at http://adam-journal.eu)
On the Terwilliger algebra of a certain family of
bipartite distance-regular graphs with ∆2 = 0
Štefko Miklavič* , Safet Penjić†
University of Primorska, Andrej Marušič Institute,
Muzejski trg 2, 6000 Koper, Slovenia
Received 27 September 2018, accepted 4 January 2019, published online 10 August 2020
Abstract
Let Γ denote a bipartite distance-regular graph with diameterD ≥ 4 and valency k ≥ 3.
Let X denote the vertex set of Γ, and let Ai (0 ≤ i ≤ D) denote the distance matrices of
Γ. We abbreviate A := A1. For x ∈ X and for 0 ≤ i ≤ D, let Γi(x) denote the set of
vertices in X that are distance i from vertex x.
Fix x ∈ X and let T = T (x) denote the subalgebra of MatX(C) generated by
A,E∗0 , E
∗
1 , . . . , E
∗
D, where for 0 ≤ i ≤ D, E∗i represents the projection onto the ith
subconstituent of Γ with respect to x. We refer to T as the Terwilliger algebra of Γ with
respect to x. By the endpoint of an irreducible T -module W we mean min{i | E∗iW 6= 0}.
In this paper we assume Γ has the property that for 2 ≤ i ≤ D− 1, there exist complex
scalars αi, βi such that for all y, z ∈ X with ∂(x, y) = 2, ∂(x, z) = i, ∂(y, z) = i, we
have αi + βi|Γ1(x) ∩ Γ1(y) ∩ Γi−1(z)| = |Γi−1(x) ∩ Γi−1(y) ∩ Γ1(z)|.
We study the structure of irreducible T -modules of endpoint 2. Let W denote an irre-
ducible T -module with endpoint 2, and let v denote a nonzero vector in E∗2W . We show
that W = span
(
{E∗i Ai−2E∗2v | 2 ≤ i ≤ D} ∪ {E∗i Ai+2E∗2v | 2 ≤ i ≤ D − 2}
)
.
It turns out that, except for a particular family of bipartite distance-regular graphs with
D = 5, this result is already known in the literature. Assume now that Γ is a member of
this particular family of graphs. We show that if Γ is not almost 2-homogeneous, then up
to isomorphism there exists exactly one irreducible T -module with endpoint 2 and it is not
thin. We give a basis for this T -module.
Keywords: Distance-regular graphs, Terwilliger algebra, irreducible modules.
Math. Subj. Class. (2020): 05E30, 05C50
*The author acknowledge the financial support from the Slovenian Research Agency (research core funding
No. P1-0285 and research projects N1-0032, N1-0038, N1-0062, J1-5433, J1-6720, J1-7051, J1-9108, J1-9110).
†The author acknowledges the financial support from the Slovenian Research Agency (research core funding
No. P1-0285 and Young Researchers Grant).
E-mail addresses: stefko.miklavic@upr.si (Štefko Miklavič), safet.penjic@iam.upr.si (Safet Penjić)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 3 (2020) #P2.04
1 Introduction
Throughout this introduction let Γ denote a bipartite distance-regular graph with diameter
D ≥ 4, valency k ≥ 3 and path-length function ∂. Let X denote the vertex set of Γ.
For x ∈ X and 0 ≤ i ≤ D, let Γi(x) denote the set of vertices in X that are distance i
from vertex x, and let T = T (x) denote the Terwilliger algebra of Γ with respect to x (see
Section 2 for formal definitions).
It is known that there exists a unique irreducible T -module with endpoint 0, and this
module is thin [8, Proposition 8.4]. Moreover, Curtin showed that up to isomorphism Γ
has exactly one irreducible T -module with endpoint 1, and this module is thin [4, Corol-
lary 7.7].
We now discuss the irreducible T -modules of endpoint 2. It turns out that the structure
of these modules is particularly nice if we assume that Γ has the following combinatorial
property: for 2 ≤ i ≤ D − 1, there exist complex scalars αi, βi such that for all y, z ∈ X
with ∂(x, y) = 2, ∂(x, z) = i, ∂(y, z) = i, we have
αi + βi|Γ1(x) ∩ Γ1(y) ∩ Γi−1(z)| = |Γi−1(x) ∩ Γi−1(y) ∩ Γ1(z)|.
Irreducible modules of endpoint 2 of these graphs were studied extensively, see [10, 11, 12,
13, 15]. We are motivated by the fact that the above equation holds if Γ is Q-polynomial.
Assume that Γ has the above mentioned combinatorial property. We show that if W is
an irreducible T -module with endpoint 2 and v is a nonzero vector in E∗2W , then
W = span
(
{E∗i Ai−2E∗2v | 2 ≤ i ≤ D} ∪ {E∗i Ai+2E∗2v | 2 ≤ i ≤ D − 2}
)
.
Except for a particular family of bipartite distance-regular graphs with D = 5, this
result is already known in the literature. To define this particular family we introduce a
certain parameter ∆2 in terms of the intersection numbers of Γ by ∆2 = (k− 2)(c3− 1)−
(c2 − 1)p222. It turns out that ∆2 ≥ 0 and that ∆2 = 0 implies c2 ∈ {1, 2} or D ≤ 5.
The above mentioned family of bipartite distance-regular graphs with D = 5 is exactly the
family of such graphs with ∆2 = 0. Assume now that Γ is such a graph. We show that if Γ
is not almost 2-homogeneous, then up to isomorphism there exists exactly one irreducible
T -module with endpoint 2, and this module is not thin. We give a basis for this T -module.
If Γ is almost 2-homogeneous, then the structure of irreducible T -modules with endpoint 2
is described in [7].
2 Preliminaries
In this section we review some definitions and basic results concerning distance-regular
graphs. See the book of A. E. Brouwer, A. M. Cohen and A. Neumaier [2] for more
background information.
Let C denote the complex number field and let X denote a nonempty finite set. Let
MatX(C) denote the C-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 over C
consisting 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 call V the standard module.
We endow V with the Hermitean inner product 〈 , 〉 that satisfies 〈u, v〉 = utv for u, v ∈ V ,
where t denotes transpose and denotes complex conjugation. Recall that
〈u,Bv〉 = 〈Btu, v〉 (2.1)
Š. Miklavič and S. Penjić: On the Terwilliger algebra of BDRG with ∆2 = 0 3
for u, v ∈ V and B ∈ MatX(C). For y ∈ X let ŷ denote the element of V with a 1 in the
y coordinate and 0 in all other coordinates. Note that
{ŷ | y ∈ X} is an orthonormal basis for V.
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 call D the diameter of Γ. For a vertex
x ∈ X and an integer i let Γi(x) denote the set of vertices at distance i from x. For an
integer k ≥ 0 we say Γ is regular with valency k whenever |Γ1(x)| = k for all x ∈ X .
We say Γ is distance-regular whenever for all integers h, i, j (0 ≤ h, i, j ≤ D) and for all
vertices x, y ∈ X with ∂(x, y) = h, the number
phij = |Γi(x) ∩ Γj(y)|
is independent of x and y. The phij are called the intersection numbers of Γ.
For the rest of this paper we assume Γ is distance-regular with diameter D ≥ 4. Note
that phij = p
h
ji for 0 ≤ h, i, j ≤ D. For convenience set ci := pi1,i−1 (1 ≤ i ≤ D),
ai := p
i
1i (0 ≤ i ≤ D), bi := pi1,i+1 (0 ≤ i ≤ D − 1), ki := p0ii (0 ≤ i ≤ D), and
c0 = bD = 0. By the triangle inequality the following hold for 0 ≤ h, i, j ≤ D: (i) phij = 0
if one of h, i, j is greater than the sum of the other two; (ii) phij 6= 0 if one of h, i, j equals
the sum of the other two. In particular ci 6= 0 for 1 ≤ i ≤ D and bi 6= 0 for 0 ≤ i ≤ D−1.
We observe that Γ is regular with valency k = k1 = b0 and that
ci + ai + bi = k (0 ≤ i ≤ D). (2.2)
Note that ki = |Γi(x)| for x ∈ X and 0 ≤ i ≤ D. By [2, p. 127],
ki =
b0b1 · · · bi−1
c1c2 · · · ci
(1 ≤ i ≤ D). (2.3)
Recall Γ is bipartite whenever ai = 0 for 0 ≤ i ≤ D. Setting ai = 0 in (2.2) we find
bi + ci = k (0 ≤ i ≤ D). (2.4)
The following formulae for the bipartite case will be useful.
Lemma 2.1 ([2, Lemma 4.1.7]). Let Γ denote a bipartite distance-regular graph with
diameter D ≥ 4 and valency k ≥ 3. Then
pi2i =
ci(bi−1 − 1) + bi(ci+1 − 1)
c2
(1 ≤ i ≤ D − 1), pD2D =
k(bD−1 − 1)
c2
.
We recall the Bose-Mesner algebra of Γ. For 0 ≤ i ≤ D let Ai denote the matrix in
MatX(C) with (x, y)-entry
(Ai)xy =
{
1 if ∂(x, y) = i,
0 if ∂(x, y) 6= i (x, y ∈ X). (2.5)
For notational convenience, we define Ai to be the zero matrix for all integers i < 0 or
i > D. We call Ai the ith distance matrix of Γ. We abbreviate A := A1 and call this the
adjacency matrix of Γ. We observe (i) A0 = I; (ii)
∑D
i=0Ai = J ; (iii) Ai = Ai (0 ≤ i ≤
D); (iv) Ati = Ai (0 ≤ i ≤ D); (v) AiAj =
∑D
h=0 p
h
ijAh (0 ≤ i, j ≤ D), where I (resp.
J) denotes the identity matrix (resp. all 1’s matrix) in MatX(C). Using these facts we find
A0, A1, . . . , AD is a basis for a commutative subalgebra M of MatX(C). We call M the
Bose-Mesner algebra of Γ. It turns out that A generates M [1, p. 190].
4 Art Discrete Appl. Math. 3 (2020) #P2.04
3 Terwilliger algebra
Let Γ denote a distance-regular with diameter D ≥ 4 and valency k ≥ 3. We first recall
the dual idempotents of Γ. To do this fix a vertex x ∈ X. We view x as a “base vertex”.
For 0 ≤ i ≤ D let E∗i = E∗i (x) denote the diagonal matrix in MatX(C) with (y, y)-entry
(E∗i )yy =
{
1 if ∂(x, y) = i,
0 if ∂(x, y) 6= i (y ∈ X).
We call E∗i the ith dual idempotent of Γ with respect to x [16, p. 378]. We observe (ei)∑D
i=0E
∗
i = I; (eii) E
∗
i = E
∗
i (0 ≤ i ≤ D); (eiii) E∗ti = E∗i (0 ≤ i ≤ D); (eiv)
E∗i E
∗
j = δijE
∗
i (0 ≤ i, j ≤ D). By these facts E∗0 , E∗1 , . . . , E∗D form a basis for a
commutative subalgebra M∗ = M∗(x) of MatX(C). We call M∗ the dual Bose-Mesner
algebra of Γ with respect to x [16, p. 378]. For 0 ≤ i ≤ D we have
E∗i V = span{ŷ | y ∈ X, ∂(x, y) = i},
so dimE∗i V = ki. We call E
∗
i V the ith subconstituent of Γ with respect to x. Note that
V = E∗0V + E
∗
1V + · · ·+ E∗DV (orthogonal direct sum). (3.1)
Moreover E∗i is the projection from V onto E
∗
i V for 0 ≤ i ≤ D.
We now recall the Terwilliger algebra of Γ. Let T = T (x) denote the subalgebra of
MatX(C) generated by M , M∗. We call T the Terwilliger algebra of Γ with respect to
x [16, Definition 3.3]. Recall M is generated by A, so T is generated by A and the dual
idempotents. We observe T has finite dimension. By construction T is closed under the
conjugate-transpose map so T is semisimple [16, Lemma 3.4(i)].
By a T -module we mean a subspace W of V such that BW ⊆ W for all B ∈ T . Let
W denote a T -module. Then W is said to be irreducible whenever W is nonzero and W
contains no T -modules other than 0 and W .
By [9, Corollary 6.2] any T -module is an orthogonal direct sum of irreducible T -
modules. In particular the standard module V is an orthogonal direct sum of irreducible
T -modules. Let W , W ′ denote T -modules. By an isomorphism of T -modules from W to
W ′ we mean an isomorphism of vector spaces σ : W →W ′ such that (σB −Bσ)W = 0
for all B ∈ T . The T -modules W , W ′ are said to be isomorphic whenever there exists
an isomorphism of T -modules from W to W ′. By [4, Lemma 3.3] any two nonisomor-
phic irreducible T -modules are orthogonal. Let W denote an irreducible T -module. By
[16, Lemma 3.4(iii)] W is an orthogonal direct sum of the nonvanishing spaces among
E∗0W,E
∗
1W, . . . , E
∗
DW . By the endpoint ofW we mean min{i | 0 ≤ i ≤ D, E∗iW 6= 0}.
By the diameter of W we mean |{i | 0 ≤ i ≤ D, E∗iW 6= 0}| − 1. We say W is thin
whenever the dimension of E∗iW is at most 1 for 0 ≤ i ≤ D.
The following matrices of MatX(C) will be useful later in the paper.
Definition 3.1. Let Γ denote a distance-regular with diameter D ≥ 4 and valency k ≥ 3.
Fix x ∈ X and let E∗i = E∗i (x) (0 ≤ i ≤ D) and T = T (x). We define matrices
L = L(x), R = R(x) by
L =
D∑
h=1
E∗h−1AE
∗
h, R =
D−1∑
h=0
E∗h+1AE
∗
h.
Š. Miklavič and S. Penjić: On the Terwilliger algebra of BDRG with ∆2 = 0 5
Note thatA = L+R [4, Lemma 4.4] andLt = R. We callL andR the lowering matrix and
the raising matrix of Γ with respect to x, respectively. Observe that L and R are contained
in T .
Definition 3.2 ([7, Definition 3.2]). Let Γ denote a distance-regular with diameter D ≥ 4
and valency k ≥ 3. Fix x ∈ X . For 1 ≤ i ≤ D we define matrices Λi = Λi(x) in
MatX(C) by
(Λi)zy =
{
|Γ1(x) ∩ Γ1(y) ∩ Γi−1(z)|, if ∂(x, y) = 2, ∂(x, z) = ∂(y, z) = i,
0, otherwise
for z, y ∈ X .
4 The scalars ∆i and γi
Let Γ denote a distance-regular graph with diameter D ≥ 4 and valency k ≥ 3. From now
on we assume that Γ is bipartite. In this section we introduce certain scalars ∆i and γi
(2 ≤ i ≤ D − 1) which we find useful.
Definition 4.1. Let Γ denote a distance-regular with diameter D ≥ 4 and valency k ≥ 3.
Then for 2 ≤ i ≤ D − 1 we define
∆i = (bi−1 − 1)(ci+1 − 1)− (c2 − 1)pi2i
and
γi =
ci(bi−1 − 1)
pi2i
(observe that pi2i > 0 by [3, Lemma 11]).
By [3, Theorem 12] we have ∆i ≥ 0 for 2 ≤ i ≤ D − 1. Moreover, the scalars ∆i and
γi are related as follows.
Lemma 4.2 ([3, Theorem 13]). Let Γ denote a distance-regular with diameter D ≥ 4 and
valency k ≥ 3 and fix an integer 2 ≤ i ≤ D − 1. Then the following (i),(ii) are equivalent.
(i) ∆i = 0.
(ii) For all x, y, z ∈ X with ∂(x, y) = 2, ∂(x, z) = i, ∂(y, z) = i,
|Γ1(x) ∩ Γ1(y) ∩ Γi−1(z)| = γi.
If ∆i = 0 for 2 ≤ i ≤ D − 2, then Γ is called almost 2-homogeneous, see [7]. In this
case the structure of irreducible T -modules is well understood, so we will assume that Γ
is not almost 2-homogeneous. In the rest of the paper we therefore consider the following
situation.
Notation 4.3. Let Γ = (X,R) denote a bipartite distance-regular graph with diameter
D ≥ 4, valency k ≥ 3 and intersection numbers bi, ci, which is not almost 2-homogeneous.
Let Ai (0 ≤ i ≤ D) be the distance matrices of Γ, and let V denote the standard module
for Γ. We fix x ∈ X and let E∗i = E∗i (x) (0 ≤ i ≤ D) and T = T (x) denote the dual
idempotents and the Terwilliger algebra of Γ with respect to x, respectively. We assume
6 Art Discrete Appl. Math. 3 (2020) #P2.04
that for 2 ≤ i ≤ D − 1, there exist complex scalars αi, βi such that for all y, z ∈ X with
∂(x, y) = 2, ∂(x, z) = i, ∂(y, z) = i, we have
αi + βi|Γ1(x) ∩ Γ1(y) ∩ Γi−1(z)| = |Γi−1(x) ∩ Γi−1(y) ∩ Γ1(z)|.
Let matrices L = L(x), R = R(x) and Λi = Λi(x) (1 ≤ i ≤ D) be as in Definitions 3.1
and 3.2. Let scalars ∆i, γi (2 ≤ i ≤ D − 1) be as in Definition 4.1.
With reference to Notation 4.3, pick 2 ≤ i ≤ D − 1 and assume that ∆i 6= 0. By [12,
Theorem 5.4] scalars αi and βi are uniquely determined and given by
αi =
ci(ci − 1)(bi−1 − c2)− cici−1(bi − 1)(c2 − 1)
c2∆i
,
βi =
ci(ci+1 − ci)(bi−1 − 1)− bi(ci+1 − 1)(ci − ci−1)
c2∆i
.
(4.1)
If ∆i = 0, then scalars αi and βi are not uniquely determined. For example, if ∆2 = 0,
then one of the possible values for α2 and β2 is α2 = 0, β2 = 1. Note however that by
Lemma 4.2 this is not the only possible solution.
5 Some products in T
With reference to Notation 4.3, in this section we compute some products of matrices of T .
We start by recalling the following results.
Lemma 5.1 ([14, Lemma 6.1]). With reference to Notation 4.3, for 0 ≤ h, i, j ≤ D and
y, z ∈ X the (y, z)-entry of E∗hAiE∗j is 1 if ∂(x, y) = h, ∂(y, z) = i, ∂(x, z) = j, and 0
otherwise.
Lemma 5.2 ([14, Lemma 6.5]). With reference to Notation 4.3, for 0 ≤ h, i, j, r, s ≤ D
and y, z ∈ X the (y, z)-entry of E∗hArE∗i AsE∗j is |Γi(x) ∩ Γr(y) ∩ Γs(z)| if ∂(x, y) = h,
∂(x, z) = j, and 0 otherwise.
Lemma 5.3 ([7, Lemma 3.3]). With reference to Notation 4.3, we have
Λ1 = E
∗
1AE
∗
2 , Λi = E
∗
i Ai−1E
∗
1AE
∗
2 − c2E∗i Ai−2E∗2 (2 ≤ i ≤ D).
In particular, Λi ∈ T (1 ≤ i ≤ D).
Theorem 5.4. With reference to Notation 4.3 the following holds for 3 ≤ i ≤ D:
LE∗i Ai−2E
∗
2 = bi−1E
∗
i−1Ai−3E
∗
2 + (ci−1 − αi−1)E∗i−1Ai−1E∗2 − βi−1Λi−1. (5.1)
Proof. Pick z, y ∈ X and an integer 3 ≤ i ≤ D. We show that (z, y)-entries of both sides
of (5.1) agree. Note that by the property (eiv) of Section 3 and Lemma 5.2,
(LE∗i Ai−2E
∗
2 )zy =
{
|Γi(x) ∩ Γi−2(y) ∩ Γ1(z)| if ∂(x, y) = 2, ∂(x, z) = i− 1,
0 otherwise.
(5.2)
It follows from (5.2), Lemma 5.1 and Definition 3.2 that the (z, y)-entries of both sides of
(5.1) are 0 if ∂(x, y) 6= 2 or ∂(x, z) 6= i−1. Assume now ∂(x, y) = 2 and ∂(x, z) = i−1.
Š. Miklavič and S. Penjić: On the Terwilliger algebra of BDRG with ∆2 = 0 7
Observe that by the triangle inequality we have that ∂(z, y) ∈ {i − 3, i − 1, i + 1}. We
consider each of these three cases separately.
Case 1: ∂(x, y) = 2, ∂(x, z) = i−1 and ∂(z, y) = i−3. Note that in this case we have
(LE∗i Ai−2E
∗
2 )zy = bi−1 by (5.2). By Lemma 5.1 and Definition 3.2 the (z, y)-entries of
both sides of (5.1) agree.
Case 2: ∂(x, y) = 2, ∂(x, z) = i − 1 and ∂(z, y) = i − 1. Observe that by (5.2) we
have
(LE∗i Ai−2E
∗
2 )zy = ci−1 − |Γ1(z) ∩ Γi−2(x) ∩ Γi−2(y)|
= ci−1 − (αi−1 + βi−1|Γi−2(z) ∩ Γ1(x) ∩ Γ1(y)|).
By Lemma 5.1 and Definition 3.2 the (z, y)-entries of both sides of (5.1) agree.
Case 3: ∂(x, y) = 2, ∂(x, z) = i − 1 and ∂(z, y) = i + 1. By (5.2), Lemma 5.1 and
Definition 3.2 the (z, y)-entries of both sides of (5.1) are 0.
6 Irreducible T -modules with endpoint 2
With reference to Notation 4.3, let W denote an irreducible T -module with endpoint 2. In
this section we find a spanning set for W .
Definition 6.1. With reference to Notation 4.3, letW denote an irreducible T -module with
endpoint 2 and let v denote a nonzero vector in E∗2W . For 0 ≤ i ≤ D, define
v+i = E
∗
i Ai−2E
∗
2v, v
−
i = E
∗
i Ai+2E
∗
2v.
Note that v+2 = v, v
+
i = 0 if i < 2, and v
−
i = 0 if i < 2 or i > D − 2.
Lemma 6.2 ([5, Corollary 9.3(i), Theorem 9.4]). With reference to Definition 6.1, the
following (i)–(iv) hold.
(i) E∗i AiE
∗
2v = −(v+i + v
−
i ) (2 ≤ i ≤ D).
(ii) Rv+i = ci−1v
+
i+1 (2 ≤ i ≤ D − 1) and Rv
+
D = 0.
(iii) Lv−i = bi+1v
−
i−1 (2 ≤ i ≤ D − 2).
(iv) Lv+i+1 −Rv
−
i−1 = biv
+
i − civ
−
i (1 ≤ i ≤ D − 1).
Lemma 6.3. With reference to Definition 6.1, the following (i)–(iii) hold.
(i) Λiv = −c2v+i (2 ≤ i ≤ D).
(ii) Lv+2 = 0 and
Lv+i = (bi−1 − ci−1 + αi−1 + c2βi−1)v
+
i−1 − (ci−1 − αi−1)v
−
i−1
for 3 ≤ i ≤ D.
(iii)
Rv−i = (c2βi+1 − ci+1 + αi+1)v
+
i+1 + αi+1v
−
i+1
for 2 ≤ i ≤ D − 2.
Proof. (i) Immediate from Lemma 5.3 and Definition 6.1.
(ii) Note that Lv+2 = 0 as the endpoint of W is 2. To obtain the result for Lv
+
i (3 ≤
i ≤ D) apply (5.1) to v and use Definition 6.1, Lemma 6.2(i) and (i) above.
(iii) Immediately by (ii) above and Lemma 6.2(iv).
8 Art Discrete Appl. Math. 3 (2020) #P2.04
Theorem 6.4. With reference to Definition 6.1,
W = span{v+2 , v
+
3 , . . . , v
+
D, v
−
2 , v
−
3 , . . . , v
−
D−2}.
Proof. Denote W ′ = span{v+2 , v
+
3 , . . . , v
+
D, v
−
2 , v
−
3 , . . . , v
−
D−2} and note that W ′ ⊆ W .
We now show that W = W ′. Note that E∗i v
+
j = δijv
+
j for 2 ≤ j ≤ D and E∗i v
−
j = δijv
−
j
for 2 ≤ j ≤ D − 2. Therefore, W ′ is invariant under the action of E∗i for 0 ≤ i ≤ D. Ob-
serve also that W ′ is invariant under the action of L by Lemma 6.2(iii) and Lemma 6.3(ii),
and also invariant under the action of R by Lemma 6.2(ii) and Lemma 6.3(iii). As A =
R+L, W ′ is invariant under the action ofA. As T is generated byA andE∗i (0 ≤ i ≤ D),
this implies that W ′ is a T -module. Recall that W is irreducible and that W ′ contains a
nonzero vector v. It follows that W = W ′.
Corollary 6.5. With reference to Definition 6.1, we have
dim (E∗D−1W ) ≤ 1, dim (E∗DW ) ≤ 1.
Proof. Immediately from Theorem 6.4.
As already mentioned, the result from Theorem 6.4 is already known in the literature,
except for the case D = 5 and ∆2 = 0, see [11, 12, 15]. In the rest of the paper we
study this case in detail. If D = 5 and ∆2 = ∆3 = 0, then Γ is almost 2-homogeneous,
contradicting our assumption in Notation 4.3. Therefore, we have that ∆3 6= 0.
7 Case ∆2 = 0 and ∆3 6= 0
With reference to Notation 4.3, in this section we study graphs with ∆2 = 0 and ∆3 6= 0.
We first have the following observation.
Lemma 7.1. With reference to Definition 6.1, assume that ∆2 = 0 and ∆3 6= 0. Then the
following (i), (ii) hold.
(i)
c3 =
(c22 − c2 + 1)k − c2(c2 + 1)
k + c22 − 3c2
.
(ii)
α3 = 0, β3 =
c2(k − 2)
k + c22 − 3c2
.
Proof. (i) Solve ∆2 = 0 for c3. Note that k+ c22 − 3c2 = (c2 − 1)(c2 − 2) + k− 2 > 0 as
k ≥ 3.
(ii) Use Definition 4.1, (4.1) and (i) above.
Lemma 7.2. With reference to Definition 6.1, assume that ∆2 = 0 and ∆3 6= 0. Then
E∗2A2E
∗
2v = −
c2(k − 2)
k + c22 − 3c2
v.
Š. Miklavič and S. Penjić: On the Terwilliger algebra of BDRG with ∆2 = 0 9
Proof. Let Γ22 = Γ
2
2(x) denote the graph with vertex set X̃ = Γ2(x) and edge set R̃ =
{yz | y, z ∈ X̃, ∂(y, z) = 2}. The graph Γ22 has exactly k2 vertices and it is regular with
valency p222 ([6, Lemma 3.2]). Let à denote the adjacency matrix of Γ
2
2. The matrix à is
symmetric with real entries. Therefore à is diagonalizable with all eigenvalues real. Note
that eigenvalues for E∗2A2E
∗
2 and à are the same.
Since ∆2 = 0, we know E∗2A2E
∗
2 has exactly one distinct eigenvalue η on E
∗
2W by
[6, Theorem 4.11, Corollary 4.13, Lemma 5.3]. Thus, every nonzero vector in E∗2W is an
eigenvector for E∗2A2E
∗
2 with eigenvalue η. By [6, Lemmas 5.4, 5.5] we find η = − c2γ2 .
The result now follows from Definition 4.1 and Lemma 7.1(i).
Corollary 7.3. With reference to Definition 6.1, assume that ∆2 = 0 and ∆3 6= 0. Then
v−2 =
b2(c2 − 1)
k + c22 − 3c2
v+2 .
Proof. By Lemma 6.2(i) and Lemma 7.2 we have
−v+2 − v
−
2 = E
∗
2A2E
∗
2v = −
c2(k − 2)
k + c22 − 3c2
v+2 .
The result follows.
Corollary 7.4. With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0.
Then
W = span{v+2 , v
+
3 , v
+
4 , v
+
5 , v
−
3 }. (7.1)
Proof. Immediately from Theorem 6.4 and Corollary 7.3.
Observe that by (3.1) vectors v+2 , v
+
3 , v
+
4 , v
+
5 are linearly independent, provided they
are non-zero.
8 Some scalar products
With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0. Our goal
for the rest of this paper is to find a basis for W . In this section we compute the norms of
vectors v+3 , v
+
4 , v
+
5 , v
−
3 in terms of the intersection numbers of Γ and ‖v‖. Note that by [10,
Lemma 6.4] we have ∆4 6= 0 as well. The assumptions of [10, Lemma 6.4] are somehow
different from assumptions of Notation 4.3. However, the proof of [10, Lemma 6.4] works
just fine also under assumptions of Notation 4.3.
Lemma 8.1. With reference to Definition 6.1, assume that ∆2 = 0 and ∆3 6= 0. Then
‖v+3 ‖2 =
b2(b2 − c2)
k + c22 − 3c2
‖v‖2.
In particular, if D ≥ 5 then v+3 6= 0.
Proof. By Lemma 6.2(ii), (2.1) and Definition 3.1 we have
‖v+3 ‖2 = 〈v
+
3 , v
+
3 〉 = 〈Rv
+
2 , v
+
3 〉 = 〈v
+
2 , Lv
+
3 〉.
10 Art Discrete Appl. Math. 3 (2020) #P2.04
The result now follows from Lemma 6.3(ii), Corollary 7.3 and since α2 = 0, β2 = 1. Now
assume that v+3 = 0. Observe that this implies b2 = c2. If D ≥ 5 then by [2, Proposition
4.1.6](i),(ii) we have c2 ≤ c3 ≤ b2, and so c2 = c3. But then c2 = 1 by Lemma 7.1(i), and
so k = b2 + c2 = 2, a contradiction.
Lemma 8.2. With reference to Definition 6.1, assume that ∆2 = 0 and ∆3 6= 0. Then
〈v+3 , v
−
3 〉 =
b2b4(c2 − 1)
k + c22 − 3c2
‖v‖2.
Proof. By Lemma 6.2(ii), (2.1) and Definition 3.1 we have
〈v+3 , v
−
3 〉 = 〈Rv
+
2 , v
−
3 〉 = 〈v
+
2 , Lv
−
3 〉.
The result now follows from Lemma 6.2(iii) and Corollary 7.3.
Lemma 8.3. With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0.
Then
‖v+4 ‖2 =
b2((b3 − 1)b2 − c3(c2 − 1)b4)
c2(k + c22 − 3c2)
‖v‖2.
In particular, v+4 = 0 if and only if c2 6= 1 and b4 = b2(b3 − 1)/(c3(c2 − 1)).
Proof. By Lemma 6.2(ii), (2.1) and Definition 3.1 we have
〈v+4 , v
+
4 〉 =
1
c2
〈Rv+3 , v
+
4 〉 =
1
c2
〈v+3 , Lv
+
4 〉.
The formula for ‖v+4 ‖2 now follows from Lemma 6.3(ii), Lemma 7.1, Lemma 8.1 and
Lemma 8.2.
It is clear that v+4 = 0 if c2 6= 1 and b4 = b2(b3 − 1)/(c3(c2 − 1)). Therefore assume
now that v+4 = 0. It follows that (b3 − 1)b2 = c3(c2 − 1)b4. If c2 = 1, then also b3 = 1
and c3 = 1 by Lemma 7.1(i). But then k = c3 + b3 = 2, a contradiction. Therefore c2 6= 1
and the result follows.
Lemma 8.4. With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0.
Then
‖v−3 ‖2 =
( (c2 − 1)(c4 − 1)b2
k + c22 − 3c2
+
(k − 1)∆3
b2 − 1
) b2b4‖v‖2
c2(kc2 − k − c2) + b2
.
Proof. By Lemma 6.2(iv), (2.1) and Definition 3.1 we have
c3〈v−3 , v
−
3 〉 = b3〈v
+
3 , v
−
3 〉+ 〈Rv
−
2 , v
−
3 〉 − 〈v
+
4 , Rv
−
3 〉.
The result now follows from Lemmas 6.3(iii), 7.1, 8.2 and 8.3, Corollary 7.3 and (4.1).
Corollary 8.5. With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0.
Then the following (i), (ii) hold.
(i) v−3 6= 0.
(ii) v+3 , v
−
3 are linearly independent.
Š. Miklavič and S. Penjić: On the Terwilliger algebra of BDRG with ∆2 = 0 11
Proof. (i) Note that (c2−1)(c4−1)b2/(k+c22−3c2) ≥ 0 and that (k−1)∆3/(b2−1) > 0
by [3, Theorem 12]. Moreover, it is easy to see that c2(kc2 − k − c2) + b2 > 0. The result
follows.
(ii) Assume on the contrary that v+3 , v
−
3 are linearly dependent. Let
B =
(
〈v+3 , v
+
3 〉 〈v
+
3 , v
−
3 〉
〈v−3 , v
+
3 〉 〈v
−
3 , v
−
3 〉
)
and note that det(B) = 0. Using Lemmas 8.1, 8.2 and 8.4 one could easily see that the
only factor of det(B) which could be zero is
c4k − c32k + 2c22k − 2c2k + c32c4 − 2c22c4 − c2c4 + 2c22.
Solving this for c4 and then computing ∆3 using Definition 4.1, we obtain ∆3 = 0, a
contradiction. This shows that v+3 , v
−
3 are linearly independent.
Lemma 8.6. With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0.
Then
‖v+5 ‖2 =
b4 − c4 + α4 + c2β4
c3
‖v+4 ‖2.
In particular, v+5 = 0 if and only if v
+
4 = 0 or b4 − c4 + α4 + c2β4 = 0.
Proof. By Lemma 6.2(ii), (2.1) and Definition 3.1 we have
〈v+5 , v
+
5 〉 =
1
c3
〈Rv+4 , v
+
5 〉 =
1
c3
〈v+4 , Lv
+
5 〉.
The result now follows from Lemma 6.3(ii).
9 A basis
With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0. In this section
we display a basis for W . We will also show that, up to isomorphism, Γ has a unique
irreducible T -module with endpoint 2.
Theorem 9.1. With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0.
Then the following (i)–(iii) hold.
(i) If v+5 6= 0, then the following is a basis for W :
v+i (2 ≤ i ≤ 5), v
−
3 . (9.1)
(ii) If v+4 6= 0 and v
+
5 = 0, then the following is a basis for W :
v+i (2 ≤ i ≤ 4), v
−
3 . (9.2)
(iii) If v+4 = 0, then the following is a basis for W :
v+i (2 ≤ i ≤ 3), v
−
3 . (9.3)
In particular, W is not thin.
12 Art Discrete Appl. Math. 3 (2020) #P2.04
Proof. Note that by (7.1), W is spanned by vectors v+i (2 ≤ i ≤ 5) and v
−
3 . Vector
v+2 = v is nonzero by definition. Vectors v
+
3 and v
−
3 are nonzero by Lemma 8.1 and
Corollary 8.5(i), respectively. We prove part (i) of the theorem. Proofs of parts (ii) and (iii)
are similar.
If v+5 6= 0, then v
+
4 6= 0 by Lemma 8.6. Vectors v
+
i (2 ≤ i ≤ 5) and v
−
3 are linearly
independent by (3.1) and Corollary 8.5(ii). This shows that (9.1) is a basis for W . As
dim (E∗2 (W )) = 2, W is not thin. The result follows.
Theorem 9.2. With reference to Definition 6.1, assume that D = 5, ∆2 = 0 and ∆3 6= 0.
Then Γ has, up to isomorphism, exactly one irreducible T -module with endpoint 2.
Proof. Let U denote an irreducible T -module with endpoint 2, different from W . Fix
nonzero u ∈ E∗2U , and for 2 ≤ i ≤ 5 define
u+i = E
∗
i Ai−2E
∗
2u
and let u−3 = E
∗
3A5E
∗
2u. It follows from the results of Section 8 and Theorem 9.1 that
u+2 , u
+
3 , u
−
3 are nonzero and that nonzero vectors in the set {u
+
i | 2 ≤ i ≤ 5} ∪ {u
−
3 }
form a basis for U . Furthermore, it follows from Lemma 8.3 and Lemma 8.6 that u+4 (u
+
5 ,
respectively) is nonzero if and only if v+4 (v
+
5 , respectively) is nonzero.
Let σ : W → U be defined by σ(v+i ) = u
+
i (2 ≤ i ≤ 5) and σ(v
−
3 ) = u
−
3 . It follows
from the comments above that σ is a vector space isomorphism from W to U . We show
that σ is a T -module isomorphism. Since A generates M and E∗0 , E
∗
1 , . . . , E
∗
5 is a basis
for M∗, it suffices to show that σ commutes with each of A,E∗0 , E
∗
1 , . . . , E
∗
5 . Using the
fact that E∗i E
∗
j = δijE
∗
i and the definition of σ we immediately find that σ commutes with
each of E∗0 , E
∗
1 , . . . , E
∗
5 . Recall that A = R + L. It follows from Lemma 6.2, Lemma 6.3
and Corollary 7.3 that σ commutes with A. The result follows.
We would like to emphasize that together with the results in [10, 12, 15], Theorems 9.1
and 9.2 imply the following characterization.
Theorem 9.3. Let Γ = (X,R) denote a bipartite distance-regular graph with diameter
D ≥ 4 and valency k ≥ 3. Assume Γ is not almost 2-homogeneous. We fix x ∈ X and let
E∗i = E
∗
i (x) (0 ≤ i ≤ D) and T = T (x) denote the dual idempotents and the Terwilliger
algebra of Γ with respect to x, respectively. Then the following (i), (ii) are equivalent.
(i) Γ has, up to isomorphism, exactly one irreducible T -module W with endpoint 2, and
W is non-thin with dim(E∗2W ) = 1, dim(E
∗
D−1W ) ≤ 1 and dim(E∗iW ) ≤ 2 for
3 ≤ i ≤ D.
(ii) ∆2 = 0, and there exist complex scalars αi, βi (2 ≤ i ≤ D − 1) such that
|Γi−1(x) ∩ Γi−1(y) ∩ Γ1(z)| = αi + βi|Γ1(x) ∩ Γ1(y) ∩ Γi−1(z)| (9.4)
for all y ∈ Γ2(x) and z ∈ Γi(x) ∩ Γi(y).
With reference to Definition 6.1, assume that ∆2 = 0 and ∆3 6= 0. It is known that this
implies c2 ∈ {1, 2}, or D ≤ 5, see [12, Theorem 4.4]. If c2 ∈ {1, 2}, then the structure
of irreducible T -modules with endpoint 2 was studied in detail in [12, 15]. Therefore, we
are mainly interested in the case c2 ≥ 3. We have to mention however that we are not
aware of any of such a graph. Using a computer program we found intersection arrays
Š. Miklavič and S. Penjić: On the Terwilliger algebra of BDRG with ∆2 = 0 13
{b0, b1, b2, b3, b4; c1, c2, c3, c4, c5} up to valency k = 20000, which satisfy the following
conditions: c2 ≥ 3, ∆2 = 0, ∆3 > 0, ∆4 > 0, γ2 ∈ N, p222 ∈ N. None of them passed the
feasibility condition p1ij ∈ N ∪ {0}, see the table below.
intersection arrays feasibility condition
(58, 57, 49, 21, 1; 1, 9, 37, 57, 58) p123 = 1102/3 /∈ N
(112, 111, 100, 45, 4; 1, 12, 67, 108, 112) p134 = 103600/67 /∈ N
(186, 185, 161, 35, 1; 1, 25, 151, 185, 186) p123 = 6882/5 /∈ N
(274, 273, 256, 120, 10; 1, 18, 154, 264, 274) p123 = 12467/3 /∈ N
(274, 273, 256, 120, 1; 1, 18, 154, 273, 274) p123 = 12467/3 /∈ N
(1192, 1191, 1156, 561, 28; 1, 36, 631, 1164, 1192) p123 = 118306/3 /∈ N
(3236, 3235, 3136, 760, 1; 1, 100, 2476, 3235, 3236) p123 = 523423/5 /∈ N
ORCID iDs
Štefko Miklavič https://orcid.org/0000-0002-2878-0745
Safet Penjić https://orcid.org/0000-0001-6664-4130
References
[1] E. Bannai and T. Ito, Algebraic combinatorics. I, The Benjamin/Cummings Publishing Co.,
Inc., Menlo Park, CA, 1984, association schemes.
[2] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-regular graphs, volume 18 of Ergeb-
nisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas
(3)], Springer-Verlag, Berlin, 1989, doi:10.1007/978-3-642-74341-2.
[3] B. Curtin, 2-homogeneous bipartite distance-regular graphs, Discrete Math. 187 (1998), 39–70,
doi:10.1016/S0012-365X(97)00226-4.
[4] B. Curtin, Bipartite distance-regular graphs. I, Graphs Combin. 15 (1999), 143–158, doi:10.
1007/s003730050049.
[5] B. Curtin, Bipartite distance-regular graphs. II, Graphs Combin. 15 (1999), 377–391, doi:10.
1007/s003730050072.
[6] B. Curtin, The local structure of a bipartite distance-regular graph, European J. Combin. 20
(1999), 739–758, doi:10.1006/eujc.1999.0307.
[7] B. Curtin, Almost 2-homogeneous bipartite distance-regular graphs, European J. Combin. 21
(2000), 865–876, doi:10.1006/eujc.2000.0399.
[8] E. S. Egge, A generalization of the Terwilliger algebra, J. Algebra 233 (2000), 213–252, doi:
10.1006/jabr.2000.8420.
[9] J. T. Go, The Terwilliger algebra of the hypercube, European J. Combin. 23 (2002), 399–429,
doi:10.1006/eujc.2000.0514.
[10] M. S. MacLean and Š. Miklavič, On bipartite distance-regular graphs with exactly one non-
thin T -module with endpoint two, European J. Combin. 64 (2017), 125–137, doi:10.1016/j.
ejc.2017.04.004.
[11] M. S. MacLean and Š. Miklavič, On bipartite distance-regular graphs with exactly two ir-
reducible T-modules with endpoint two, Linear Algebra Appl. 515 (2017), 275–297, doi:
10.1016/j.laa.2016.11.021.
14 Art Discrete Appl. Math. 3 (2020) #P2.04
[12] M. S. MacLean, Š. Miklavič and S. Penjić, On the Terwilliger algebra of bipartite distance-
regular graphs with ∆2 = 0 and c2 = 1, Linear Algebra Appl. 496 (2016), 307–330, doi:
10.1016/j.laa.2016.01.040.
[13] M. S. MacLean, Š. Miklavič and S. Penjić, An A-invariant subspace for bipartite distance-
regular graphs with exactly two irreducible T -modules with endpoint 2, both thin, J. Algebraic
Combin. 48 (2018), 511–548, doi:10.1007/s10801-017-0798-7.
[14] Š. Miklavič, The Terwilliger algebra of a distance-regular graph of negative type, Linear Alge-
bra Appl. 430 (2009), 251–270, doi:10.1016/j.laa.2008.07.013.
[15] S. Penjić, On the Terwilliger algebra of bipartite distance-regular graphs with ∆2 = 0 and
c2 = 2, Discrete Math. 340 (2017), 452–466, doi:10.1016/j.disc.2016.09.001.
[16] P. Terwilliger, The subconstituent algebra of an association scheme. I, J. Algebraic Combin. 1
(1992), 363–388, doi:10.1023/A:1022494701663.