1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.