\documentclass{article}
\usepackage{a4wide}
\usepackage{amstex}
\usepackage{epsfig}

\begin{document}

\newenvironment{proof}[0]{{\bf Proof:}}{\rule{2.5mm}{2.5mm}.}
\newtheorem{theorem}{\bf Theorem}[section]
\newtheorem{lemma}{{\bf Lemma}}
\newtheorem{Proposition} {Proposition}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\fsA}{{\cal A}}
\newcommand{\Rr}{{\Bbb R}}
\newcommand{\rk}{{\rm rk}}
\newcommand{\tr}{{\rm tr}}

\title{The spectrum of the second subconstituent of the bilinear forms graph
$H_q(d,e)$ }

\author{Andries Brouwer \\ Remko Riebeek}
\maketitle

\begin{abstract}
In this article we compute the spectrum of the second subconstituent of the bilinear forms graph by turning it into a scheme with 23 relations, that can be refined to an association scheme.
\end{abstract}

\section{Introduction}

Hobart and Ito asked for the spectrum of the second subconstituent of the bilinear forms graph $H_q(d,e)$.

$H_q(d,e)$ has as vertices the bilinear forms $\{f | f: V \times W \rightarrow {\Bbb F} \}$, where ${\Bbb F} = {\Bbb F}_q$ is the field with $q$ elements, $V$ is an $e$-dimensional vector space over ${\Bbb F}_q$ and $W$ a $d$-dimensional vector space over ${\Bbb F}_q$. Two forms are defined to be adjacent if their difference has rank one. This graph is distance-regular. More details can be found in \cite{BCN}, Section 9.5A. A better suited description for us is the following geometric one.

Take a $(d+e)$-dimensional vector space $Y$ over the field ${\Bbb F}_q$ with a fixed $d$-dimensional subspace $U$. The vertices of $H_q(d,e)$ are the $e$-dimensional subspaces disjoint from $U$. Two vertices are adjacent if and only if they have an intersection of dimension $e-1$. Now fix a vertex. The second subconstituent is the induced graph on the vertices at distance two from this fixed vertex.

The adjacency matrix of a graph is the square $0/1$-matrix of order the number of vertices, that has a $1$ as $(x,y)$-entry if and only if $x$ and $y$ are adjacent. The spectrum of a graph is the spectrum of the adjacency matrix of the graph.

We shall compute the spectrum of the second subconstituent of $H_q(d,e)$.

Hobart and Ito already obtained the following partial results:
\vspace*{5mm}

\begin{tabular}{ll}
eigenvalue & multiplicity \\
$(q+1)(q^e+q^d-q^2-q-1)$ & 1 \\
$(q+1)(q^e-q^2-1)+q^d-q^2$ & $(q^d-q)/(q-1)$\\
$(q+1)(q^d-q^2-1)+q^e-q^2$ & $(q^e-q)/(q-1)$\\
$q^e+q^d-q^2-2q-1$ & $(q^e-1)(q^d-1)(q-2)/(q-1)^2$ \\
$q^e+q^d-q^2-q-2$ & $(q^e-q)(q^d-q)/(q-1)^2$ \\
$q^e+q^d-q^3-2q^2-1$ & $(q^e-q)(q^d-q)/(q-1)^2$ \\
\end{tabular}

\vspace*{5mm}
\noindent
This is in perfect accordance with our results.

\section{Results} \label{results}

The second subconstituent of $H_q(d,e)$ has the following spectrum:\\

