2

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?

MR_BD
  • 5,942

1 Answers1

4

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$.

Chris Godsil
  • 13,703
  • Does not it mean that $dim(ker)=1$? – MR_BD Aug 28 '18 at 17:45
  • 1
    @Leila: what I've proved is that, if $\ker(S)$ is non-trivial, it has dimension 1. The Seidel matrix for $K_n$ is invertible. – Chris Godsil Aug 28 '18 at 19:36
  • nice argument. Do you mean perhaps that $-1/2$ cannot be an eigenvalue of $A$? I will try to find a reference for this fact you are referring to. – Malkoun Aug 24 '19 at 18:37
  • I found a reference to that fact here: https://math.stackexchange.com/questions/2936232/showing-that-every-rational-eigenvalue-of-a-graph-is-integral This may be useful to the readers. Thank you. – Malkoun Aug 24 '19 at 18:57