数理解析研究所講究録
991 巻 1997 年 93-100

93
The Terwilliger algebra of certain spin models.
Brian Curtin
Kyushu University
curtin@math.kyushu-u.ac.jp

The Terwilliger algebra is an algebraic tool for studying association schemes.
By a result of F. Jaeger, spin models can be interpreted as association schemes
which satisfy a few additional conditions. Thus it is natural to consider the
Terwilliger algebra of those association schemes which arise from spin model.
The strongest results can be stated for these spin model association schemes
which are actually distance-regular.
In this note we will focus on the bipartite distance-regular graphs which
are spin models. These graphs are all known due to the work of Nomura. We
have also studied these graphs, but from an algebraic perspective. This note
is meant to be an elementary examination of some of the algebraic propertiesof the Terwilliger algebra of these graphs.
$\mathrm{g}\mathrm{r}\mathrm{a}\dot{\mathrm{p}}\mathrm{h}\mathrm{s}$1Distance-regular graphs

Let $\Gamma=(X, R)$ denote a finite, connected, simple graph with diameter D.
is said to be distance-regular whenever for all integers $(0\leq i\leq D)$ and for
all $x,$ $y\in X$ with $\partial(x, y)=i$ , the numbers$\Gamma$$i,$$c_{i}$$=$$|\{z|\partial(_{X,z})=i-1, \partial(y, z)=1\}|$$a_{i}$$=$$|\{z|\partial(X, z)=.

$=$$|\{z|\partial(_{X,z})=\dot{i}+1, \partial(y, z)=1\}|$$b_{i}$

i, \partial(y, z)=1\}|$,,are independent of and . The constants, and $b_{i}(0\leq\dot{i}\leq D)$ are
known as the intersection numbers of .
For each integer $i(0\leq i\leq D)$ , let
entry
denote the matrix with
$x$

$y$