\begin{tabular}{ll}
eigenvalue & multiplicity \\
$(q+1)(q^e+q^d-q^2-q-1)$ & 1 \\
$q^{e+1}+q^e-q^3-q^2-q-1$ & $(q^d-1)(q^d-q^3)/(q(q+1)(q-1)^2)$ \\
$q^{d+1}+q^d-q^3-q^2-q-1$ & $(q^e-1)(q^e-q^3)/(q(q+1)(q-1)^2)$ \\
$q^{e+1}+q^e+q^d-q^3-2q^2-q-1$ & $(q^d-q)/(q-1)$ \\
$q^{d+1}+q^d+q^e-q^3-2q^2-q-1$ & $(q^e-q)/(q-1)$ \\
$q^d-q^2-q-1$ & $(q^e-q^2)\alpha$ \\
$q^e-q^2-q-1$ & $(q^d-q^2)\alpha$ \\
$q^d-q^3-q^2-1$ & $(q^e-1)(q^e-q^3)(q^d-q)/(q(q-1)^3(q+1))$ \\
$q^e-q^3-q^2-1$ & $(q^d-1)(q^e-q)(q^d-q^3)/(q(q-1)^3(q+1))$ \\
$q^e+q^d-q^2-2q-1$ & $(q^e-1)(q^d-1)(q-2)/(q-1)^2$ \\
$q^e+q^d-q^3-2q^2-1$ & $(q^d-q)(q^e-q)/(q-1)^2$ \\
$q^e+q^d-q^2-q-2$ & $(q^d-q)(q^e-q)/(q-1)^2$ \\
$-q^3-1$ & $\frac{(q^d-1)(q^e-1)(q^d-q^3)(q^e-q^3)}{((q-1)^4q^2(q+1)^2)}$ \\
$-q^2-1$ & $\frac{(q-2)(q^d-q^2)(q^e-q^2)(q^e-1)(q^d-1)}{((q-1)^4q^2)}$ \\
$-q^2-q$ & $\frac{(q^d-q^2)(q^e-q^2)(q^d-q)(q^e-q)}{((q+1)^2(q-1)^4)}$ \\
$-q-1$ & $\beta$ \\
\end{tabular}\\

\vspace*{5mm}
\noindent
, where $\alpha = \\
(q^{d+e+2}-2q^{d+e}-2q^{e+2}+q^{e+1}+2q^e-2q^{d+2}+q^{d+1}+2q^d+q^3+q^2-q-2)/\\
((q-1)^3(q+1)q)$,\\
 and $\beta$ is the number of vertices minus the sum of the other multiplicities.

Notice that in the cases that $q=2$, $d=2$, $d=3$, $e=2$, or $e=3$, some eigenvalues come with multiplicity zero. In the case that $d=e$ some eigenvalues will collapse.
The construction of the scheme below shows the reason for both these behaviours.

\section{The 23-Class Scheme}

Let $Y$ be, as in the geometric description above, a $(d+e)$-dimensional space
over ${\Bbb F}_q$, $U$ a $d$-dimensional subspace, and $V$ a fixed vertex, that
is an $e$-dimensional subspace disjoint from $U$. The vertices of the graph under
examination are the $e$-dimensional subspaces of $Y$ disjoint from $U$, and with
intersection of dimension $(e-2)$ with $V$ (see Figure 1).

\begin{figure}
\begin{center}
\epsfig{file=realfig.eps, height=4cm}
\caption{$W$ is a vertex of $H_q(d,e)$}
\end{center}
\end{figure}

We want to construct a distance distribution diagram. Hereto we fix a vertex $W$. Let $P$ be (the $(e-2)$-dimensional subspace) $V \cap W$.
For a subspace $X$, we mean by saying $X$ {\em modulo} $P$, $(X+P)/P$, the quotient space spanned by $X$ and $P$, divided out by $P$.

When we look at $Y$ modulo $P$ (see Figure 2), we see that $U$ is a $d$-dimensional subspace, that $V+W$ is a four-dimensional subspace and that $U$ meets $V+W$ in a two-dimensional subspace, and that $V$ and $W$ are also two-dimensional subspaces in $V+W$. 
Now remember that if we take three pairwise skew lines in $PG(3,q)$ we have a uniquely determined regulus and opposite regulus, together forming a grid of $(q+1)^2$ points. This grid of $(q+1)^2$ points is the grid that is mentioned below.

\begin{figure}
\begin{center}
\epsfig{file=modulofig.eps, height=4cm}
\caption{Modulo $P$ the picture looks like this}
\end{center}
\end{figure}

We consider $Y$ as the projective space $PG(d+e-1,q)$. All dimensions are vector space dimensions. So two-dimensional spaces are lines, three-dimensional spaces are planes, etcetera.

