\documentclass[a4paper]{article}
% \addtolength{\oddsidemargin}{-25pt}
% \addtolength{\textwidth}{50pt}
% \addtolength{\textheight}{120pt}
% \setlength{\topmargin}{20pt}
% \setlength{\headheight}{0pt}
% \setlength{\headsep}{0pt}

% Definitions Willem
%
\def\({\left[\begin{array}}
\def\){\end{array}\right]}
\def\0{{\bf 0}}
\def\1{{\bf 1}}
\def\d{{d}}
\def\s{{s}}
\def\u{{u}}
\def\v{{v}}
\def\T{{\bf T}}
\def\F{{\bf F}}
\def\U{{\bf U}}
\def\t{\tilde}
\def\cs{\circ}
\def\tensor{\otimes}
\def\eigA{{\theta}}
\def\eigB{{\eta}}
\def\laplace{{\mu}}
\def\A{{\cal A}}
\def\l{\ell}
\def\qed{\hfill$\Box$}
\def\2{{\textstyle \frac{1}{2}}}
\def\~{\widetilde}
\newcommand{\rayl}[2]{ {\frac{ {#1}^\top{#2}{#1} }{ {#1}^\top{#1} }}}
% \newtheorem{thm}{Theorem}[section]
% \newtheorem{lem}{Lemma}[section]
% \newtheorem{cor}{Corollary}[section]

% Definitions Andries
%
% Either use amssymbols or invent some ourselves
\usepackage{amssymb}
\newcommand{\normalsubgp}{{\trianglelefteq\,}}
%\newcommand{\mathbb}{\bf}
%\newcommand{\normalsubgp}{{??}}
%
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof.}\quad }
%\newcommand{\eop}{$\Box$}
% \newcommand{\qed}{\hfill\eop\medskip}
\newcommand{\Example}{ \medskip\noindent{\bf Example}\quad }
\newcommand{\Exercise}{ \medskip\noindent{\bf Exercise}\quad }
%\newcommand{\Exercises}{ \medskip\noindent{\bf Exercises}\quad }
\newcommand{\Remark}{ \medskip\noindent{\bf Remark}\quad }
\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\newcommand{\Cc}{{\mathbb {C}}}
\newcommand{\Ff}{{\mathbb {F}}}
\newcommand{\Nn}{{\mathbb {N}}}
\newcommand{\Rr}{{\mathbb {R}}}
\newcommand{\Zz}{{\mathbb {Z}}}
\newcommand{\Aut}{{\rm Aut}\ }
\newcommand{\diag}{{\rm diag}}
\newcommand{\tr}{{\rm tr}}
\newcommand{\rk}{{\rm rk}}
\newcommand{\adj}{\,\sim\,}
\newcommand{\adjns}{\sim}
\newcommand{\mod}{{\rm mod}\ }
\newcommand{\nadj}{\,\not\sim\,}
\newcommand{\isom}{\,\simeq\,}
\newcommand{\norm}{\|}
\newcommand{\eps}{\varepsilon}
\newcommand{\maysplit}{\discretionary{}{}{}}
\begin{document}
\begin{center}
\bigskip
{\LARGE \bf Topics in algebraic graph theory}
\\[30pt]
{\Large Andries E. Brouwer}\\[8pt]
{\Large Willem H. Haemers}
\end{center}
\clearpage
\begin{tableofcontents}
\end{tableofcontents}
\clearpage

{\em Algebraic graph theory} is the branch of mathematics that studies
graphs by using algebraic properties of associated matrices.
More in particular, {\em spectral graph theory} studies the relation
between graph properties and the spectrum of the adjacency matrix
or Laplace matrix. And the theory of {\em association schemes}
and {\em coherent configurations} studies the algebra generated
by associated matrices.

\section{Graph spectrum}

This section presents some simple results on graph spectra.
We assume the reader to be familiar with elementary linear algebra
and graph theory.
Throughout $J$ will denote the all-$1$ matrix, and $\1$ is the all-$1$
vector.

\subsection{Matrices associated to a graph}

Let $\Gamma$ be a graph without multiple edges.
The {\em adjacency matrix} of $\Gamma$
is the 0-1 matrix $A$ indexed by the vertex set of $\Gamma$, where
$A_{xy} = 1$ when there is an edge from $x$ to $y$ in $\Gamma$
and $A_{xy} = 0$ otherwise.

Let $\Gamma$ be an undirected graph without loops.
The {\em incidence matrix} of $\Gamma$
is the 0-1 matrix $N$, with rows indexed by the vertices
and columns indexed by the edges, where $N_{xe} = 1$ when
vertex $x$ is an endpoint of the edge $e$.

Let $\Gamma$ be a directed graph without loops. The {\em directed
incidence matrix} of $\Gamma$ is the 0-1 matrix $N$, with rows
indexed by the vertices and columns by the edges, where
$N_{xe} = -1,1,0$ when $x$ is the head of $e$, the tail of $e$, or
not on $e$, respectively.

Let $\Gamma$ be an undirected graph without loops.
The {\em Laplace matrix} of $\Gamma$ is the matrix $L$
indexed by the vertex set of $\Gamma$, with zero row sums,
where $L_{xy} = - A_{xy}$ for $x \ne y$.

The Laplace matrix is important because it is positive semidefinite.
(Indeed, one has $L = NN^\top$ if $N$ is the directed incidence
matrix of the directed graph obtained by orienting the edges of
$\Gamma$ in an arbitrary way.) If $D$ is the diagonal matrix,
indexed by the vertex set of $\Gamma$ such that $D_{xx}$ is the
degree (valency) of $x$, then $L = D - A$.

\subsection{The spectrum of a graph}

The (ordinary) {\em spectrum} of a finite graph $\Gamma$
is by definition the spectrum
of the adjacency matrix $A$, that is, its set of eigenvalues together
with their multiplicities. % (Formally, a multiset.)
The {\em Laplace spectrum} of a finite undirected graph without
loops is the spectrum of the Laplace matrix $L$.

The rows and columns of a matrix of order $n$ are numbered from 1 to
$n$, while $A$ is indexed by the vertices of $\Gamma$, so that
writing down $A$ requires one to assign some numbering to the
vertices. However, the spectrum of the matrix obtained does not
depend on the numbering chosen. It is the spectrum of the linear
transformation $A$ on the vector space $K^X$ of maps from $X$ into
$K$, where $X$ is the vertex set, and $K$ is some field such as
$\Rr$ or $\Cc$.

The {\em characteristic polynomial} of $\Gamma$ is that of $A$, that is,
the polynomial $p_A$ defined by
$p_A ( \theta ) = \det ( \theta I - A )$.

\Example Let $\Gamma$ be the path $P_3$ with three vertices and two
edges. Assigning some arbitrary order to the three vertices of
$\Gamma$, we find that the adjacency matrix $A$ becomes one of
\[
\left[\begin{array}{ccc}
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0 \\
\end{array}\right]
\mbox{ or }
\left[\begin{array}{ccc}
0 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 0 \\
\end{array}\right]
\mbox{ or }
\left[\begin{array}{ccc}
0 & 0 & 1 \\
0 & 0 & 1 \\
1 & 1 & 0 \\
\end{array}\right].
\]
The characteristic polynomial is $p_A ( \theta ) = \theta^3 - 2 \theta$.
The spectrum is $\sqrt 2$, 0, $- \sqrt 2$. The eigenvectors are:
$$
\begin{picture}(360,20)(-7,-5)
\put(0,0){\circle{4}}\put(2,0){\line(1,0){36}}
\put(0,10){\makebox(0,0)[c]{\scriptsize $\sqrt 2$}}
\put(40,0){\circle{4}}\put(42,0){\line(1,0){36}}
\put(40,10){\makebox(0,0)[c]{\scriptsize $2$}}
\put(80,0){\circle{4}}
\put(80,10){\makebox(0,0)[c]{\scriptsize $\sqrt 2$}}
\put(120,0){\circle{4}}\put(122,0){\line(1,0){36}}
\put(120,10){\makebox(0,0)[c]{\scriptsize $1$}}
\put(160,0){\circle{4}}\put(162,0){\line(1,0){36}}
\put(160,10){\makebox(0,0)[c]{\scriptsize $0$}}
\put(200,0){\circle{4}}
\put(200,10){\makebox(0,0)[c]{\scriptsize $-1$}}
\put(240,0){\circle{4}}\put(242,0){\line(1,0){36}}
\put(240,10){\makebox(0,0)[c]{\scriptsize $\sqrt 2$}}
\put(280,0){\circle{4}}\put(282,0){\line(1,0){36}}
\put(280,10){\makebox(0,0)[c]{\scriptsize $-2$}}
\put(320,0){\circle{4}}
\put(320,10){\makebox(0,0)[c]{\scriptsize $\sqrt 2$}}
\put(330,0){\makebox(0,0)[c]{.}}
\end{picture}
$$
%
(Here, for an eigenvector $u$, we write $u_x$ as a label at the
vertex $x$; one has $Au = \theta u$ if and only if
$\sum_{ y \leftarrow x } u_y = \theta u_x$.)
%
The Laplace matrix $L$ is one of
\[
\left[\begin{array}{rrr}
2 & -1 & -1 \\
-1 & 1 & 0 \\
-1 & 0 & 1 \\
\end{array}\right]
\mbox{ or }
\left[\begin{array}{rrr}
1 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 1 \\
\end{array}\right]
\mbox{ or }
\left[\begin{array}{rrr}
1 & 0 & -1 \\
0 & 1 & -1 \\
-1 & -1 & 2 \\
\end{array}\right].
\]
Its eigenvalues are 0, 1 and 3.
The Laplace eigenvectors are:
$$
\begin{picture}(360,20)(-7,-5)
\put(0,0){\circle{4}}\put(2,0){\line(1,0){36}}
\put(0,10){\makebox(0,0)[c]{\scriptsize $1$}}
\put(40,0){\circle{4}}\put(42,0){\line(1,0){36}}
\put(40,10){\makebox(0,0)[c]{\scriptsize $1$}}
\put(80,0){\circle{4}}
\put(80,10){\makebox(0,0)[c]{\scriptsize $1$}}
\put(120,0){\circle{4}}\put(122,0){\line(1,0){36}}
\put(120,10){\makebox(0,0)[c]{\scriptsize $1$}}
\put(160,0){\circle{4}}\put(162,0){\line(1,0){36}}
\put(160,10){\makebox(0,0)[c]{\scriptsize $0$}}
\put(200,0){\circle{4}}
\put(200,10){\makebox(0,0)[c]{\scriptsize $-1$}}
\put(240,0){\circle{4}}\put(242,0){\line(1,0){36}}
\put(240,10){\makebox(0,0)[c]{\scriptsize $1$}}
\put(280,0){\circle{4}}\put(282,0){\line(1,0){36}}
\put(280,10){\makebox(0,0)[c]{\scriptsize $-2$}}
\put(320,0){\circle{4}}
\put(320,10){\makebox(0,0)[c]{\scriptsize $1$}}
\put(330,0){\makebox(0,0)[c]{.}}
\end{picture}
$$

\Example
Let $\Gamma$ be the directed triangle with adjacency matrix
\[
A = \left[\begin{array}{ccc}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
\end{array}\right].
\]
Then $A$ has characteristic polynomial $p_A ( \theta ) = \theta^3 - 1$
and spectrum 1, $\omega$, $\omega^2$, where
$\omega$ is a primitive cube root of unity.

\Example Let $\Gamma$ be the directed graph with two vertices
and a single directed edge. Then
$A = {\scriptsize [\begin{array}{cc}
\! 0\! &\! 1\!\! \\
\! 0\! &\! 0\!\!
\end{array}]}$
with $p_A ( \theta ) = \theta^2$.
So $A$ has the eigenvalue $0$ with geometric multiplicity
(that is, the dimension of the corresponding eigenspace)
equal to 1 and algebraic multiplicity (that is, its
multiplicity as a root of the polynomial $p_A$) equal to 2.

\subsection{The spectrum of an undirected graph}
Suppose $\Gamma$ is undirected and simple with $n$ vertices.
Since $A$ is real and symmetric, all
its eigenvalues are real. Also, for each eigenvalue $\theta$, its
algebraic multiplicity coincides with its geometric multiplicity,
so that we may omit the adjective and just speak about `multiplicity'.
Conjugate algebraic integers have the same multiplicity.
Since $A$ has zero diagonal, its trace $\tr A$, and hence the sum
of the eigenvalues is zero.

Similarly, $L$ is real and symmetric, so that the Laplace spectrum
is real. Moreover, $L$ is positive semidefinite and singular, so
we may denote the eigenvalues by
$\mu_1\ (= 0)\leq \mu_2\leq\ldots\leq\mu_n$.
The sum of these eigenvalues is $\tr L$, which is twice the number
of edges of~$\Gamma$.

The complement of $\Gamma$ has adjacency matrix $\overline{A} = J-I-A$
and Laplace matrix $\overline{L} = nI-J-L$.
Because eigenvectors of $L$ are also eigenvectors of $J$,
the eigenvalues of $\overline{L}$ are $0,n-\mu_n,\ldots,n-\mu_2$.
If $\Gamma$ is regular we have a similar
result for the ordinary eigenvalues:
%
\begin{Proposition}
{~}\\[-15pt]
\begin{itemize}
\item[(i)]
$\Gamma$ is regular (of degree $k$) if and only if $A\1 = k\1$,
\item[(ii)]
if $\Gamma$ is $k$-regular with eigenvalues $\theta_1\geq\ldots\geq\theta_n$,
then $\theta_1=k$, and the eigenvalues of the complement are
$n-k-1,-1-\theta_n,\ldots,-1-\theta_2$.
\item[(iii)]
if $\Gamma$ is $k$-regular with ordinary eigenvalues
$\theta_1\ (=k)\geq\ldots\geq\theta_n$ and Laplace eigenvalues
$\mu_1\ (= 0)\leq \mu_2\leq\ldots\leq\mu_n$,
then $\theta_i=k-\mu_{n+1-i}$ for $i=1,\ldots,n$.
\end{itemize}
\end{Proposition}
%
Another useful property is:
%
\begin{Proposition}
Let $h$ be a nonnegative integer.
Then $(A^h )_{xy}$ is the number of walks of length $h$
from $x$ to $y$. In particular, $(A^2 )_{xx}$ is the degree
of the vertex $x$, and $\tr A^2$ equals twice the number of edges
of $\Gamma$; similarly, $\tr A^3$ is six times the number of triangles
in $\Gamma$.
\end{Proposition}
%
We saw that all eigenvalues of a single directed edge are zero.
For undirected graphs this does not happen.
%
\begin{Proposition}
Let $\Gamma$ be an undirected graph. All its eigenvalues are zero
if and only if $\Gamma$ has no edges.
The same holds for the Laplace eigenvalues.
\end{Proposition}
%
As a consequence of this proposition we find a (lower) bound for the diameter:
%
\begin{Proposition}
If $\Gamma$ is connected graph with diameter $d$.
Then $\Gamma$ has at least $d + 1$ distinct eigenvalues.
\end{Proposition}
%
% should have \ldots \cdots and \ldots here, but it doesnt fit
\Proof Let the distinct eigenvalues of the adjacency matrix $A$ of $\Gamma$
be $\theta_1 , ... , \theta_t$.
Then $(A - \theta_1 I) ... (A - \theta_t I) = 0$,
so that $A^t$ is a linear combination of
$I, A, ... , A^{t-1}$. But if $d(x,y) = t$ for two vertices
$x, y$ of $\Gamma$, then $(A^i )_{xy} = 0$ for $0 \le i \le t - 1$
and $(A^t )_{xy} > 0$, contradiction. Hence $t > d$.
\qed\\[5pt]
%
Distance-regular graphs, discussed below in Section \ref{drg},
have equality here.
%
\subsection{Connectedness}\label{conn}
The spectrum of a disconnected graph is easily found from the spectra
of its connected components:
%
\begin{Proposition}
Let $\Gamma$ be a graph with connected components $\Gamma_i$
$(1 \le i \le s)$.
Then the spectrum of $\Gamma$ is the union of the spectra of $\Gamma_i$
(and multiplicities are added).
The same holds for the Laplace spectrum. \qed
\end{Proposition}
%
\begin{Proposition}
The multiplicity of 0 as a Laplace eigenvalue of an undirected graph $\Gamma$
equals the number of connected components of $\Gamma$.
\end{Proposition}
%
\Proof
We have to show that a connected graph has Laplace eigenvalue 0
with multiplicity 1. As we saw earlier, $L = NN^\top$, where $N$
is the incidence matrix of an orientation of $\Gamma$.
Now $Lu = 0$ is equivalent to $N^\top u = 0$ (since
$0 = u^\top Lu = ||N^\top u||^2$), that is, for every edge
the vector $u$ takes the same value on both endpoints.
Since $\Gamma$ is connected that means that $u$ is constant. \qed
%
\begin{Proposition}
Let the undirected graph $\Gamma$ be regular of valency $k$.
Then $k$ is the largest eigenvalue of $\Gamma$, and its multiplicity
equals the number of connected components of $\Gamma$.
\end{Proposition}
%
\Proof We have $L = kI - A$.
\qed\\[5pt]
%
One cannot see from the spectrum alone whether a (nonregular)
graph is connected:
Both $K_{1,4}$ and $K_1 + C_4$ have spectrum
$2^1$, $0^3$, $(-2)^1$
(we write multiplicities as exponents).
And both $\hat{E}_6$ and $K_1 + C_6$ have spectrum
$2^1$, $1^2$, $0$, $(-1)^2$, $(-2)^1$.
$$
\begin{picture}(360,70)(-15,-10)
\put(0,0){\circle{2}}\put(0.707,0.707){\line(1,1){18.585}}
\put(0,40){\circle{2}}\put(0.707,39.293){\line(1,-1){18.585}}
\put(20,20){\circle{2}}
\put(40,0){\circle{2}}\put(39.293,0.707){\line(-1,1){18.585}}
\put(40,40){\circle{2}}\put(39.293,39.293){\line(-1,-1){18.585}}
\put(90,0){\circle{2}}\put(91,0){\line(1,0){38}}
\put(90,40){\circle{2}}\put(91,40){\line(1,0){38}}
\put(110,20){\circle{2}}
\put(130,0){\circle{2}}\put(90,1){\line(0,1){38}}
\put(130,40){\circle{2}}\put(130,1){\line(0,1){38}}
\put(170,0){\circle{2}}\put(170.89442,0.44721){\line(2,1){18.21116}}
\put(250,0){\circle{2}}
\put(190,10){\circle{2}}\put(190.89442,10.44721){\line(2,1){18.21116}}
\put(230,10){\circle{2}}\put(230.89442,9.55279){\line(2,-1){18.21116}}
\put(210,20){\circle{2}}\put(210.89442,19.55279){\line(2,-1){18.21116}}
\put(210,40){\circle{2}}\put(210,21){\line(0,1){18}}
\put(210,60){\circle{2}}\put(210,41){\line(0,1){18}}
\put(300,20){\circle{2}}\put(280.44721,19.10558){\line(1,-2){9.10558}}
\put(280,20){\circle{2}}\put(280.44721,20.89442){\line(1,2){9.10558}}
\put(320,20){\circle{2}}
\put(290,40){\circle{2}}\put(291,40){\line(1,0){18}}
\put(310,40){\circle{2}}\put(310.44721,39.10558){\line(1,-2){9.10558}}
\put(290,0){\circle{2}}\put(291,0){\line(1,0){18}}
\put(310,0){\circle{2}}\put(310.44721,0.89442){\line(1,2){9.10558}}
\put(20,-8){\makebox(0,0)[c]{\small $K_{1,4}$}}
\put(110,-8){\makebox(0,0)[c]{\small $K_1 + C_4$}}
\put(210,-8){\makebox(0,0)[c]{\small $\hat{E}_6$}}
\put(300,-8){\makebox(0,0)[c]{\small $K_1 + C_6$}}
\end{picture}$$

\subsection{Spectrum of some simple graphs}
In this section we discuss some special graphs and their spectra.
All graphs in this section are finite, undirected and simple.
Observe that the all-1 matrix $J$ of order $n$ has rank 1, and that the
all-1 vector $\1$ is an eigenvector with eigenvalue $n$. So the
spectrum is $n^1,~0^{n-1}$
(where multiplicities are written as exponents).

\subsubsection{The complete graph}
Let $\Gamma$ be the complete graph $K_n$ on $n$ vertices. Its
adjacency matrix is $A = J-I$, and the spectrum is
$(n-1)^1,~(-1)^{n-1}$.
The Laplace matrix is $nI-J$, which has spectrum
$0^1,~n^{n-1}$.

\subsubsection{The complete bipartite graph}
The spectrum of the complete bipartite graph $K_{m,n}$ is $\pm
\sqrt{mn}$, $0^{m+n-2}$. The Laplace spectrum is
$0^1,~m^{n-1},~n^{m-1},~(m+n)^1$.
%(With multiplicities written as exponents.)

\subsubsection{The cycle}
Let $\Gamma$ be the directed $n$-cycle $D_n$. Eigenvectors are
$(1,\zeta,\zeta^2,\ldots,\zeta^{n-1})^\top$ where $\zeta^n = 1$, and
the corresponding eigenvalue is $\zeta$. Thus, the spectrum consists
precisely of the complex $n$-th roots of unity $e^{2\pi i j/n}$
$(j=0,\ldots,n-1)$.

Now consider the undirected $n$-cycle $C_n$. If $B$ is the adjacency
matrix of $D_n$, then $A = B + B^\top$ is the adjacency matrix of
$C_n$. We find the same eigenvectors as before, with eigenvalues
$\zeta + \zeta^{-1}$, so that the spectrum consists of the numbers
$2\cos (2\pi j/n)$ $(j=0,\ldots,n-1)$.

This graph is regular of valency 2, so the Laplace spectrum consists
of the numbers $2 - 2\cos (2\pi j/n)$ $(j=0,\ldots,n-1)$.

\subsubsection{The path}
Let $\Gamma$ be the undirected path $P_n$ with $n$ vertices. The
ordinary spectrum consists of the numbers $2\cos (\pi j/(n+1))$
$(j=1,\ldots,n)$. The Laplace spectrum is $2 - 2\cos (\pi j/n)$
$(j=0,\ldots,n-1)$.

The ordinary spectrum follows by looking at $C_{2n+2}$. If
$u(\zeta) = (1,\zeta,\zeta^2,\maysplit\ldots,\maysplit\zeta^{2n+1})^\top$
is an eigenvector of $C_{2n+2}$, where $\zeta^{2n+2} = 1$, then $u(\zeta)$
and $u(\zeta^{-1})$ have the same eigenvalue $2\cos (\pi j/(n+1))$,
and hence so has $u(\zeta) - u(\zeta^{-1})$. This latter vector has
two zero coordinates distance $n+1$ apart and (for $\zeta \ne \pm
1$) induces an eigenvector on the two paths obtained by removing the
two points where it is zero.

Eigenvectors of $L$ with eigenvalue $2 - \zeta - \zeta^{-1}$ are
$(1+\zeta^{2n-1},\ldots,\zeta^j+\zeta^{2n-1-j},\ldots,\zeta^{n-1}+\zeta^n)$
where $\zeta^{2n} = 1$. One can check this directly, or consider
$P_n$ the result of folding $C_{2n}$ where the folding has no fixed
vertices. An eigenvector of $C_{2n}$ that is constant on the
preimages of the folding yields an eigenvector of $P_n$ with the
same eigenvalue.

\subsubsection{Line graphs}
The {\em line graph} $L(\Gamma)$ of $\Gamma$ is the graph with the
edge set of $\Gamma$ as vertex set, where two vertices are adjacent
if the corresponding edges of $\Gamma$ have an endpoint in common.
If $N$ is the incidence matrix of $\Gamma$, then $N^\top N-2I$ is
the adjacency matrix of $L(\Gamma)$. Since $N^\top N$ is positive
semidefinite, the eigenvalues of a line graph are not smaller that
$-2$. If $\Gamma$ is regular we have an explicit formula for the
eigenvalues of $L(\Gamma)$.
%
\begin{Proposition}
If $\Gamma$ is a $k$-regular graph ($k\geq 2$) with $n$ vertices,
$e=kn/2$ edges and eigenvalues $\theta_i$ ($i=1,\ldots,n$), then
$L(\Gamma)$ is $(2k-2)$-regular with eigenvalues $\theta_i+k-2$
($i=1,\ldots,n$) and $e-n$ times $-2$.
\end{Proposition}
%
\Proof The adjacency matrices $A$ and $B$ of $\Gamma$ and
$L(\Gamma)$, respectively, satisfy $A+kI=NN^\top$ and $B+2I =
N^\top\! N$. Because $NN^\top$ and $N^\top\! N$ have the same
nonzero eigenvalues (multiplicities included), the result follows.
\qed
\\[5pt]
%
The line graph of the complete graph $K_n$ ($n\geq 2$), is known as
the {\em triangular graph} $T(n)$. It has spectrum $2(n-2)^1$,
$(n-4)^{n-1}$, $(-2)^{n(n-3)/2}$.
The line graph of the regular complete bipartite graph $K_{m,m}$
($m\geq2$), is known as the {\em lattice graph} $L_2(m)$.
It has spectrum $2(m-1)^1$, $(m-2)^{2m-2}$, $(-2)^{(m-1)^2}$.
These two families of graphs and their complements are examples of
strongly regular graphs, which will be the subject of
Section~\ref{srg}. The complement of $T(5)$ is the famous {\em
Petersen graph}. It has spectrum $3^1,~1^5,~(-2)^4$.

\subsubsection{Products}
Consider the Cartesian product $\Gamma \times \Delta$ of two graphs
$\Gamma$ and $\Delta$, where the vertex set is the Cartesian product
of the vertex sets of the factors, and two vertices are adjacent
where they agree in one coordinate and are adjacent in the other.

If $u$ and $v$ are eigenvectors for $\Gamma$ and $\Delta$ with
ordinary or Laplace eigenvalues $\theta$ and $\eta$, respectively,
then the vector $w$ defined by $w_{(x,y)} = u_x v_y$ is an
eigenvector of $\Gamma \times \Delta$ with ordinary or Laplace
eigenvalue $\theta + \eta$.

For example, $L_2(m) = K_m \times K_m$.

For example, the hypercube $2^n$, also called $Q_n$, is the
Cartesian product of $n$ factors $K_2$. The spectrum of $K_2$ is $1,
-1$, and hence the spectrum of $2^n$ consists of the numbers $n-2i$
with multiplicity ${n \choose i}$ $(i=0,1,\ldots,n)$.

\subsection{Decompositions}
Here we present two non-trivial application of linear algebra
to graph decompositions.

\subsubsection{Decomposing $K_{10}$ into Petersen graphs}
An amusing application is the following. Can the edges of the
complete graph $K_{10}$ be colored with three colors such that
each color induces a graph isomorphic to the Petersen graph?
$K_{10}$ has 45 edges, 9 on each vertex, and the Petersen graph
has 15 edges, 3 on each vertex, so at first sight this might seem
possible. Let the adjacency matrices of the three color classes
be $P_1$, $P_2$ and $P_3$, so that $P_1+P_2+P_3=J-I$.
If $P_1$ and $P_2$ are Petersen graphs, they both have
a 5-dimensional eigenspace for eigenvalue 1, contained in
the 9-space $\1^\perp$. Therefore, there is a common 1-eigenvector $u$
and $P_3 u = (J-I)u - P_1u - P_2u = -3u$ so that $u$ is an eigenvector
for $P_3$ with eigenvalue $-3$. But the Petersen graph does not have
eigenvalue $-3$, so the result of removing two edge-disjoint Petersen
graphs from $K_{10}$ is not a Petersen graph.
(In fact, it follows that $P_3$ is connected and bipartite.)

The argument is more often applicable. For example, $K_{55}$ is not
the union of three copies of the triangular graph $T(11)$.
% n=4t-1, v=(n choose 2), K_v is not t copies of T(n) fot t>1

\subsubsection{Decomposing $K_n$ into complete bipartite graphs}
% Graham-Polla(c)k, Tverberg, ...
A famous result is the fact that for any edge-decomposition of $K_n$
into complete bipartite graphs one need to use at least $n-1$ summands.
Since $K_n$ has eigenvalue $-1$ with multiplicity $n-1$ this follows
directly from the following:
%
\begin{Proposition}
Suppose a graph $\Gamma$ with adjacency matrix $A$ has an
edge decomposition into $r$ complete bipartite graphs.
Then $r \ge n_+(A)$ and $r \ge n_-(A)$, where $n_+(A)$ and $n_-(A)$
are the numbers of positive (negative) eigenvalues of $A$.
\end{Proposition}
%
\Proof
Let the $i$-th complete bipartite graph have a bipartition
where $u_i$ and $v_i$ are the characteristic vectors of both sides
of the bipartition, so that its adjacency matrix is
$D_i = u_i v_i^\top + v_i u_i^\top$, and $A = \sum D_i$.
Let $w$ be a vector orthogonal to all $u_i$. Then
$w^\top A w = 0$ and it follows that $w$ cannot be chosen in the
span of eigenvectors of $A$ with positive (negative) eigenvalue.
\qed

\subsection{Automorphisms}

An {\em automorphism} of a graph $\Gamma$ is a permutation $\pi$
of its point set $X$ such that $x \adj y$ if and only if
$\pi (x) \adj \pi (y)$.
Given $\pi$, we have a linear transformation $P_\pi$ on $V$
defined by $(P_\pi (u))_x = u_{ \pi (x) }$
for $u \in V$, $x \in X$. That $\pi$ is an automorphism
is expressed by $AP_\pi = P_\pi A$. It follows that $P_\pi$
preserves the eigenspace $V_\theta$ for each eigenvalue $\theta$
of $A$.

More generally, if $G$ is a group of automorphisms of $\Gamma$
then we find a linear representation of degree
$m( \theta ) = \dim V_\theta$ of $G$.

We denote the group of all automorphisms of $\Gamma$ by $\Aut \Gamma$.
One would expect that when $\Aut \Gamma$ is large, then
$m( \theta )$ tends to be large, so that $\Gamma$ has only few
distinct eigenvalues. And indeed the arguments below will
show that a transitive group of automorphisms does not go
very well together with simple eigenvalues.

Suppose $\dim V_\theta = 1$, say $V_\theta = \langle u\rangle$.
Since $P_\pi$ preserves $V_\theta$ we must have $P_\pi u = \pm u$.
So either $u$ is constant on the orbits of $\pi$, or
$\pi$ has even order, $P_\pi (u) = -u$, and $u$ is constant on the
orbits of $\pi^2$. For the Perron-Frobenius eigenvector we are
always in the former case.
%
\begin{Corollary}
If all eigenvalues are simple, then $\Aut \Gamma$ is an elementary
abelian $2$-group.
\end{Corollary}
%
\Proof If $\pi$ has order larger than two, then there are two distinct
vertices $x$, $y$ in an orbit of $\pi^2$, and all eigenvectors
have identical $x$- and $y$-coordinates, contradiction.
\qed
%
\begin{Corollary}
Let $\Aut \Gamma$ be transitive on $X$. (Then $\Gamma$ is regular of degree
$k$, say.)
\begin{enumerate}
\item
If $m( \theta ) = 1$ for some eigenvalue $\theta \ne k$,
then $v = | X |$ is even, and $\theta \equiv k$ $( \mod 2 )$.
If $\Aut \Gamma$ is moreover edge-transitive
then $\Gamma$ is bipartite and $\theta = - k$.
\item
If $m( \theta ) = 1$ for two distinct eigenvalues $\theta \ne k$,
then $v \equiv 0$ $( \mod 4 )$.
\item
If $m( \theta ) = 1$ for all eigenvalues $\theta$, then
$\Gamma$ has at most two vertices.
\end{enumerate}
\end{Corollary}
%
\Proof
(i) Suppose $V_\theta = \langle u\rangle$. Then $u$ induces a partition
of $X$ into two equal parts: $X = X_+ \cup X_-$,
where $u_x = a$ for $x \in X_+$ and
$u_x = -a$ for $x \in X_-$. Now
$\theta = k - 2 | \Gamma (x) \cap X_- |$ for $x \in X_+$.

(ii) If $m(k) = m( \theta ) = m( \theta' ) = 1$, then we find 3
pairwise orthogonal $( \pm 1)$-vectors, and a partition of $X$ into
four equal parts.

(iii) There are not enough integers $\theta \equiv k$ $( \mod 2 )$
between $-k$ and $k$.
\qed\\[5pt]
For more details, see
Cvetkovi\'c, Doob \& Sachs \cite{CDS}, Chapter 5.

\subsection{Exercises}

\Exercise
Show that no undirected graph has eigenvalue $\sqrt{2 + \sqrt 5}$.
(Hint: consider the algebraic conjugates of this number.)

\Exercise
Let $\Gamma$ be a tournament, that is, a directed graph
in which there is precisely one edge between any two distinct vertices,
in other words, of which the adjacency matrix $A$ satisfies
$A^\top + A = J-I$.
\begin{itemize}
\item[(i)]
Show that all eigenvalues have real part not less than $-1/2$.
\item[(ii)]
The tournament $\Gamma$ is called {\em regular} when
each vertex has the same number of out-arrows. Clearly,
when there are $n$ vertices, this number of out-arrows is $(n-1)/2$.
Show that all eigenvalues $\theta$ have real part at most $(n-1)/2$,
and that ${\rm Re} (\theta) = (n-1)/2$ occurs if and only if
$\Gamma$ is regular (and then $\theta = (n-1)/2$).
\item[(iii)]
Show that $A$ either has full rank $n$ or has rank $n-1$,
and that $A$ has full rank when $\Gamma$ is regular.
\end{itemize}
(Hint: for a vector $u$, consider the expression
$\bar{u}^\top (A^\top + A) u$.)

\Exercise
Let $\Gamma$ be bipartite and consider its line graph $L(\Gamma)$.
\begin{itemize}
\item[(i)]
Show that $\Gamma$ admits a directed incidence matrix $N$ such that
$N^\top\! N - 2I$ is the adjacency matrix of $L(\Gamma)$.
\item[(ii)]
Give a relation between the Laplace eigenvalues of $\Gamma$
and the ordinary eigenvalues of $L(\Gamma)$.
\item[(iii)]
Verify this relation in case $\Gamma$ is the path $P_n$.
\end{itemize}

\section{Linear algebra}

In this section we present some less elementary, but relevant results
from linear algebra.

\subsection{Hermitean linear transformations}

%First we recall some properties of Hermitean linear transformations.
%
Let $V$ be a complex vector space with finite dimension,
and fix a basis.
Then we can define an inner product on $V$ by putting
$(x,y) = \sum \bar{x}_i y_i = \bar{x}^\top y$ for $x,y \in {V}$,
where the bar denotes complex conjugation. If $A$ is {\em Hermitean},
i.e., if $(Ax,y) = (x,Ay)$ for all $x,y \in V$, then all eigenvalues
of $A$ are real, and $V$ admits an orthonormal basis of
eigenvectors of $A$.
%
\begin{Proposition}
Suppose ${\cal A}$ is a collection of commuting Hermitean
linear transformations on $V$ (i.e., $AB = BA$ for
$A,B \in {\cal A}$), then $V$ has a basis consisting of common
eigenvectors of all $A \in {\cal A}$.
\end{Proposition}
%
\Proof Induction on $\dim V$.
If each $A \in {\cal A}$ is a multiple of the identity $I$, then all
is clear. Otherwise, let $A \in {\cal A}$ not be a multiple of $I$.
If $Au = \theta u$ and $B \in {\cal A}$, then
$A(Bu) = BAu = \theta Bu$ so that $B$ acts as a linear transformation
on the eigenspace $V_\theta$ for the eigenvalue $\theta$ of $A$.
By the induction hypothesis we can choose a basis consisting of
common eigenvectors for each $B \in {\cal A}$ in each eigenspace.
The union of these bases is the basis of $V$ we were looking
for.
\qed
\\[5pt]
Given a square matrix $A$, we can regard $A$ as a linear transformation
on a vector space (with fixed basis). Hence the above concepts apply.
The matrix $A$ will be Hermitean precisely when $A = \bar{A}^\top$;
in particular, a real symmetric matrix is Hermitean.
%
% Let $A$ be a matrix, and let $u,v$ be right and left eigenvectors:
% $Au = \theta u$ and $v^\top A = \eta v^\top$.
% From $\eta v^\top u = v^\top Au = \theta v^\top u$ we see
% that if $\theta \ne \eta$ then $v^\top u = 0$.
%
% Now let $A$ be real and symmetric. If $Au = \theta u$, then
% $A \bar{u} = \bar{theta} \bar{u}$, where the bar denotes complex conjugation.
% If $\theta$ is not real, then it follows that $\bar{u}^\top u = 0$,
% so that $u = 0$.
%
% Thus: real symmetric matrices have real eigenvalues,
% and the eigenvectors for different eigenvalues are orthogonal.

\subsection{Perron-Frobenius Theory}
Let $T$ be a real $n \times n$ matrix with nonnegative entries.
$T$ is called {\em primitive} if for some $k$ we have $T^k > 0$;
$T$ is called {\em irreducible} if for all $i,j$ there is a $k$
such that $( T^k )_{ij} > 0$.

Here, for a matrix (or vector) $A$, $A > 0$ $( \ge 0)$ means that all
its entries are positive (nonnegative).

The matrix $T = (t_{ij} )$ is irreducible if and only if
the directed graph $\Gamma_T$ with vertices $\{1,\ldots,n\}$
and edges $(i,j)$ whenever $t_{ij} > 0$ is strongly connected.

(A graph $(X,E)$ is {\em strongly connected} if for any two vertices $x,y$
there is a directed path from $x$ to $y$, i.e.,
there are vertices $x_0=x, x_1, \ldots, x_m = y$ such that
$(x_{i-1},x_i) \in E$ for $1 \le i \le m$.)

Note that if $T$ is irreducible, then $I + T$ is primitive.

The {\em period} $d$ of an irreducible matrix $T$ is the greatest
common divisor of the integers $k$ for which $(T^k )_{ii} > 0$.
It is independent of the $i$ chosen.

\begin{Theorem}\label{PFthm}
Let $T \ge 0$ be irreducible. Then there is a (unique) positive
real number $\theta_0$ with the following properties:
%
\begin{enumerate}
\item
There is a real vector $x_0 > 0$ with $Tx_0 = \theta_0 x_0$.
\item
$\theta_0$ has geometric and algebraic multiplicity one.
\item
For each eigenvalue $\theta$ of $T$ we have $| \theta | \le \theta_0$.
If $T$ is primitive, then $| \theta | = \theta_0$ implies
$\theta = \theta_0$. In general, if $T$ has period $d$, then
$T$ has precisely $d$ eigenvalues $\theta$ with $| \theta | = \theta_0$,
namely $\theta = \theta_0 e^{ 2 \pi i j / d }$ for
$j = 0,1, ... ,d-1$. In fact the entire spectrum of $T$ is
invariant under rotation of the complex plane over an angle
$2 \pi / d$ about the origin.
\item
Any (nonzero) nonnegative left or right eigenvector of $T$ has
eigenvalue $\theta_0$. More generally, if $x \ge 0$, $x \ne 0$
and $Tx \le \theta x$, then $x > 0$ and $\theta \ge \theta_0$;
moreover, $\theta = \theta_0$ if and only if $Tx = \theta x$.
\item
If $0 \le S \le T$ or if $S$ is a principal minor of $T$,
and $S$ has eigenvalue $\sigma$, then
$| \sigma | \le \theta_0$; if $| \sigma | = \theta_0$, then $S = T$.
\end{enumerate}
\end{Theorem}
%
\Proof
(i) Let $P = (I + T)^{n-1}$. Then $P > 0$ and $PT = TP$.
Let $B = \{ x \mid x \ge 0 \mbox{~and~} x \ne 0 \}$. Define for $x \in B$:
$$
\theta ( x ) = \max_{ \theta \in \Rr } \{ \theta \mid \theta x \le Tx \}
= \min_{{1 \le i \le n} \atop {x_i \ne 0}} { (Tx)_i \over x_i }.
$$
Now $\theta ( \alpha x ) = \theta ( x )$ for $\alpha \in \Rr$, $\alpha > 0$,
and ($x \le y$, $x \ne y$ implies $Px < Py$, so)
$\theta ( Px ) \ge \theta ( x )$; in fact $\theta ( Px ) > \theta (x)$
unless $x$ is an eigenvector of $T$.
Put $C = \{ x \mid x \ge 0$ and $\norm x \norm = 1 \}$.
Then since $C$ is compact and $\theta ( . )$ is continuous on $P[C]$
(but not in general on $C$ !), there is an
$x_0 \in P[C]$ such that
$$
\theta_0 := \sup_{ x \in B } \theta (x) =
\sup_{ x \in C } \theta (x) =
\sup_{ x \in P[C] } \theta (x) = \theta ( x_0 ).
$$
Now $x_0 > 0$ and $x_0$ is an eigenvector of $T$,
so $Tx_0 = \theta_0 x_0$, and $\theta_0 > 0$.

(ii) For a vector $x = (x_1 , ... , x_n )^\top$,
write $x_{+} = ( | x_1 | , ... , | x_n | )^\top$.
If $Tx = \theta x$, then by the triangle inequality we have
$T x_{+} \ge | \theta | x_{+}$.
For nonzero $x$ this means
$| \theta | \le \theta (x_{+} ) \le \theta_0$.
If, for some vector $z \in B$, we have $Tz \ge \theta_0 z$, then
$z$ is eigenvector of $T$
(otherwise $\theta ( Pz ) > \theta_0$), and since
$0 < Pz = (1 + \theta_0 )^{n-1} z$ we have $z > 0$.
Now if $x$ is any eigenvector of $T$ with eigenvalue $\theta_0$,
then if $x$ is real consider $y = x_0 + \eps x$,
where $\eps$ is chosen such that $y \ge 0$ but not $y > 0$;
now $y \not\in B$, i.e., $y = 0$, so $x$ is a multiple of $x_0$.
In the general case, both the real and imaginary parts of $x$
are multiples of $x_0$.
This shows that the eigenspace of $\theta_0$ has
dimension 1, i.e., that the geometric multiplicity of $\theta_0$
is 1. We shall look at the algebraic multiplicity later.

(iii)
We have seen $| \theta | \le \theta_0$.
If $| \theta | = \theta_0$ and $Tx = \theta x$, then
$Tx_{+} = \theta_0 x_{+}$ and we had equality in the
triangle inequality
$| \sum_j t_{ij} x_j | \le \sum_j t_{ij} | x_j |$;
this means that all numbers $t_{ij} x_j$ ($1 \le j \le n$)
have the same angular part (argument).
If $T$ is primitive, then we can apply this reasoning with $T^k$
instead of $T$, where $T^k > 0$,
and conclude that all $x_j$ have the same angular part.
Consequently, in this case $x$ is a multiple of a real vector
and may be taken real, nonnegative. Now $Tx = \theta x$ shows that
$\theta$ is real, and $| \theta | = \theta_0$ that
$\theta = \theta_0$.
In the general case, $T^d$ is a direct sum of primitive matrices
$T^{(0)} , ... , T^{(d-1)}$,
and if $x = ( x^{(0)} , ... , x^{(d-1)} )$ is the corresponding
decomposition of an eigenvector of $T$ (with eigenvalue $\theta$), then
$( x^{(0)} , \zeta x^{(1)} , ... , \zeta^{d-1} x^{(d-1)} )$ also
is an eigenvector of $T$, with eigenvalue $\zeta \theta$, for any
$d$-th root of unity $\zeta$.
(Here we assume that the $T^{(i)}$ are ordered in such a way
that in $\Gamma_T$ the
arrows point from the subset corresponding to $T^{(i)}$ to the
subset corresponding to $T^{(i+1)}$.)
Since $T^d$ has a unique eigenvalue of maximum modulus
(let $T_{(i)}^{(i+1)}$ be the (nonsquare) submatrix of $T$
describing the arrows in $\Gamma_T$ between the subset corresponding
to $T^{(i)}$ to the subset corresponding to $T^{(i+1)}$;
then $T^{(i)} = \prod_{j=0}^{d-1} T_{(i+j)}^{(i+j+1)}$
and if $T^{(i)} z = \gamma z$, $z > 0$ then
$T^{(i-1)} z' = \gamma z'$ where
$z' = T_{(i-1)}^{(i)} z \ne 0$, so that all $T^{(i)}$ have
the same eigenvalue of maximum modulus), it follows that
$T$ has precisely $d$ such eigenvalues.

(iv)
Doing the above for left eigenvectors instead of right ones,
we find $y_0 > 0$ with $y_0^\top T = \eta_0 y_0^\top$.
If $Tx = \theta x$ and $y^\top T = \eta y^\top$, then
$\eta y^\top x = y^\top T x = \theta y^\top x$.
It follows that either $\theta = \eta$ or $y^\top x = 0$.
Taking $y \in B$, $x = x_0$ or $x \in B$, $y = y_0$
we see that $\theta = \eta$ ($= \theta_0 = \eta_0$).
Similarly, if $Tx \le \theta x$, $x \in B$ then
$\theta_0 y_0^\top x = y_0^\top Tx \le \theta y_0^\top x$
so that $\theta_0 \le \theta$; also
$0 < Px \le (1 + \theta )^{n-1} x$, so
$x > 0$.
If $\theta = \theta_0$, then $y_0^\top (Tx - \theta x) = 0$
so $Tx = \theta x$.

(v)
If $s \ne 0$, $Ss = \sigma s$, then
$Ts_{+} \ge Ss_{+} \ge | \sigma | s_{+}$,
so $| \sigma | \le \theta_0$.
But if $| \sigma | = \theta_0$ then $s_{+}$ is eigenvector
of $T$ and $s_{+} > 0$ and $(T - S)s_{+} = 0$,
so $S = T$.

(vi)
Finally, in order to prove that $\theta_0$ is a simple root
of $\chi_T$, the characteristic polynomial of $T$,
we have to show that ${d \over { d \theta }} \chi_T ( \theta )$
is nonzero for $\theta = \theta_0$.
But $\chi_T ( \theta ) = \det ( \theta I - T)$
and ${d \over { d \theta }} \chi_T ( \theta ) = \sum_i
\det ( \theta I - T_{ii} )$, and by (v) we have
$\det ( \theta I - T_{ii} ) > 0$ for $\theta = \theta_0$.
\qed

\Remark In case $T \ge 0$ but $T$ not necessarily irreducible,
we can say the following.
\begin{enumerate}
\item
The spectral radius $\theta_0$ of $T$ is an eigenvalue,
and there are nonnegative left and right eigenvectors
corresponding to it.
\item
If $0 \le S \le T$ and $S$ has eigenvalue $\sigma$, then
$| \sigma | \le \theta_0$.
\end{enumerate}
%
(\Proof (i) Use continuity arguments; (ii) the old proof still applies.)

For more details, see the exposition of the Perron-Frobenius theory in
Gantmacher \cite{Gantmacher}, Chapter XIII; cf. also
Varga \cite{Varga},
Marcus \& Minc \cite{MarcusMinc},
Berman \& Plemmons \cite{BermanPlemmons},
Seneta \cite{Seneta}, Chapter 1.

\medskip\noindent
By Perron-Frobenius theory, we know something about the largest
eigenvalue of a graph.

\begin{Proposition}
Each graph $\Gamma$ has a real eigenvalue $\theta_0$ with
nonnegative real corresponding eigenvector, and such
that for each eigenvalue $\theta$ we have $| \theta | \le \theta_0$.
\begin{enumerate}
\item
If $\Gamma$ is strongly connected, then $\theta_0$ has
multiplicity 1.
\item
If $\Gamma$ is primitive (strongly connected, and such that
not all cycles have a length that is a multiple of some
integer $d > 1$), then $| \theta | < \theta_0$ for all
eigenvalues $\theta$ different from $\theta_0$.
\item
The function $\theta_0 (\Gamma)$ decreases when vertices or edges
are removed from $\Gamma$.
\end{enumerate}
\end{Proposition}

\subsection{Equitable partitions}\label{partitions}

Suppose $A$ is a symmetric real matrix whose rows and columns are
indexed by $X = \{1,\ldots,n\}$. Let $\{X_1,\ldots,X_m\}$ be a
partition of $X$. The {\it characteristic matrix} $S$ is the
$n\times m$ matrix whose $j^{\mbox{\scriptsize th}}$ column is
the characteristic vector of $X_j$ ($j=1,\ldots,m$). Define
$n_i=|X_i|$ and $K={\rm diag}(n_1,\ldots,n_m)$. Let $A$ be
partitioned according to $\{X_1,\ldots,X_m\}$, that is
\[
A = \left[ \begin{array}{ccc}
A_{1,1} & \ldots & A_{1,m}\\
\vdots  &        & \vdots \\
A_{m,1} & \ldots & A_{m,m}
\end{array} \right],
\]
wherein $A_{i,j}$ denotes the submatrix (block) of $A$ formed by
rows in $X_i$ and the columns in $X_j$. Let $b_{i,j}$ denote the
average row sum of $A_{i,j}$. Then the matrix $B=(b_{i,j})$ is
called the {\it quotient matrix}. We easily have
\[
KB = {S^\top}AS,\ {S^\top}S = K.
\]
If the row sum of each block $A_{i,j}$ is constant then the
partition is called {\it equitable} (or {\it regular}) and we
have $A_{i,j}\1=b_{i,j}\1$ for $i,j = 0,\ldots,d$, so
\[
AS = SB.
\]
The following result is well-known and useful.
%
\begin{Lemma} If, for a equitable partition, $\v$ is an eigenvector
of $B$ for an eigenvalue $\lambda$, then $S\v$ is an eigenvector of
$A$ for the same eigenvalue $\lambda$.
\end{Lemma}
%
{\bf Proof.}
$B\v = \eigA\v$ implies $AS\v = SB\v = \eigA S\v$.
\qed\\[5pt]
For example, the adjacency matrix of the complete bipartite graph
$K_{m,n}$ has an equitable partition with $m=2$. The quotient
matrix $B$ equals
${\scriptsize [\begin{array}{cc}
\! 0\! &\! m\!\! \\
\! n\! &\! 0\!\!
\end{array}]}$
and has eigenvalues $\pm\sqrt{mn}$, which are the nonzero
eigenvalues of $K_{m,n}$.

\subsection{Interlacing}\label{interlacing0}

Consider two sequences of real numbers:
$\eigA_1\geq\ldots\geq\eigA_n$, and $\eigB_1\geq\ldots\geq\eigB_m$ with
$m<n$. The second sequence is said to {\it interlace} the first one
whenever
\[
\eigA_i\geq\eigB_i\geq\eigA_{n-m+i}, \mbox{ for } i=1,\ldots,m .
\]
The interlacing is {\it tight} if there exist an integer $k\in[0,m]$
such that
\[
\eigA_i=\eigB_i\mbox{ for } 1\leq i\leq k\ \mbox{ and }
\ \eigA_{n-m+i}=\eigB_i\mbox{ for }k+1\leq i\leq m .
\]
If $m=n-1$, the interlacing inequalities become
$\eigA_1\geq\eigB_1\geq\eigA_2\geq\eigB_2\geq\ldots\geq\eigB_m\geq\eigA_n$,
which clarifies the name. Godsil~\cite{god} reserves the name
`interlacing' for this particular case and calls it generalized
interlacing otherwise. Throughout, the $\eigA_i$'s and $\eigB_i$'s will
be eigenvalues of matrices $A$ and $B$, respectively. Basic to
eigenvalue interlacing is Rayleigh's principle, a standard (and easy
to prove) result from linear algebra, which can be stated as
follows. Let $\u_1,\ldots,\u_n$ be an orthonormal set of eigenvectors
of the real symmetric matrix $A$, such that $u_i$ is a
$\eigA_i$-eigenvector (we use this abbreviation for an eigenvector
corresponding to the eigenvalue $\eigA_i$). Then
\[
\rayl{\u}{A}\geq\eigA_i \mbox{ if }
u \in \left< \u_1,\ldots,\u_i \right> \mbox{ and}
\]
\[
\rayl{\u}{A}\leq\eigA_i \mbox{ if }
\u \in \left<\u_1,\ldots,\u_{i-1}\right>^\perp .
\]
In both cases, equality implies that $\u$ is a $\eigA_i$-eigenvector
of $A$.
%
\begin{Theorem}\label{interlacing}
Let $S$ be a real $n \times m$ matrix such that $S^\top S=I$.
Let $A$ be a real symmetric matrix of order $n$ with eigenvalues
$\eigA_1\geq\ldots\geq\eigA_n$. Define $B=S^\top AS$ and let $B$
have eigenvalues $\eigB_1\geq\ldots\geq\eigB_m$ and respective eigenvectors
$\v_1\ldots\v_m$.
%
\begin{itemize}
\item[(i)]
The eigenvalues of $B$ interlace those of $A$.
\item[(ii)]
If $\eigB_i=\eigA_i$ or $\eigB_i=\eigA_{n-m+1}$ for some $i\in[1,m]$, then
$B$ has a $\eigB_i$-eigenvector $\v$ such that $S\v$ is a
$\eigB_i$-eigenvector of $A$.
\item[(iii)]
If for some integer $l$, $\eigB_i=\eigA_i$, for $i=1,\ldots,l$ (or
$\eigB_i = \eigA_{n-m+i}$ for $i = l,\ldots,m$), then $S\v_i$ is a
$\eigB_i$-eigenvector of $A$ for $i=1,\ldots,l$ (respectively
$i=l,\ldots,m$).
\item[(iv)]
If the interlacing is tight, then $SB=AS$.
\end{itemize}
%
\end{Theorem}
%
{\bf Proof.}
With $\u_1,\ldots,\u_n$ as above, for each $i\in [1,m]$,
take a nonzero vector $\s_i$ in
\begin{eqnarray}\label{1}
\left<\v_1,\ldots,\v_i\right> \cap \left< S^\top\u_1,\ldots,S^\top
\u_{i-1}\right>^\perp .
\end{eqnarray}
Then $S\s_i\in\left<\u_1,\ldots,\u_{n-1}\right>^\perp $, hence by
Rayleigh's principle,
\[
\eigA_i\geq\rayl{(S\s_i)}{A}=\rayl{\s_i}{B}\geq\eigB_i ,
\]
and similarly (or by applying the above inequality to $-A$ and $-B$)
we get $\eigA_{n-m+i}\leq\eigB_i$, proving (i). If $\eigA_i=\eigB_i$,
then $\s_i$ and $S\s_i$ are $\eigA_i$-eigenvectors of $B$ and $A$,
respectively, proving (ii).
We prove (iii) by induction on $l$. Assume $S\v_i=\u_i$ for
$i=1,\ldots,l-1$. Then we may take $\s_l=\v_l$ in \ref{1}, but in
proving (ii) we saw that $S\s_l$ is a $\eigA_l$-eigenvector of $A$.
(The statement between parentheses follows by considering $-A$ and
$-B$.) Thus we have (iii).
Let the interlacing be tight. Then by (iii), $S\v_1,\ldots,S\v_m$ is
an orthonormal set of eigenvectors of $A$ for the eigenvalues
$\eigB_1,\ldots,\eigB_m$. So we have $SB\v_i=\eigB_iS\v_i=AS\v_i$, for
$i=1,\ldots,m$. Since the vectors $\v_i$ form a basis, it follows
that $SB=AS$.
\qed\\[5pt]
If we take $S=[I\ O]^\top$, then $B$ is just a principal submatrix of
$A$ and we have the following corollary.
%
\begin{Corollary}\label{ci}
If $B$ is a principal submatrix of a symmetric matrix $A$, then the
eigenvalues of $B$ interlace the eigenvalues of $A$.
\end{Corollary}
%
Suppose rows and columns of $A$ are partitioned with characteristic
matrix $\t S$ and quotient matrix $\t B$
(See Section~\ref{partitions}.)
%
\begin{Corollary}\label{hs}\label{interlacing2}
Let $\t B$ be the quotient matrix of a symmetric matrix $A$ whose
rows and columns are partitioned according to a partitioning
$\{X_1,\ldots,X_m\}$.
%
\begin{itemize}
\item[(i)]
The eigenvalues of $\t B$ interlace the eigenvalues of $A$.
\item[(ii)]
If the interlacing is tight, then the partition is equitable.
\end{itemize}
%
\end{Corollary}
%
{\bf Proof.}
Put $S=\t S K^{-\frac{1}{2}}$, where $K=\mbox{diag}(|X_1|,\ldots,|X_m|)$.
Then the eigenvalues of $B=S^\top AS$ interlace those of $A$. This proves
(i), because $B$ and $\t B = K^{-\frac{1}{2}}BK^{\frac{1}{2}}$ have the
same spectrum. If the interlacing is tight, then $SB=AS$, hence
$A\t S=\t S\t B$, and the partition is equitable.
\qed\\[5pt]
Theorem~\ref{interlacing}(i) is a classical result; see
Courant \& Hilbert~\cite{CourantHilbert1924}.
For the special case of a pricipal submatrix
(Corollary~\ref{ci}), the result even goes back to Cauchy and is
therefore often referred to as Cauchy interlacing. Interlacing for
the quotient matrix (Corollary~\ref{hs}) is especially applicable to
combinatorial structures (as we shall see). Payne (see, for
instance, \cite{pay}) has applied the extremal inequalities
$\eigA_1\geq\eigB_i\geq\eigA_n$ to finite geometries several times. He
attributes the method to Higman and Sims and therefore calls it the
Higman-Sims technique.

\Remark This theorem generalizes directly to complex Hermitean matrices
instead of real symmetric matrices (with conjugate transpose instead
of transpose) with virtually the same proof.

\medskip\noindent
For more detailed eigenvalue inequalities, see
Haemers \cite{HaemersThesis},\cite{hae'}.

\subsection{Exercises}
\Exercise
Consider a symmetric $n\times n$ matrix $A$ with eigenvalues
$\theta_1,\ldots,\theta_n$.
Suppose $A$ has an equitable partition $\{X_1,\ldots,X_m\}$,
where all classes have equal size.
Let $S$ and $B$ be the characteristic matrix and the
quotient matrix of this partition, respectively.
Assume that $\theta_1,\ldots,\theta_n$ are ordered such that
$\theta_1,\ldots,\theta_m$ are the eigenvalues of $B$.
Prove that $A$ and $SS^\top$ commute and give an expression
for the eigenvalues of $A+\alpha SS^\top$ for $\alpha\in\Rr$.

\Exercise
Let $B$ denote the quotient matrix of a symmetric matrix $A$ whose
rows and columns are partitioned according to a partitioning
$\{X_1,\ldots,X_m\}$.
\begin{enumerate}
\item
Give an example, where the eigenvalues of $B$ are a sub(multi)set of
the eigenvalues of $A$, whilst the partition is not equitable.
\item
Give an example where the partition is equitable, whilst the interlacing
in not tight.
\end{enumerate}

\section{Application to adjacency matrices}

\subsection{The largest eigenvalue}

By Perron-Frobenius theory and interlacing we find an upper
and lower bound for the largest eigenvalue of a connected graph.
(Note that $A$ is irreducible if and only if $\Gamma$ is connected.)

\begin{Proposition}
Let $\Gamma$ be a connected graph with largest eigenvalue $\theta_1$.
If $\Gamma$ is regular of valency $k$, then $\theta_1 = k$.
Otherwise, we have $k_{\min} < \bar{k} < \theta_1 < k_{\max}$
where $k_{\min}$, $k_{\max}$ and $\bar{k}$ are the
minimum, maximum and average degree.
\end{Proposition}

\Proof
Let ${\bf 1}$ be the vector with all entries equal to 1.
Then $A {\bf 1} \le k_{\max} {\bf 1}$, and by Theorem \ref{PFthm}(iv)
we have $\theta_1 \le k_{\max}$ with equality if and only if
$A {\bf 1} = \theta_1 {\bf 1}$, that is,
if and only if $\Gamma$ is regular of degree $\theta_1$.

Now consider the partition of the vertex set consisting of
a single part. By Corollary \ref{interlacing2}
we have $\bar{k} \le \theta_1$ with equality if and only if
$\Gamma$ is regular.
\qed\\[5pt]
For not necessarily connected graphs, we have
$\bar{k} \le \theta_1 \le k_{\max}$, and
$\bar{k} = \theta_1$ if and only if $\Gamma$ is regular, but
if $\theta_1 = k_{\max}$ then we only know
that $\Gamma$ has a regular component with this valency,
but $\Gamma$ need not be regular itself.
%
% \Remark Choosing the vector $u$ in the previous proof more subtly,
% we may obtain better bounds on $\theta_1$.

\subsection{Graphs with largest eigenvalue at most 2}

As an example of the application of Theorem \ref{PFthm} we can
mention:

\begin{Theorem}
{\rm (Smith \cite{Smith1970},
cf. Lemmens \& Seidel \cite{LemmensSeidel}).}
The only connected graphs having largest eigenvalue $2$ are
the following graphs (the number of vertices is one more than
the index given).
%
$$\begin{picture}(200,45)(-30,0)
\put(-40,0){\makebox(0,0)[c]{$\hat{A}_n$ $(n \ge 2)$}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(30,-8){\makebox(0,0)[c]{$1$}}
\put(60,0){\circle{4}}\multiput(62,0)(6.88,0){13}{\line(1,0){3.44}}
\put(60,-8){\makebox(0,0)[c]{$1$}}
\put(150,0){\circle{4}}\put(152,0){\line(1,0){26}}
\put(150,-8){\makebox(0,0)[c]{$1$}}
\put(180,0){\circle{4}}
\put(180,-8){\makebox(0,0)[c]{$1$}}
\put(105,37.5){\circle{4}}
\put(105,45){\makebox(0,0)[c]{$1$}}
\put(31.7889,0.8944){\line(2,1){71.4223}}
\put(178.2111,0.8944){\line(-2,1){71.4223}}
\end{picture}$$
$$\begin{picture}(200,45)(-30,0)
\put(-40,0){\makebox(0,0)[c]{$\hat{D}_n$ $(n \ge 4)$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(0,-8){\makebox(0,0)[c]{$1$}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(30,-8){\makebox(0,0)[c]{$2$}}
\put(60,0){\circle{4}}\multiput(62,0)(6.88,0){13}{\line(1,0){3.44}}
\put(60,-8){\makebox(0,0)[c]{$2$}}
\put(150,0){\circle{4}}\put(152,0){\line(1,0){26}}
\put(150,-8){\makebox(0,0)[c]{$2$}}
\put(180,0){\circle{4}}\put(182,0){\line(1,0){26}}
\put(180,-8){\makebox(0,0)[c]{$2$}}
\put(210,0){\circle{4}}
\put(210,-8){\makebox(0,0)[c]{$1$}}
\put(30,30){\circle{4}}\put(30,2){\line(0,1){26}}
\put(37,30){\makebox(0,0)[c]{$1$}}
\put(180,30){\circle{4}}\put(180,2){\line(0,1){26}}
\put(187,30){\makebox(0,0)[c]{$1$}}
\end{picture}$$
$$\begin{picture}(200,75)(-30,0)
\put(-40,0){\makebox(0,0)[c]{$\hat{E}_6$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(0,-8){\makebox(0,0)[c]{$1$}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(30,-8){\makebox(0,0)[c]{$2$}}
\put(60,0){\circle{4}}\put(62,0){\line(1,0){26}}
\put(60,-8){\makebox(0,0)[c]{$3$}}
\put(90,0){\circle{4}}\put(92,0){\line(1,0){26}}
\put(90,-8){\makebox(0,0)[c]{$2$}}
\put(120,0){\circle{4}}
\put(120,-8){\makebox(0,0)[c]{$1$}}
\put(60,30){\circle{4}}\put(60,2){\line(0,1){26}}
\put(60,60){\circle{4}}\put(60,32){\line(0,1){26}}
\put(67,30){\makebox(0,0)[c]{$2$}}
\put(67,60){\makebox(0,0)[c]{$1$}}
\end{picture}$$
$$\begin{picture}(200,45)(-30,0)
\put(-40,0){\makebox(0,0)[c]{$\hat{E}_7$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(0,-8){\makebox(0,0)[c]{$1$}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(30,-8){\makebox(0,0)[c]{$2$}}
\put(60,0){\circle{4}}\put(62,0){\line(1,0){26}}
\put(60,-8){\makebox(0,0)[c]{$3$}}
\put(90,0){\circle{4}}\put(92,0){\line(1,0){26}}
\put(90,-8){\makebox(0,0)[c]{$4$}}
\put(120,0){\circle{4}}\put(122,0){\line(1,0){26}}
\put(120,-8){\makebox(0,0)[c]{$3$}}
\put(150,0){\circle{4}}\put(152,0){\line(1,0){26}}
\put(150,-8){\makebox(0,0)[c]{$2$}}
\put(180,0){\circle{4}}
\put(180,-8){\makebox(0,0)[c]{$1$}}
\put(90,30){\circle{4}}\put(90,2){\line(0,1){26}}
\put(97,30){\makebox(0,0)[c]{$2$}}
\end{picture}$$
$$\begin{picture}(200,50)(-30,-5)
\put(-40,0){\makebox(0,0)[c]{$\hat{E}_8$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(0,-8){\makebox(0,0)[c]{$2$}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(30,-8){\makebox(0,0)[c]{$4$}}
\put(60,0){\circle{4}}\put(62,0){\line(1,0){26}}
\put(60,-8){\makebox(0,0)[c]{$6$}}
\put(90,0){\circle{4}}\put(92,0){\line(1,0){26}}
\put(90,-8){\makebox(0,0)[c]{$5$}}
\put(120,0){\circle{4}}\put(122,0){\line(1,0){26}}
\put(120,-8){\makebox(0,0)[c]{$4$}}
\put(150,0){\circle{4}}\put(152,0){\line(1,0){26}}
\put(150,-8){\makebox(0,0)[c]{$3$}}
\put(180,0){\circle{4}}\put(182,0){\line(1,0){26}}
\put(180,-8){\makebox(0,0)[c]{$2$}}
\put(210,0){\circle{4}}
\put(210,-8){\makebox(0,0)[c]{$1$}}
\put(60,30){\circle{4}}\put(60,2){\line(0,1){26}}
\put(67,30){\makebox(0,0)[c]{$3$}}
\end{picture}$$

\medskip\noindent
For each graph,
the corresponding eigenvector is indicated by the
integers at the vertices. Moreover, each connected graph
with largest eigenvalue less than $2$ is a subgraph of one of the above
graphs, i.e., one of the graphs $A_n = P_n$, the path
with $n$ vertices $(n \ge 1)$, or

$$\begin{picture}(200,35)(-30,0)
\put(-40,0){\makebox(0,0)[c]{$D_n$ $(n \ge 4)$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(60,0){\circle{4}}\multiput(62,0)(6.88,0){13}{\line(1,0){3.44}}
\put(150,0){\circle{4}}\put(152,0){\line(1,0){26}}
\put(180,0){\circle{4}}\put(182,0){\line(1,0){26}}
\put(210,0){\circle{4}}
\put(30,30){\circle{4}}\put(30,2){\line(0,1){26}}
\end{picture}$$
$$\begin{picture}(200,35)(-30,0)
\put(-40,0){\makebox(0,0)[c]{$E_6$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(60,0){\circle{4}}\put(62,0){\line(1,0){26}}
\put(90,0){\circle{4}}\put(92,0){\line(1,0){26}}
\put(120,0){\circle{4}}
\put(60,30){\circle{4}}\put(60,2){\line(0,1){26}}
\end{picture}$$
$$\begin{picture}(200,35)(-30,0)
\put(-40,0){\makebox(0,0)[c]{$E_7$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(60,0){\circle{4}}\put(62,0){\line(1,0){26}}
\put(90,0){\circle{4}}\put(92,0){\line(1,0){26}}
\put(120,0){\circle{4}}\put(122,0){\line(1,0){26}}
\put(150,0){\circle{4}}
\put(90,30){\circle{4}}\put(90,2){\line(0,1){26}}
\end{picture}$$
$$\begin{picture}(200,45)(-30,-10)
\put(-40,0){\makebox(0,0)[c]{$E_8$}}
\put(0,0){\circle{4}}\put(2,0){\line(1,0){26}}
\put(30,0){\circle{4}}\put(32,0){\line(1,0){26}}
\put(60,0){\circle{4}}\put(62,0){\line(1,0){26}}
\put(90,0){\circle{4}}\put(92,0){\line(1,0){26}}
\put(120,0){\circle{4}}\put(122,0){\line(1,0){26}}
\put(150,0){\circle{4}}\put(152,0){\line(1,0){26}}
\put(180,0){\circle{4}}
\put(60,30){\circle{4}}\put(60,2){\line(0,1){26}}
\end{picture}$$
%
Finally, each connected graph with largest eigenvalue more than $2$
contains one of $\hat{A}_n$, $\hat{D}_n$, $\hat{E}_6$,
$\hat{E}_7$, $\hat{E}_8$ as a subgraph.
\end{Theorem}

\Proof The vectors indicated are eigenvectors for the eigenvalue 2.
Therefore, $\hat{A}_n$, $\hat{D}_n$ and $\hat{E}_m$
($m = 6,7,8$) have largest eigenvalue 2.
Any graph containing one of these as an induced proper subgraph
has an eigenvalue larger than 2. So, if $\Gamma$ has largest
eigenvalue at most 2 and is not one of
$\hat{A}_n$ or $\hat{D}_n$, then $\Gamma$ is a tree
without vertices of degree at least 4 and with at most one vertex
of degree three, and the result easily follows.
\qed

\Remark It is possible to go a little bit further, and find all graphs
with largest eigenvalue at most
$\sqrt { 2 + \sqrt 5 } ~ \approx ~ 2.058171$, cf.
Brouwer \& Neumaier \cite{BroNeum89}.

\subsection{Regular graphs}

It is possible to see from the spectrum whether a graph is regular:

\begin{Proposition}
Let $\Gamma$ be a graph with eigenvalues
$k = \theta_1 \ge \theta_2 \ge ... \ge \theta_v$.
Equivalent are:
%
\begin{enumerate}
\item $\Gamma$ is regular (of degree $k$),
\item $AJ = kJ$,
\item $\sum \theta_i^2 = kv$.
\end{enumerate}
\end{Proposition}
%
\Proof We have seen that (i) and (ii) are equivalent. Also, if
$\Gamma$ is regular of degree $k$, then
$\sum \theta_i^2 = \tr A^2 = kv$. Conversely, if
(iii) holds, then $\bar{k} = v^{-1} \sum \theta_i^2 = \theta_1$
and by the above $\Gamma$ is regular.
\qed\\[5pt]
%
As we saw above in Section \ref{conn}, it is also possible to see
from the spectrum whether a graph is regular and connected.
However, for nonregular graphs it is not possible to see
from the spectrum whether it is connected.

A very useful characterization of regular connected graphs
was given by Hoffman \cite{Hoffman63}:

\begin{Proposition}
The graph $\Gamma$ is regular and connected if and only if
there exists a polynomial $p$ such that $J = p(A)$.
\end{Proposition}

\Proof If $J = p(A)$, then $J$ commutes with $A$ and hence $\Gamma$
is regular (and clearly also connected).
Conversely, let $\Gamma$ be connected and regular. Choose a basis
such that the commuting matrices $A$ and $J$ become diagonal.
Then $J$ becomes $\diag ( v , 0 , ... , 0 )$ and $A$ becomes
$\diag ( k , \theta_2 , ... , \theta_v )$.
Hence, if we put $f(x) = \prod_{i=2}^v (x - \theta_i )$, then
$J = vf(A)/f(k)$, so that $p(x) = vf(x)/f(k)$ satisfies the requirements.
\qed

\subsection{Bipartite graphs}

Among the connected graphs $\Gamma$, those with imprimitive $A$
are precisely the bipartite graphs (and for these,
$A$ has period 2).
Consequently we find from Theorem \ref{PFthm}(iii):

\begin{Proposition}
Equivalent are:
\begin{enumerate}
\item
$\Gamma$ is bipartite,
\item
for each eigenvalue $\theta$ of $\Gamma$, $- \theta$ is also
an eigenvalue, with the same multiplicity.
\end{enumerate}
\noindent
If $\Gamma$ is connected with largest eigenvalue $\theta_1$,
then (i) and (ii) are also equivalent to:
\begin{itemize}
\item[(iii)]
$-\theta_1$ is an eigenvalue of $\Gamma$.
\end{itemize}
\end{Proposition}
%
\Proof For connected graphs all is clear from the the
Perron-Frobenius theorem.
For not necessarily connected graphs we argue by induction
on the number of connected components.
Indeed, that (i) implies (ii) is clear, and for the opposite
direction, let $\theta_1$ be the spectral radius of $\Gamma$.
Then some connected component of $\Gamma$ has eigenvalues
$\theta_1$ and $- \theta_1$, and hence is bipartite. Removing
its contribution to the spectrum of $\Gamma$ we see by induction
on the number of components that all components are bipartite.
\qed

\subsection{The second largest eigenvalue of a regular graph}
Let $\Gamma$ be a regular graph of valency $k$ on $v$ vertices,
and assume that (for some real constant $\lambda$) we have
$|\theta| \le \lambda$ for all eigenvalues $\theta \ne k$.
The ratio $\lambda / k$ determines randomness and expansion
properties of $\Gamma$: the smaller $\lambda / k$, the more
random, and the better expander $\Gamma$ is.

For example, the following proposition says that most points
have approximately the expected number of neighbors in a
given subset of the vertex set.
%
\begin{Proposition}
Let $R$ be a subset of size $r$ of the vertex set $X$ of $\Gamma$.
Then
$$\sum_{x \in X} ( |\Gamma(x) \cap R| - {rk \over v})^2 \le
{r(v-r) \over v} \lambda^2 .$$
\end{Proposition}
%
\Proof
Apply interlacing to $A^2$ and the partition $\{R, X \setminus R \}$
of $X$.
\qed\\[5pt]
An {\em expander} is a graph with the property that the number of
points at distance at most one from any given (not too large) set is
at least a fixed constant (larger than one) times the size of the given set.
Expanders became famous because of their r\^ole in sorting networks
(cf. Ajtai-Koml\'os-Szemer\'edi \cite{AKS83})
and have since found many other applications.
The above proposition already implies that there cannot be too many vertices
without neighbors in $R$. A better bound was given by Tanner \cite{Tanner}
(in order to show that generalized polygons are good expanders).
%
\begin{Proposition} {\rm (Tanner \cite{Tanner})}
Let $R$ be a set of $r$ vertices of $\Gamma$ and let $\Gamma(R)$ be the
set of vertices adjacent to some point of $R$. Then
$${|\Gamma(R)| \over v } \ge { \rho \over \rho + {\lambda^2 \over k^2} (1 - \rho)}$$
where $\rho = r/v$.
\end{Proposition}
%
\Proof
Let $\chi$ be the characteristic vector of $R$.
Write it as a linear combination of a set of orthonormal eigenvectors of $A$:
$\chi = \sum \alpha_i u_i$ where $Au_i = \theta_i u_i$.
Then $A \chi = \sum \alpha_i \theta_i u_i$ and
$(A\chi,A\chi) = \sum \alpha_i^2 \theta_i^2$, so that
$\norm A\chi \norm^2 \le \alpha_0^2 (\theta_0^2 - \lambda^2) +
\lambda^2 \sum \alpha_i^2
= (\chi,u_0)^2 (k^2 - \lambda^2) + \lambda^2 (\chi,\chi)
= {r^2 \over v} (k^2 - \lambda^2) + r \lambda^2$.
Now let $\psi$ be the characteristic vector of $\Gamma(R)$.
Then
$k^2r^2 = (A\chi,1)^2 = (A\chi,\psi)^2 \le \norm A\chi \norm^2 \norm \psi \norm^2
\le |\Gamma(R)| . ({r^2 \over v} (k^2 - \lambda^2) + r \lambda^2)$,
proving our claim. \qed\\[5pt]
%
For similar results for not necessarily regular graphs, see
Section \ref{laplaceinterlacing}.

\subsection{Cliques and cocliques}

A {\em clique} in a graph is a set of pairwise adjacent vertices.
A {\em coclique} in a graph is a set of pairwise nonadjacent vertices.
The {\em clique number} $\omega(\Gamma)$ is the size of the
largest clique in $\Gamma$.
The {\em independence number} $\alpha(\Gamma)$ is the size of the
largest coclique in $\Gamma$.

Let $\Gamma$ be a graph on $n$ vertices (undirected, simple, and
loopless) having an adjacency matrix $A$ with eigenvalues
$\eigA_1\geq\ldots\geq\eigA_n$. Both Corollaries \ref{ci}
and \ref{hs} lead to a bound for $\alpha(\Gamma)$.
%
\begin{Theorem}\label{cv}
$\alpha(\Gamma)\leq n-n_{-} = | \{i|\eigA_i\geq 0\} |$ and
$\alpha(\Gamma)\leq n-n_{+} = | \{i|\eigA_i\leq 0\} |$.
\end{Theorem}
%
{\bf Proof.}
$A$ has a principal submatrix $B=O$ of size $\alpha=\alpha(\Gamma)$.
Corollary~\ref{ci} gives $\eigA_\alpha\geq\eigB_\alpha = 0$ and
$\eigA_{n-\alpha-1}\leq\eigB_1 = 0$.
\qed
%
\begin{Theorem}\label{ho}
If $\Gamma$ is regular of nonzero degree $k$, then
\[
\alpha(\Gamma)\leq n\frac{-\eigA_n}{k-\eigA_n},
\]
and if a coclique $C$ meets this bound, then every vertex not
in $C$ is adjacent to precisely $-\eigA_n$ vertices of $C$.
\end{Theorem}
%
{\bf Proof.}
We apply Corollary~\ref{hs}. The coclique gives rise to a
partition of $A$ with quotient matrix
\[
B=\left[ \begin{array}{cc}
0 & k \\ \frac{k\alpha}{n-\alpha} & k-\frac{k\alpha}{n-\alpha}
\end{array} \right] ,
\]
where $\alpha=\alpha(\Gamma)$. $B$ has eigenvalues $\eigB_1=k=\eigA_1$
(the row sum) and $\eigB_2= -k\alpha/(n-\alpha)$ (since
trace~$B=k+\eigB_2$) and so $\eigA_n\leq\eigB_2$ gives the required
inequality. If equality holds, then $\eigB_2=\eigA_n$, and since
$\eigB_1=\eigA_1$, the interlacing is tight and hence the partition
is equitable.
\qed\\[5pt]
The first bound is due to Cvetkovi\'c~\cite{cve}. The second bound
is an unpublished result of Hoffman.

\Example
The Petersen graph has 10 vertices and spectrum $3^1,~1^5,~(-2)^4$,
%(with multiplicities written as exponents),
and its independence number is 4. So both bounds are tight.

% \Example
% The strongly regular Higman-Sims graph has
% parameters $(v,k,\lambda,\mu) = (100,22,0,6)$ and eigenvalues
% $22, 2, -8$ of multiplicities $1, 77, 22$, respectively.
% Each point neighborhood is a coclique of size 22, and we
% have equality in (i).

\subsection{Chromatic number}\label{chrom}

A {\em proper vertex coloring} of a graph is an assignment of colors
to the vertices so that adjacent vertices get different colors.
(In other words, a partition of the vertex set into cocliques.)
The {\em chromatic number} $\chi(\Gamma)$ is the minimum number of
colors of a proper vertex coloring of $\Gamma$.

Since each coclique (color class) has size at most $\alpha(\Gamma)$,
we have $\chi(\Gamma) \ge n / \alpha(\Gamma)$ for a graph $\Gamma$
with $n$ vertices.
Thus upper bounds for $\alpha(\Gamma)$ give lower bounds for $\chi(\Gamma)$.
For instance if $\Gamma$ is regular of degree $k = \eigA_1$ then
Theorem~\ref{ho} implies that
$\chi(\Gamma)\geq1-\frac{\eigA_1}{\eigA_n}$. This bound remains
however valid for non-regular graphs.
%
\begin{Theorem}\label{chi}
%
\begin{itemize}
\item[(i)]
If $\Gamma$ is not edgeless then ${\displaystyle \chi(\Gamma)\geq
1-\frac{\eigA_1}{\eigA_n}}\ $. \vspace*{-8pt}
\item[(ii)]
If $\eigA_2>0$ then ${\displaystyle \chi(\Gamma)\geq
1-\frac{\eigA_{n-\chi(\Gamma)+1}}{\eigA_2}}\ $.
\end{itemize}
%
\end{Theorem}
%
{\bf Proof.}
Let $X_1,\ldots,X_{\chi}$ ($\chi=\chi(\Gamma)$) denote the color classes
of $\Gamma$ and let $\u_1,\ldots,\u_n$ be an orthonormal set of
eigenvectors of $A$ (where $\u_i$ corresponds to $\eigA_i$).
For $i=1,\ldots,\chi$ let $\s_i$ denote the restriction of $\u_1$
to $X_i$, that is
\[
(\s_i)_j = \left\{\begin{array}{ll}
(\u_1)_j&\mbox{ if }j\in X_i\ ,\\
0  &\mbox{ otherwise },
\end{array} \right.
\]
and put $\t S=[\s_1\ \cdots\ \s_{\chi}]$
(if some $\s_i=0$ we delete it from $\t S$ and
proceed similarly) and $D=\t S^{\top}\t S$, $S=\t SD^{-\2}$ and
$B=S^{\top}AS$. Then $B$ has zero diagonal (since each color class
corresponds to a zero submatrix of $A$) and an eigenvalue $\eigA_1$
($\d=D^{\2}\1$ is a $\eigA_1$-eigenvector of $B$). Moreover
Corollary~\ref{interlacing2} gives that the remaining eigenvalues of $B$
are at least $\eigA_n$. Hence
\[
0 = \mbox{trace}(B) = \eigB_1+\ldots+\eigB_{\chi} \geq
\eigA_1+(\chi-1)\eigA_n\ ,
\]
which proves (i), since $\eigA_n < 0$ because $\Gamma$ is not edgeless.
The proof of (ii) is similar, but a bit more complicated. With
$\s_1,\ldots,\s_{\chi}$ as above, choose a non-zero vector $\s$ in
\[
\left<\u_{n-\chi+1},\ldots,\u_n\right> \cap
\left<\s_1,\ldots,\s_\chi\right>^\perp\ .
\]
The two spaces have non-trivial intersection since the dimensions
add up to $n$ and $\u_1$ is orthogonal to both. Redefine $\s_i$
to be the restriction of $\s$ to $X_i$, and let $\t S, D, S$, and
$\d$ be analogous to above.
Put $A'=A-(\eigA_1-\eigA_2)\u_1\u_1^\top$, then the largest eigenvalue
of $A'$ equals $\eigA_2$, but all other eigenvalues of $A$ are also
eigenvalues of $A'$ with the same eigenvectors. Define
$B=S^{\top}A'S$. Now $B$ has again zero diagonal (since $\u_1^\top
S=0$). Moreover, $B$ has smallest eigenvalue
$\eigB_\chi\leq\eigA_{n-\chi+1}$, because
\[
\eigB_\chi \leq \rayl{\d}{B} = \rayl{\s}{A'} \leq \eigA_{n-\chi+1}\ .
\]
So interlacing gives
\[
0 = \mbox{trace}(B) = \eigB_1+\ldots+\eigB_\chi \leq
\eigA_{n-\chi+1} + (\chi-1)\eigA_2\ .
\]
Since $\eigA_2>0$, (ii) follows.
\qed\\[5pt]
The first inequality is due to Hoffman~\cite{hof}. The proof given
here appeared in \cite{hae`}. A coloring that meets this bound is
called a {\it Hoffman coloring}. For regular graphs, the color
classes of a Hoffman coloring are cocliques that meet Hoffman's
coclique bound. So in this case all the color classes have
equal size and the corresponding matrix partition is equitable.
In \cite{HaemersThesis} more inequalities of the above kind are given.
But only the two treated here turned out to be useful.
The condition $\eigA_2>0$ is not strong; only the complete
multipartite graphs, possibly extended with some isolated vertices
have $\eigA_2\leq0$. The second inequality looks a bit awkward,
but can be made more explicit if the smallest eigenvalue $\eigA_n$
has a large multiplicity.
%
\begin{Corollary}\label{chi'}
If the eigenvalue $\eigA_n$ has multiplicity $m$ and $\eigA_2>0$,
then
\[
\chi(\Gamma) \geq \mbox{min} \{1+m,1-\frac{\eigA_n}{\eigA_2}\}.
\]
\end{Corollary}
%
{\bf Proof.}
If $\chi(\Gamma) \leq m$, then $\eigA_n=\eigA_{n-\chi(\Gamma)+1}$,
hence $\chi(\Gamma) \geq 1-\frac{\eigA_n}{\eigA_2}$.
\qed

\subsection{Exercises}
\Exercise
Consider a graph with largest eigenvalue $\theta_1$ and
maximum valency $k_{\max}$. Use interlacing to show that
$\theta_1 \ge \sqrt{k_{\max}}$.
When does equality hold?
% only the star has equality

\Exercise
Let $\Gamma$ be a $k$-regular graph with $n$ vertices
and eigenvalues $\theta_1~(=k)\geq\ldots\geq\theta_n$.
Let $\Gamma'$ be an induced subgraph of $\Gamma$
with $n'$ vertices and average degree $k'$.
\begin{enumerate}
\item
Prove that
$ \theta_2\geq\frac{nk'-n'k}{n-n'}\geq\theta_n~$.
\item
What can be said in case of equality (on either side)?
\item
Deduce Hoffman's bound from the above inequality.
\end{enumerate}

\section{More applications of interlacing}

\subsection{The Laplace matrix}\label{laplaceinterlacing}

Let $\Gamma$ be a graph with Laplace matrix $L$
and Laplace eigenvalues
$0=\laplace_1\leq\ldots\leq\laplace_n$.
%(Laplace eigenvalues are usually ordered increasingly).
The Laplace matrix of a subgraph $\Gamma'$ of $\Gamma$ is not
a submatrix of $L$, unless $\Gamma'$ is a component.
So the interlacing techniques of Section~\ref{interlacing0}
do not work in such a straightforward manner here.
But we can obtain results if we consider off-diagonal submatrices
of $L$.
%
\begin{Proposition}\label{xy}
Let $X$ and $Y$ be disjoint sets of vertices of $\Gamma$, such that
there is no edge between $X$ and $Y$, then
\[
\frac{|X||Y|}{(n-|X|)(n-|Y|)} \leq
\left(\frac{\laplace_n-\laplace_{2}}{\laplace_n+\laplace_{2}}\right)^2\ .
\]
\end{Proposition}
%
{\bf Proof.}  Put $\laplace=-\2(\laplace_n+\laplace_{2})$ and
\[
A=\( {cc} O &L+\laplace{I}\\L+\laplace{I}& O \) \ .
\]
Then $\eigA_1=-\eigA_{2n}=\laplace$ and
$\eigA_2=-\eigA_{2n-1}=\2(\laplace_n-\laplace_{2})$. The sets $X$
and $Y$ give rise to a partitioning of $A$ with quotient matrix
\[
B=\({cccc}0&0&\laplace&0\\
0&0&\laplace-\laplace\frac{|X|}{n-|Y|}&\laplace\frac{|X|}{n-|Y|}\\
\laplace\frac{|Y|}{n-|X|}&\laplace-\laplace\frac{|Y|}{n-|X|}&0&0\\
0&\laplace&0&0\)\ .
\]
Clearly $\eigB_1=\eigA_1=\laplace$ and $\eigB_4=\eigA_{2n}=-\laplace$.
Using interlacing we find
\[
\laplace^2\frac{|X||Y|}{(n-|X|)(n-|Y|)} =
-\eigB_2\eigB_3 \leq -\eigA_2\eigA_{2n-1} =
(\2(\laplace_n-\laplace_{2}))^2,
\]
which gives the required inequality.
\qed\\[5pt]
The vertex sets $X$ and $Y$ with the above property are sometimes
called {\it disconnected vertex sets}. In the complement $X$ and
$Y$ become sets such that all edges between $X$ and $Y$ are present.
Such a pair is called a {\it biclique}.
A direct consequence of Proposition~\ref{xy} is an inequality of Helmberg,
Mohar, Poljak and Rendl~\cite{hmpr}, concerning the bandwidth of
a graph. A symmetric matrix $M$ is said to have bandwidth $w$ if
$(M)_{i,j}=0$ for all $i,j$ satisfying $|i-j|>w$. The bandwidth
$w(\Gamma)$ of a graph $\Gamma$ is the smallest possible bandwidth for its
adjacency matrix (or Laplace matrix). This number (and the
vertex order realizing it) is of interest for
some combinatorial optimization problems.
%
\begin{Theorem}\label{band}
Suppose $\Gamma$ is not edgeless and define $b=\left\lceil
n\frac{\laplace_{2}}{\laplace_n}\right\rceil$, then
\[
w(\Gamma)\geq\left\{\begin{array}{c}b\ \mbox{ if }\ n-b\ \mbox{ is even,}\\
b-1\ \mbox{ if }\ n-b\ \mbox{ is odd.}\end{array}\right.
\]
\\[-25pt]
\end{Theorem}
%
{\bf Proof.}  Order the vertices of $\Gamma$ such that $L$ has bandwidth
$w=w(\Gamma)$. If $n-w$ is even, let $X$ be the first $\2(n-w)$ vertices
and let $Y$ be the last $\2(n-w)$ vertices. Then Proposition~\ref{xy}
applies and thus we find the first inequality. If $n-w$ is odd, take
for $X$ and $Y$ the first and last $\2(n-w-1)$ vertices and the
second inequality follows. If $b$ and $w$ have different parity,
then $w-b\geq 1$ and so the better inequality holds.
\qed\\[5pt]
In case $n-w$ is odd, the bound can be improved a little by applying
Proposition~\ref{xy} with $|X|=\2(n-w+1)$ and $|Y|=\2(n-w-1)$. It is
clear that the result remains valid if we consider graphs with
weighted edges.

A more recent application of Proposition~\ref{xy} is the following
sufficient condition for existence of a perfect matching
(a {\it perfect matching} in a graph is a subset of the edges,
such that every vertex of the graph is incident with exactly one
edge of the subset).
%
\begin{Theorem}\label{pm}
Let $\Gamma$ be a graph with $n$ vertices, and Laplacian eigenvalues
$0=\laplace_1\leq\laplace_2\leq\ldots\leq\laplace_n$. If $n$ is even and
$\laplace_n\leq 2\laplace_2$, then $\Gamma$ has a perfect matching.
\end{Theorem}
%
Except for Proposition~\ref{xy}, we need two more tools. The first one
is Tutte's famous characterization of graphs with a perfect matching
(see \cite{tut}).
The second one is an elementary observation.
%
\begin{Theorem}
A graph $\Gamma = (V,E)$ has no perfect matching if and only
if there exists a subset $S\subset V$, such that the subgraph of
$\Gamma$ induced by $V\setminus S$ has more than $|S|$ odd
components.
\end{Theorem}
%
\begin{Lemma}\label{s}
Let $x_1\ldots x_n$ be $n$ positive integers such that $\sum_{i=1}^n
x_i = k\leq 2n-1$. Then for every integer $\ell$, satisfying $0 \leq
\ell \leq k$, there exists an $I\subset\{1,\ldots,n\}$ such that
$\sum_{i\in I} x_i = \ell$.
\end{Lemma}
%
{\bf Proof.} Induction on $n$. The case $n=1$ is trivial. If $n\geq
2$, assume $x_1\geq\ldots\geq x_n$. Then $n-1 \leq k-x_1 \leq
2(n-1)-1$ and we apply the induction hypothesis to $\sum_{i=2}^n x_i
= k-x_1$ with the same $\ell$ if $\ell\leq n-1$, and $\ell-x_1$
otherwise.
\qed\\[5pt]
{\bf Proof of Theorem~\ref{pm}.}
Assume $\Gamma=(V,E)$ has no perfect matching. By
Tutte's theorem there exists a set $S\subset V$ of size $s$ (say),
such that the subgraph $\Gamma'$ of $\Gamma$ induced by $V\setminus
S$ has $q > s$ odd components. But since $n$ is even, $s+q$ is even,
hence $q\geq s+2$.
\\
First assume $n\leq 3s+3$. Then $\Gamma'$ has at most $2s+3$
vertices and at least $s+2$ components. By Lemma~\ref{s}, $\Gamma'$
and hence $\Gamma$, has a pair of disconnected vertex sets $X$ and
$Y$ with $|X| = \lfloor\2 (n-s)\rfloor$ and $|Y| =
\lceil\2(n-s)\rceil$. Now Proposition~\ref{xy} implies
\[
\left( \frac{\laplace_n-\laplace_2}{\laplace_n+\laplace_2}\right)^2 \geq
\frac{|X|\cdot|Y|}{ns+|X|\cdot|Y|} =
\frac{(n-s)^2-\epsilon}{(n+s)^2-\epsilon}\ ,
\]
where $\epsilon=0$ if $n-s$ is even and $\epsilon=1$ if $n-s$ is odd.
Using $n\geq 2s+2$ we obtain
\[
\frac{\laplace_n-\laplace_2}{\laplace_n+\laplace_2} > \frac{n-s-1}{n+s} \geq
\frac{s+1}{3s+2} > \frac{1}{3} .
\]
Hence $2\laplace_2 < \laplace_n$.
\\
Next assume $n \geq 3s+4$. Now $\Gamma'$, and hence $\Gamma$, has a
pair of disconnected vertex sets $X$ and $Y$ with $|X|+|Y|=n-s$ and
$\min\{|X|,|Y|\}\geq s+1$, so
$|X|\cdot|Y|\geq(s+1)(n-2s-1)>ns-2s^2$. Now Proposition~\ref{xy} implies
\[
\left( \frac{\laplace_n-\laplace_2}{\laplace_n+\laplace_2}\right)^2 \geq
\frac{|X|\cdot|Y|}{ns+|X|\cdot|Y|} \geq
\frac{ns-2s^2}{2ns-2s^2} =
\frac{1}{2}-\frac{s}{2n-2s}>\frac{1}{4},
\]
by use of $n \geq 3s+4$. So
\[
\frac{\laplace_n-\laplace_2}{\laplace_n+\laplace_2} > \frac{1}{2} > \frac{1}{3},
\]
hence $2\laplace_2 < \laplace_n$.
\qed\\[5pt]
The complete bipartite graphs $K_{l,m}$ with $l\leq m$ have
Laplacian eigenvalues $\laplace_2=m$ and $\laplace_n=n=l+m$. This shows that
$2\laplace_2$ can get arbitrarily close to $\laplace_n$ for graphs with $n$
even and no perfect matching.

If the graph is regular, the result can be improved considerably.
Then $\laplace_2\geq 1$ and $n$ even is already sufficient for
existence of a perfect matching (see \cite{bh''}).

\subsection{Block Designs}\label{designs}

In case we have a non-symmetric matrix $N$ (say) we can still use
interlacing by considering the matrix
\[
A=\({cc}O&N\\N^\top&O\)\
\]
like we did in the previous section. Then we find
results in terms of the eigenvalues of $A$, which now satisfy
$\eigA_i=-\eigA_{n-i+1}$ for $i=1,\ldots,n$. The positive
eigenvalues of $A$ are the singular values of $N$, they are also the
square roots of the non-zero eigenvalues of $NN^\top$ (and of
$N^\top N$).

Suppose $N$ is the $0$-$1$ incidence matrix of an incidence structure
$(P,B)$ with point set $P$ (rows) and block set $B$ (columns).
%In particular if $N$ is the $v\times b$ , represents an incidence
%relation between
%points (rows) and blocks (columns) of incidence structure $D$,
Then we consider the so-called {\em incidence graph} $\Gamma$ of
$(P,B)$, which is the bipartite graph with
vertex set $P \cup B$, where two vertices are adjacent if they
correspond to an incident point-block pair.
An edge of $\Gamma$ is called a {\em flag} of $(P,B)$.

An incidence structure $(P,B)$ is called a $t$-$(v,k,\lambda)$ design
if $|P|=v$, if all blocks are incident with $k$ points, and if
for every $t$-set of points there are exactly $\lambda$ blocks
incident with all $t$ points.
For example $(P,B)$ is a $1$-$(v,k,r)$ design precisely when $N$
has constant column sums $k$ (i.e. $N^\top\1=k\1$),
and constant row sums $r$ (i.e. $N\1=r\1$), in
other words $\Gamma$ is biregular with degrees $k$ and $r$.
Moreover, $(P,B)$ is a $2$-$(v,k,\lambda)$ design if and only if
$N^\top\1=k\1$ and $NN^\top=\lambda J + (k-\lambda)I$.
Note that for $t\geq 1$, a $t$-design is also a $(t-1)$-design.
In particular a $2$-$(v,k,\lambda)$ design is also a $1$-$(v,k,r)$
design with $r=\lambda(v-1)/(k-1)$.
%
\begin{Theorem}\label{subd}
Let $(P,B)$ be a $1$-$(v,k,r)$ design with $b$ blocks and let
$(P',B')$ be a substructure with $m'$ flags. Define $b=|B|$,
$v'=|P'|$ and $b'=|B'|$. Then
\[(m'\frac{v}{v'}-b'k)(m'\frac{b}{b'}-v'r)\leq\eigA_2^2(v-v')(b-b')\ .\]
Equality implies that all four substructures induced by
$P'$ or $V\setminus V'$
%the point set of $D'$ or its complement,
and
$B'$ or $B\setminus B'$
%the block set of $D'$ or its complement
form a $1$-design (possibly degenerate).
\end{Theorem}
%
{\bf Proof.} We apply Corollary~\ref{hs}. The substructure $(P',B')$
gives rise to a partition of $A$ with the following quotient matrix
\[
B=\({cccc}0&0&\frac{m'}{v'}&r-\frac{m'}{v'}\\ \\
0&0&\frac{b'k-m'}{v-v'}&r-\frac{b'k-m'}{v-v'}\\ \\
\frac{m'}{b'}&k-\frac{m'}{b'}&0&0\\ \\
\frac{v'r-m'}{b-b'}&k-\frac{v'r-m'}{b-b'}&0&0\)\ .
\]
We easily have $\eigA_1=-\eigA_n=\eigB_1=-\eigB_4=\sqrt{rk}$ and
$$\det(B) = rk\left(\frac{m'\frac{v}{v'}-b'k}{v-v'}\right)
             \left(\frac{m'\frac{b}{b'}-v'r}{b-b'}\right).$$
Interlacing gives
\[
\frac{\det(B)}{rk}=-\eigB_2\eigB_3\leq-\eigA_2\eigA_{n-1}=\eigA_2^2\ ,
\]
which proves the first statement. If equality holds then
$\eigA_1=\eigB_1$, $\eigA_2=\eigB_2$, $\eigA_{n-1}=\eigB_3$ and
$\eigA_n=\eigB_4$, so we have tight interlacing, which implies the
second statement.
\qed\\[5pt]
The above result becomes especially useful if we can express $\eigA_2$ in
terms of the design parameters.
For instance if $(P,B)$ is a 2-$(v,k,\lambda)$ design,
then $\eigA_2^2=r-\lambda=\lambda\frac{v-k}{k-1}$
(see exercises)
%(see for example Hughes and Piper~\cite{hupi})
and if $(P,B)$ is a generalized quadrangle of order $(s,t)$, then
$\lambda^2_2=s+t$ (see Section~\ref{gq}). Let us consider two
special cases.
(A $2$-design $(P,B)$ with $|P|=|B|$ is called {\em symmetric}.)
%
\begin{Corollary}\label{symm}
If a symmetric $2$-$(v,k,\lambda)$ design $(P,B)$ has a symmetric
$2$-$(v',k',\lambda')$ subdesign $(P',B')$ (possibly degenerate) then
\[
(k'v-kv')^2 \leq (k-\lambda){(v-v')}^2.
\]
If equality holds, then the subdesign $(P',B\setminus B')$
is a $2$-$(v',v'(k-k')/(v-v'),\lambda-\lambda')$ design
(possibly degenerate).
\end{Corollary}
%
{\bf Proof.}
Take $b=v$, $r=k$, $b'=v'$, $m'=v'k'$ and $\eigA_2^2=k-\lambda$
and apply \ref{subd}.\qed\\[-15pt]
%
\begin{Corollary}\label{zero}
Let $X$ be a subset of the points and let $Y$ be a subset of the
blocks of a $2$-$(v,k,\lambda)$ design $(P,B)$, such that no point of
$X$ is incident with a block of $Y$, then
\[
kr|X||Y|\leq(r-\lambda)(v-|X|)(b-|Y|).
\]
If equality holds then the substructure $(X,B')=(X,B\setminus Y)$
is a $2$-design.
\end{Corollary}
%
{\bf Proof.}
Take $m'=0$, $v'=|X|$, $b'=|Y|$ and $\eigA_2^2=r-\lambda$.
Now \ref{subd} gives the inequality and that $(X,B')$ is a 1-design.
But then $(X,B')$ is a 2-design, because $(P,B)$ is.
\qed\\[5pt]
An example of a subdesign of a symmetric design is the incidence
structure formed by the absolute point and lines of a polarity in a
projective plane of order $q$. This gives a (degenerate)
$2$-$(v',1,0)$ design in a $2$-$(q^2+q+1,q+1,1)$ design. The bound
gives $v'\leq q\sqrt{q} +1$. The $2$-$(q\sqrt{q}+1,q+1,1)$ design,
which is obtained in case of equality is called a {\it unital}.
Other examples of symmetric designs that meet the bound can be found
in Haemers and Shrikhande~\cite{hash} or Jungnickel~\cite{jun}.
Wilbrink used Theorem~\ref{subd} to shorten the proof of Feit's
result on the number of points and blocks fixed by an automorphism
group of a symmetric design (see \cite{bw}). The inequality of the
second corollary is for example tight for hyperovals and (more
generally) maximal arcs in finite projective planes.

\subsection{Exercises}
\Exercise
A biclique in a graph $\Gamma$ is a complete bipartite
subgraph $K_{\ell,m}$ of $\Gamma$ (not necessarily induced).
The {\em size} of a biclique equals $\ell m$ (i.e. the number
of edges in $K_{\ell,m}$).
Let $\mu_1\leq\ldots\leq\mu_n$ be the Laplace eigenvalues
of $\Gamma$.
Prove that the size of a biclique is at most
$(n(\mu_2-\mu_n)/2\mu_2)^2$.

\Exercise
Let $A$ be the incidence graph of a $2$-$(v,k,\lambda)$ design
with $b$ blocks and $r$ blocks incident with each point.
Express the spectrum of $A$ in the design parameters
$v$, $k$, $\lambda$, $b$ and $r$.

\Exercise
Let $(P,B)$ is a $2$-$(v,k,\lambda)$ design,
and suppose that some block is repeated
$\ell$ times (i.e. $\ell$ blocks
are incident with exactly the same set
of $k$ points).
Prove that $b\geq\ell v$
(this is Mann's inequality).

\section{Strongly regular graphs}

\subsection{General results}

A graph (simple, undirected and loopless) of order $v$ is called
{\it strongly regular} with parameters $v$, $k$, $\lambda$, $\mu$
whenever it is not complete or edgeless and
%
\begin{itemize}
\item[(i)]
each vertex is adjacent to $k$ vertices,
\item[(ii)]
for each pair of adjacent vertices there are $\lambda$ vertices
adjacent to both,
\item[(iii)]
for each pair of non-adjacent vertices there are $\mu$ vertices
adjacent to both.
\end{itemize}
%
For example, the pentagon is strongly regular with
parameters $(v,k,\lambda ,\mu ) = (5,2,0,1)$.
One easily verifies that a graph $\Gamma$ is strongly regular
with parameters $(v,k,\lambda ,\mu )$ if and only if
its complement $\overline{\Gamma}$ is strongly regular with parameters
$(v, v-k-1, v-2k+ \mu -2, v-2k+ \lambda )$.
The line graph of the complete graph of order $m$, known as
the {\it triangular graph} $T(m)$, is strongly regular with
parameters $(\frac{1}{2}m(m-1), 2(m-2), m-2, 4)$.
%The complement of $T(5)$ is the Petersen graph.

For convenience we call an eigenvalue {\it restricted} if it
has an eigenvector perpendicular to the all-ones
vector $\1$.
%
\begin{Theorem}\label{srg}
For a simple graph $\Gamma$ of order $v$, not complete or edgeless,
with adjacency matrix $A$, the following are equivalent:
\begin{itemize}
\item[(i)]
$\Gamma$ is strongly regular with parameters $(v,k,\lambda ,\mu )$ for
certain integers $k$, $\lambda$, $\mu$,
\item[(ii)]
$A^2 = (\lambda - \mu )A + (k - \mu )I + \mu J$ for certain real numbers
$k$, $\lambda$, $\mu$,
\item[(iii)]
$A$ has precisely two distinct restricted eigenvalues.
\end{itemize}
\end{Theorem}
%
{\bf Proof.}
The equation in (ii) can be rewritten as
\[
A^2 = kI + \lambda A + \mu (J - I - A).
\]
Now (i) $\iff$ (ii) is obvious.\\
(ii) $\Rightarrow$ (iii): Let $\rho$ be a restricted eigenvalue, and
$u$ a corresponding eigenvector perpendicular to $\1$.
Then $Ju = 0$. Multiplying the equation in (ii) on the right by $u$
yields $\rho^2 = ( \lambda - \mu ) \rho + (k - \mu )$.
This quadratic equation in $\rho$ has two distinct solutions.
(Indeed, $( \lambda - \mu )^2 = 4( \mu - k)$ is impossible since
$\mu \leq k$ and $\lambda \leq  k-1$.)\\
(iii) $\Rightarrow$ (ii): Let $r$ and $s$ be the restricted
eigenvalues. Then $(A - rI)(A - sI) = \alpha J$ for some real number
$\alpha$. So $A^2$ is a linear combination of $A$, $I$ and $J$.
\qed\\[5pt]
As an application, we show that quasi-symmetric block designs
give rise to strongly regular graphs. A {\em quasisymmetric design}
is a 2-$(v,k, \lambda )$ design
(see Section~\ref{designs}) such that any two blocks meet in
either $x$ or $y$ points, for certain fixed $x$, $y$.
Given this situation, we may define a graph $\Gamma$ on the set of blocks,
and call two blocks adjacent when they meet in $x$ points.
Then there exist coefficients $\alpha_1 , \dots , \alpha_7$
such that
$NN^\top = \alpha_1 I + \alpha_2 J$,
$NJ = \alpha_3 J$, $JN = \alpha_4 J$,
$A = \alpha_5 N^\top N + \alpha_6 I + \alpha_7 J$,
where $A$ is the adjacency matrix of the graph $\Gamma$.
(The $\alpha_i$ can be readily expressed
in terms of $v$, $k$, $\lambda$, $x$, $y$.)
Then $\Gamma$ is strongly regular by (ii) of the previous theorem.
(Indeed, from the equations just given it follows straightforwardly
that $A^2$ can be expressed as a linear combination of
$A$, $I$ and $J$.)
A large class of quasisymmetric block designs is provided by
the 2-$(v,k,\lambda )$ designs with $\lambda = 1$ (also known as
Steiner systems $S(2,k,v)$) - such designs have only two
intersection numbers since no two blocks can meet in more than one point.
This leads to a substantial family of strongly regular graphs,
including the triangular graphs $T(m)$ (derived from the
trivial design consisting of all pairs out of an $m$-set).

Another connection between strongly regular graphs and designs is
found as follows: Let $A$ be the adjacency matrix of a strongly
regular graph with parameters $(v,k, \lambda , \lambda )$ (i.e.,
with $\lambda = \mu$; such a graph is sometimes called a $(v,k,
\lambda )$ graph). Then, by Theorem~\ref{srg}
\[
AA^\top = A^2 = (k -\lambda ) I +\lambda J,
\]
which reflects that $A$ is the incidence matrix of a
symmetric 2-$(v,k, \lambda )$ design.
(And in this way one obtains precisely all symmetric 2-designs
possessing a polarity without absolute points.)
For instance, the triangular graph $T(6)$ provides a symmetric
2-$(15,8,4)$ design, the complementary design of the design of
points and planes in the projective space $PG(3,2)$.
Similarly, if $A$ is the adjacency matrix of a strongly regular graph
with parameters $(v,k, \lambda , \lambda +2)$, then $A + I$ is the incidence
matrix of a symmetric 2-$(v,k,\lambda )$ design (and in this way one obtains
precisely all symmetric 2-designs possessing a polarity with all points
absolute).
%
\begin{Theorem}\label{srgparam}
Let $\Gamma$ be a strongly regular graph with adjacency matrix $A$ and
parameters $(v,k, \lambda , \mu )$. Let $r$ and $s$ $(r > s)$ be the
restricted eigenvalues of $A$ and let $f$, $g$ be their respective
multiplicities. Then
%
\begin{itemize}
\item[(i)]
$k(k - 1 - \lambda ) = \mu (v - k - 1)$,
\item[(ii)]
$r s = \mu - k,~ r + s = \lambda - \mu$,
\item[(iii)]
$f,~g = \frac{1}{2} ( v - 1 \mp \frac{(r + s)(v - 1) + 2k}{r - s})$.
\item[(iv)]
$r$ and $s$ are integers, except perhaps when $f = g$,
$(v,k, \lambda , \mu ) = (4t+1,2t,t-1,t)$ for some integer $t$.
\end{itemize}
%
\end{Theorem}
%
{\bf Proof.}
(i) Fix a vertex $x$ of $\Gamma$. Let $\Gamma(x)$ and $\Delta(x)$ be
the sets of vertices adjacent and non-adjacent to $x$,
respectively. Counting in two ways the number of edges between
$\Gamma(x)$ and $\Delta(x)$ yields (i). The equations (ii) are direct
consequences of Theorem~\ref{srg}(ii), as we saw in the proof.
Formula (iii) follows from $f + g = v - 1$ and $0 = \mbox{trace }
A = k + fr + gs = k + \frac{1}{2}(r+s)(f+g) + \frac{1}{2}(r-s)(f-g)$.
Finally, when $f\neq g$ then one can solve for $r$ and $s$ in (iii)
(using (ii)) and find that $r$ and $s$ are rational, and hence
integral. But $f = g$ implies $(\mu -\lambda )(v - 1) = 2k$, which is
possible only for $\mu - \lambda = 1$, $v = 2k + 1$.
\qed\\[5pt]
These relations imply restrictions for the possible values of the
parameters. Clearly, the right hand sides of (iii) must be positive
integers. These are the so-called {\it rationality conditions}.
As an example of the application of the rationality conditions
we can derive the following result due to Hoffman \&
Singleton~\cite{hs}
%
\begin{Theorem}\label{moore}
Suppose $(v,k,0,1)$ is the parameter set of a strongly regular graph.
Then $(v,k) = (5,2)$, $(10,3)$, $(50,7)$ or $(3250,57)$.
\end{Theorem}
%
{\bf Proof.}
The rationality conditions imply that either $f = g$, which leads to
$(v,k) = (5,2)$, or $r-s$ is an integer dividing $(r+s)(v-1) + 2k$.
By use of \ref{srgparam}(i)-(ii) we have
\[
s = -r-1,~ k = r^2 +r+1,~ v = r^4 +2r^3 +3r^2 +2r + 2,
\]
and thus we obtain $r = 1$, $2$ or $7$.
\qed
\\[5pt]
The first three possibilities are uniquely realized by the pentagon, the
Petersen graph and the Hoffman-Singleton graph. For the last case
existence is unknown (but see Aschbacher~\cite{asc}).

Except for the rationality conditions, a few other restrictions on the
parameters are known. We mention two of them.
The Krein conditions, due to Scott~\cite{sco},
can be stated as follows:
\[
(r + 1)(k + r + 2rs) \leq  (k + r)(s + 1)^2 ,
\]
\[
(s + 1)(k + s + 2rs) \leq  (k + s)(r + 1)^2 .
\]
Seidel's absolute bound (see Delsarte, Goethals \&
Seidel~\cite{dgs}) reads,
\[
v \leq  f(f + 3)/2,\ v \leq  g(g + 3)/2.
\]
The Krein conditions and the absolute bound
are special cases of general inequalities for
association schemes - we'll meet them again in the next section.
In Brouwer \& Van Lint~\cite{bl}
one may find a list of known restrictions.
It is a sequel to Hubaut's~\cite{hub}
earlier survey of constructions.
%Seidel~\cite{sei} gives a good treatment of the theory.

\subsection{Strongly regular graphs with eigenvalue
$-2$}\label{srg-2}

For later use we give without proof Seidel's classification
\cite{Seidelmin2} of the strongly regular graphs with $s = -2$.
%
\begin{Theorem}
Let $\Gamma$ be a strongly regular graph with smallest eigenvalue $-2$.
Then $\Gamma$ is one of
%
\begin{itemize}
\item[(i)]
the complete $n$-partite graph $K_{2,\ldots,2}$, with parameters
$(v,k,\lambda,\mu) = \maysplit (2n, \maysplit 2n-2, 2n-4, 2n-2)$,
$n \ge 2$,
\item[(ii)]
the lattice graph $L_2(n) = K_n \times K_n$, with parameters
$(v,k,\lambda,\mu) = (n^2, \maysplit 2(n-1), \maysplit n-2, 2)$, $n \ge 3$,
\item[(iii)]
the Shrikhande graph, with parameters
$(v,k,\lambda,\mu) = (16,6,2,2)$,
\item[(iv)]
the triangular graph $T(n)$ with parameters
$(v,k,\lambda,\mu) = \maysplit ({n \choose 2}, 2(n-2),\maysplit n-2,
\maysplit 4)$, $n \ge 5$,
\item[(v)]
one of the three Chang graphs, with parameters
$(v,k,\lambda,\mu) = (28, 12, 6, 4)$,
\item[(vi)]
the Petersen graph, with parameters $(v,k,\lambda,\mu) = (10, 3, 0, 1)$,
\item[(vii)]
the Clebsch graph, with parameters $(v,k,\lambda,\mu) = (16, 10, 6, 6)$,
\item[(viii)]
the Schl\"{a}fli graph, with parameters $(v,k,\lambda,\mu) = (27, 16, 10, 8)$.
\end{itemize}
\end{Theorem}

\subsection{Connectedness}
A strongly regular graph is called {\em imprimitive} if it,
or its complement, is disconnected, and {\em primitive} otherwise.
Imprimitive strongly regular graphs are boring.

If a strongly regular graph is not connected, then $\mu = 0$ and
$k = \lambda+1$. And conversely, if $\mu = 0$ or $k = \lambda+1$
then the graph is a disjoint union $aK_m$ of some number $a$
of complete graphs $K_m$.
In this case $v = am$, $k = m-1$, $\lambda = m-2$, $\mu = 0$
and the spectrum is $(m-1)^a, ~ (-1)^{a(m-1)}$.
%(with multiplicities written as exponents).

If the complement of a strongly regular graph is not connected,
then $k = \mu$. And conversely, if $k = \mu$ then the graph is
the complete multipartite graph $K_{a \times m}$, the complement
of $aK_m$, with parameters $v = am$, $k = \mu = (a-1)m$, $\lambda = (a-2)m$
and spectrum $(a-1)m^1,~0^{a(m-1)},~(-m)^{a-1}$.

For a primitive strongly regular graph one has $k > r > 0$ and $s < -1$.

\medskip\noindent
For a graph $\Gamma$, let $\Gamma_i(x)$ denote the set of vertices
at distance $i$ from $x$ in $\Gamma$. Instead of $\Gamma_1(x)$ we
write $\Gamma(x)$.
%
\begin{Proposition}\label{farconnected}
If $\Gamma$ is a primitive strongly regular graph,
then for each vertex $x$ the subgraph $\Gamma_2 (x)$ is connected.
\end{Proposition}
%
\Proof
Note that $\Gamma_2 (x)$ is regular of valency $k - \mu$.
If it is not connected, then its eigenvalue $k - \mu$ would have
multiplicity at least two, and hence would be not larger than the
second largest eigenvalue $r$ of $\Gamma$. Then
$x^2 + ( \mu - \lambda ) x + \mu - k \le 0$ for $x = k - \mu$, i.e.,
$(k - \mu )(k - \lambda - 1) \le 0$, contradiction.
\qed\\[5pt]
The {\em vertex connectivity} $\kappa(\Gamma)$ of a connected non-complete
graph $\Gamma$ is the smallest integer $m$ such that $\Gamma$ can be
disconnected by removing $m$ vertices.
%
\begin{Theorem}\label{bromesner} {\rm (\cite{BroMesner}).}
Let $\Gamma$ be a connected strongly regular graph of valency $k$.
Then $\kappa(\Gamma) = k$, and the only disconnecting sets of size $k$
are the sets of all neighbors of some vertex $x$.
\end{Theorem}
%
\Proof
Clearly, $\kappa(\Gamma) \le k$.
Let $S$ be a disconnecting set of vertices not containing all
neighbors of some vertex. Let $\Gamma \setminus S = A + B$
be a separation of $\Gamma \setminus S$. Since the eigenvalues
of $A \cup B$ interlace those of $\Gamma$, it follows that
at least one of $A$ and $B$, say $B$, has largest eigenvalue
at most $r$. It follows that the average valency of $B$ is at most $r$.
Since $B$ has an edge, $r > 0$.

Now let $|S| \le k$. Since $B$ has average valency at most $r$,
we can find two points $x,y$ in $B$ such that
$|S \cap \Gamma(x)| + |S \cap \Gamma(y)| \ge 2(k-r)$, so that
these points have at least $k - 2r$ common neighbors in $S$.

If $\Gamma$ has nonintegral eigenvalues, the we have
$(v,k,\lambda,\mu) = (4t+1,2t,t-1,t)$ for some $t$, and
$r = (-1 + \sqrt{v})/2$. The inequality
$\max(\lambda,\mu) \ge k-2r$ gives $t \le 2$, but for $t = 2$
the eigenvalues are integral, so we have $t = 1$ and $\Gamma$
is the pentagon. But the claim is true in that case.

Now let $r,s$ be integral. If $s \le -3$, then
$\mu = k + rs \le k - 3r$ and $\lambda = \mu + r + s \le k - 2r - 3$,
so that no two points can have $k-2r$ common neighbors.

Therefore $s = -2$, and we have one of the eight cases in
Seidel's classification. But not case (i), since $r > 0$.

% Now $A+2I$ is positive semidefinite, and hence is the Gram matrix
% of a set of vectors $X$ in a space of (very small) dimension $f+1$.
% ...?

Since both $A$ and $B$ contain an edge, both $B$ and $A$
have size at most $\bar{\mu} = v-2k+\lambda$, so that
both $A$ and $B$ have size at least $k-\lambda$, and $v \ge 3k-2\lambda$.
This eliminates cases (vii) and (viii).

If $B$ is a clique, then $|B| \le r+1 = k-\lambda-1$, contradiction.
So, $B$ contains two nonadjacent vertices, and their neighbors must be in
$B \cup S$, so $2k-\mu \le |B|+|S|-2$ and
$k-\mu+2 \le |B| \le \bar{\mu}$.

In cases (iii), (v), (vi) we have $\bar{\mu} = k-\mu+2$, so equality
holds and $|B| = \bar{\mu}$ and $|S| = k$. Since $v < 2\bar{\mu} + k$,
we have $|A| < \bar{\mu}$ and $A$ must be a clique
(of size $v - k - \bar{\mu} = k - \lambda$).
But the Petersen graph does not contain a 3-clique,
and the Shrikhande graph does not contain 4-cliques;
also, if $A$ is a 6-clique in a Chang graph, and $a,b,c \in A$,
then $\Gamma(a) \cap S$, $\Gamma(b) \cap S$, and $\Gamma(c) \cap S$
are three 7-sets in the 12-set $S$ that pairwise meet in precisely
two points, impossible. This eliminates cases (iii), (v), (vi).

We are left with the two infinite families of lattice graphs
and triangular graphs. In both cases it is easy to see that if
$x,y$ are nonadjacent, then there exist $k$ paths joining $x$ and $y$,
vertex disjoint apart from $x,y$, and entirely contained in
$\{x,y\} \cup \Gamma(x) \cup \Gamma(y)$. Hence $|S| = k$, and
if $S$ separates $x,y$ then $S \subseteq \Gamma(x) \cup \Gamma(y)$.

The subgraph
$\Delta := \Gamma \setminus (\{x,y\} \cup \Gamma(x) \cup \Gamma(y))$
is connected (if one removes a point and its neighbors from
a lattice graph, the result is a smaller lattice graph, and the same holds
for a triangular graph), except in the case of the triangular graph
${5 \choose 2}$ where $\Delta$ is empty.

Each vertex of $(\Gamma(x) \cup \Gamma(y)) \setminus S$
has a neighbor in $\Delta$ and we find a path of length 4
disjoint from $S$ joining $x$ and $y$, except in the case
of the triangular graph ${5 \choose 2}$, where each vertex
of $\Gamma(x) \setminus S$ is adjacent to each vertex of
$\Gamma(y) \setminus S$, and we find a path of length 3
disjoint from $S$ joining $x$ and $y$.
\qed

\subsection{Cocliques and colorings}

In Section~\ref{interlacing0} we have derived some bounds
the size of a coclique in terms of eigenvalues. These bounds
are especially useful for strongly regular graphs. Moreover,
strongly regular graphs for which the bounds of Hoffman and
Cvet\-kovi\'c are tight have a very special structure:
%
\begin{Theorem}\label{ch}
Let $\Gamma$ be a strongly regular graph with eigenvalues $k$ (degree),
$r$ and $s$ ($r>s$) and multiplicities $1$, $f$ and $g$, respectively.
Suppose that $\Gamma$ is not complete multi-partite (i.e. $r\neq 0$)
and let $C$ be a coclique in $\Gamma$.
\begin{itemize}
\item[(i)] $|C|\leq g$,
\item[(ii)] $|C|\leq ns/(s-k)$,
\item[(iii)] if $|C|=g=ns/(s-k)$, then the subgraph $\Gamma'$ of $\Gamma$
induced by the vertices which are not in $C$, is strongly
regular with eigenvalues $k'=k+s$ (degree), $r'=r$ and $s'=r+s$
and respective multiplicities $1$, $g-1$ and $f-g+1$.
\end{itemize}
\end{Theorem}
%
To prove this theorem we use the following matrix lemma:
%
\begin{Lemma}\label{l}
Let $M$ be a symmetric $v\times v$ matrix with a symmetric partition
\[
M= \left[ \begin{array}{cc}
M_1 & N \\
N^\top & M_2
\end{array} \right],
\]
where $M_1$ has order $v_1$ (say). Suppose $M$ has just two distinct
eigenvalues $r$ and $s$ ($r>s$) with multiplicities $f$ and $v-f$.
Let $\eigA_1\geq\ldots\geq\eigA_{v_1}$ be the eigenvalues of
$M_1$ and let $\eigB_1\geq\ldots\geq\eigB_{v-v_1}$ be the eigenvalues of
$M_2$. Then $r\geq\eigA_i\geq s$ for $i=1,\ldots,v_1$, and
\[
\eigB_i=\left\{\begin{array}{l}
r\ {\rm if }\ 1\leq i\leq f-v_1,\\
s\ {\rm if }\ f+1\leq i\leq v-v_1,\\
r+s-\eigA_{f-i+1}\ {\rm otherwise}.
\end{array} \right.
\]
\end{Lemma}
%
{\bf Proof.}
The inequalities $r\geq\eigA_i\geq s$ and also the first two
lines of the formulas for $\eigB_i$ follow from Corollary~\ref{ci}.
We have $(M-rI)(M-sI)=O$.
With the given block structure of $M$ this gives
$N^\top M_1+M_2N^\top-(r+s)N^\top=O$.
Suppose that $\eigA_i\neq r,s$, let $V$ be the corresponding
eigenspace and let $\{\v_1,\ldots,\v_{m}\}$ be a basis for $V$.
We claim that $B=\{N^\top\v_1,\ldots,N^\top\v_m\}$ is independent.
Suppose not.
Then $N^\top\v=\0$ for some $\v\in V$, $\v\neq\0$ which implies that
$M\left[^{\v}_{\0}\right] = \eigA_i\left[^{\v}_{\0}\right]$,
that is, $\eigA_i$ is an eigenvalue of $M$, a contradiction.
Now $N^\top M_1+M_2 N^\top = (r+s)N^\top$ gives
$M_2(N^\top\v_i)=(r+s-\eigA_i)N^\top\v_i$,
thus $B$ is an independent set of eigenvectors of $M_2$ for the
eigenvalue $r+s-\eigA_i$.
This almost proves the lemma.
Only the numbers of $\eigB_i$'s that are equal to $r$ or $s$ are not
determined, but these follow from
$\sum\eigB_i+\sum\eigA_i={\rm trace}\;M_1+{\rm trace}\;M_2={\rm
trace}\;M=fr+(v-f)s$.
\qed\\[5pt]
{\bf Proof of Theorem~\ref{ch}.}
(i) and (ii) follow from Theorems~\ref{cv} and
\ref{ho}. Assume $|C|=g=ns/(s-k)$, then Theorem~\ref{hs} gives
that $\Gamma'$ is regular of degree $k+s$.
Next we apply Lemma~\ref{l} to $M=A-\frac{k-r}{n} J$,
where $A$ is the adjacency matrix of $\Gamma$.
Since $\Gamma$ is regular, $A$ and $J$ commute and therefore
$M$ has eigenvalues $r$ and $s$ with multiplicities
$f+1$ and $g$, respectively.
We take $M_1=-\frac{k-r}{n} J$ of size $|C|=g$
and $M_2 = A'-\frac{k-r}{n} J$, where $A'$ is the
adjacency matrix of $\Gamma'$.
Lemma~3.2 gives the eigenvalues of $M_2$:
$r$ ($f+1-g$ times, $s$ (0 times), $r+s$ ($g-1$ times)
and $r+s+g(k-r)/n$ (1 time).
Since $\Gamma'$ is regular of degree $k+s$ and $A'$ commutes
with $J$ we obtain the required eigenvalues for $A'$.
By Theorem~\ref{srg} $\Gamma'$ is strongly regular.
\qed\\[5pt]
For instance, an $(m-1)$-coclique in the complement of the
triangular graph $T(m)$ is tight for both bounds and the
graph on the remaining vertices is the complement of
$T(m-1)$.
Also for the chromatic number we can say more in case of
a strongly regular graph.
%
\begin{Theorem}\label{chi''}
If $\Gamma$ is a primitive strongly regular graph,
not the pentagon, then
\[
{\chi(\Gamma)\geq 1-\frac{s}{r}}\ .
\]
\end{Theorem}
%
{\bf Proof.}
Since $\Gamma$ is primitive, $r>0$ and by Corollary~\ref{chi'}, it
suffices to show that the multiplicity $g$ of $s$ satisfies
$g\geq-s/r$ for all primitive strongly regular graphs but the
pentagon.
First we check this claim for all feasible parameter sets with
at most $23$ vertices.
Next we consider strongly regular graphs with
$v\geq 24$ and $r<2$.
The complements of these graphs have $s>-3$, and
by Theorem~\ref{srgparam}~(iv), $s=-2$.
By use of Theorem~\ref{srg-2} we easily find
that all these graphs satisfy the claim.
%All strongly regular graphs with $v\leq 23$
%or $r<2$ are known, and it is straightforward to check
%that for these graphs the above statement is true.

Assume that $\Gamma$ is primitive, that $r\geq 2$,
and that the claim does not hold (that is $g<-s/r$).
Now $(v-1-g)r + g s + k = 0$ gives
\[
g^2<-sg/r=v-1-g + k/r\leq v-1-g+k/2<3v/2-g .
\]
This implies $g(g+3)\leq 3v/2 = 2\sqrt{3v/2}$.
By use of the absolute bound $v\leq g(g+3)/2$,
we get $v/2<2\sqrt{3v/2}$, so $v<24$.
Contradiction.
\qed\\[5pt]
For example if $\Gamma$ is the complement of the triangular graph
$T(m)$ then $\Gamma$ is strongly regular with eigenvalues
$k=\2(m-2)(m-3)$, $r=1$ and $s=3-m$ (for $m\geq4$).
The above bound gives $\chi(\Gamma) \geq m-2$, which is tight, whilst
Hoffman's lower bound (Theorem~\ref{chi}~(i)) equals $\2 m$.
On the other hand, if $m$ is even,
Hoffman's bound is tight for the complement of $\Gamma$
whilst the above bound is much less.
We saw (see Section~\ref{chrom}) that a Hoffman coloring
(i.e. a coloring with $1-k/s$ classes) corresponds
to an equitable partition of the adjacency matrix.
For the complement this is gives an equitable partition
into maximal cliques, which is called a spread of
the strongly regular graph.
%(see \cite{ht}).
For more application of eigenvalues to the chromatic number
we refer to \cite{hf} and \cite{gr}. See also Section~\ref{81}.

\subsection{Generalized quadrangles}\label{gq}
A {\em generalized $n$-gon} is a connected bipartite graph
of diameter $n$ and girth $2n$.
(The girth of a graph is the length of a shortest circuit.)

It is common to call the vertices in one color class of the
unique 2-coloring {\em points}, and the other vertices {\em lines}.
For example, a generalized 3-gon is the same thing as a projective plane:
any two points have an even distance at most 3, hence are joined by a line,
and similarly any two lines meet in a point; finally two lines cannot meet
in two points since that would yield a quadrangle, but the girth is 6.

A {\em generalized quadrangle} is a generalized 4-gon.
In terms of points and lines, the definition becomes:
a {\em generalized quadrangle} is an incidence structure
$(P,L)$ with set of points $P$ and set of lines $L$,
such that two lines meet in at most one point, and
if $p$ is a point not on the line $m$, then there is a unique
point $q$ on $m$ and a unique line $n$ on $p$ such that $q$ is on $n$.

\subsubsection{Parameters}
A generalized $n$-gon is called {\em firm} when each vertex
has at least 2 neighbors. (Each point is on at least two lines,
and each line is on at least two points.)

For a vertex $x$ of a generalized $n$-gon, let $k(x)$ be its degree.
Call two vertices of a generalized $n$-gon {\em opposite}
when they have distance $n$. If $x$ and $y$ are opposite
then each neighbor of one is on a unique shortest path to the other,
and we find $k(x) = k(y)$.

If a generalized $n$-gon $\Gamma$ has a pair of opposite vertices
$x,y$ with $k(x) > 1$, then every vertex has an opposite,
and $\Gamma$ is firm.

(Indeed, being non-opposite gives a bijection between $\Gamma(x)$
and $\Gamma(y)$, and hence if $k(x) > 1$ then also each neighbor $z$ of $x$
has an opposite and satisfies $k(z) > 1$. Since $\Gamma$ is connected,
the conclusion follows.)

An example of a non-firm generalized quadrangle is a
pencil of lines on one common point $x_0$. Each point
different from $x_0$ is on a unique line, and
$\Gamma_3(x_0) = \emptyset$.

A generalized $n$-gon is called {\em thick} when each vertex
has at least 3 neighbors. (Each point is on at least three lines,
and each line has at least three points.)

For a thick generalized $n$-gon, any two points, and any two lines,
have the same number of neighbors. If $n$ is odd then any point
and any line have the same number of neighbors.

(Indeed, let $x,z$ be two points joined by the line $y$.
Let $w$ be opposite to $y$. Since $k(w) > 2$ there is a neighbor
$u$ of $w$ opposite to both $x$ and $z$. Now $k(x) = k(u) = k(z)$.
Since $\Gamma$ is connected and bipartite this shows that
$k(p)$ is independent of the point $p$. If $n$ is odd, then
a vertex opposite a point is a line.)

A firm, non-thick generalized quadrangle is the vertex-edge
incidence graph of a complete bipartite graph.

The {\em halved graph} of a bipartite graph $\Gamma$, is the graph on the
same vertex set, where two vertices are adjacent when they have distance
2 in $\Gamma$.
The {\em point graph} and {\em line graph} of a generalized $n$-gon
are the two components of its halved graph containing the points
and lines, respectively.

The point graph and line graph of a finite thick generalized $n$-gon
are distance-regular of diameter $\lfloor n\rfloor$ (See
Section~\ref{drg}).
In particular, the point graph and line graph of a thick generalized
quadrangle are strongly regular (See Theorem~\ref{gq-srg}).

It is customary to let $GQ(s,t)$ denote a finite generalized quadrangle
with $s+1$ points on each line and $t+1$ lines on each point.
Note that it is also customary to use $s$ to denote the smallest
eigenvalue of a strongly regular graph, so in this context one
has to be careful to avoid confusion.

It is a famous open problem whether a thick generalized $n$-gon
can have finite $s$ and infinite $t$. In the special case of
generalized quadrangles a little is known: Cameron, Kantor, Brouwer,
and Cherlin \cite{CameronGQfin,BrouwerGQfin,Cherlin}
show that this cannot happen for $s+1 \le 5$.

\subsubsection{Constructions of generalized quadrangles}\label{gq-constr}
Suppose $V$ is a vector space provided with a nondegenerate
quadratic form $f$ of Witt index 2 (that is, such that the maximal
totally singular subspaces have vector space dimension 2).
Consider in the projective space $PV$ the singular projective points
and the totally singular projective lines. These will form a
generalized quadrangle.

Indeed, $f$ defines a bilinear form $B$ on $V$ via
$B(x,y) = f(x+y) - f(x) - f(y)$. Call $x$ and $y$ {\em orthogonal}
when $B(x,y) = 0$. When two singular vectors are orthogonal,
the subspace spanned by them is totally singular.
And conversely, in a totally singular subspace any two vectors
are orthogonal.
The collection of all vectors orthogonal to a given vector
is a hyperplane. We have to check that if $P = \langle x \rangle$
is a singular projective point, and $L$ is a totally singular
projective line not containing $P$, then $P$ has a unique neighbor on $L$.
But the hyperplane of vectors orthogonal to $x$ meets $L$,
and cannot contain $L$ otherwise $f$ would have larger Witt index.

\medskip\noindent
This construction produces generalized quadrangles over arbitrary fields.
If $V$ is a vector space over a finite field $\Ff_q$, then a nondegenerate
quadratic form can have Witt index 2 in dimensions 4, 5, and 6.
A hyperbolic quadric in 4 dimensions yields a generalized quadrangle
with parameters $GQ(q,1)$, a parabolic quadric in 5 dimensions
yields a generalized quadrangle with parameters $GQ(q,q)$,
and an elliptic quadric in 6 dimensions yields a generalized quadrangle
with parameters $GQ(q,q^2)$.

Other constructions, and other parameters occur.

\medskip\noindent
In the below we'll meet $GQ(2,t)$ for $t=1,2,4$ and $GQ(3,9)$.
Let us give simple direct descriptions for $GQ(2,1)$ and $GQ(2,2)$.

The unique $GQ(2,1)$ is the 3-by-3 grid: 9 points, 6 lines.
Its point graph is $K_3 \times K_3$.

The unique $GQ(2,2)$ is obtained by taking as points the
15 pairs from a 6-set, and as lines the 15 partitions of that
6-set into three pairs. Now collinearity is being disjoint.
Given a point $ac$, and a line $\{ab,cd,ef\}$, the two points
$ab$ and $cd$ on this line are not disjoint from $ac$, so that
$ef$ is the unique point on this line collinear with $ac$,
and the line joining $ac$ and $ef$ is $\{ac,bd,ef\}$.

\subsubsection{Strongly regular graphs from generalized quadrangles}
As mentioned before, the collinearity graph
of a finite thick generalized quadrangle is strongly regular.
The parameters and eigenvalue can be obtained in a
straightforward way (see exercises).
%
\begin{Theorem}\label{gq-srg}
The point graph (collinearity graph) of a finite
generalized quadrangle with parameters $GQ(s,t)$ is strongly regular
with parameters
$$v = (s+1)(st+1),~~ k = s(t+1),~~ \lambda = s-1,~~ \mu = t+1$$
and spectrum
$$\begin{array}{cll}
s(t+1) & \mbox{with multiplicity} & 1, \\
s-1 & \mbox{with multiplicity} & st(s+1)(t+1)/(s+t), \\
-t-1 & \mbox{with multiplicity} & s^2(st+1)/(s+t).\\
\end{array}$$
In particular, if a $GQ(s,t)$ exists, then $(s+t) | s^2(st+1)$.
\end{Theorem}

\subsubsection{Generalized quadrangles with lines of size $3$}
Let a {\em weak generalized quadrangle} be a point-line geometry
with the properties that two lines meet in at most one point,
and given a line $m$ and a point $p$ outside there is a unique
pair $(q,n)$ such that $p \adj n \adj q \adj m$, where $\adj$ denotes
incidence. The difference with the definition of a generalized quadrangle
is that connectedness is not required. (But of course,
as soon as there is a point and a line then the geometry is connected.)
%
\begin{Theorem}
A weak generalized quadrangle where all lines lines have size $3$
is one of the following:
\begin{itemize}
\item[(i)] a coclique (no lines),
\item[(ii)] a pencil (all lines passing through a fixed point),
\item[(iii)] the unique $GQ(2,1)$,
\item[(iv)] the unique $GQ(2,2)$,
\item[(v)] the unique $GQ(2,4)$.
\end{itemize}
\end{Theorem}
%
\Proof After reducing to the case of $GQ(2,t)$ one finds
$(t+2) | (8t+4)$, i.e., $(t+2) | 12$, i.e., $t \in \{1,2,4,10\}$,
and $t = 10$ is ruled out by the Krein conditions.
Alternatively, or afterwards, notice that the point graphs have eigenvalue 1,
so that their complements have smallest eigenvalue $-2$,
and apply Seidel's classification. Cases (iii), (iv), (v) here
have point graphs that are the complements of the lattice graph
$K_3 \times K_3$, the triangular graph $T(6)$,
and the Schl\"{a}fli graph, respectively.
\qed\\[5pt]
This theorem can be used in the classification of root lattices,
where the five cases correspond to $A_n$, $D_n$, $E_6$, $E_7$, $E_8$,
respectively.

And the classification of root lattices can be used
in the classification of graphs with smallest eigenvalue $-2$.
Indeed, for such graphs $A + 2I$ is positive semidefinite,
and one can represent these graphs by vectors in a Euclidean space
such that $(x,y) = 2,1,0$ when $x$ and $y$ are equal, adjacent,
nonadjacent, respectively. The lattice spanned by these vectors
is a root lattice.

\subsection{Other algebraic invariants}
As we have seen, a graph need not be determined by its spectrum.
It need not be determined by the Laplace spectrum either ---
e.g., there exist pairs of cospectral regular graphs.
A well-known example is the strongly regular Shrikhande graph
and the lattice graph $L_2(4)=K_4 \times K_4$, both with spectrum
$6^1,~2^6,~(-2)^9$ (see Section~\ref{srg-2}).
In fact, most known strongly regular graphs are not determined by
its spectrum. Computer results for small graphs give the impression
that for arbitrary graphs the behavior is different.
However, for large $n$ nothing is known about the fraction
of the graphs on $n$ vertices that are determined by its spectrum.
See also \cite{dh}.

\medskip\noindent
Other invariants have been used to distinguish graphs
and study their properties.
One is the $p$-rank: the rank of the adjacency matrix $A$
(or of $A+mI$ for some integer $m$) over the field $\Ff_p$.

Another is the Smith Normal Form.
The {\em Smith Normal Form} $S(M)$ of an integral matrix $M$
is a diagonal matrix $S(M) = PMQ = \mbox{diag}(s_1,\ldots,\s_n)$,
where $P$ and $Q$ have determinant $\pm 1$ and $s_1 | s_2 | \cdots | s_n$.
It exists and is uniquely determined up to the signs of the $s_i$.

The Smith Normal Form is a finer invariant than the $p$-rank:
the $p$-rank is just the number of $s_i$ not divisible by $p$.

For example, if $A$ is the adjacency matrix of the lattice graph
$K_4 \times K_4$ and $B$ that of the Shrikhande graph,
then $S(A) = S(B) = \mbox{diag}(1^6, 2^4, 4^5, 12)$,
but $S(A+2I) = \mbox{diag}(1^6, 8^1, 0^9)$ and
$S(B+2I) = \mbox{diag}(1^6, 2^1, 0^9)$.
All have 2-rank equal to 6.

An example where the $p$-rank suffices to distinguish, is given
by the Chang graphs, strongly regular graphs with the same
parameters as the triangular graph $T(8)$,
with $(v,k,\lambda,\mu) = (28, 12, 6, 4)$ and spectrum
$12^1~4^7~(-2)^{20}$. If $A$ is the adjacency matrix of the
triangular graph and $B$ that of one of the Chang graphs
then $S(A) = \mbox{diag}(1^6, 2^{15}, 8^6, 24^1)$
and $S(B) = \mbox{diag}(1^8, 2^{12}, 8^7, 24^1)$,
so that $A$ and $B$ have different 2-rank.
Another example is given by the point graph and the line
graph of the $GQ(3,3)$ constructed in Section~\ref{gq-constr}.
The $2$-ranks of the adjacency matrices are 10 and 16
respectively.
For these and more results on $p$-ranks, see
\cite{BrouwervEijl} and \cite{Peeters}.

\subsection{Exercises}

\Exercise
For a strongly regular graph $\Gamma$ and a vertex $x$ of $\Gamma$,
let $\Delta = \Gamma_2 ( x )$ be the subgraph consisting of the
vertices at distance two from $x$.
If $\Gamma$ has no triangles and spectrum $k^1,~r^f,~s^g$,
then show that $\Delta$ has spectrum
$(k - \mu )^1, ~r^{f-k}, ~\maysplit s^{g-k}, ~\maysplit(-\mu)^{k-1}$.
Conclude that $f \ge k$ and $g \ge k$, and that if equality holds
then $\Delta$ is itself strongly regular.
Determine all strongly regular graphs with $\lambda = 0$ and $f = k$.

\Exercise
Prove Theorem~\ref{gq-srg}.

\Exercise
A spread in a generalized quadrangle is a subset $S$ of the lines
such that every point is on exactly one line of $S$.
Prove that a $GQ(q^2,q)$ has no spread.
Hint: A spread is a coclique in the line graph.

\section{Association schemes}

\subsection{Definition}

An {\it association scheme with $d$ classes} is a finite set $X$
together with $d+1$ relations $R_i$ on $X$ such that
%
\begin{itemize}
\item[(i)]
$\{ R_0 , R_1 ,\dots , R_d \}$ is a partition of $X \times X$;
\item[(ii)]
$R_0 = \{ (x, x) | x \in X \}$;
\item[(iii)]
if $(x,y) \in R_i$, then also $(y,x) \in R_i$,
for all $x,y \in X$ and $i \in \{ 0, ... , d\}$;
\item[(iv)]
for any $(x,y) \in R_k$ the number $p_{ij}^k$
of $z \in X$ with $ ( x , z ) \in R_i$
and $( z , y ) \in R_j$ depends only on $i$, $j$ and $k$.
\end{itemize}
%
The numbers $p_{ij}^k$ are called the {\it intersection numbers}
of the association scheme. The above definition is the original
definition of Bose \& Shimamoto~\cite{bs}; it is what
Delsarte~\cite{del}
calls a symmetric association scheme.
In Delsarte's more general definition, (iii) is replaced by:
%
\begin{itemize}
\item[(iii')]
for each $i \in \{ 0, ... , d\}$ there exists a
$j \in \{ 0, ... ,d\}$ such that $(x,y) \in R_i$ implies
$(y,x) \in R_j$,
\item[(iii'')]
$p_{ij}^k = p_{ji}^k$, for all $i,j,k \in \{ 0, ... , d \} $.
\end{itemize}
%
Define $n = |X|$, and $n_i = p_{ii}^0$. Clearly, for each
$i \in \{ 1, ... ,d \}$, $(X, R_i )$ is a simple graph which is
regular of degree $n_i$.
%
\begin{Theorem}\label{p}
The intersection numbers of an association scheme satisfy
%
\begin{itemize}
\item[(i)]
$p_{0j}^k = \delta_{jk} ,~ p_{ij}^0 = \delta_{ij} n_j ,~
p_{ij}^k = p_{ji}^k$,
\item[(ii)]
$\sum_i p_{ij}^k = n_j ,~ \sum_j n_j = n$,
\item[(iii)]
$p_{ij}^k n_k = p_{ik}^j n_j$,
\item[(iv)]
$\sum_l p_{ij}^l p_{kl}^m = \sum_l p_{kj}^l p_{il}^m$.
\end{itemize}
%
\end{Theorem}
%
{\bf Proof. }
Equations (i), (ii) and (iii) are straightforward.
The expressions at both sides of (iv) count quadruples
$(w,x,y,z)$ with $(w,x) \in R_i$,
$(x,y) \in R_j$, $(y,z) \in R_k$,
for a fixed pair $(w,z) \in R_m$.
\qed\\[5pt]
It is convenient to write the intersection numbers as entries of
the so-called {\it intersection matrices} $L_0, \dots ,L_d$:
\[
(L_i )_{kj} = p_{ij}^k .
\]
Note that $L_0 = I$.
From the definition it is clear that an association scheme
with two classes is the same as a pair of complementary
strongly regular graphs.
If $(X,R_1 )$ is strongly
regular with parameters $(v,k, \lambda , \mu )$, then
the intersection matrices of the scheme are
\[
L_1 = \left[ \begin{array}{ccc}
0 & k & 0 \\
1 & \lambda & {k- \lambda -1} \\
0 & \mu & k- \mu
\end{array}\right]\ ,
\ \ L_2 = \left[\begin{array}{ccc}
0 & 0 & v-k-1\\
0 & { k- \lambda -1} & { v-2k + \lambda }\\
1 & k-\mu & { v-2k+ \mu -2 }
\end{array}\right] .
\]

\subsection{The Bose-Mesner algebra}

The relations $R_i$ of an association scheme are described
by their adjacency matrices $A_i$ of order $n$
defined by
\[
(A_i )_{xy} =
\left\{ \begin{array}{ll}
1 & \mbox{whenever } (x,y) \in R_i,\\
0 & \mbox{otherwise.}
\end{array}\right.
\]
In other words, $A_i$ is the adjacency matrix of the graph $(X,R_i )$.
In terms of the adjacency matrices, the axioms (i)-(iv) become
%
\begin{itemize}
\item[(i)]
$\sum_{i=0}^d A_i = J$,
\item[(ii)]
$A_0 = I$,
\item[(iii)]
$A_i = A_i^\top$, for all $i \in \{0,\ldots,d\}$,
\item[(iv)]
$A_i A_j = \sum_k p_{ij}^k A_k$, for all
$i,j,k \in \{0,\ldots,d\}$.
\end{itemize}
%
From (i) we see that the $(0,1)$ matrices
$A_i$ are linearly independent, and by use
of (ii)-(iv) we see that they generate a commutative
$(d+1)$-dimensional
algebra $\A$ of symmetric matrices with constant diagonal.
This algebra was first studied by
Bose \& Mesner~\cite{bm}
and is called the Bose-Mesner algebra of the association scheme.

Since the matrices $A_i$ commute,
they can be diagonalized simultaneously (see
Marcus \& Minc~\cite{mm}),
that is, there exist a matrix $S$ such that for each $A \in\A$,
$S^{-1} AS$ is a diagonal matrix. Therefore $\A$ is
semisimple and has a unique basis of minimal idempotents
$E_0 ,\ldots,E_d$ (see Burrow~\cite{bur}).
These are matrices satisfying
\[
E_i E_j = \delta_{ij} E_i ,\ \sum_{i=0}^d E_i = I.
\]
The matrix $\frac{1}{n} J$ is a minimal idempotent
(idempotent is clear, and minimal follows since rk~$J = 1$).
We shall take $E_0 = \frac{1}{n} J$.
Let $P$ and $\frac{1}{n} Q$ be the matrices
relating our two bases for $\A$:
\[
A_j = \sum_{i=0}^d P_{ij} E_i ,
\ E_j = \frac{1}{n} \sum_{i=0}^d Q_{ij} A_i .
\]
Then clearly
\[
PQ = QP = nI.
\]
It also follows that
\[
A_j E_i = P_{ij} E_i ,
\]
which shows that the $P_{ij}$ are the eigenvalues of $A_j$
and that the columns of $E_i$ are the corresponding
eigenvectors.
Thus $\mu_i = \mbox{rk }E_i$ is the multiplicity
of the eigenvalue $P_{ij}$ of $A_j$ (provided that
$P_{ij} \neq P_{kj}$ for $k \neq i$).
We see that $\mu_0 = 1$, $\sum_{i}\mu_i = n$,
and $\mu_i = \mbox{trace }E_i = n(E_i )_{jj}$
(indeed, $E_i$ has only eigenvalues 0 and 1, so rk~$E_k$
equals the sum of the eigenvalues).
%
\begin{Theorem}\label{pq}
The numbers $P_{ij}$ and $Q_{ij}$ satisfy
%
\begin{itemize}
\item[(i)] $P_{i0} = Q_{i0} = 1$, $P_{0i} = n_i$, $Q_{0i} = \mu_i$,
\item[(ii)] $P_{ij} P_{ik} = \sum_{l=0}^d p_{jk}^l P_{il}$,
\item[(iii)] $\mu_i P_{ij} = n_j Q_{ji}$,
$\sum_i\mu_i P_{ij} P_{ik} = n n_j \delta_{jk}$,
$\sum_i n_i Q_{ij}Q_{ik} = n \mu_j \delta_{jk}$,
\item[(iv)]
$| P_{ij} | \leq  n_j$, $| Q_{ij} | \leq \mu_j$.
\end{itemize}
%
\end{Theorem}
%
{\bf Proof.}
Part (i) follows easily from $\sum_i E_i = I = A_0$,
$\sum_i A_i = J = nE_0$, $A_i J = n_i J$, and trace~$ E_i = \mu_i$.
Part (ii) follows from $A_j A_k = \sum_l p_{jk}^l A_l$. The first
equality in (iii) follows from $\mu_i P_{ij} = \tr A_j E_i = n_j Q_{ji}$,
and the other two follow since $PQ = nI$. The first inequality of (iv) holds
because the $P_{ij}$ are eigenvalues of the $n_j$-regular graphs
$(X,R_j )$. The second inequality then follows by use of (iii).
\qed\\[5pt]
Relations (iii) are often referred to as the {\it orthogonality relations},
since they state that the rows (and columns)
of $P$ (and $Q$) are orthogonal with respect to a suitable weight function.

If $d = 2$, and $(X,R_1 )$ is strongly regular with parameters
$(v,k, \lambda , \mu )$, the matrices $P$ and $Q$ are
\[
P = \left[ \begin{array}{ccc}
1 & k & v-k-1\\
1 & r & -r-1\\
1 & s & -s-1\\
\end{array}\right], ~
Q = \left[\begin{array}{ccc}
1 & f & g \\1 & fr/k & gs/k \\
1 & -f\frac{r+1}{v-k-1} & -g\frac{s+1}{v-k-1}\\
\end{array}\right],
\]
where $r$, $s$, $f$ and $g$ can be expressed in terms of
$v$, $k$, $\lambda$ by use of 1.2.

In general the matrices $P$ and $Q$ can be computed from the intersection
numbers of the scheme, as follows from the following
%
\begin{Theorem}\label{eigL}
For $i = 0,\ldots,d$, the intersection matrix $L_j$
has eigenvalues $P_{ij}$ $(0 \leq  i \leq  d)$.
\end{Theorem}
%
{\bf Proof.}
Theorem~\ref{pq}(ii) yields
\[
\sum_{k,l} P_{il} (L_j )_{lk} (P^{-1} )_{km} =
P_{ij} \sum_k P_{ik} (P^{-1})_{km} = \delta_{im} P_{ij} ,
\]
hence $PL_j P^{-1} = \mbox{diag }( P_{0j},\ldots,P_{dj})$.
\qed\\[5pt]
Thanks to this theorem, it is relatively easy to compute $P$,
$Q$ ($ = \frac{1}{n} P^{-1}$) and $\mu_i$ $( = Q_{0i})$.
It is also possible to express $P$ and $Q$ in terms of
the (common) eigenvectors of the $L_j$.
Indeed, $PL_j P^{-1} = \mbox{diag }( P_{0j},\ldots,P_{dj})$
implies that the rows of $P$ are left eigenvectors and the
columns of $Q$ are right eigenvectors. In particular,
$\mu_i$ can be computed from the right eigenvector $u_i$
and the left eigenvector $v_i^\top$, normalized such that
$(u_i )_0 = (v_i )_0 = 1$, by use of $\mu_i u_i^\top v_i = n$.
Clearly, each $\mu_i$ must be an integer. These are
the {\it rationality conditions} for an association scheme.
As we saw in the case of a strongly regular graph, these conditions
can be very powerful.

\subsection{The Linear Programming Bound}
One of the main reasons association schemes have been studied
is that they yield upper bounds for the size of substructures.

Let $Y$ be a nonempty subset of $X$, and let its {\em inner distribution}
be the vector $a$ defined by $a_i = |(Y \times Y) \cap R_i| / |Y|$,
the average number of elements of $Y$ in relation $R_i$ to a given one.
Let $\chi$ be the characteristic vector of $Y$. Then
$a_i = \frac{1}{|Y|} \chi^\top A_i \chi$.
%
\begin{Theorem} {\rm (Delsarte)} $aQ \ge 0$.
\end{Theorem}
%
\Proof
We have $|Y| (aQ)_j = |Y| \sum a_i Q_{ij} = \chi^\top \sum Q_{ij} A_i \chi =
n \chi^\top E_j \chi \ge 0$ since $E_j$ is positive semidefinie. \qed

\Example
Consider the schemes of the triples from a 7-set, where two triples
are in relation $R_i$ when they have $3-i$ elements in common
$(i=0,1,2,3)$. We find
$$
P=\left[\begin{array}{rrrr}
1 & 12 & 18 & 4 \\
1 & 5 & -3 & -3 \\
1 & 0 & -3 & 2 \\
1 & -3 & 3 & -1 \\
\end{array}\right]~~\mbox{and}~~
Q=\left[\begin{array}{rrrr}
1 & 6\   & 14\  &  14\ \\
1 & 5/2  &  0\  & -7/2 \\
1 & -1\  & -7/3 &  7/3 \\
1 & -9/2 &  7\  & -7/2 \\
\end{array}\right] .
$$
How many triples can we find such that any two meet in at most
one point? For the inner distribution $a$ of such a collection $Y$
we have $a_1 = 0$, so $a = (1,0,s,t)$, and $aQ \ge 0$ gives
the three inequalities
$$
{\textstyle
6 - s - \frac{9}{2}t \ge 0,~~
14 - \frac{7}{3}s + 7t \ge 0,~~
14 + \frac{7}{3}s - \frac{7}{2}t \ge 0.
}
$$
The linear programming problem is to maximize $|Y| = 1+s+t$ given these
inequalities, and the unique solution is $s=6$, $t=0$.
This shows that one can have at most 7 triples that pairwise meet
in at most one point in a 7-set, and if one has 7, then no two
are disjoint. Of course an example is given by the Fano plane.

\medskip\noindent
How many triples can we find such that any two meet in at least
one point? Now $a = (1,r,s,0)$ and the optimal solution of $aQ \ge 0$
is $(1,8,6,0)$. An example of such a collection is given by
the set of 15 triples containing a fixed point.

\medskip\noindent
How many triples can we find such that no two meet in precisely
one point? Now $a = (1,r,0,t)$ and the maximum value of $1+r+t$
is 5. An example is given by the set of 5 triples containing
two fixed points.

\subsection{The Krein parameters}

The Bose-Mesner algebra $\A$ is not only closed under ordinary
matrix multiplication, but also under componentwise (Hadamard, Schur)
multiplication (denoted $\cs$). Clearly $\{ A_0 , \ldots , A_d \}$
is the basis of minimal idempotents with respect to this multiplication.
Write
\[
E_i \cs E_j = \frac{1}{n} \sum_{k=0}^d q_{ij}^k E_k .
\]
The numbers $q_{ij}^k$ thus defined are called the {\it Krein
parameters}. (Our $q_{ij}^k$ are those of Delsarte, but differ
from Seidel's~\cite{sei} by a factor $n$.) As expected, we now have
the analogue of Theorems~\ref{p} and \ref{pq}.
%
\begin{Theorem}\label{q}
The Krein parameters of an association scheme satisfy
%
\begin{itemize}
\item[(i)]
$q_{0j}^k = \delta_{jk} ,~ q_{ij}^0 = \delta_{ij} \mu_j ,~
q_{ij}^k = q_{ji}^k$,
\item[(ii)]
$\sum_i q_{ij}^k = \mu_j ,~ \sum_j \mu_j = n$,
\item[(iii)]
$q_{ij}^k \mu_k = q_{ik}^j \mu_j$,
\item[(iv)]
$\sum_l q_{ij}^l q_{kl}^m = \sum_l q_{kj}^l q_{il}^m$,
\item[(v)]
$Q_{ij} Q_{ik} = \sum_{l=0}^d q_{jk}^l Q_{il}$,
\item[(vi)]
$n \mu_k q_{ij}^k = \sum_l  n_l Q_{li} Q_{lj} Q_{lk}$.
\end{itemize}
%
\end{Theorem}
%
{\bf Proof.}
Let $\sum(A)$ denote the sum of all entries of the matrix $A$.
Then $JAJ = \sum(A) J$, $\sum(A \cs B) = \mbox{trace }
AB^\top$ and $\sum( E_i ) = 0$ if $i \neq 0$, since then $E_i J = nE_i
E_0 = 0$. Now (i) follows by use of $E_i \cs E_0 = \frac{1}{n}E_i$,
$q_{ij}^0 = \sum(E_i \cs E_j ) = \mbox{trace }E_i E_j = \delta_{ij}
\mu_j$, and $E_i \cs E_j = E_j \cs E_i$, respectively. Equation (iv)
follows by evaluating $E_i \cs E_j \cs E_k$ in two ways, and (iii)
follows from (iv) by taking $m = 0$. Equation (v) follows from
evaluating $A_i \cs E_j \cs E_k$ in two ways, and (vi) follows from
(v), using the orthogonality relation $\sum_l n_l Q_{lj} Q_{lk} =
\delta_{mk} \mu_k n$. Finally, by use of (iii) we have
\[
\mu_k \sum_j q_{ij}^k = \sum_j q_{ik}^j \mu_j =
n\cdot\mbox{trace }(E_i \cs E_k ) =
n \sum_l (E_i )_{ll} (E_k )_{ll} =
\mu_i \mu_k ,
\]
proving (ii).
\qed\\[5pt]
The above results illustrate a dual behavior between ordinary
multiplication, the numbers $p_{ij}^k$ and the matrices $A_i$
and $P$ on  the one hand, and Schur multiplication, the numbers
$q_{ij}^k$ and the matrices $E_i$ and $Q$ on the other hand.
If two association schemes have the property that the intersection
numbers of one are the Krein parameters of the other, then the converse is
also true. Two such schemes are said to be (formally) dual to each other.
One scheme may have several (formal) duals, or none at all
(but when the scheme is invariant under a regular abelian group,
there is a natural way to define a dual scheme, cf.
Delsarte~\cite{del}).
In fact usually the Krein parameters are not even integers.
But they cannot be negative. These important restrictions,
due to Scott~\cite{sco} are the so-called Krein conditions.
%
\begin{Theorem}
The Krein parameters of an association scheme satisfy
$q_{ij}^k \geq 0$ for all $i,j,k \in \{0,\ldots,d\}$.
\end{Theorem}
%
{\bf Proof.}
The numbers $\frac{1}{n} q_{ij}^k$ ($0 \leq  k \leq d$) are the
eigenvalues of $E_i \cs E_j$ (since $(E_i \cs E_j ) E_k
= \frac{1}{n} q_{ij}^k E_k$). On the other hand, the Kronecker
product $E_i \tensor E_j$ is positive semidefinite, since each $E_i$
is. But $E_i \cs E_j$ is a principal submatrix of $E_i \tensor E_j$,
and therefore is positive semidefinite as well, i.e., has no
negative eigenvalue.
\qed\\[5pt]
The Krein parameters can be computed by use of equation~\ref{q}(vi).
This equation also shows that the Krein condition is
equivalent to
\[
\sum_l n_l Q_{li} Q_{lj} Q_{lk} \geq 0 ~\mbox{ for all }
i,j,k \in\{0,\ldots,d\}.
\]
In case of a strongly regular graph we obtain
\[
q_{11}^1 = \frac{ f^2 }{v}\left(
1 + \frac{ r^3 }{ k^2 } - \frac{ (r + 1)^3 }{ (v - k - 1)^2 }
\right) \geq 0,
\]
\[
q_{22}^2 = \frac{ g^2 }{v}\left(
1 + \frac{ s^3 }{ k^2 } - \frac{ (s + 1)^3 }{ (v - k - 1)^2 }
\right)\geq 0
\]
(the other Krein conditions are trivially satisfied in this case),
which is equivalent to the result mentioned in the previous section.

Neumaier~\cite{neu} generalized Seidel's absolute bound to
association schemes, and obtained the following.
%
\begin{Theorem}
The multiplicities $\mu_i$ $(0 \leq  i \leq  d)$ of an association
scheme with $d$ classes satisfy
\[
\sum_{ q_{ij}^k \neq 0 } \mu_k \leq  \left\{
\begin{array}{ll} \mu_i \mu_j & \mbox{if }i\neq j,\\
\frac{1}{2}\mu_i ( \mu_i + 1 ) & \mbox{if }i = j .
\end{array}\right.
\]
\end{Theorem}
%
{\bf Proof.}
The left hand side equals rk~$(E_i \cs E_j )$. But
$\rk\,(E_i \cs E_j ) \leq \rk\,(E_i \tensor E_j ) = \rk\, E_i
\cdot \rk\, E_j = \mu_i\mu_j$. And if $i = j$, then
$\rk\,(E_i \cs E_i ) \leq \frac{1}{2}\mu_i (\mu_i + 1)$.
Indeed, if the rows of $E_i$ are linear combinations of $\mu_i$ rows,
then the rows of $E_i \cs E_i$ are linear combinations of the
$\mu_i + \frac{1}{2}\mu_i (\mu_i - 1)$ rows that are the elementwise
products of any two of these $\mu_i$ rows.
\qed\\[5pt]
For strongly regular graphs with $q_{11}^1 = 0$ we obtain
Seidel's bound: $v \leq \frac{1}{2} f(f + 3)$.
But in case $q_{11}^1 > 0$, Neumaier's result states that the
bound can be improved to $v \leq \frac{1}{2}f(f + 1)$.

\subsection{$P$- and $Q$-polynomial association schemes}
In many cases, the association scheme carries a distance function
such that relation $R_i$ is the relation of having distance $i$.
Such schemes are called {\em metric}. They are characterized
by the fact that $p^i_{jk}$ is zero whenever one of $i,j,k$
is larger than the sum of the other two, while $p^i_{jk}$
is nonzero for $i = j+k$.

Dually, a {\em cometric} scheme is defined by $q^i_{jk} = 0$ for
$i > j+k$ and $q^i_{jk} > 0$ for $i = j+k$.

There are several equivalent formulations of the metric (cometric)
property.

An association scheme is called $P$-{\it{polynomial}} if there exist
polynomials $f_k$ of degree $k$ with real coefficients, and
real numbers $z_i$ such that $P_{ik} = f_k (z_i)$.
Clearly we may always take $z_i = P_{i1}$.
By the orthogonality relation~\ref{pq}(iii) we have
\[
\sum_i \mu_i f_j (z_i) f_k (z_i) =
\sum_i \mu_i P_{ij} P_{ik} = nn_j \delta_{jk} ,
\]
which shows that the $f_k$ are orthogonal polynomials.

Dually, a scheme is called $Q$-{\it{polynomial}} when the same holds
with $Q$ instead of $P$.
The following result is due to Delsarte~\cite{del} (Theorem~5.6, p. 61).
%
\begin{Theorem}
An association scheme is metric if and only if it is $P$-polynomial.
An association scheme is cometric if and only if it is $Q$-polynomial.
\end{Theorem}
%
{\bf Proof.}
Let the scheme be metric. Then
\[
A_1 A_i = p_{1i}^{i-1} A_{i-1} + p_{1i}^i A_i + p_{1i}^{i+1} A_{i+1} .
\]
Since $p_{1i}^{i+1}\neq 0$, $A_{i+1}$ can be expressed in terms of
$A_1$, $A_{i-1}$ and $A_i$. Hence for each $j$ there exists
a polynomial $f_j$ of degree $j$ such that $A_j = f_j (A_1)$,
and it follows that $P_{ij}E_i = A_j E_i = f_j (A_1) E_i = f_j (P_{i1}) E_i$,
hence $P_{ij} = f_j ( P_{i1})$.

Now suppose that the scheme is $P$-polynomial. Then the $f_j$ are
orthogonal polynomials, and therefore they satisfy a 3-term recurrence
relation (see Szeg\"{o}~\cite{sze}~p.42)
\[
\alpha_{j+1} f_{j+1} (z) = ( \beta_j - z )
f_j (z) + \gamma_{j-1} f_{j-1}(z) .
\]
Hence
\[
P_{i1} P_{ij} = - \alpha_{j+1} P_{i,j+1} + \beta_j P_{ij} +
\gamma_{j-1} P_{i,j-1}\ \mbox{ for } i = 0 ,\ldots,d.
\]
Since $P_{i1}P_{ij} = \sum_l p_{1j}^l P_{il}$ and $P$ is
nonsingular, it follows that $p_{1j}^l = 0$ for $|l-j| > 1$.
Now the full metric property easily follows by induction.
The proof for the cometric case is similar.
\qed\\[5pt]
Given a sequence of nonzero real numbers, let its number
of {\em sign changes} be obtained by first removing all
zeros from the sequence, and then counting the number of
consecutive pairs of different sign.
(Thus, the number of sign changes in 1, $-1$, 0, 1 is 2.)
%
\begin{Proposition}
(i) If $(X, {\cal R})$ is a $P$-polynomial association scheme,
and the relations are ordered according to the $P$-polynomial ordering
and the eigenspaces are ordered according to descending real order
on the $\theta_i := P_{i1}$, then both row $i$ and column $i$
of both matrices $P$ and $Q$ have precisely $i$ sign changes
$(0 \le i \le d)$.\\
(ii) Dually, if $(X, {\cal R})$ is a $Q$-polynomial association scheme,
and the eigenspaces are ordered according to the $Q$-polynomial ordering
and the relations are ordered according to descending real order
on the $\sigma_i := Q_{i1}$, then row $i$ and column $i$
of the matrices $P$ and $Q$ have precisely $i$ sign changes
$(0 \le i \le d)$.
\end{Proposition}
%
\Proof
% a_i, b_i, c_i first defined later
Since $\mu_i P_{ij} = n_j Q_{ji}$ the statements about $P$ and $Q$
are equivalent. Define polynomials $p_j$ of degree $j$ for $0 \le j \le d+1$
by $p_{-1}(x) = 0$, $p_0(x) = 1$,
$(x-a_j)p_j(x) = b_{j-1}p_{j-1} + c_{j+1}p_{j+1}(x)$,
taking $c_{d+1} = 1$.
Then $A_j = p_j(A)$, and $p_{d+1}(x) = 0$ has as roots the
eigenvalues of $A$.
The numbers in row $j$ of $P$ are $p_i(\theta_j)$ $(0 \le i \le d)$,
and by the theory of Sturm sequences the number of sign changes
is the number of roots of $p_{d+1}$ larger than $\theta_j$, which is $j$.
The numbers in column $i$ of $P$ are the values of $p_i$ evaluated
at the roots of $p_{d+1}$. Since $p_i$ has degree $i$, and there is
at least one root of $p_{d+1}$ between any two roots of $p_i$
there are $i$ sign changes.
The proof in the $Q$-polynomial case is similar.
\qed

\Example
Consider the Hamming scheme $H(4,2)$, the association scheme
on the binary vectors of length 4, where the relation is
their Hamming distance. Now

$$P = Q = \left[\begin{array}{rrrrr}
1 & 4 & 6 & 4 & 1 \\
1 & 2 & 0 & -2 & -1 \\
1 & 0 & -2 & 0 & 1 \\
1 & -2 & 0 & 2 & -1 \\
1 & -4 & 6 & -4 & 1 \\
\end{array}\right] .$$

\subsection{Distance regular graphs}\label{drg}

Consider a connected simple graph with vertex set $X$ of
diameter $d$. Define $R_i \subset X^2$ by $(x,y)\in R_i$
whenever $x$ and $y$ have graph distance $i$.
If this defines an association scheme, then the graph
$(X,R_1 )$ is called {\it distance-regular}.
The corresponding association scheme is called {\it metric}.
By the triangle inequality, $p_{ij}^k = 0$ if
$i + j < k$ or $| i - j | > k$. Moreover,
$p_{ij}^{i+j} > 0$. Conversely,
if the intersection numbers of an association scheme
satisfy these conditions, then $(X,R_1 )$ is easily
seen to be distance-regular.

Many of the association schemes that play a r\^ole in
combinatorics are metric. Families of distance-regular graphs
with unbounded diameter include the Hamming graphs, the Johnson graphs,
the Grassmann graphs and graphs associated to dual polar spaces.
Recently Van Dam \& Koolen \cite{vDamKoolen} constructed a new such family,
the 15th, and the first without transitive group.

Many constructions and results for strongly regular graphs are the $d = 2$
special case of corresponding results for distance-regular graphs.

% Strongly regular graphs are obviously metric.
% The line graph of the Petersen graph and the Hoffman-Singleton
% graph are easy examples of distance-regular graphs that are not
% strongly regular.

\subsubsection{Parameters}
Conventionally, the parameters are $b_i = p^i_{i+1,1}$ and
$c_i = p^i_{i-1,1}$ (and $a_i = p^i_{i,1}$).
The {\em intersection array} of a distance-regular graph of
diameter $d$ is $\{b_0,\ldots,b_{d-1};~\maysplit c_1,\dots,c_d\}$.
The valencies $p^0_{i,i}$, that were called $n_i$ above,
are usually called $k_i$ here. We have $c_i k_i = b_{i-1} k_{i-1}$.

It is easy to see that one has $b_0 \ge b_1 \ge \ldots \ge b_{d-1}$
and $c_1 \le c_2 \le \ldots \le c_d$ and $c_j \le b_{d-j}$ $(1 \le j \le d)$.

\subsubsection{Bannai-Ito conjecture}
The most famous problem about distance-regular graphs is the
Bannai-Ito conjecture (\cite{bi}, p. 237): show that there are only
finitely many distance-regular graphs with fixed valency $k$ larger than 2.
This has been shown in a series of papers for $k=3,4$
(and also in the bipartite case) by Bannai \& Ito,
and for $k=5,6,7$ by Koolen \& Moulton \cite{KoolenMoulton}.
There is steady progress.

\subsubsection{Connectedness}
For strongly regular graphs we had Theorem \ref{bromesner} stating
that the vertex connectivity $\kappa(\Gamma)$ equals the valency $k$.
It is unknown whether the same holds for distance-regular graphs.
In \cite{bh''} it was shown that the edge connectivity equals the valency.

For strongly regular graphs we also had Proposition \ref{farconnected}
that says that the induced subgraph on the vertices at maximal distance
from a given vertex is connected. This is a very important property,
but for distance-regular graphs additional hypotheses are needed.
For example, there are two generalized hexagons with parameters $GH(2,2)$
(duals of each other) and in one of them the subgraphs $\Gamma_3(x)$
are disconnected.

\subsubsection{Degree of eigenvalues}
For strongly regular graphs we saw that eigenvalues are integral,
except in the `half case' where they are quadratic.
Something similar happens for distance-regular graphs.

Polygons have eigenvalues of high degree: for an $n$-gon the
degree of the $i$-th eigenvalue is $\phi(m)$ where $m = {\rm gcd}(i,n)$,
where $\phi$ is the Euler totient function.
But elsewhere only integral and quadratic eigenvalues seem to occur.

For the case of a $P$- and $Q$-polynomial scheme of diameter at least 34,
Bannai \& Ito \cite{bi} Theorem 7.11 show that the eigenvalues are integers.

There is precisely one known distance-regular graph of valency larger than 2
with a cubic eigenvalue, namely the Biggs-Smith graph, the unique graph
with intersection array $\{3,2,2,2,1,1,1;~1,1,1,1,1,1,3\}$.
It has 102 vertices, and spectrum $3^1~2^{18}~0^{17}~\maysplit
((1\pm\sqrt{17})/2)^9~\theta_j^{16}$ where the $\theta_j$
are the three roots of $\theta^3 + 3\theta^2 - 3 = 0$.

A result in this direction is
%
\begin{Proposition}
The only distance-regular graph of diameter $3$ with a cubic eigenvalue
is the heptagon.
\end{Proposition}
%
\Proof
Let $\Gamma$ be a distance-regular graph of diameter 3 on $n$ vertices
with a cubic eigenvalue.
Since algebraically conjugate eigenvalues have the same multiplicity
we have three eigenvalues $\theta_i$ with multiplicity $f = (n-1)/3$.
Since $\tr A = 0$ we find that $\theta_1+\theta_2+\theta_3 = -k/f$.
Now $k/f$ is rational and an algebraic integer, hence an integer,
and $k \ge (n-1)/3$. The same reasoning applies to $A_i$ for $i=2,3$
and hence $k_i \ge (n-1)/3$, and we must have equality.
Since $k = k_2 = k_3$ we see that $b_1 = c_2 = b_2 = c_3$.

Write $\mu := c_2$.
The distinct eigenvalues $k,\theta_1,\theta_2,\theta_3$ of $A$ are
the eigenvalues of the matrix $L_1$ (Theorem \ref{eigL}) and hence
$k-1 = k+\theta_1+\theta_2+\theta_3 = \tr L_1 = a_1+a_2+a_3 =
(k-\mu-1)+(k-2\mu)+(k-\mu)$, so that $k = 2\mu$ and $a_2 = 0$.

Let $d(x,y) = 3$ and put $A = \Gamma(x) \cap \Gamma_2(y)$,
$B = \Gamma_2(x) \cap \Gamma(y)$, so that $|A| = |B| = c_3 = \mu$.
Every vertex in $B$ is adjacent to every vertex in $A$, and hence
two vertices in $B$ have at least $\mu+1$ common neighbors,
so must be adjacent. Thus $B$ is a clique, and $\mu = |B| \le a_2+1$,
that is, $\mu = 1$, $k = 2$. \qed

\subsubsection{Moore graphs and generalized polygons}
Any $k$-regular graph of diameter $d$ has at most
\[
1 + k + k(k-1) + \ldots + k(k-1)^{d-1}
\]
vertices, as is easily seen.
Graphs for which equality holds are called {\it Moore graphs}.
Moore graphs are distance-regular, and those of diameter 2
were dealt with in Theorem \ref{moore}. Using the rationality
conditions Damerell~\cite{dam}
and Bannai \& Ito~\cite{bi'} showed:
%
\begin{Theorem}
A Moore graph with diameter $d \ge 3$ is a $(2d+1)$-gon.
\end{Theorem}
%
A strong non-existence result of the same nature is the
theorem of Feit \& G.~Higman~\cite{fh}
about finite generalized polygons.
We recall that a {\it generalized $m$-gon} is a point-line
incidence geometry such that the incidence graph is a
connected, bipartite graph
of diameter $m$ and girth $2m$. It is called {\it regular}
of order $(s,t)$ for certain (finite or infinite) cardinal
numbers $s$, $t$ if each line is incident with $s+1$ points
and each point is incident with $t+1$ lines.
% (It is not difficult to prove that if each point is on at least
% three lines, and each line has at least three points
% (and $m < \infty$), then the geometry is necessarily regular,
% and in fact $s = t$ in case $m$ is odd.)
From such a regular generalized $m$-gon of order $(s,t)$,
where $s$ and $t$ are finite and $m \ge 3$,
we can construct a distance-regular graph with valency
$s(t+1)$ and diameter $d = \lfloor\frac{m}{2}\rfloor$ by taking the
collinearity graph on the points.
%
\begin{Theorem}
A finite generalized $m$-gon of order $(s,t)$ with $s > 1$ and
$t > 1$ satisfies $m \in \{2,3,4,6,8\}$.
\end{Theorem}
%
Proofs of this theorem can be found in Feit \& Higman~\cite{fh},
%Kilmoyer \& Solomon~\cite{ks},
Brouwer, Cohen \& Neumaier~\cite{bcn} and Van Maldeghem~\cite{mal};
again the rationality conditions do the job.
The Krein conditions yield some additional information:
%
\begin{Theorem}
A finite regular generalized $m$-gon with $s > 1$ and $t > 1$
satisfies $s \leq t^2$ and $t \leq s^2$ if $m = 4$ or $8$;
it satisfies $s \leq t^3$ and $t \leq s^3$ if $m = 6$.
\end{Theorem}
%
This result is due to Higman~\cite{hig} and Haemers \& Roos~\cite{hr}.
% For each $m \in \{2,3,4,6,8\}$ infinitely many generalized $m$-gons
% exist. (For $m = 2$ we have trivial structures - the incidence
% graph is complete bipartite; for $m = 3$ we have (generalized)
% projective planes; an example of a generalized 4-gon of order (2,2) with
% collinearity graph $T(6)$ can be described as follows:
% the points are the pairs from a 6-set, and the lines are the
% partitions of the 6-set into three pairs, with obvious incidence.)

\subsubsection{Primitivity}
A distance-regular graph $\Gamma$ of diameter $d$ is called
{\em imprimitive} when one of the relations $(X,R_i)$ with
$i \ne 0$ is disconnected.
This can happen in three cases:
either $\Gamma$ is an $n$-gon, and $i | n$,
or $i = 2$, and $\Gamma$ is bipartite,
or $i = d$, and $\Gamma$ is {\em antipodal}, that is,
having distance $d$ is an equivalence relation.
Graphs can be both bipartite and antipodal.
Even polygons fall in all three cases.

\subsubsection{Euclidean representations}
Let $\Gamma$ be distance regular, and let $\theta$ be a fixed eigenvalue.
Let $E = E_j$ be the idempotent in the association scheme
belonging to $\theta$, so that $AE = \theta E$.
Let $u_i = Q_{ij}/n$, so that $E = \sum u_i A_i$. Let $f = \rk E$.

The map sending vertex $x$ of $\Gamma$ to the vector $\bar{x} = Ee_x$,
column $x$ of $E$, provides a representation of $\Gamma$
by vectors in an $f$-dimensional Euclidean space, namely the column span
of $E$, where graph distances are translated into inner products:
if $d(x,y) = i$ then $(\bar{x},\bar{y}) = E_{xy} = u_i$.

If this map is not injective, and $\bar{x} = \bar{y}$ for
two vertices $x,y$ at distance $i \ne 0$, then $u_i = u_0$
and any two vertices at distance $i$ have the same image.
For $i = 1$ this happens when $\theta = k$.
Otherwise, $\Gamma$ is imprimitive, and
either $i = 2$ and $\Gamma$ is bipartite and $\theta = -k$,
or $i = d$ and $\Gamma$ is antipodal,
or $2 < i < d$ and $\Gamma$ is a polygon.

This construction allows one to translate problems about graphs
into problems in Euclidean geometry. Especially when $f$ is small,
this is a very useful tool.

\medskip\noindent
As an example of the use of this representation,
let us prove Terwilliger's Tree Bound.
Call an induced subgraph $T$ of $\Gamma$ {\em geodetic}
when distances measured in $T$ equal distances measured in $\Gamma$.

\begin{Proposition}
Let $\Gamma$ be distance regular, and let $\theta$ be an eigenvalue
different from $\pm k$. Let $T$ be a geodetic tree in $\Gamma$.
Then the multiplicity $f$ of the eigenvalue $\theta$ is at least
the number of endpoints of $T$.
\end{Proposition}
\Proof
We show that the span of the vectors $\bar{x}$ for $x \in T$
has a dimension not less than the number $e$ of endpoints of $T$.
Induction on the size of $T$.
If $T=\{x,y\}$ then $\bar{x} \ne \bar{y}$ since $k \ne \theta$.
Assume $|T| > 2$. If $x \in T$, and $S$ is the set
of endpoints of $T$ adjacent to $x$, then for $y,z \in S$
and $w \in T\setminus S$ we have $(\bar{w}, \bar{y}-\bar{z}) = 0$.
Pick $x$ such that $S$ is nonempty, and $x$ is an endpoint of
$T' = T\setminus S$.
By induction $\dim \langle \bar{w} \,|\, w \in T' \rangle \ge e-|S|+1$.
Since $\theta \ne \pm k$ we have
$\dim \langle \bar{y}-\bar{z} \,|\, x,y \in S \rangle = |S|-1$.
% This proves $\dim \langle \bar(x) \,|\, x \in T \rangle \ge e$.
\qed

\Example
For a distance-regular graph without triangles,
$f \ge k$. Equality can hold. For example, the Higman-Sims graph
is strongly regular with parameters $(v,k,\lambda,\mu) = (100,22,0,6)$
and spectrum $22^1~2^{77}~(-8)^{22}$.

\subsection{Exercises}

\Exercise
Given an association scheme.
Show that the number of relations of valency 1 is $2^m$ for
some $m \ge 0$, and $2^m | n$.
Hint: the relations of valency 1 form an elementary abelian 2-group
with operation $i \oplus j = k$ when $A_iA_j = A_k$.

\Exercise
Show that for the special case where $Y$ is a coclique
in a strongly regular graph, the linear programming
bound is the Hoffman bound (Theorem~\ref{ho}).

\Exercise
Consider a primitive strongly regular graph $\Gamma$ on $v$
vertices with eigenvalues $k^1, r^f, s^g$ ($k>r>s$) with a
Hoffman coloring (that is a coloring with $1-k/s$ colors).
Consider the following relations on the vertex set of $\Gamma$:
$R_0$: identity,\\
$R_1$: adjacent in $\Gamma$,\\
$R_2$: nonadjacent in $\Gamma$ with different colors,\\
$R_3$: nonadjacent in $\Gamma$ with the same color.\\
Prove that these relations define an association scheme on the
vertex set of $\Gamma$, and determine the matrices $P$ and $Q$.

\section{The (81,20,1,6) strongly regular graph}\label{81}

Let $\Gamma = (X,E)$ be a strongly regular graph with parameters
$(v,k, \lambda , \mu ) = (81,20,1,6)$.
Then $\Gamma$
% (that is, its adjacency matrix)
has spectrum $\{20^1, 2^{60}, -7^{20}\}$, where the exponents denote
multiplicities.
We will show that up to isomorphism there is a unique such graph $\Gamma$.
More generally we give a short proof for the fact (due to
Ivanov \& Shpectorov~\cite{is}
that a strongly regular graph with parameters
$(v,k, \lambda , \mu ) = (q^4, (q^2 + 1)(q-1), q-2, q(q-1))$
that is the collinearity graph of a partial quadrangle (that is,
in which all maximal cliques have size $q$) is the second subconstituent
of the collinearity graph of a generalized quadrangle $GQ(q,q^2)$.
In the special case $q = 3$ this will imply our previous claim, since
$\lambda = 1$ implies that all maximal cliques have size 3, and it is known
(see Cameron, Goethals \& Seidel~\cite{cgs}) that there is a unique
generalized quadrangle $GQ(3,9)$ (and this generalized quadrangle
has an automorphism group transitive on the points).

\subsection{Descriptions}

Let us first give a few descriptions of our graph on 81 vertices.
Note that the uniqueness shows that all constructions below
give isomorphic graphs, something, which is not immediately
obvious from the description in all cases.
%
\begin{itemize}
\item[A.]
Let $X$ be the point set of $AG(4,3)$, the 4-dimensional
affine space over $\F_3$, and join two points when the
line connecting them hits the hyperplane at infinity
(a $PG(3,3)$) in a fixed elliptic quadric $Q$.
This description shows immediately that $v = 81$ and $k = 20$
(since $| Q | = 10$). Also $\lambda = 1$ since no line meets $Q$
in more than two points, so that the affine lines are the only
triangles. Finally $\mu = 6$, since a point outside $Q$ in
$PG(3,3)$ lies on 4 tangents, 3 secants and 6 exterior lines
with respect to $Q$, and each secant contributes 2 to $\mu$.
We find that the group of automorphisms contains
$G = 3^4\cdot PGO_4^{-}\cdot 2$, where the last factor 2
accounts for the linear transformations that do not preserve
the quadratic form $Q$, but multiply it by a constant.
In fact this is the full group, as will be clear from the
uniqueness proof.
\item[B.]
A more symmetric form of this construction is found by
starting with $X = \1^\perp/\left<\1\right>$ in $\F_3^6$ provided
with the standard bilinear form.
The corresponding quadratic form
($Q(x) = \mbox{wt}(x)$, the number of nonzero coordinates of $x$)
is elliptic, and if we join two vertices
$x + \left< \1 \right> , y + \left< \1 \right>$ of $X$
when $Q(x-y) = 0$, i.e., when their difference has weight 3,
we find the same graph as under A.
This construction shows that the automorphism group contains
$G = 3^4\cdot(2 \times \mbox{Sym }(6))\cdot 2$, and again this
is the full group.
\item[C.] There is a unique strongly regular graph $\Gamma$ with parameters
$(112,30,2,10)$, the collinearity graph
of the unique generalized quadrangle with parameters $GQ(3,9)$.
Its second subconstituent is an $(81, 20, 1, 6)$ strongly regular
graph, and hence isomorphic to our graph $\Gamma$.
(See Cameron, Goethals \& Seidel~\cite{cgs}.)
We find that Aut~$\Gamma$ contains (and in fact it equals)
the point stabilizer in $U_4 (3)\cdot D_8$ acting on $GQ(3,9)$.
\item[D.]
The graph $\Gamma$ is the coset graph of the truncated
ternary Golay code $C$: take the $3^4$ cosets of $C$
and join two cosets when they contain vectors differing
in only one place.
\item[E.]
The graph $\Gamma$ is the Hermitean forms graph on $\F_9^2$;
more generally, take the $q^4$ matrices $M$ over $\F_{q^2}$
satisfying
$M^\top = \overline{M}$, where $^-$ denotes the field
automorphism $x \rightarrow x^q$ (applied entrywise),
and join two matrices when their difference has rank 1.
This will give us a strongly regular graph with parameters
$(v,k, \lambda , \mu ) = (q^4 , (q^2 + 1)(q-1), q-2, q(q-1))$.
\item[F.]
The graph $\Gamma$ is the graph with vertex set $\F_{81}$, where
two vertices are joined when their difference is a fourth power.
(This construction was given by
Van Lint \& Schrijver~\cite{ls}.)
\end{itemize}

\subsection{Uniqueness}

Now let us embark upon the uniqueness proof.
Let $\Gamma = (X,E)$ be a strongly regular graph with parameters
$(v,k, \lambda , \mu ) = (q^4 , (q^2 + 1)(q-1), q-2, q(q-1))$
and assume that all maximal cliques (we shall just call them lines)
of $\Gamma$ have size $q$.
Let $\Gamma$ have adjacency matrix $A$. Using the spectrum of $A$ -
it is $\{k^1, (q-1)^f, (q-1-q^2 )^g \}$, where
$f = q(q-1)(q^2 + 1 )$ and $g = (q-1)(q^2 + 1)$ -
we can obtain some structure information.
Let $\T$ be the collection of subsets of $X$ of cardinality $q^3$
inducing a subgraph that is regular of degree $q-1$.
%
\begin{itemize}
\item[1.] {\bf Claim.}
{\it If $T \in \T$, then each point of $X \setminus T$ is adjacent to
$q^2$ points of $T$.}\\
Look at the matrix $B$
of average row sums of $A$, with sets of rows and columns
partitioned according to $\{ T , X\setminus T \}$. We have
\[
B = \left[ \begin{array}{cc}
q-1 & {q^2 (q-1)} \\
q^2 & {k-q^2}
\end{array} \right]
\]
with eigenvalues $k$ and $q-1-q^2$, so interlacing is tight,
and by Corollary~\ref{hs}(ii) it follows that the row sums are constant
in each block of $A$.
\item[2.] {\bf Claim.}
{\it Given a line $L$, there is a unique $T_L \in \T$ containing
$L$.}\\
Let $Z$ be the set of vertices in $X \setminus L$
without a neighbor in $L$.
Then $|Z| = q^4 - q - q (k-q+1) = q^3 - q$. Let $T = L \cup Z$.
Each vertex of $Z$ is adjacent to $q \mu = q^2 (q-1)$ vertices with
a neighbor in $L$, so $T$ induces a subgraph that is regular
of degree $q-1$.
\item[3.] {\bf Claim.}
{\it If $T \in \T$ and $x \in X \setminus T$, then $x$ is on at
least one line $L$ disjoint from $T$, and $T_L$ is disjoint from
$T$ for any such line $L$.}\\
The point $x$ is on $q^2 + 1$ lines, but has only $q^2$
neighbors in $T$. Each point of $L$ has $q^2$ neighbors in $T$,
so each point of $T$ has a neighbor on $L$ and hence is not in
$T_L$.
\item[4.] {\bf Claim.}
{\it Any $T \in \T$ induces a subgraph $\Delta$ isomorphic to
$q^2 K_q$.}\\
It suffices to show that the multiplicity $m$ of the eigenvalue $q-1$ of
$\Delta$ is (at least) $q^2$ (it cannot be more).
By interlacing we find $m \ge q^2 - q$, so we need some additional work.
Let $M := A - ({q-1}/{q^2}) J$.
Then $M$ has spectrum $\{ (q-1)^{f+1}, (q-1-q^2 )^g\}$,
and we want that $M_T$, the submatrix of $M$ with rows and
columns indexed by $T$, has eigenvalue $q-1$ with multiplicity
(at least) $q^2 - 1$, or, equivalently (by Lemma~\ref{l}), that
$M_{X \setminus T}$ has eigenvalue $q-1-q^2$ with multiplicity
(at least) $q-2$.
But for each $U \in\T$ with $U \cap T = \emptyset$ we find an eigenvector
$x_U = (2-q) \chi_U + \chi_{ X \setminus (T \cup U) }$
of $M_{X \setminus T}$ with eigenvalue $q-1-q^2$.
A collection $\{ x_U | U \in \U \}$
of such eigenvectors cannot be linearly dependent when
$\U = \{ U_1 , U_2 ,\dots\}$ can be ordered
such that $U_i \not\subset \bigcup_{j<i} U_j$ and
$\bigcup\U \neq X \setminus T$, so we can find (using Claim~3)
at least $q-2$ linearly independent such eigenvectors, and we are done.
\item[5.] {\bf Claim.}
{\it Any $T \in \T$ determines a unique partition of $X$ into members
of $\T$.}\\
Indeed, we saw this in the proof of the previous step.
\end{itemize}
%
Let $\Pi$ be the collection of partitions of $X$ into members of $\T$.
We have $|\T| = q(q^2 + 1)$ and $| \Pi | = q^2 + 1$.
Construct a generalized quadrangle $GQ(q,q^2 )$
with point set $\{\infty\}\cup\T \cup X$ as follows:
The $q^2 + 1$ lines on $\infty$ are $\{\infty\}\cup\pi$ for
$\pi \in\Pi$.
The $q^2$ remaining lines on each $T\in\T$ are
$\{T\}\cup L$ for $L\subset T$.
It is completely straightforward to check that we really
have a generalized quadrangle $GQ(q,q^2 )$.

\subsection{Independence and Chromatic numbers}
We have $\alpha(\Gamma) = 15$ and $\chi(\Gamma)=7$.

Clearly, the independence number of our graph is one less than the
independence number of the unique $GQ(3,9)$ of which it is the second
subconstituent. So it suffices to show that $\alpha(\Delta) = 16$,
where $\Delta$ is the collinearity graph of $GQ(3,9)$.

It is easy to indicate a 16-coclique:
define $GQ(3,9)$ in $PG(5,3)$ provided with the nondegenerate
elliptic quadratic form $\sum_{i=1}^6 x_i^2$.
There are 112 isotropic points, 80 of weight 3 and 32 of weight 6.
Among the 32 of weight 6, 16 have coordinate product 1, and 16
have coordinate product $-1$, and these two 16-sets are cocliques.

That there is no larger coclique can be seen by cubic counting.

Let $C$ be a 16-coclique in $\Delta$. Let there be $n_i$
vertices outside that have $i$ neighbors inside. Then
$$\sum n_i = 96,~~
\sum in_i = 480,~~
\sum {i \choose 2} n_i = 1200,~~
\sum {i \choose 3} n_i = 2240,$$
so that
$$\sum (i-4)^2 (i-10) n_i = 0.$$
(Here the quadratic counting is always possible in a strongly
regular graph, and the last equation can be written because the second
subconstituent is itself strongly regular.)
Now each point is on 10 lines, and hence cannot have more than 10
neighbors in $C$. It follows that each point has either 4 or 10
neighbors in $C$. In particular, $C$ is maximal.

As an aside:
Solving these equations gives $n_4 = 80$, $n_{10} = 16$.
Let $D$ be the set of 16 vertices with 10 neighbors in $C$.
If two vertices $d_1,d_2 \in D$ are adjacent then they can have
only 2 common neighbors in $C$, but each has 10 neighbors in $C$,
contradiction. So, also $D$ is a 16-coclique, which means that
16-cocliques in $\Delta$ come in pairs.

\medskip\noindent
Since $81 / 15 > 5$, we have $\chi(\Gamma) \ge 6$.
Since $\Delta$ has a split into two Gewirtz graphs,
and the Gewirtz graph has chromatic number 4, it follows
that $\chi(\Delta) \le 8$. (And in fact equality holds.)
This shows that for our graph $6 \le \chi(\Gamma) \le 8$.
In fact $\chi(\Gamma) = 7$ can be seen by computer
(Edwin van Dam, pers. comm.).
% verified, aeb

Since $\lambda=1$, the maximum clique size equals 3. And from the
uniqueness proof it is clear that $\Gamma$ admits a partition into 27
triangles. So the complement of $\Gamma$ has chromatic number 27.

\subsection{Exercises}

\Exercise
With $C$ and $D$ as above, show that $C \cup D$ induces a
distance-regular graph of diameter three with intersection
array $\{10,9,4;1,6,10\}$.
% By counting:
% Let the be m_i vertices adjacent to 2 fixed vertices of C
% and i more. Then m_2+m_8 = 10, 2m_2+8m_8 = 56, so m_8 = 6
% that is, two vertices in C have 6 common neighbors in D.

\Exercise
Show that $\chi(\Gamma)\geq 6$ also follows from Corollary~\ref{chi'}
applied to the induced subgraph of $\Gamma$, obtained by deleting all
vertices of one color class.

\begin{thebibliography}{999}

\bibitem{AKS83} M. Ajtai, J. Koml\'os \& E. Szemer\'edi,
{\it Sorting in $c \log n$ parallel steps},
Combinatorica {\bf 3} (1983) 1--19.

\bibitem{asc}
M. Aschbacher,
{\it The non-existence of rank three permutation groups of degree 3250
and subdegree 57},
J. Algebra {\bf 19} (1971) 538--540.

\bibitem{bi'}
E. Bannai \& T. Ito,
{\it On finite Moore graphs},
J. Fac. Sci. Univ. Tokyo, Sect IA {\bf 20} (1973) 191--208.

\bibitem{bi}
E. Bannai \& T. Ito,
{\it Algebraic Combinatorics I: Association Schemes,}
Benjamin/Cummings, London, 1984.

\bibitem{BermanPlemmons}
A. Berman \& R. J. Plemmons,
{\it Nonnegative matrices in the mathematical sciences},
Acad. Press, New York, 1979.

\bibitem{big}
N. L. Biggs,
{\it Algebraic Graph Theory},
Cambridge Tracts in Mathematics, Vol 67, Cambridge Univ. Press,
Cambridge, 1974.

\bibitem{bm}
R. C. Bose, \& D. M. Mesner,
{\it On linear associative algebras corresponding to association schemes
of partially balanced designs},
Ann. Math. Statist. {\bf 30} (1959) 21--38.

\bibitem{bs}
R. C. Bose \& T. Shimamoto,
{\it Classification and analysis of partially balanced incomplete
block designs with two associate classes},
J. Am. Statist. Assoc. {\bf 47} (1952) 151--184.

\bibitem{BrouwerGQfin}
A. E. Brouwer,
{\it A non-degenerate generalized quadrangle with lines of size four
is finite}, in: Advances in finite geometries and designs,
Proc. 3rd Isle of Thorns Conf., Chelwood Gate/UK 1990, pp. 47--49.

\bibitem{bcn}
A. E. Brouwer, A. M. Cohen \& A. Neumaier,
{\it Distance-Regular Graphs}, Springer-Verlag, 1989.

\bibitem{BrouwervEijl}
A. E. Brouwer \& C. A. van Eijl,
{\it On the $p$-rank of the adjacency matrices of strongly regular graphs},
J. Alg. Combinatorics {\bf 1} (1992) 329-346.

\bibitem{bh}
A. E. Brouwer \& W. H. Haemers,
{\it Association Schemes}, in:
Handbook of Combinatorics,
eds. R. Graham, M. Gr\"otschel \& L. Lov\'asz,
Elsevier, Amsterdam, 1995, pp. 747--771.

\bibitem{bh'}
A. E. Brouwer \& W. H. Haemers,
{\it Structure and uniqueness of the $(81,20,1,6)$ strongly regular graph},
Discrete Math. {\bf 106/107} (1992) 77--82.

\bibitem{bh''}
A. E. Brouwer \& W. H. Haemers,
{\it Eigenvalues and perfect matchings},
Linear Alg. Appl. {\bf 395} (2005) 155--162.

\bibitem{bl}
A. E. Brouwer \& J. H. van Lint,
{\it Strongly regular graphs and partial geometries},
in: Enumeration and designs, Proc. Silver Jubilee
Conf. on Combinatorics, Waterloo 1982,
eds. D. M.~Jackson \& S. A.~Vanstone,
Academic Press, Toronto. pp. 85--122.

\bibitem{BroMesner}
A. E. Brouwer \& D. M. Mesner,
{\it The connectivity of strongly regular graphs},
Europ. J. Combin. {\bf 6} (1985) 215-216.

\bibitem{BroNeum89}
A. E. Brouwer \& A. Neumaier,
{\it The graphs with spectral radius between $2$ and $\sqrt{2 + \sqrt 5}$},
Lin. Alg. Appl. {\bf 114/115} (1989) 273--276.

\bibitem{bw}
A. E. Brouwer \& H. A. Wilbrink,
{\it Block designs},
in: Handbook of Incidence Geometry (F. Buekenhoud ed.),
Elsevier, 1995, pp. 349--382.

\bibitem{bur}
M. Burrow,
{\it Representation theory of finite groeps,}
Academic Press, New York, 1965.

\bibitem{CK86}
A. R. Calderbank \& W. M. Kantor,
{\it The geometry of two-weight codes},
Bull. London Math. Soc. {\bf 18} (1986) 97--122.

\bibitem{CameronGQfin}
P. J. Cameron,
{\it Orbits of permutation groups on unordered sets. II},
J. Lond. Math. Soc., II. Ser. {\bf 23} (1981) 249--264.

\bibitem{cgs}
P. J. Cameron, J.-M. Goethals \& J. J Seidel,
{\it Strongly regular graphs having strongly regular subconstituents},
J. Algebra {\bf 55} (1978) 257--280.

\bibitem{Cherlin}
Gregory Cherlin,
{\it Locally finite generalized quadrangles with at most five points
per line}, Discrete Math. {\bf 291} (2005) 73--79.

\bibitem{CourantHilbert1924}
R. Courant \& D. Hilbert,
{\it Methoden der Mathematischen Physik},
Springer Verlag, Berlin, 1924.

\bibitem{cve}
D. M. Cvetkovi\'{c},
{\it Graphs and their spectra},
Publ. Elektrotehn. Fak. Ser. Mat. Fiz. {\bf 354--356} (1971) 1--50.

\bibitem{CDS}
D. M. Cvetkovi\'c, M. Doob \& H. Sachs,
{\it Spectra of Graphs: Theory and Applications},
V.E.B. Deutscher Verlag der Wissenschaften,
Berlin, 1979. (Also: Academic Press, New York, 1980.
Third edition, Johann Abrosius Barth Verlag, Heidelberg-Leipzig, 1995.)

\bibitem{dh}
E. R. van Dam \& W. H. Haemers,
{\it Which graphs are determined by their spectra?}
Linear Alg. Appl. {\bf 373} (2003) 241--272.

\bibitem{vDamKoolen}
E. R. van Dam \& J. H. Koolen,
{\it A new family of distance-regular graphs with unbounded diameter},
preprint, 2005.

\bibitem{dam}
R. M. Damerell,
{\it On Moore graphs},
Proc. Cambridge Philos. Soc. {\bf 74} (1973) 227--236.

\bibitem{Del72} Ph. Delsarte,
{\it Weights of linear codes and strongly regular normed spaces},
Discrete Math. {\bf 3} (1972) 47--64.

\bibitem{del}
Ph. Delsarte,
{\it An algebraic approach to the association schemes of coding theory},
Philips Res. Rep. Suppl. {\bf 10} (1973).

\bibitem{dgs}
Ph. Delsarte, J.-M. Goethals \& J. J. Seidel,
{Bounds for systems of lines and Jacobi polynomials},
Philips Res. Rep. {\bf 30} (1975) 91*--105*

% \bibitem{Duval} Art M. Duval,
% {\it A directed graph version of strongly regular graphs},
% J. Combinat. Th. (A) {\bf 47} (1988) 71--100.

\bibitem{fh}
W. Feit \& G. Higman,
{\it The non-existence of certain generalized polygons},
J. Algebra {\bf 1} (1964) 114--131.

% \bibitem{FKP}
% F. Fiedler, M. Klin \& Ch. Pech,
% {\it Directed strongly regular graphs as elements of coherent algebras},
% in: General Algebra and Discrete Mathematics: proceedings of the Conference
% on General Algebra and Discrete Mathematics,
% Potsdam 1998, K. Denecke \& H.-J. Vogel (eds.),
% Shaker Verlag, Aachen 1999, 69--87.

\bibitem{Fischer1905} E. Fischer,
{\it \"Uber quadratische Formen mit reellen Koeffizienten},
Monatsh. f. Math. u. Phys. {\bf 16} (1905) 234--249.

% \bibitem{Fi71} B. Fischer,
% {\it Finite groups generated by 3-transpositions},
% Invent. Math. {\bf 13} (1971) 232--246.

\bibitem{Gantmacher} F.R. Gantmacher,
{\it Applications of the Theory of Matrices},
Interscience, New York, 1959.

\bibitem{god}
Godsil, C.D.,
{\it Algebraic Combinatorics},
Chapman and Hall, New York, 1993.

\bibitem{gr}
Godsil, C.D. \& G. Royle,
{\it Algebraic Graph Theory},
Springer-Verlag, New York, 2001.

% \bibitem{GM97} A. Gunawardena \& G.E. Moorhouse,
% {\it The non-existence of ovoids in $O_9(q)$},
% Europ. J. Combin. {\bf 18} (1997) 171--173.

\bibitem{hae`}
W. H. Haemers.
{\it Eigenvalue methods},
in: Packing and covering in combinatorics (A. Schrijver ed.),
Math. Centre Tract 106, Mathematical Centre, Amsterdam, 1979, pp. 15--38.

\bibitem{HaemersThesis}
W. H. Haemers,
{\it Eigenvalue techniques in design and graph theory},
Reidel, Dordrecht, 1980.
Thesis (T.H. Eindhoven, 1979) = Math. Centr. Tract 121 (Amsterdam, 1980)

\bibitem{hae'}
W. H. Haemers,
{\it Interlacing eigenvalues and graphs},
Linear Alg. Appl. {\bf 226--228} (1995) 593--616.

\bibitem{hf}
W. H. Haemers \& N. C. Fiala,
{\it 5-Chromatic strongly regular graphs},
Proceedings IPM workshop on Combinatorics, 2003.
Discrete Mathematics, to appear.

\bibitem{hr}
W. H. Haemers \& C. Roos,
{\it An inequality for generalized hexagons},
Geom. Dedicata {\bf 10} (1981) 219--222.

\bibitem{hash}
W. H. Haemers \& M. S. Shrikhande,
{\it Some remarks on subdesigns of symmetric designs},
J. Stat. Plann. Inference 3 (1979) 361--366.

% \bibitem{Hammersley} J. M. Hammersley,
% {\it The friendship theorem and the love problem},
% pp. 31--54 in: Surveys in Combinatorics (E. Keith Lloyd, ed.),
% Cambridge University Press 1983.

\bibitem{hmpr}
C. Helmberg, B. Mohar, S. Poljak \& F. Rendl,
{\it A spectral approach to bandwidth and separator problems in graphs},
Proceedings third IPCO conf. (G. Rinaldi and L. Wolsey, eds.)
(1993) 183--194.

\bibitem{hig}
D. G. Higman,
{\it Partial geometries, generalized quadrangles and strongly regular graphs},
in: Atti Convegno di Geometria, Combinatoria e sue Applicazioni, Perugia 1970,
(A. Berlotti, ed.) (1971) pp. 263--293.

% \bibitem{Hill76} R. Hill,
% {\it Caps and Groups},
% pp. 389--394 in:
% Coll. Intern. Teorie Combin. Acc. Naz. Lincei, Roma 1973,
% Atti dei convegni Lincei 17, Rome, 1976.

% \bibitem{HoSh} S.A. Hobart \& T.J. Shaw,
% {\it A note on a family of directed strongly regular graphs},
% Europ. J. Comb. {\bf 20} (1999) 819--820.

\bibitem{Hoffman63}
A. J. Hoffman,
{\it On the polynomial of a graph},
Amer. Math. Monthly {\bf 70} (1963) 30--36.

\bibitem{hof}
A. J. Hoffman,
{\it On eigenvalues and colourings of graphs},
in: Graph theory and its applications, (B. Harris, ed.),
Acad. Press, New York, 1970, pp. 79--91.

\bibitem{hs}
A. J. Hoffman \& R. R.~Singleton,
{\it On Moore graphs with diameter 2 and 3},
IBM J. Res. Develop. {\bf 4} (1960) 497--504.

\bibitem{hub}
X. Hubaut,
{\it Strongly regular graphs},
Discrete Math. {\bf 13} (1975) 357--381.

\bibitem{is}
A. A. Ivanov \& S. V. Shpectorov,
{\it The association schemes of dual polar spaces of type
${}^2A_{2d-1}(p^f)$ are characterized by their parameters if $d > 3$},
Linear Alg. Appl. {\bf 114} (1989) 113--139.

% \bibitem{Jorg1}
% Leif K. J\o rgensen,
% {\it Directed strongly regular graphs with $\mu = \lambda$},
% Discrete Math. {\bf 231} (2001) 289--293.
% % Aalborg University preprint R-99-2009, August 1999.

% \bibitem{Jorg2} Leif K. J\o rgensen,
% {\it Non-existence of directed strongly regular graphs},
% Aalborg University preprint R-00-2024, September 2000.

\bibitem{jun}
D. Jungnickel,
{\it On subdesigns of symmetric designs},
Math. Z. {\bf 181} (1982) 383--393.

% \bibitem{KMMZ} M. Klin, A. Munemasa, M. Muzychuk \& P.-H. Zieschang,
% {\it Directed strongly regular graphs via coherent (cellular) algebras},
% preprint Kyushu MPS-1997-12, Kyushu University, 1997.

% \bibitem{KPZ} Mikhail Klin, Christian Pech \& Paul-Hermann Zieschang,
% {\it Flag algebras of block designs: I. Initial notions,
% Steiner 2-designs, and generalized quadrangles}, preprint,
% Technische Universität Dresden.

\bibitem{KoolenMoulton}
J. H. Koolen \& V. Moulton,
{\it On a conjecture of Bannai and Ito: There are finitely many
distance-regular graphs with degree 5, 6 or 7},
European J. Combin. {\bf 23} (2002) 987-–1006.

% \bibitem{lan}  E.S. Lander,
% {\it Symmetric designs: an algebraic approach,} London Math. Soc.
% Lect. Note Ser. 74, Cambridge Univ. Press, Cambridge, 1983.

% \bibitem{deLange} C.L.M. de Lange,
% {\it Some new cyclotomic strongly regular graphs},
% J. Algebraic Combin. {\bf 4} (1995) 329--330.

\bibitem{LemmensSeidel}
P. W. H. Lemmens \& J. J. Seidel,
{\it Equiangular lines}, J. Algebra {\bf 24} (1973) 494--512.

% \bibitem{vL82}
% J. H. van Lint,
% {\it Introduction to coding theory},
% Graduate Texts in Math. 86, Springer, New York, 1982.

\bibitem{ls}
J. H. van Lint \& A. Schrijver,
{\it Constructions of strongly regular graphs, two-weight codes and
partial geometries by finite fields},
Combinatorica {\bf 1} (1981) 63--73.

% \bibitem{lov}  L. Lov\'asz, {\it Combinatorial problems and exercises},
% North Holland, Amsterdam, 1979.

% \bibitem{McWS} F. J. MacWilliams \& N. J. A. Sloane,
% {\it The Theory of Error-Correcting Codes},
% North Holland Publ. Co., Amsterdam, 1977.

\bibitem{MarcusMinc}
M. Marcus \& H. Minc,
{\it A survey of matrix theory and matrix inequalities},
Allyn and Bacon, Boston, 1964.

\bibitem{mm}
M. Marcus \& H. Minc,
{\it Introduction to linear algebra.}
Macmillan, New York, 1965.

% \bibitem{McER72}
% R. J. McEliece \& H. Rumsey, jr.,
% {\it Euler products, cyclotomy and coding},
% J. Number Th. {\bf 4} (1972) 302--311.

\bibitem{neu}
A. Neumaier,
{\it New inequalities for the parameters of an association scheme},
in: Combinatorics and Graph Theory, Proc. Calcutta 1980,
Lecture Notes in Math. Vol 885 (S.B. Rao, ed.),
Springer, Berlin, pp. 365--367.

\bibitem{pay}
S. E. Payne,
{\it An inequality for generalized quadrangles},
Proc. Amer. Math. Soc. {\bf 71} (1978) 147--152.

\bibitem{Peeters}
M. J. P. Peeters, {\it Ranks and Structure of Graphs},
PhD thesis, Tilburg University, 1995.

\bibitem{sco}
L. L. Scott Jr,
{\it A condition on Higman's parameters},
Notices Amer. Math. Soc. {\bf 20}, A-97 (1973) 701-20-45.

\bibitem{Seidelmin2}
J. J. Seidel,
{\it Strongly regular graphs with $(-1,1,0)$ adjacent matrix
having eigenvalue 3}, Lin. Alg. Appl. {\bf 1} (1968) 281--298.

\bibitem{sei}
J. J. Seidel,
{\it Strongly regular graphs}, in:
Surveys in Combinatorics, Proc. 7th Bitish Combinatorial Conf.,
LMSLN ser. Vol 38, ed. B.~Bollob\'as,
Cambridge Univ. Press, Cambridge, 1979, pp.157--180.

\bibitem{Seneta}
E. Seneta,
{\it Non-negative matrices and Markov chains},
Springer Series in Statistics, Springer, New York, 1981.

\bibitem{Smith1970}
J. H. Smith,
{\it Some properties of the spectrum of a graph},
pp. 403--406 in: Combinatorial Structures and their applications
(Proc. Conf. Calgary, 1969), R. Guy et al. (eds.)
Gordon and Breach, New York, 1970.

\bibitem{Sylvester}
J. J. Sylvester,
{\it A demonstration of the theorem that every homogeneous
quadratic polynomial is reducible by real orthogonal substitutions
to the form of a sum of positive and negative squares},
Philos. Mag. {\bf 4} (1852) 138--142.
(Reprinted in: Coll. Math. Papers 1, Cambridge Univ. Press, 1904,
pp. 378--381.)

\bibitem{sze}
G. Szeg\"o,
{\it Orthogonal Polynomials},
AMS Colloq. Publ. {\bf 23}, 1939 (1st ed.), 1975 (4th ed.).

\bibitem{Tanner}
R.M. Tanner,
{\it Explicit concentrators from generalized $n$-gons},
SIAM J. Algebr. Discr. Meth. {\bf 5} (1984) 287--293.

\bibitem{tut}
W. T. Tutte,
{\it The factorizations of linear graphs},
J. London Math. Soc. {\bf 22} (1947) 107--111.

\bibitem{mal}
H. Van Maldeghem,
{\it Generalized Polygons}, Birkh\"auser, Basel, 1998.

\bibitem{Varga}
R. S. Varga,
{\it Matrix iterative analysis},
Prentice-Hall, Englewood Cliffs, New York, 1962.

% \bibitem{WilsonXiang}
% R. M. Wilson \& Qing Xiang,
% {Cyclotomy, Half Ovoids and Two-weight Codes},
% Preprint, 1997.

\end{thebibliography}
\end{document}

\section{Gram matrices}

Real symmetric $n \times n$-matrices $G$ are in bijective correspondence
with quadratic forms $q$ on $\Rr^n$ via the relation
$$
q(x) = x^\top G x ~~~~ ( x \in \Rr^n ) .
$$
Two quadratic forms $q$ and $q'$ on $\Rr^n$ are {\em congruent},
i.e., there is a nonsingular $n \times n$-matrix $S$ such that
$q(x) = q' ( Sx)$ for all $x \in \Rr^n$,
if and only if their corresponding matrices $G$ and $G'$ satisfy
$G = S^\top G' S$. Moreover, this occurs for some $S$ if and only
if $G$ and $G'$ have the same rank and the same number of
nonnegative eigenvalues
(Sylvester \cite{Sylvester}'s `law of inertia for quadratic forms', cf.
Gantmacher \cite{Gantmacher}, Vol. 1, Chapter X, \S 2);
recall the basic fact that every real symmetric square matrix
has real eigenvalues only, and an orthonormal basis of eigenvectors.
We shall now be concerned with matrices having nonnegative eigenvalues only.

\begin{Lemma}
Let $G$ be a real symmetric $n \times n$-matrix.
Then {(i)} and {(ii)} are equivalent:

(i)
For all $x \in \Rr^n$,
$x^\top G x \ge 0$.

(ii)
All eigenvalues of $G$ are nonnegative.
\end{Lemma}
\Proof
There is an orthogonal matrix $Q$ and
a diagonal matrix $D$ whose
nonzero entries are the eigenvalues of $G$ such that
$G = Q^\top D Q$. If (ii) holds, then
$x^\top G x = (Qx)^\top D(Qx) \ge 0$
implies (i).
Conversely, (ii) follows from (i)
by choosing $x$ to be an eigenvector.
\qed

A symmetric $n \times n$-matrix $G$ satisfying (i) and (ii) is called
{\em positive semidefinite}.
It is called {\em positive definite} when $x^\top G x = 0$
implies $x = 0$, or, equivalently, when all its eigenvalues are positive.
For any collection $X$ of vectors of $\Rr^n$,
we define its {\em Gram matrix}
as the square matrix $G$ indexed by $X$
(or by some index set for $X$) whose
$( x , y )$-entry $G_{x y}$ is the inner product
$( x , y ) = x^\top y$.
This matrix
is always positive semidefinite, and it
is definite if and only if the vectors in $X$ are
linearly independent. (Indeed, if we use $H$ to denote the
$n \times | X |$-matrix whose columns are the vectors of $X$,
then $G = H^\top H $, and $x^\top G x = (Hx,Hx) \ge 0$.)
Conversely, if
$G$ is an arbitrary symmetric positive
semidefinite matrix of rank $n$
then $G$ is congruent to a diagonal
matrix consisting of zeros and $n$
ones,
$$
G = ( S_{11}^{\top}
~ S_{12}^\top )
\left(\begin{array}{cc}
I & 0 \\
0 & 0
\end{array}\right)
\left(\begin{array}{c}
S_{11} \\
S_{12}
\end{array}\right) = S_{11}^\top ~ S_{11},
$$
so that $G$ is the Gram matrix of the set
of columns of $S_{11}$ in $\Rr^n$.
