Rank of Seidel adjacency matrix?

Question

Seidel adjacency matrix of a graph, $S=[s_{i,j}]_{n\times n}$, with $V=\{1,2,\ldots,n\}$ is defined as follows:

$$s_{ij}=\begin{cases} 1 \quad i\nsim j , i\neq j \\-1 \quad i\sim j \\0\quad i=j \end{cases}$$

I want to prove that $rk(S)\geqslant n-1$.

I 've found a special case when equality holds. Consider a $d-$regular graph $G$ with $n=2k+1$. But I'm not sure if there is another family for which equality holds or not.

Is there any help?

Answer 1

The key point is that $\frac12$ cannot be an eigenvalue of $A$ (because the eigenvalues of $A$ are algebraic integers). In particular, $2A+I$ is invertible.

We have $S=2A+I-J$ and so if $Sx=0$, then $(2A+I)x=Jx$. If $Jx=0$, then $x$ is an eigenvector for $2A=I$ and $\frac12$ is an eigenvalue of $A$.

Now scale $x$ so that its entries sum to 1, whence it follows that $Jx = z$, where $z$ is the all-ones vector. Then we have \[ x = (2A+I)^{-1}z. \] It follows that $\dim(\ker(2A+I-J))\le1$.