Now we describe the 23 relations that will form our scheme.
These relations consist of the pairs of vertices $(W,X)$ such that:

\begin{enumerate}

\item $X=W$

\item dim($X \cap W$) = $e-1$, dim($X \cap V \cap W$) = $e-2$. Modulo $P$, $X$ is a line in $V+W$ secant to the grid (meeting $W$).
\item dim($X \cap W$) = $e-1$, dim($X \cap V \cap W$) = $e-2$. Modulo $P$, $X$ is a line in $V+W$ tangent to the grid (meeting $W$).
\item dim($X \cap W$) = $e-1$, dim($X \cap V \cap W$) = $e-2$. Modulo $P$, $X$ is a line that meets $V+W$ in one point only (on $W$).

\item dim($X \cap W$) = $e-1$, dim($X \cap V \cap W$) = $e-3$. (Then, modulo $P$, $X$ is a plane in $V+W$ meeting the grid in two intersecting lines, one of which is $W$.)

\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-2$.  Modulo $P$, $X$ is a line of the grid in $V+W$ (not meeting $W$).
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-2$.  Modulo $P$, $X$ is a secant to the grid (not meeting $W$).
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-2$.  Modulo $P$, $X$ is a tangent to the grid (not meeting $W$, but in $V+W$).
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-2$.  Modulo $P$, $X$ is a line in $V+W$ missing the grid.
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-2$.  Modulo $P$, $X$ is a line that meets $V+W$ in one point and in the grid (not on $W$).
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-2$.  Modulo $P$, $X$ is a line that meets $V+W$ in one point not in the grid.
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-2$.  Modulo $P$, $X$
 is a line completely outside $V+W$.

\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$
 is a plane in $V+W$ meeting the grid in two lines ($W$ is not one of them).
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$
 is a plane in $V+W$ meeting the grid in a conic.
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$ is a plane that meets $V+W$ in a line that is a line of the grid (meeting $V$ and $W$).  
\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$ is a plane that meets $V+W$ in a line that is a secant to the grid (and meets both $V$ and $W$).

\item dim($X \cap W$) = $e-2$, dim($X \cap V \cap W$) = $e-4$. (Then modulo $P$, $X$ equals $V+W$).

\item dim($X \cap W$) = $e-3$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$ is a plane that meets $V+W$ in a line that is a secant to the grid, through $V$ and $U \cap (V+W)$.
\item dim($X \cap W$) = $e-3$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$ is a plane that meets $V+W$ in a line that is a secant to the grid, through $V$, not through $U \cap (V+W)$.
\item dim($X \cap W$) = $e-3$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$
is a plane that meets $V+W$ in a line that is a tangent to the grid, through $V$.
\item dim($X \cap W$) = $e-3$, dim($X \cap V \cap W$) = $e-3$.  Modulo $P$, $X$ is a plane that meets $V+W$ in a point (of $V$).

\item dim($X \cap W$) = $e-3$, dim($X \cap V \cap W$) = $e-4$ (Then modulo $P$, $X$ is a 4-space meeting $V+W$ in a plane through $V$). 

\item dim($X \cap W$) = $e-4$, dim($X \cap V \cap W$) = $e-4$ (Then modulo $P$, $X$ is a 4-space meeting $V+W$ only in the line $V$).
\end{enumerate}

\noindent

All these relations are symmetric, except for the relations 18 and 20,
which are each other's inverses.

Given $W$, the set of vertices is partitioned into 23 classes, each
consisting of the vertices $X$ for which $(W,X)$ belongs to a given relation.
The valencies of the relations, i.e., the sizes of these classes, are as follows.

