数理解析研究所講究録
第 1926 巻 2014 年 132-139

132

On a Characterization of the Bilinear Forms Graphs$Bil_{q}(d\cross d)$Alexander L. Gavrilyuk, Jack H. Koolen

June 10, 2014

Introduction

1

Much attention has been paid to a problem of classification of all -polynomial distance-regulargraphs with large diameter [1] (for the definitions, we refer the reader to Section 2). One of the steps
towards solution of this problem is a characterization of known distance-regular graphs by theirintersection arrays. For the current status of the classification of the -polynomial distance-regulargraphs, we refer the reader to the survey paper [3] by Van Dam, Koolen and Tanaka.
$Q$

$Q$

-matrices
The bilinear forms graph denoted here by $Bil_{q}(d\cross n)$ is a graph defined on the set ofwith two matrices being adjacent if and only if the rank of their diﬀerence is 1. We referover
to [2, Chapter 9. $5.A$ ] for the detailed description of these graphs.
$d\cross n$$\mathbb{F}_{q}$In 1999, K. Metsch [5] obtained the following result.

Result 1.1 The bilinear forms graph $Bil_{q}(d\cross n)$ is characterized by its intersection array if:$\bullet$$q=2$ and $n\geq d+4,$$\bullet$$q\geq 3$

and $n\geq d+3.$

Thus, the open cases are:$\bullet$$q=2$ and $n\in\{d, d+1, d+2, d+3\},$$\bullet$$q\geq 3$

and $n\in\{d, d+1, d+2\}.$In this paper, we discuss a problem of characterization of the bilinear forms graphs $Bil_{q}(d, d)$ ,$d\geq 3$ , by their intersection arrays.

133This paper is based on a talk given at RIMS, and describes a sketch of the proof of our main result(see Section 3). The details of the proof will be given elsewhere.

2

Definitions and preliminaries

All the graphs considered in this paper are finite, undirected and simple. Suppose that is aconnected graph with vertex set
and edge set, whereconsists of unordered pairs ofadjacent vertices. The distance $d(x, y)$ between any two verticesof is the length of a shortest
path connecting and in$\Gamma$$V(\Gamma)$$E(\Gamma)$$E(\Gamma)$$\Gamma$$x,$ $y$$x$$\Gamma.$$y$

For a subset $X$ of the vertex set of , we will also w1ite $X$ for the subgraph of induced by $X.$
For a vertex $x\in V(\Gamma)$ , define
to be the set of vertices which are at distance precisely from$x(0\leq i\leq D)$ , where $D$ $:= \max\{d(x, y)|x, y\in V(\Gamma)\}$ isthe diameter of . In addition, define$\Gamma_{-1}(x)=\Gamma_{D+1}(x)=\emptyset$ .
The subgraph induced byis called the neighborhood or the local
graph of a vertex . The ball of radius 1 around is denoted by, i.e. $x^{\perp}=\{x\}\cup\Gamma_{1}(x)$ . We
write
instead offor short, and we denote $x\sim ry$ or simply $x\sim y$ if two vertices andare adjacent in . For a graph , a graph is called locally if any local graph of is isomorphic
to $G.$$\Gamma$$\Gamma$$\Gamma_{i}(x)$$i$$\Gamma$$\Gamma_{1}(x)$$x$$x^{\perp}$$x$$\Gamma(x)$$\Gamma_{1}(x)$$x$$\Gamma$$G$

For a set of vertices , . . . ,distance 2 in , we call
$x_{1}$$\Gamma$$x_{n}$, let$\Gamma(x, y)$$G$$\Gamma$$\Gamma(x_{1}, \ldots, x_{n})$the -graph of$\mu$denote$\bigcap_{i=1}^{n}\Gamma_{1}(x_{i})$$y$$\Gamma$. Moreover, if

$x$

and

$y$

are at$x,$ $y.$

