# Spectrum of the adjacency matrix of strongly regular graphs

I am working through a proof of the following Theorem: Let $G$ be a connected, $k$-regular graph, $G\neq K_n$, then $G$ is strongly regular if and only if $|Spec(G)|=3$.

Now I am having trouble with the given proof of the "$\Leftarrow$" direction:

Let $k,\beta_1,\beta_2$ be the eigenvalues of $A$. Consider the matrix \begin{align*} M:=\frac{1}{(k-\beta_1)(k-\beta_2)}(A-\beta_1 I)(A-\beta_2 I), \end{align*} then $M$ has all of its eigenvalues equal to $0$ or $1$. This is, since if $b_i$ is an eigenvector of $A$ to eigenvalue $\beta_i$, $i=1,2$, with $b_i\perp\mathbb{1}$, then \begin{align*} M\cdot b_1 =0,\\ M\cdot b_2 =0,\\ M\cdot\mathbb{1}=\mathbb{1}. \end{align*} Therefore $Spec(M)=\{1^{(1)},0^{(n-1)}\}$. Since $G$ is connected and because of the spectrum of $J$ (the $n\times n$ matrix with all 1's entries) as computed as $Spec(J)=\{1^{(1)},0^{(n-1)}\}$, we get $M=\frac{1}{n}\cdot J$. That is \begin{align*} \frac{1}{n}\cdot J=\frac{1}{(k-\beta_1)(k-\beta_2)}(A-\beta_1 I)(A-\beta_1 I)(A-\beta_2 I). \end{align*} Factorising this out gives \begin{align*} A^2=k\cdot I+\lambda\cdot A+\mu\cdot(J-I-A), \end{align*} which is a characterization of $G$ being strongly regular.

Now I doubt the implication to $M=\frac{1}{n}J$. For all we know, $M$ might be a diagonal matrix with a single $1$ and otherwise only $0$'s. Does this implication hold?

## 1 Answer

One approach is to note that the rank of $(A-\beta_1I)(A-\beta_2I)$ is 1, and that its column space contains the all-ones vector. For this note that $(A-\beta_1I)(A-\beta_2I)J = (k-\beta_1)(k-\beta_2)J$, where $(k-\beta_1)(k-\beta_2)\ne0$. Hence the sum of the columns of $(A-\beta_1I)(A-\beta_2I)$ is a non-zero constant vector.