\[
\begin{array}{ll}
1 & 1 \\
2 & (q+1)q(q-2) \\
3 & (q+1)(q-1) \\
4 & (q+1)(q^d-q^2) \\
5 & (q+1)(q^e-q^2) \\
6 & q-2 \\
7 & \frac{1}{2}(q+1)q(q-2)(q-3) \\
8 & (q-2)(q+1)(q-1) \\
9 & \frac{1}{2}q^2(q-1)^2 \\
10 & (q+1)(q-2)(q^d-q^2) \\
11 & q(q+1)(q-1)(q^d-q^2) \\
12 & (q^d-q^2)(q^d-q^3) \\
13 & (q+1)(q-2)(q^e-q^2) \\
14 & q(q+1)(q-1)(q^e-q^2) \\
15 & (q+1)(q^e-q^2)(q^d-q^2)/q \\
16 & (q+1)q(q^e-q^2)(q^d-q^2)/(q-1) \\
17 & (q^e-q^2)(q^e-q^3) \\
18 & (q^d-q^2)(q^e-q^2)(q+1) \\
19 & (q^d-q^2)(q^e-q^2)(q+1)(q-2)q/(q-1) \\
20 & (q^d-q^2)(q^e-q^2)(q+1) \\
21 & (q^d-q^2)(q^d-q^3)(q^e-q^2)(q+1)/((q-1)q) \\
22 & (q^d-q^2)(q^e-q^2)(q^e-q^3)(q+1)/((q-1)q) \\
23 & (q^e-q^2)(q^e-q^3)(q^d-q^2)(q^d-q^3)/((q-1)^2(q+1)q) \\
\end{array}
\]

\noindent
Now we enumerate the number of neighbours one vertex in one class has
in another class. This is done by hand in a straightforward manner.
The result is stated below.
The rows and columns are indexed by the numbers of the classes.
The $(i,j)$-entry is the number of neighbours a vertex in class $j$
has in class $i$.
(Note that two vertices are adjacent when they are in relation 2, 3, 4 or 5.
Thus, the entries in the table below are the values of
$\sum_{b \in \{2,3,4,5\}} p_{ib}^j$.)