$c_{i},$$a_{i}$$\Gamma$$A_{i}$$(A_{i})(x, y)=\{$

1 ifotherwise$\partial(x, y)=\dot{i}$

$x,$

,

$(x,$ $y\in^{x)}$

$0$

$y$

.

The matrix is known as -distance matrix for . ( $A=A_{1}$ is the adjacency
matrix.) Let $M$ denote the complex matrix algebra$i^{th}$$A_{i}$$\Gamma$$M=<A>$ .
The algebra $M$ is called the Bose-Mesner algebra of F. It is a well known fact
, :..,
that $M$ has basis. For more details a.b out distance-regulargraphs we refer the reader to [1] or [2].
$A_{0},$$A_{1}$$A_{D}$

94

Spin models

2

Let $X$ be a finite nonempty set of size . A spin model is a matrix $W$ whoserows and columns are indexed by $X$ with nonzero entries which satisfies the$c\in X$ :following equations for all$n$$a,$ $b,$$\sum_{x\in X}W(_{X}, b)W(X, c)^{-1}$$\sum_{x\in x}W(X, a)W(x, b)W(X,c)^{-1}$

For all$b,$$c\in X$,$=$$n\delta_{b,c}$$=$$\sqrt{n}W(a, b)W(a, c)-1W(_{C}, b)-1$, define the column vector$\mathrm{Y}_{b\mathrm{c}}$by$(x\in X)$$\mathrm{Y}_{bc}(_{X})=\frac{W(x,b)}{W(x,c)}$.

Then $N(W)$ is defined to be the set of all matrices such that, for all ,$c\in X$ , the vector
is an eigenvector of .
$N(W)$
It turns out thatis the Bose-Mesner algebra of some association
scheme and that $W\in N(W)$ .
Let $\Gamma=(X, R)$ be a distance-regular graph,
let $M$ denote the BoseMesner algebra of . A spin model $W$ is said to be supported by whenever$W\in M\subseteq N(W)$ . For more details on spin models and the facts quoted here
we refer the reader to [6] (or [8]).
$A$

$b$

$A$

$\mathrm{Y}_{b\mathrm{c}}$$\mathrm{a}\mathrm{n}\dot{\mathrm{d}}$$\Gamma$3$\Gamma$

The Terwilliger algebraFix any $x\in X$ . We write$\Gamma_{i}(X)=\{y\in x|\partial(_{X}, y)--i.\}$For each integer $i(0\leq i\leq D)$ , let
in
with
entry
$Mat_{X}(\mathrm{c})$$E_{i}^{*}=E_{i}^{*}(x)$.

denote the diagonal matrix$y,$ $y$$(E_{i^{*}})_{yy}=\{$

1 if,otherwise$y\in\Gamma_{i}(x)$$(y\in X)$$0$.

Let $T=T(x)$ denote the subalgebra ofgenerated by $M$ and,,. The algebra is called the Terwifliger algebra of with respectto .
Define operators $L=L(x),$ $F=F(x),$ $R=R(x)$ :$Mat_{X}(\mathrm{c})$$E_{1}^{*},$$\ldots$$T$$E_{D}^{*}$$E_{0}^{*}$$\Gamma$$x$$\acute{L}=\sum_{h=0}^{D}E_{h}*AE^{*}-1h$’$F= \sum_{h=0}^{D}E^{*}hAE_{h}^{*}$,$R= \sum_{h=0}^{D}E_{h1}*+AE_{h}^{*}$

.

95
Then

$A=L+F+R$ .
We refer to $L,$ , andas the lowering matrix, the flat matrix, and theraising matrix with respect to , respectively.
is a semisimple algebra over , so decomposes into the direct sumof full matrix algebras:
$F$

$R$

$x$

$T$

$T$

$\mathrm{C}$$T= \bigoplus_{i=0}^{s}\tau_{i}$,$T_{i}\cong Mat_{n:}(\mathrm{C})$.

For all $i(0\leq i\leq s)$ , letdenote the orthogonal projection of onto .
For more details on semisimple
for example [5].
By Terwilliger [9], for every $i(0\leq i\leq s)$ there exist numbers $r(i),$ $d(i)$such thator $j>r(i)+d(i)$ .
The numbers $r(i)$ and $d(i)$ are called the endpoint and diameter of , respectively.
is said to be thin if
has rank at most 1 for all $j(0\leq i\leq D)$ .
is said to be thin if is thin for all $i(0\leq i\leq s)$ .
The bipartite distance-regular graphs are easily described.
$T$$\varphi_{i}$$T_{i}$$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a},\cdot \mathrm{s}\mathrm{e}\mathrm{e}$$E_{j}^{*}\varphi_{i}=0\Leftrightarrow j<r(i)$$T_{i}$$\Gamma$$T_{i}$$E_{j}^{*}\varphi_{i}$$T_{i}$

Lemma 1 (see for exampfe [3]) Let $\Gamma=(X, R)$ be a distance-regular graphof diameter D. Then the following are equivalent.
(i)$\Gamma$is bipartite.

(ii) $a_{i}=0$ for all $\dot{i}(0\leq i\leq D)$ .
(iii) $F=0$ .

4$\square$

Background

It turns out that the bipartite distance-regular graphs which support a spinmodel are the 2-homogeneous. Thus we will focus on this combinatorialproperty.

Definition 2 Let $\Gamma=(X, R)$ denote a bipartite distance-regular graph ofdiameter $D\geq 3$ and valency $k\geq 3$ . is said to be 2-homogeneous whenever$z\in X$ with $\partial(y, z)=2$ ,for all integers $i(1\leq i\leq D-1)$ and all$\partial(x, y)=i,$ $\partial(x, z)=i$ , the number$\Gamma$

$x,$

$y,$

$\gamma_{i}=|\Gamma 1(y)\cap\Gamma_{1}(Z)\cap\Gamma_{i1}-(X)|$is independent of$x,$ $y,$

$z$

.

96
Theorem 3 (Nomura [7]) Any bipartite distance-regular graph which $\sup-$ports a spin modef is 2-homogeneous.

Theorem 4 (Curtin [4]) Let $\Gamma=(X, R)$ denote a bipartite distance-regulargraph with diameter $D\geq 3$ and valency $k\geq 3$ . Suppose is 2-homogeneous.
Then there exists a real scalar such that$\Gamma$$q$$c_{i}$$b_{i}$$\gamma_{i}$$(0\leq\dot{i}\leq D)$$=$$\frac{(q^{D}+q^{2})}{(q^{D}+q^{2i})}\frac{(q^{2i}-1)}{(q^{2}-1)}$$=$$\frac{(q^{D}+q^{2})(q-Dq.)2i-D}{(q^{D}+q^{2i})(q^{2}-1)}$$=$$c_{D-i}$$=$$\frac{(q^{D}+q^{2})}{(q^{D}+q^{4})}\frac{(q^{D}+q^{2i+2})}{(q^{D}+q^{2i})}$,$(0\leq i\leq D)$,

where we allow the limiting cases$q\vdasharrow\pm 1$$(1 \leq\dot{i}\leq D-1)$,.

This parameterization is equivalent to the 2-homogeneous property.

The operators

5

$R$

and

$L$

Lemma 5 Let $\Gamma=(X, R)$ denote a bipartite distance-regufar graph of diameter $D\geq 3$ and valency $k\geq 3$ . Fix $x\in X.$ Then the following are
equivalent.
(i)$\Gamma$is 2-homogeneous.

(ii) There exist scalars $\gamma_{i}(1\leq i\leq D-1)$ such that
$E_{ii}^{*}LRE^{*}=biE^{*}+(i\mu-\gamma_{i})E_{i}^{*}A_{2}E_{i^{*}}$.

(iii) There exist scalars $\gamma_{i}(1\leq i\leq D-1)$ such that
$E_{i}^{*}RLE_{i}^{*}=C_{i}E^{*}+i\gamma iE_{i}^{*}A2E_{i^{*}}$$(.\mathrm{i}\mathrm{v})RLE_{i}^{*},$$.LRE^{*}i’ E_{i}^{*}$.

are linearly dependent.

Suppose (i) $-(iv)$ hold. Then the scalars
are all equal.

$\gamma_{i}$of 2-homogeneous and$(ii)_{f}(iii)$

97
Proof. (sketch)
For vertices$(\mathrm{i})\Rightarrow(\mathrm{i}\mathrm{i}\mathrm{i})$$y,$ $z\in\Gamma_{i}(x)$consider the$c_{i}$$RL(y, Z)=\{$$\gamma_{i}$

$0$

$z$

$y,$

entry of $RL$ .

if $y=z$ ,if $\partial(y, z)=2$ ,otherwise.

The matrix form of this observation is (iii). Pictorially, we have:$(\mathrm{i}\mathrm{i}\mathrm{i})\Rightarrow(\mathrm{i})$$\partial(y, z)=2$.

$(\mathrm{i})\Leftrightarrow(\mathrm{i}\mathrm{i})$(ii),

Consider the

$y,$

$z$

entry of each side when

Similar.
Clear
Straight forward.

$y,$$z\in\Gamma_{i}(x)$and$(\mathrm{i}\mathrm{i}\mathrm{i})\Rightarrow(\mathrm{i}\mathrm{V})$$(\mathrm{i}\mathrm{v})\Rightarrow(\mathrm{i})$$\square$Observe that $0<\gamma_{i}<\mu$ for all $i(1\leq i\leq D-1)$ .

Lemma 6 Let $\Gamma=(X, R)$ denote a 2-homogeneous bipartite distance-regulargraph with diameter $D\geq 3$ and valency $k\geq 3$ . Fix $x\in X$ . Then
$E_{i}^{*}LRE_{i}*=\sigma_{i}E_{ii^{*}}*RLE+\rho iE_{i}^{*}$

,

where
$\sigma_{i}$$\rho_{i}$Proof.
$j\leq d(i))$,$=$$\frac{(q^{D+2}+q^{2i})}{(q^{Di}+q^{2}+2)}$$=$$\frac{(q^{D}+q^{2})2(q-D2i)q}{q^{D}(q^{2}-1)(qD+q2i+2)}$.

By scaling, we can choose nonzero elements
such that$Rv_{j}=v_{j+1}$) $+j(0\leq$$v_{j}\in\varphi_{i}E_{r(i}^{*}T$.

We show that this is a basis for and describe the action of on thisbasis by induction. Observe that $Lv_{0}=0$ by the definition of endpoint.
Suppose that
$Lv_{j}=xj-1(i)vj-1$ ,$T_{i}$$L$

98
where $\chi_{-1}(i)=0$ .
Now$Lv_{j+1}$$=$$LRE_{i+j}^{*}v_{j}$$=\sigma_{i+j}RLE_{i^{*}jj}v+pi+jEi+jv_{j}+)*$$=\sigma_{i+jx_{j1}(i}-)Rvj-1+\rho_{i+}jvj$$(\sigma_{i+j}\chi j-1(i)+\rho_{i+j})v_{j}$$=$In particular, for every
solution to the recurrence$i,$$Lv_{j+1}$$xj(i)$

is a multiple of$v_{j}$.

. We define$\chi_{j}(i)$to be the$=\sigma_{i+jx(i)}j-1+\rho i+j$$=0$ .

$\chi_{-1}(i)$It is now routine to verify that$\chi_{j}(i)=\frac{(q^{D}+q^{2})2(q^{2}-j+21)(q-Dq^{4i2})+j-D}{(q^{2}-1)^{2}(q^{D}+q^{2})i+2j(q+Dq^{2i+j+2})2}$

is the solution to the recurrence.

$\square$Corollary 7 Referring to Lemma 6:(i)$\Gamma$is thin.

(ii) For every $r(0\leq r\leq\lfloor D/2\rfloor)$ there is a unique(iii) The diameter of$T_{i}$

with $r(i)=r$ .

$T_{i}$

is $d(i)=D-2r(i)$ .

Proof. (sketch)(i) Observe that the form a basis.
only depend upon .
(ii) Observe that the numbers(iii) This is a lower bound for $d(i)$ by Terwilliger ([9]),upper bound since) $+1(j)=0$ .
$v_{j}$$i$$\chi_{j}$$\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{s}\square$is an$\chi_{D-2r(}i$be the unique block with endpoint . Then$v_{D-2r}$ such that

Corollary 8 Let$v_{0},$$v_{1_{f}}\ldots,$$T_{r}$$r$$Lv_{j}$$Rv_{j}$,$=c_{j+1}(r)v_{j+}1$ ,$=b_{j-1}(r)vj-1$

where
,

$c_{j}(r)$$=$$\frac{(q^{r}(q^{2}+q)D(q2j-1)}{(q^{D}+q^{2j}r)+2(q^{2}-1)}$$b_{j}(r)$$=$$\frac{(q^{D}+q^{2})(q^{D}-q-D)4r+2j}{q^{r}(q^{D}+q^{2}r+2j)(q^{2}-1)}$.

$T_{r}$

has basis

99
Proof. This is just a rescaling of the basis of Lemma 6.
preserves $LRv_{j}=\chi_{j-1}(r)vj,$ $Lv_{0}=0$ , and $Rv_{d(r)}+r=0$ .

$\mathrm{O}\mathrm{b}\mathrm{s}\mathrm{e}_{\square }\mathrm{r}\mathrm{v}\mathrm{e}$that itA simple consequence of this corollary is the following.

Theorem 9 The Terwilliger algebra of any 2-homogeneous bipartite distanceregular graph is a quantum Lie algebra with respect to the operators$L_{f}F_{f}$

and

$R$

.

We conjecture that the Terwilliger aigebra of any distance-regular graphwhich supports a spin model has a similar structure.
Let us conclude with an observation about the numbers
and.
$c_{i}(r)$Lemma 10 Fix $r(0\leq r\leq d)$ . Let$d=d(r)=D-2r$ .

$b_{0}(r)$$b_{i}(r)+ci(r)$$b_{d-i}(r)$$c_{0}(r)$$b_{d}(r)$$\theta_{r}$$b_{i}(r)$be the $r^{th}eigenvalue_{f}$ and write$=\theta_{r}$,,$=c_{i}(r)$ ,$=0$ ,$=b_{0}(r)$$=0$ .

Proof. (sketch)
Compare the various formulas in for the quantities involved.
$q$$\square$

These conditions satisfied by the intersection numbers with $d=D$ . In
fact, $c_{j}(0)=c_{j},$ $b_{j}(0)=b_{j}$ .

References[1] E. Bannai and T. Ito. Algebraic Combinatorics I.. Association Schemes.
Lecture Note 58. The
Publishing Company, Inc.,
Menlo Park, 1984.
$\mathrm{B}\mathrm{e}\mathrm{n}\mathrm{j}\mathrm{a}\mathrm{m}\mathrm{i}\mathrm{n}/\mathrm{C}\mathrm{u}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}$[2] A. E. Brouwer, A. M. Cohen, and A. Neumaier.
Graphs. Springer-Verlag, New York, 1989.

Distance-Regular[3] B. Curtin. Bipartite distance-regular graphs (65 pages). submitted, 1995.
[4] B. CuTtin. -Homogeneous bipartite distance-regular graphs (49 pages).
preprint, 1996.
$2$

100
[5] C. W. Curtis and I. Reiner. Representation theory of finite groups andassociative algebras. Interscience, New York, 1962.
[6] F. Jaeger, M. Matsumoto, and K. Nomura. Bose-Mesner algebras relatedwith type II matrices and spin mode.ls. Preprint, 1995.
[7] K. Nomura. Spin m,odels on bipartite distance-regular graphs. J. Combin. Theory Ser. B, $64(2):300-313$ , 1994.
[8] K. Nomura. An algebra associated with a spin model. Journal of Algebraic Combinatorics, 1996.
[9] P. Terwilliger. The subconstituent algebra of an association scheme (partI). Journal of A lgebraic Combinatorics, 1 (4):363-388, 1992.

[10] P. Terwilliger. The subconstituent algebra of an association scheme (partII). Journal of Algebraic Combinatorics, $2(1):73-103$ , 1993.
[11] P. Terwilliger. The subconstituent algebra of an association scheme (partIII). Journaf of Algebraic Combinatorics, 2(2):177-210, 1993.