2
$\begingroup$

Take a periodic one-dimensional lattice of size $N$ with $2k$ nearest neighborers. That is, vertex $i$ is connected to $i+1,i+2,...,i+k$ and $i-1,i-2,...i-k$ (with the understanding that the indices are modulo $N$). Call the associated adjacency matrix $A_k$, and consider the limit of large $N$.

If I'm not mistaken, the eigenvalue spectrum for $A_1$ can be well approximated by a cosine wave with amplitude $2$ and period $2N$.

Main Question

Why does the spectra for $A_2$ have a 'kink'?

Side Questions

Why does the kink in $A_2$ appear at a magnitude of zero?

Why do the kinks in $A_3$ appear touch exactly when the curve hits the spectra for $A_2$ (it looks that after a certain point, one graph is supported by the other).

In general, the spectra for $A_k$ seem to have $k-1$ kinks, can this be shown?

I've included an example of the spectra for $N=2^{11}$

  • 0
    @joriki - you're correct, there are $2k$ nearest neighbors (mistyped)2011-04-21

1 Answers 1

2

The eigenvectors of such a circulant matrix are $(v_j)_m=\exp(2\pi \mathrm i jm/N)$. The corresponding eigenvalue spectra are the linear combinations of exponentials corresponding to a row of the matrix. For your $A_k$, these combinations are

$\lambda_{kl}=\sum_{j=1}^k \cos(2\pi\mathrm i jl)\;,$

Here are plots of the spectra for $A_2$ and for $A_3$. If you reorder them in descending order, as it seems that you have, then once your sort hits a maximum, you suddenly have three branches instead of just one, and also the eigenvalues are more dense around the maxima; that accounts for the kinks. The second, "inverse" kink for $A_3$ is caused by the minimum in the spectrum.