{\tiny
\[
\begin{array}{|l||l|l|l|l|l|l|} \hline \hline
  & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \hline
1 & 0&  1&1&1&  1&  0 \\ \hline  
2 & (q+1)q(q-2)&   2q^2-5q+1&2q(q-2)&q(q-2)&   q(q-2)&   q(q+1) \\ \hline  
3 & (q-1)(q+1)&   2(q-1)&q-2&q-1&   q-1&   0 \\ \hline  
4 & (q+1)(q^d-q^2)&   (q^d-q^2)&(q^d-q^2)&q^d-q-1&   0&   0 \\ \hline
5 & (q+1)(q^e-q^2)&   (q^e-q^2)&(q^e-q^2)&0&   q^e-q-1&   0 \\ \hline  
6 & 0&   1&0&0&   0&   0 \\ \hline  
7 & 0&   1/2(q-3)(q^2-q+2)&1/2q(q-2)(q-3)&0&   0&   (q+1)q(q-3) \\ \hline  
8 & 0&   (q-1)^2&q(q-2)&0&   0&   (q+1)(q-1) \\ \hline  
9 & 0&   1/2q(q-1)^2&1/2q^2(q-1)&0&   0&   0 \\ \hline  
10& 0&   q^d-q^2&0&q^2(q-2)&   0&   (q+1)(q^d-q^2) \\ \hline  
11& 0&   (q-1)(q^d-q^2)&q(q^d-q^2)&q^3(q-1)&   0&   0 \\ \hline  
12& 0&   0&0&q(q^d-q^3)&   0&   0 \\ \hline  
13& 0&   q^e-q^2&0&0&   (q-2)q^2&   (q+1)(q^e-q^2) \\ \hline  
14& 0&   (q-1)(q^e-q^2)&q(q^e-q^2)&0&   (q-1)q^3&   0\\ \hline  
15&0&   0&0&q^e-q^2&   q^d-q^2&   0 \\ \hline  
16&0&   0&0&q(q^e-q^2)&   q(q^d-q^2)&   0 \\ \hline  
17&0&   0&0&0&   q(q^e-q^3)&   0 \\ \hline  
18& 0&   0&0&0&   0&   0 \\ \hline  
19& 0&   0&0&0&   0&   0 \\ \hline  
20& 0&   0&0&0&   0&   0 \\ \hline  
21& 0&   0&0&0&   0&   0 \\ \hline  
22& 0&   0&0&0&   0&   0 \\ \hline  
23& 0&   0&0&0&  0&   0 \\ \hline \hline 
\end{array}
\]

\[
\begin{array}{|l||l|l|l|l|l|} \hline \hline
\mbox{cont'd} & 7 & 8 & 9 & 10 & 11 \\ \hline\hline
1 &0&0&0&0&0 \\ \hline
2 &q^2-q+2&q(q-1)&(q+1)(q-2)&q&q-2 \\ \hline
3 &q-1&q&q+1&0&1 \\ \hline
4 &0&0&0&q^2&q^2 \\ \hline
5 &0&0&0&0&0 \\ \hline
6 &2&1&0&1&0 \\ \hline
7 &1/2q^3-q^2-3/2q-4&1/2q^2(q-3)&1/2(q+1)(q-2)(q-3)&q(q-3)&1/2(q-2)(q-3) \\ \hline
8 &q(q-1)&q^2-2q-2&(q+1)(q-2)&q-1&q-2 \\ \hline
9 &1/2q(q-1)^2&1/2q^2(q-1)&1/2q^3-3/2q-1&0&1/2q(q-1) \\ \hline
10&2(q^d-q^2)&(q^d-q^2)&0&q^d+q^3-3q^2-q-1&q^2(q-2) \\ \hline
11&(q-1)(q^d-q^2)&q(q^d-q^2)&(q+1)(q^d-q^2)&q^3(q-1)&q^d+q^4-q^3-q^2-q-1 \\ \hline
12&0&0&0&q(q^d-q^3)&q(q^d-q^3) \\ \hline
13&2(q^e-q^2)&(q^e-q^2)&0&0&0 \\ \hline
14&(q-1)(q^e-q^2)&q(q^e-q^2)&(q+1)(q^e-q^2)&0&0 \\ \hline
15&0&0&0&q^e-q^2&0 \\ \hline
16&0&0&0&0&q^e-q^2 \\ \hline
17&0&0&0&0&0 \\ \hline
18&0&0&0&0&q^e-q^2 \\ \hline
19&0&0&0&q(q^e-q^2)&(q-2)(q^e-q^2) \\ \hline
20&0&0&0&0&q^e-q^2\\ \hline
21&0&0&0&0&0 \\ \hline
22&0&0&0&0&0\\ \hline
23&0&0&0&0&0\\ \hline
\end{array}
\]

\[
\begin{array}{|l||l|l|l|l|l|}\hline\hline
\mbox{cont'd}& 12 & 13 & 14 & 15 & 16 \\ \hline\hline
1 &0&  0& 0&0&0 \\ \hline
2 &0&   q& q-2&0&0 \\ \hline
3 &0&   0&1&0&0 \\ \hline
4 &q(q+1)&0&0&q&q-1 \\ \hline
5 &0&   q^2&q^2&q&q-1 \\ \hline
6 &0&   1&0&0&0 \\ \hline
7 &0&   q(q-3)&1/2(q-2)(q-3)&0&0 \\ \hline
8 &0&   q-1&q-2&0&0 \\ \hline
9 &0&   0 &1/2q(q-1)&0&0  \\ \hline
10&q(q+1)(q-2)&   0&0&q(q-2)&0 \\ \hline
11&q^2(q^2-1)&   0&0&0&(q-1)^2 \\ \hline
12&(q+1)(q^d-q^3-1)&0&0&0&0 \\ \hline
13&0&q^e+q^3-3q^2-q-1&q^2(q-2)&q(q-2)&0 \\ \hline
14&0&   q^3(q-1)&q^e+q^4-q^3-q^2-q-1&0&(q-1)^2 \\ \hline
15&0&   q^d-q^2&0&q^e+q^d-2q^2-q-1&2(q-1)^2 \\ \hline
16&0&   0&q^d-q^2&2q^2(q-1)&q^e+q^d+2q^3-6q^2+3q-2 \\ \hline
17&0&   q(q^e-q^3)&q(q^e-q^3)&0&0 \\ \hline
18&0&   0&q^d-q^2&2q^2(q-1)&(q-1)^2(2q-1) \\ \hline
19&0&   q(q^d-q^2)&(q-2)(q^d-q^2)&2q^2(q-1)(q-2)&(q-2)(2q-1)(q^2-q+1) \\ \hline
20&0&   0&q^d-q^2&q(q-1)^2&2(q-1)(q^2-q+1) \\ \hline
21&(q+1)(q^e-q^2)&   0&0&q(q^d-q^3)&q(q^d-q^3) \\ \hline
22&0&   0&0&q(q^e-q^3)&q(q^e-q^3)\\ \hline
23&0&   0&0&0&0\\ \hline
\end{array}
\]

\[
\begin{array}{|l||l|l|l|l|}\hline\hline
\mbox{cont.}& 17 & 18 & 19 & 20 \\ \hline\hline
1 &0&   0& 0&0 \\ \hline
2 &0&   0& 0&0 \\ \hline
3 &0&   0& 0&0\\ \hline
4 &0&   0& 0&0 \\ \hline
5 &q(q+1)&   0& 0&0 \\ \hline
6 &0&   0& 0&0 \\ \hline
7 &0&   0& 0&0 \\ \hline
8 &0&   0& 0&0 \\ \hline
9 &0&   0& 0&0 \\ \hline
10&0&   0& q-1&0 \\ \hline
11&0&   q(q-1)& (q-1)^2&q(q-1) \\ \hline
12&0&   0& 0&0 \\ \hline
13&q(q+1)(q-2)&    0& q-1&0 \\ \hline
14&q^2(q^2-1)&   q(q-1)& (q-1)^2&q(q-1) \\ \hline
15& 0&   2q(q-1)& 2(q-1)^2&(q-1)^2 \\ \hline
16&0&   q(q-1)(2q-1)& (2q-1)(q^2-q+1)&2q(q^2-q+1) \\ \hline
17&(q+1)(q^e-q^3-1)&   0& 0&0 \\ \hline
18&0&   q^d+q^e+2q^3-6q^2+q-1& (q-1)^2(2q-1)&2q(q-1)^2 \\ \hline
19&0&   q(q-1)(q-2)(2q-1)& q^d+q^e+2q^4-7q^3+6q^2-7q+1&   2q(q-2)(q^2-q+1) \\ \hline
20&0&   2q(q-1)^2& 2(q-1)(q^2-q+1)&q^d+q^e+q^3-5q^2+2q-2 \\ \hline
21&0&   q(q^d-q^3)& q(q^d-q^3)&q(q^d-q^3) \\ \hline
22&(q+1)(q^d-q^2)&   q(q^e-q^3)& q(q^e-q^3)&q(q^e-q^3) \\ \hline
23&0&   0& 0&0 \\ \hline
\end{array}
\]

\[
\begin{array}{|l||l|l|l||}\hline\hline
\mbox{cont.} & 21 & 22 & 23 \\ \hline\hline
1 & 0&   0&   0 \\ \hline
2 & 0&   0&   0 \\ \hline
3 & 0&   0&   0 \\ \hline
4 & 0&   0&   0 \\ \hline
5 & 0&   0&   0 \\ \hline
6 & 0&   0&   0 \\ \hline
7 & 0&   0&   0 \\ \hline
8 & 0&   0&   0 \\ \hline
9 & 0&   0&   0 \\ \hline
10& 0&   0&   0 \\ \hline
11&0&   0&   0 \\ \hline
12& q(q-1)&   0&   0 \\ \hline
13& 0&   0&   0 \\ \hline
14& 0&   0&   0 \\ \hline
15& q(q-1)&   q(q-1)&   0 \\ \hline
16& q^3&   q^3&   0 \\ \hline
17&0&   q(q-1)&   0 \\ \hline
18& q^2(q-1)&   q^2(q-1)&   0 \\ \hline
19& q^3(q-2)&   q^3(q-2)&   0 \\ \hline
20& q^2(q-1)&q^2(q-1)&   0\\ \hline
21& q^{(d+1)}+q^d+q^e-2q^3-2q^2-1&   0&  q(q+1)^2(q-1) \\ \hline
22& 0&   q^{(e+1)}+q^e+q^d-2q^3-2q^2-1&  q(q+1)^2(q-1) \\ \hline
23& q(q^e-q^3)&   q(q^d-q^3)&   (q+1)(q^e+q^d-2q^3-q^2+q-1) \\ \hline
\end{array}
\]

}

\section{The Spectrum}

What have we obtained so far?
We have 23 relations $S_s$ with adjacency matrices $B_s$, say,
such that the adjacency matrix $A$ of the graph under consideration
satisfies $A B_s = \sum c_{st} B_t$, where the matrix
$C = (c_{st})_{st}$ (of order 23) was given explicitly above.

At first we hoped that these 23 relations would define an
association scheme, but that turns out not to be the case.
Still, the matrices $A$ and $B_s$ $(1 \leq s \leq 23)$ are elements
of the Bose-Mesner algebra of some association scheme.
Indeed, the subgroup of $PGL_{d+e}(q)$ stabilizing $U$ and $V$
is a transitive group of automorphisms of our graph.

This means that we can use an analog of Proposition 2.2.2
from \cite{BCN} (formulated there for the case of a symmetric
association scheme, and a matrix with distinct eigenvalues
in the different eigenspaces) to express the spectrum of $A$
in terms of the parameters of this association scheme.
Since however we do not know the parameters (or even the number
of relations) for our association scheme, we need a second
proposition to express the spectrum in terms of the known matrix $C$.

The eigenvalues of the second subconstituent of $H_q(d,e)$ are now
computed from these propositions and the parameters
of the scheme as computed above, using MAPLE. The result
of this computation is a number of eigenvalues with a lower bound
on their multiplicities. Because the sum of these lower bounds
is exactly the number of vertices, we know that these lower bounds
are in fact the multiplicities themselves. The results are as stated
in Section \ref{results}.\\

\noindent{\bf{Proposition: }}{\it
Let $(X,\{R_0, ... ,R_d\})$ be an association scheme on $v$ points
with adjacency matrices $A_0$, ..., $A_d$ (where $A_0 = I$)
and intersection numbers $p_{ij}^k$ (so that $A_i A_j = \sum p_{ij}^k A_k$).
Let $L_i$ be the matrix of order $d+1$ defined by $(L_i)_{kj} = p_{ij}^k$.
Let $A = \sum c_i A_i$ be a symmetric matrix in the Bose-Mesner algebra
of the scheme, and let $L := \sum c_i L_i$. Then the matrices $A$ and $L$
have the same eigenvalues.
If $\lambda$ is an eigenvalue of $L$, then there is a unique real eigenvector
$u$ of $L$ such that $L u = \lambda u$, $u_0 = 1$, $u^{\top} \Delta_n u$
minimal, where $\Delta_n$ is the diagonal matrix with the valencies
$n_j = p_{jj'}^0$ on the diagonal, and the multiplicity of $\lambda$
as an eigenvalue of $A$ equals $v / (u^{\top} \Delta_n u)$.
}

\medskip\Proof
The map $A_i \mapsto L_i$ is an isomorphism from the
Bose-Mesner algebra $\fsA = \langle A_i ~|~ 0 \le i \le d \rangle_F$
spanned by the matrices $A_i$ (over some field $F$) onto the algebra
$\langle L_i ~|~ 0 \le i \le d \rangle_F$. Indeed,
it preserves multiplication, and both algebras have the same dimension
since the $L_i$ are independent (because $(L_i)_{k0} = \delta_{i,k}$).
Now let $F = \Rr$.
Both $A$ and $L$ are diagonalizable (since $A$ and $\Delta_n L$ are symmetric);
let $m(X) := \prod_{i=1}^s (X - \theta_i)$ be the minimal polynomial of $A$
(and hence of $L$). Put $m_j(X) := m(X)/(X - \theta_j)$, and
$E_j := m_j(A)/m_j(\theta_j)$. Then the $E_j$ are mutually orthogonal
idempotents in $\fsA$ (not necessarily the primitive idempotents
of the scheme!), and $A E_j = \theta_j E_j$.
The multiplicity of $\theta_j$ as an eigenvalue
of $A$ equals $f_j := \rk E_j = \tr E_j$.
Define a $(d+1) \times s$ matrix $Q$ by
$E_j = {1 \over v} \sum_{i=0}^d Q_{ij} A_i$ ($1 \le j \le s$).
Now $L Q e_j = \theta_j Q e_j$ (where $e_j$ is the $j$-th unit vector)
as one sees by comparing the coefficients of the $A_i$ on both sides
of $A E_j = \theta_j E_j$. Furthermore, $(Qe_j)_0 = Q_{0j} = f_j$ follows by
taking traces in the expression for $E_j$.
Finally, $Q^{\top} \Delta_n Q = v \Delta_f$ follows from
$\delta_{ij} f_i = \tr E_i E_j = {1 \over v} \sum Q_{li} Q_{lj} n_l$.
(Note that if $R_l$ and $R_{l'}$ are inverse relations, so that
$A_{l'} = A_l^{\top}$, then $Q_{li} = Q_{l'i}$, since $E_i$ is symmetric.)
Thus, if we take $u = f_j^{-1} (Qe_j)$, then $u_0 = 1$ and
$f_j = v/ (u^{\top} \Delta_n u)$.

Remains to show that this $u$ minimizes $u^{\top} \Delta_n u$.
But if $u$ is arbitrary with $u_0 = 1$, $L u = \theta_j u$, then
the matrix $U := \sum u_i A_i$ satisfies $A U = \theta_j U$ and hence
$U = E_j M$ for some matrix $M$.
Also $u^{\top} \Delta_n u = {1 \over v} \tr U^\top U$ and
$u_0 = {1 \over v} \tr U$,
so we have to minimize $\tr U^\top U$ (that is, the sum of the squares of the
elements of $U$) given $\tr U$ (and $U = E_j M$). Diagonalising $E_j$ we see
immediately that $U$ is uniquely determined, and corresponds to the $u$
we had above.
\qed

\noindent{\bf{Proposition: }}{\it
Let $(X, \{R_0, \ldots, R_d\})$ be an association scheme,
and $A$ and $B_s$ $(1 \le s \le e)$ matrices in its Bose-Mesner
algebra satisfying $A B_s = \sum_t c_{st} B_t$ for certain
constants $c_{st}$.
Suppose that $A$ is symmetric. Then each eigenvalue $\lambda$
of the matrix $C = (c_{st})_{st}$ is also an eigenvalue of $A$.
Suppose moreover that for some partition $\{ \pi_1, ... , \pi_e \}$
of $\{0, ..., d\}$ with $\pi_1 = \{0\}$,
we have $B_s = \sum_{i \in \pi_s} A_i$, where the $A_i$ are the
0-1 adjacency matrices of the relations $R_i$.
Then $\lambda$ is an eigenvalue of $C$ with multiplicity at least
$v / (u^{\top} \Delta_b u)$, where $v = |X|$, $\Delta_b$ is the
$e \times e$-diagonal matrix where the entry $(\Delta_b)_{ss}$
equals the row sum of $B_s$, and $u$ is an eigenvector of $C$
with eigenvalue $\lambda$ and $u_1 = 1$.
}

\medskip\Proof
Let $A_i$ be the adjacency matrix of $R_i$ $(0 \le i \le d)$.
Since $A$ and $B_s$ are elements of the Bose-Mesner algebra,
we can write $A = \sum \alpha_i A_i$ and
$B_s = \sum \beta_{si} A_i$. Put $B := (\beta_{si})_{si}$
and $L = \sum \alpha_i L_i = L^{\top}$.
Then $A B_s = \sum_t c_{st} B_t$ is expressed by $B L = C B$.
If $u C = \lambda u$, then $(uB)L = \lambda uB$.
Under the given additional assumptions the claim follows
from the previous proposition applied to $u' = (uB)^{\top}$,
since $(u')^{\top} \Delta_n u' = u \Delta_b u^{\top}$
and $(u')_0 = u_1 = 1$.
\qed

\begin{thebibliography}{NNNNNNNN}
\bibitem[BCN]{BCN} A.E. Brouwer, A.M. Cohen, A. Neumaier,
{\em Distance-Regular Graphs}, Springer Verlag, Berlin, 1989.
\end{thebibliography}

\end{document}
