Prove that a strongly regular graph is imprimitive $\iff$ $0$ or $-1$ is an eigenvalue.

375 Views Asked by At

First, let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form: $$k, \qquad \theta=\dfrac{(a-c)+ \sqrt{(a-c)^2+4(k-c)}}{2}, \qquad \tau =\dfrac{(a-c)- \sqrt{(a-c)^2+4(k-c)}}{2}.$$

So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above: $$0= \dfrac{(a-c)\pm \sqrt{(a-c)^2+4(k-c)}}{2} \implies c=k,$$ and so we have $0<c\not<k$, which implies that $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have $$-1=\dfrac{(a-c)\pm \sqrt{(a-c)^2+4(k-c)}}{2} \implies a=k-1.$$

Question 1: I know that since $X$ is a SRG with parameters $(n,k,a,c)$, then $\overline{X}$ is a SRG with parameters $(n,n-k-1,n-2-2k+c,n-2k+a)$. So if a substitute $a=k-1$ into the last parameter of $\overline{X}$, I get $n-k-1$. Can I say that since $0<c<k$ for $X$ implies primitive, then $0<n-k-1\not<n-k-1$ implies that $X$ must be imprimitive?

Question 2: I don't know how to show the converse. That is, if I suppose that $X$ is imprimitive, how do I show that $0$ or $-1$ must be an eigenvalue?

1

There are 1 best solutions below

0
On BEST ANSWER

I think I've solved the question. In case someone else is interested in this question, I've included my solution below:

Let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form: $$k, \qquad \theta=\dfrac{(a-c)+ \sqrt{(a-c)^2+4(k-c)}}{2}, \qquad \tau =\dfrac{(a-c)- \sqrt{(a-c)^2+4(k-c)}}{2}.$$

So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above: $$0= \dfrac{(a-c)\pm \sqrt{(a-c)^2+4(k-c)}}{2} \implies c=k,$$ and so we have $0<c\not<k$; therefore, $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have $$-1=\dfrac{(a-c)\pm \sqrt{(a-c)^2+4(k-c)}}{2} \implies a=k-1.$$

So then for $\overline{X}$ we have $0<n-k-1 \not< n-k-1$, and so $X$ is imprimitive.

Conversely, suppose that $X$ is imprimitive. Then either $X$ or $\overline{X}$ is disconnected. If $X$ is disconnected, then $c=0$ for $X$, which implies that within any connected component of $X$, no two pair of non-adjacent vertices have a common neighbour. Hence, $X=\cup K_n$. Let $A(K_n)$ be the adjacency matrix for $K_n$. Then $A(K_n)=J-I$, where $J$ is the all-ones matrix and $I$ is the identity matrix. Since $J$ has spectrum $n$ and $0^{n-1}$ and $I$ has spectrum $1^n$ (and $IJ=JI$), it follows that $K_n$ has spectrum $(n-1)^1$ and $(-1)^{n-1}$ and so $-1$ is an eigenvalue of $X$. Similarly, if $\overline{X}$ is disconnected, then it follows that $X=\cup\overline{K}_n$, where the spectrum of $A(\overline{K}_n)=J-I-A(K_n)$ is $0^n$; hence, $0$ is an eigenvalue of $X$.

Therefore, if $X$ is imprimitive, then $-1$ or $0$ is an eigenvalue of $X$.