The eigenvalues of a graph are the eigenvalues of its adjacency matrix (recall that they are algebraic
integers). If, for some eigenvalue of , its eigenspace contains a vector orthogonal to the all ones
vector, we say the eigenvalue is non-principal. If is regular with valency then all its eigenvalues
are non-principal unless the graph is connected and then the only eigenvalue that is principal is its
valency$\Gamma$$\eta$$\Gamma$$k$$\eta$$k.$

For a graph.

$\Gamma$and its vertex$x$, we say that$\eta$

is a local eigenvalue at

$x$

, if

$\eta$

is an eigenvalue of$\Gamma_{1}(x)$A connected graphwith diameter $D$ is called distance-regular if there exist integers$(1\leq i\leq D)$ such that, for any two vertices $x,$ $y\in V(\Gamma)$with $d(x, y)=i$ , there are precisely
neighbors of inand neighbors of in. In particular, any distance-regular graphis regular with valency $:=b_{0}$ . We define$:=k-b_{i}-c_{i}$ for notational convenience and notethat $a_{i}=|\Gamma(y)\cap\Gamma_{i}(x)|$ holds for any two vertices $x,$ with $d(x, y)=i(1\leq i\leq D)$ . The arrayis called the intersection array of the distance-regular graph$\Gamma$$b_{i-1},$$c_{i}$$c_{i}$$\Gamma_{i-1}(x)$$y$$b_{i}$$y$$\Gamma_{i+1}(x)$$k$$a_{i}$$y$$\{b_{0}, b_{1}, .

.

.

, b_{D-1};c_{1}, c_{2}, .

.

.

, c_{D}\}$$\Gamma.$A distance-regular graph with diameter 2 is called a strongly regular graph. We say that a strongly
regular graph has parameters, if $v=|V(\Gamma)|,$ is its valency, $:=a_{1}$ , and $:=c_{2}.$$\Gamma$$(v, k, \lambda, \mu)$$k$$\lambda$$\mu$

If a graph$x,$ $y\in V(\Gamma)$

is distance-regular then, for all integers
with $d(x, y)=h$ , the number$\Gamma$$h,$ $i,$$j(0\leq h, i, j\leq D)$ ,$p_{ij}^{h}:=|\{z\in V(\Gamma)|d(x, z)=i, d(y, z)=j\}|$and all vertices

134
does not depend on the choice of$a_{i}=pi_{i}$ , andNote that$x,$ $y$$c_{\eta}=p_{1i-1}^{i},$. The numbers

are called the intersection numbers of$p_{ij}^{h}$$\Gamma.$$b_{i}=p_{1i+1}^{i}.$For each integer $i(0\leq i\leq D)$ , the ith distance matrix
the vertex of , and, for any $x,$ $y\in V(\Gamma)$ ,$A_{i}$

of$\Gamma$

