# Calculating eigenvalue gap of a torus graph

Consider a two-dimensional grid with wrap-around edges (a doughnut-shaped graph). I need to calculate the second-largest eigenvalue of the adjacency matrix. Is there a faster way of computing it for such a special graph than a general method such as the "eigs" function in MATLAB?

• Note that your phrasing reads like "How do I do that in Matlab?" which would be offtopic here. You might want to avoid that in the future. Feb 2, 2014 at 13:39

Suppose that the torus is $n\times n$. Let $\omega = e^{2\pi i/n}$ be a primitive $n$th root of unity, and let $v_{\alpha,\beta}$ be the $n\times n$ vector given by $v_{\alpha,\beta}(i,j) = \omega^{i\alpha+j\beta}$. Using $A$ for the adjacency matrix of the torus (indexed by pairs $(i,j) \in \mathbb{Z}_n$), \begin{align*} (Av_{\alpha,\beta})(i,j) &= v_{\alpha,\beta}(i+1,j) + v_{\alpha,\beta}(i-1,j) + v_{\alpha,\beta}(i,j+1) + v_{\alpha,\beta}(i,j-1) \\ &= v_{\alpha,\beta}(i,j) (\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}). \end{align*} In other words, $v_{\alpha,\beta}$ is an eigenvector with eigenvalue $\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}$. It is not hard to check that the $n^2$ vectors $v_{\alpha,\beta}$ are linearly independent, and so they form a basis of eigenvectors for $A$. The eigenvalues are $$\lambda_{\alpha,\beta} = \omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta} = 2\left(\cos \frac{\alpha2\pi}{n} + \cos \frac{\beta2\pi}{n}\right).$$ For $\alpha \in \{0,\ldots,n-1\}$, the function $\cos \frac{\alpha2\pi}{n}$ reaches its maximum $1$ at $\alpha = 0$, and otherwise its second largest value is attained at $\alpha=1$ and $\alpha=n-1$. Therefore the second-largest eigenvalue is $2 + 2\cos \frac{2\pi}{n}$. More generally, for a $d$-dimensional grid, the second-largest eigenvalue is $2(d-1) + 2\cos \frac{2\pi}{n}$, and the eigenvalue gap is $2-2\cos \frac{2\pi}{n} = \Theta(\frac{1}{n^2})$.
More generally, the $n\times n$ torus is the cartesian product of the $n$-cycle with itself. It is well-known that if $G$ has eigenvalues $\lambda_i$ and $H$ has eigenvalues $\mu_j$ then the eigenvalues of the cartesian product of $G$ and $H$ are $\lambda_i + \mu_j$ (the proof follows the computation above, replacing $\omega^{i\alpha}$ with an arbitrary eigenvector of $G$, and $\omega^{j\beta}$ with an arbitrary eigenvector of $H$). It follows that the eigenvalue gap of the product is the minimum between the eigenvalue gaps of $G$ and $H$.