1
$\begingroup$

For any prime number $p$ we can define a Cayley graph with integer vertices and edges:

\begin{eqnarray} V &=& \mathbb{Z}/p\mathbb{Z} \\ E &=& \{ (x, x\pm 1), (x, x \pm 2) : x \in V \} \end{eqnarray}

What is the spectrum of this graph? I think that is an easy one. Then I would like to add one edge: $$ E' = E \cup \bigg\{ \big(0\;,\; 0 + \tfrac{p+1}{2}\big) \bigg\} $$

How does the spectrum of my new graph change with respect to the old ones?

If I write out the matrix I think I get (here for $p = 5$) in general a band matrix and even a Toeplitz matrix

$$ \left[ \begin{array}{ccccc} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{array} \right]$$ Or even better we could just define the transfer operator (arithmetic taken mod $p$): $$ f(x) \stackrel{T}{\mapsto} \frac{f(x+1)+ f(x+2)+f(x-1)+f(x-2)}{4} $$ I don't immediately recall the eigenvalues but they were quite explicit.

I believe spectrum is the set of roots of unity $\lambda \in \{ = e^{2\pi i \, \frac{k}{p}}: 0 \leq k < p-1 \}$ but the eigenvectors change with the choice of generators (in our case $\pm1, \pm 2$).

These notes say I have defined $C\big(\mathbb{Z}/p\mathbb{Z}, (1,2)\big)$ but I could have used any generators. And the eigenvalues are all real.

We can predict how the eigenvalues change when we add the single edge: $\big(0, \frac{1}{2}(p-1)\big)$ e.g. using Hadamard's variation formulas how much does it move?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hi. The graph you start with before adding that extra edge is called a circulant graph. Its spectrum is well-known. For instance, say we view the vector space C^V as functions from V to C. Then for each fixed c in Z_p, we get a function $f_c (x) = e^{2 \pi i c x /p}$ (a character of the group $\mathbb{Z}_p$). These are eigenfunctions with eigenvalues $\omega ^{-2c} + \omega^{-c} + \omega^{c} + \omega^{2c},$ where $\omega = e^{2 \pi i /p}.$ Didn't think about the extra edge, but think about what happens to these characters to understand it. $\endgroup$
    – Pat Devlin
    Nov 19, 2016 at 1:31
  • $\begingroup$ And as for your post, the eigenvalues ought to be real because they're eigenvalues of a symmetric matrix. (And they are in fact real.) $\endgroup$
    – Pat Devlin
    Nov 19, 2016 at 1:33

1 Answer 1

Reset to default
1
$\begingroup$

As I understand your question, you are starting with a regular graph of degree $4$ and adding a single edge, so that the graph is no longer regular and no longer a Cayley graph. In that case, if $n=5$, your graph on vertex set $\{0,1,2,3,4\}$ has 11 edges $01, 02, 12, 13, 23, 24, 34,30, 40,41$ and $03$ and the adjacency matrix you give is incorrect.

The regular graph (as Pat Devlin says) has real eigenvalues which are sums of roots of unity. (They are all of the form $2\cos(2c\pi/p)+2\cos(4c\pi/p)$ for integers $c$, $0 \le c \le (p-1)/2$.) It is not immediately clear what the single edge does to the spectrum; yes, it will "perturb" these real numbers into other real numbers, presumably numbers close to the original sums of roots of unity. I think a question about the perturbation of eigenvalues by adding just one edge is a good one.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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