has rows and columns indexed by$\Gamma$$(A_{i})_{x,y}=\{\begin{array}{l}1 if d(x, y)=i,0 if d(x, y)\neq i.\end{array}$

Then $A:=A_{1}$ is just the adjacency matrix of$\Gamma,$$A_{0}=I,$ $A_{i}^{T}=A_{i}(0\leq i\leq D)$$A_{i}A_{j}= \sum_{h=0}^{D}p_{ij}^{h}A_{h} (0\leq i,j\leq D)$

, and

,

in particular,$A_{1}A_{i}=b_{i-1}A_{i-1}+a_{i}A_{i}+c_{x+1}A_{i+1} (1\leq i\leq D-1)$,$A_{1}A_{D}=b_{D-1}A_{D-1}+a_{D}A_{D},$and this implies that $A_{i}=p_{i}(A_{1})$ for certain polynomial$p_{i}$of degree$i.$over . It follows thatof is a matrix algebra generated by
The Bose-Mesner algebra$A_{0}=I,$, which form a,...,ofmatrices
the
set
$D+1$
by
spanned,and it ishas dimension
basis of$\mathcal{M}$$\mathbb{C}$$A_{1}$$\Gamma$$\mathcal{M}$$A_{D}$$A_{1}$$\mathcal{M}.$

Since the algebra
idempotents$\mathcal{M}$also has a basis of pairwise orthogonal
is semi-simple and commutative,):(the so-called primitive idempotents of,...,$\mathcal{M}$$\mathcal{M}$$E_{D}$$E_{0}:= \frac{1}{|V(\Gamma)|}J,$ $E_{1}$$E_{i}E_{j}=\delta_{ij}E_{i}(0\leq i,j\leq D) , E_{i}.=E_{i}^{T}(0\leq i,j\leq D)$,$E_{0}+E_{1}+\ldots+E_{D}=I,$

where

$J$

is the all ones matrix.

In fact, $E_{j}(0\leq j\leq D)$ is the matrix representing orthogonal projection onto the eigenspace ofcorresponding to some eigenvalue of . In other words, one can write$A_{1}$$\Gamma$$A_{1}= \sum_{j=0}^{D}\theta_{j}E_{j},$where $\theta_{j}(0\leq j\leq D)$ are the real and pairwise distinct scalars, known as the eigenvalues of . We
say that the eigenvalues are in natural order if $b_{0}=\theta_{0}>\theta_{1}>\ldots>\theta_{D}$ . We denote$\Gamma$$\hat{\theta}_{i}=-1-\frac{b}{\theta_{i}+}\overline{1}$for $i\in\{1, D\}.$is also closed under entrywise (Hadamard or Schur) matrix multipliThe Bose-Mesner algebrawith, . . .,
are the primitive idempotents ofcation, denoted by . Then the matrices$\sum_{i=0}^{D}A_{i}=J$. This implies that, andrespect to , i.e.,$\mathcal{M}$$A_{0},$$0$$\circ$$A_{1}$$A_{D}$$A_{i}\circ A_{j}=\delta_{ij}A_{i}$$E_{i} \circ E_{j}=\sum_{h=0}^{D}q_{ij}^{h}E_{h} (0\leq i,j\leq D)$$\mathcal{M}$135holds for some real numbers$q_{ij}^{h}$, known as the Krein parameters of$\Gamma.$Let be a distance-regular graph, and $E$ be a primitive idempotent of its Bose-Mesner algebra.
The graphis called -polynomial (with respect to $E$ ) if there exist real numbers$(1\leq i\leq D)$ and an ordering of primitive idempotentssuch thatand $E_{1}=E$ , and$\Gamma$$\Gamma$$Q$$c_{i}^{*},$$a_{i}^{*},$$b_{i-1}^{*}$$E_{0}= \frac{1}{|V(\Gamma)|}J$$E_{1}\circ E_{i}=b_{i-1}^{*}E_{i-1}+a_{i}^{*}E_{i}+c_{i+1}^{*}E_{i+1} (1\leq i\leq D-1)$,$E_{1}\circ E_{D}=b_{D-1}^{*}E_{D-1}+a_{D}^{*}E_{D}.$Note that aordering.

$Q$-polynomial ordering of the eigenvalues/idempotents does not have to be the natural

Further, the dual eigenvalues ofassociated with $E$ are the real scalars$\Gamma$$\theta_{i}^{*}(0\leq i\leq D)$

defined by$E= \frac{1}{|V(\Gamma)|}\sum_{i=0}^{D}\theta_{i}^{*}A_{i}.$We say that a distance-regular graph has classical parameters, and the intersection numbers of satisfy$\Gamma$$D$$(D, b, \alpha, \beta)$

if the diameter of$\Gamma$is$\Gamma$$c_{i}=\{\begin{array}{l}i1\end{array}\}(1+\alpha\{\begin{array}{l}i-11\end{array}\})$,(1)

so that, in particular, $c_{2}=(b+1)(\alpha+1)$ ,$b_{i}=(\{\begin{array}{l}D1\end{array}\}-\{\begin{array}{l}i1\end{array}\})(\beta-\alpha\{\begin{array}{l}i1\end{array}\})$

,

(2)

where
$\{\begin{array}{l}j1\end{array}\}:=1+b+b^{2}+\ldots+b^{j-1}.$

The following important fact about

Result 2.1 Let

be a

$Q$

-polynomial distance-regular graphs was proven in [7].

-polynomial distance-regular graph with diameter $D\geq 3$ . Then, for anyof degree 4 such that, for any vertex $x\in V(\Gamma)$
and any non-principal eigenvalue of the local graph of $x,$
holds. The polynomials$i=2$ , . . . , $D-1$ , diﬀer only in a scalar multiple.
$\Gamma$$Q$$i=2$ , . . . , $D-1$ , there exists a polynomial$T_{i}$$T_{\iota’}(\uparrow 7)\geq 0$$\eta$$T_{i},$

We call these polynomials the Terwilliger polynomials of F. The existence of these polynornials
was calculated explicitly.

was established in [7]. In [4], the polynomial$T_{2}$

136
Result 2.2 Suppose that$T_{2}(\lambda)$of$\Gamma$$\Gamma$

has classical parameters$(D, b, \alpha, \beta)$. Then the Terwilliger polynomialis$T_{2}( \lambda)=\frac{b_{2}}{\alpha+1}(-\lambda^{2}+\lambda(\alpha\{\begin{array}{l}D1\end{array}\}+\beta-\alpha-1-(\alpha+1)(b+1))+\beta\{\begin{array}{l}D1\end{array}\}-(\alpha+1)(b+1))\cross$$\cross(\lambda^{2}+\lambda(2-\alpha b)-\alpha b+1)-b_{2}^{2}(\lambda+1)^{2}$

Furthermore, the roots of$T_{2}(\lambda)$

.

(3)

are

$\beta-\alpha-1, -1, -b-1, \alpha b\frac{b^{D-1}-1}{b-1}-1.$

Note that the bilinear forms graph $Bil_{q}(d\cross n)$ , $n\geq d$ , has classical parameters $(D, b, \alpha, \beta)=$$(d, q, q-1, q^{n}-1)$ . In particular, if
is a distance-regular graph with the same intersection array$d\geq3$$x\in V(\Gamma)$ and any non-principal eigenvalue$Bil_{q}(d\crossd)$of the local
then,
any
,
,
for
vertexasgraph of , one has:$\eta\in[-q-1, -1]$ or $\eta=q^{n}-q-1$ ,(4)$\Gamma$$\eta$$x$3

Main result

In this section, we suppose that
$Bil_{2}(d\cross d)$ , $d\geq 3.$$\Gamma$

is a distance-regular graph with the same intersection array as

Proposition 3.1 The local graph of any vertex

$x$

of

$\Gamma$is the $(2^{d}-3)\cross(2^{d}-3)$ -grid.

Proof: By (4), for $q=2$ , a local non-principal eigenvalue$\eta\in[-3, -1]$

Claim 3.2$\Gamma_{1}(x)$$\eta$

at any vertex$x\in\Gamma$

satisfies:

or $\eta=2^{d}-3.$

has only integral eigenvalues, i. e., $-3,$ $-2,$ $-1$ , or $2^{d}-3.$

Proof: Recall that the eigenvalues of a graph are algebraic integers, and their product is an integer.
is an integer,. Then $\eta_{i}\in(-3, -1)$ and
Let , . . . , be all irrational eigenvalues ofand thus
is an integer. Now $\eta_{i}\in(-3, -1)\Rightarrow|\eta_{i}+2|<1\Rightarrow\Pi_{i=1}^{s}(\eta_{i}+2)=0$ . The
claim is proved.
$\Gamma_{1}(x)$$\eta_{s}$$\eta_{1}$$\Pi_{i=1}^{s}(\eta_{i}+2)$

Claim 3.3$\Gamma_{1}(x)$has spectrum $2(2^{n}-2)^{1},$ $(2^{n}-3)^{2(2^{n}-2)},$ $(-2)^{(2^{n}-1)^{2}}$$\Pi_{i=1}^{s}\eta_{i}$

137
,...,
be thebe its adjacency matrix. Then:

Proof: Recall the following basic fact from algebraic graph theory. Let
spectrum of a regular (with valency k) graph on$v$

vertices, and$A$$\theta_{0}^{m_{0}},$$\theta_{1}^{m_{1}}$$\sum_{i=0}^{s}m_{i}=v, tr(A)=\sum_{i=0}^{s}m_{i}\theta_{i}=0, tr(A^{2})=\sum_{i=0}^{s}m_{i}\theta_{i}^{2}=vk$

where we may put
Apply this fact to$\theta_{0}=k$$\Gamma_{1}(x)$$\theta_{s}^{m_{s}}$(5),and, moreover, $m_{0}=1$ if the graph is connected.

. In our notation:$b_{0}=v=(2^{n}-1)^{2}, \theta_{0}=k=a_{1}=2(2^{n}-2)$ ,$\theta_{1}=2^{n}-3, \theta_{2}=-1, \theta_{3}=-2, \theta_{4}=-3,$

andis connected).

