1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Feb 2, 2014 at 13:39

1 Answer 1

3
$\begingroup$

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

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