$m_{1},$ $m_{2},$ $m_{3},$ $m_{4}$are unknown multiplicities of$\theta_{1},$$\theta_{2},$$\theta_{3},$$\theta_{4}$, respectively, while $m_{0}=1$ (asThen (5) gives a system of (three) linear equations with respect to (four) unknowns
One can show that this system has the only non-negative integral solution:$m_{1}$$\Gamma_{1}(x)$,...,$m_{4}.$$m_{1}=2(2^{n}-2) , m_{2}=0, m_{3}=(2^{n}-1)^{2}, m_{4}=0,$

which shows the claim,
We now see thatis a regular graph with exactly 3 distinct eigenvalues. This yields thatis a strongly regular graph with smallest eigenvalue $-2$ . It now easily follows from Seidel’s classification of strongly regular graphs with smallest eigenvalue $-2$ , see [9], thatis a$\Gamma_{1}(x)$$\Gamma_{1}(x)$$\Gamma_{1}(x)$$(2^{d}-3)\cross(2^{d}-3)$ -grid.

1

Lemma 3.4 For every pair of vertices $x,$
is a 6-gon.

$y\in\Gamma$

with $d(x, y)=2$ , the induced subgraph$\Gamma(x)\cap\Gamma(y)$Proof: The lemma easily follows from Proposition 3.1 and the fact that $c_{2}=6$ .
We now see that$\Gamma$

1

has the same local graphs as $Bil_{2}(d\cross d)$ .

$x\in\Gamma$ ,Letdenote the bilinear forms graph $Bil_{2}(d\cross d)$ . For vertices
an isomorphism, mapping::is called extendable if there is a bijection
say
that
).
We
(in this caseedges to edges, such thatis called the extension of$\Gamma(x,y)=\Gamma(x,z)$$z\in\Gamma_{2}(x)$implies $y=z$ . This property yields thathas distinct -graphs if
for $y,$the extension
above is unique.
$x\in \mathcal{H},$$\mathcal{H}$$x^{\perp}arrow x^{\perp}$$\varphi’$$\varphi$$\varphi’|_{x^{\perp}}=\varphi$$x^{\perp}\cup \mathcal{H}_{2}(x)arrow x^{\perp}\cup\Gamma_{2}(x)$$\Gamma$$\varphi’$$\varphi$$\mu$$\varphi’$A graphis called triangulable if every cycle in it can be decomposed into a product of triangles(see [6, Section 6$\triangle$

For the following result, see [6, Theorem 7.1].

138
Result 3.5 Assume:(1)$\Gamma$

has distinct$\mu$-graphs.

(2) There exist a vertex

$x$

of

$\mathcal{H}$and a vertex(3) If $x,$ are vertices of, respectively,
extension, and, then$x$$\mathcal{H},$$\Gamma$$w\in \mathcal{H}(x)$(4)$\mathcal{H}$

Then

$x$

$\varphi’|_{w^{\perp}}:$$\varphi$of , and an extendable isomorphism$\Gamma$:$x^{\perp}arrow x^{\perp}is$$w^{\perp}arrow\varphi(w)^{\perp}is$$\varphi$:$x^{\perp}arrow x^{\perp}.$an extendable isomorphism,$\varphi’$is itsextendable.

is triangulable.
$\Gamma$

is covered byIndeed, since$\Gamma$and$\mathcal{H}.$$\mathcal{H}$have the same intersection arrays, Result 3.5 implies that

It is not diﬃcult to see that$\Gamma$$\Gamma\cong \mathcal{H}.$satisfies Conditions (1) and (4) of Result 3.5.

$:=\{w_{ij}\}_{i,j}$ , and, as usually, for distinct pairs $(i,j)$ and $(i’,j’)$ ,Let
holds if andonly if $i=i’$ or $j=j’$ . Denote by
the maximal clique ofthat contains the vertices
forall , and by
the maximal clique ofthat contains the vertices
for all . For a vertex
denotes $\{x\}\cup\Gamma(x)$ .
$\Gamma(x)$$w_{ij}\sim w_{i’j’}$$L_{i}$$j$$x\in\Gamma,$$\Gamma(x)$$\Gamma(x)$$L_{j}^{T}$$w_{ij}$$i$$w_{ij}$$x^{\perp}$

Without loss of generality, we may assume that there is a vertex $z\in\Gamma_{2}(x)$ such that. Define a subgraph induced in by the vertex subset$L_{1}\cup L_{2}\cup L_{3}$$\Sigma$$\Gamma(x, z)\subset$$\Gamma$$\{x\}\cup L_{1}\cup L_{2}\cup L_{3}\cup\{z’\in\Gamma_{2}(x)|\Gamma(x, z’)\subset L_{1}\cup L_{2}\cup L_{3}\},$

so that $\Sigma(x)=L_{1}\cup L_{2}UL_{3}.$In order to show that

Lemma 3.6$\Sigma$$\Gamma$satisfies Conditions (2) and (3) of Result 3.5, one has to show the following.

is isomorphic to $Bil_{2}(2, d)$ .

The main result of this work is the following theorem.

Theorem 3.7 The bilinear forms graphs $Bil_{2}(d, d)$ , $d\geq 3$ , are uniquely determined by their intersection arrays.

Acknowledgements. Part of this work was done while the first author was visiting Tohoku
University as a JSPS Postdoctoral Fellow.

139
References[1] Bannai E., Ito T. Algebraic combinatorics. I. Association schemes. The Benjamin/Cummings
Publishing Co., Inc., Menlo Park, CA, 1984. $xxiv+425$ pp.
[2] Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Ergebnisse der Mathematik
und ihrer Grenzgebiete, (3), 18. Springer-Verlag, Berlin, 1989. $xviii+495$ pp.

[3] Van Dam E., Koolen J.H., Tanaka H. Distance-regular graphs. Preprint, August 2013 version.
[4] A.L. Gavrilyuk, J.H. Koolen, The Terwilliger polynomial of a -polynomial distance-regulargraph and its application to the pseudo-partition graphs//arXiv:1403.4027.
$Q$[5] Metsch K. On a characterization of bilinear forms graphs. European J. Combin., 20(4):293-306,

1999.
[6] A. Munemasa, S.V. Shpectorov, “A local characterization of the graphs of alternating forms
Finite geometry and combinatorics, 1993. P. 289-302[7] Terwilliger P. Lecture note on Terwilliger algebra (edited by H. Suzuki), 1993.
[8] Terwilliger P. The subconstituent algebra of an association scheme, I. J. Algebraic Combin.,$1(4):363-388$ , 1992.

[9] Seidel J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3. Lin.
Alg. Appl., 1:281-298, 1968.

ALG:
Research Center for Pure and Applied Mathematics, Graduate Sch6o1 of Information Sciences,
Tohoku University, Sendai 980-8579, JAPANand
N.N. Krasovsky Institute of Mathematics and Mechanics UB RAS,
Kovalevskaya str., 16, Ekaterinburg 620990, RUSSIA-mail address: alexander.gavriliouk@gmail.com
$E$

JHK:
School of Mathematical Sciences
University of Science and Technology of China, Hefei, 230026, Anhui, PR CHINA-mail address: koolen@ustc.edu.cn$E$