Eigenvalues of periodic lattice Laplacian?

Question

Consider the graph given by taking a rectangular lattice with $m$ rows and $n$ columns and joining each vertex to its four nearest neighbors, where vertices on the boundary are connected periodically (for example, $(1,2)$ is connected to $(1,1),(1,3),(2,2)$ and $(m,2)$). Are the exact eigenvalues of its Laplacian matrix $L$ known?

I know how to handle the problem in the 1D case. Here except for the first and last rows, the matrix is tridiagonal, with its diagonal entries being $2$ and its superdiagonal and subdiagonal entries being $-1$. (Here I am using the positive semidefinite convention for the Laplacian, as usual in graph theory but reversed from the usual for PDE). Additionally there is a $-1$ in the top right and bottom left corners. This means that we have the circulant matrix corresponding to the vector $(2,-1,0,0,\dots,-1)$, where there are $n-3$ zeros. In this case as for any circulant matrix, the eigenvectors are the columns of the discrete Fourier transform and the eigenvalues can be read off by substitution.

This suggests that the columns of an appropriate 2D Fourier transform would be the eigenvectors of our matrix here...and in fact that is correct. To be specific, under the column major ordering of the vertices, the eigenvectors of the Laplacian matrix are the columns of $F_n \otimes F_m$ where $F_n$ and $F_m$ are the discrete Fourier matrices and $\otimes$ is the Kronecker product.

Is there an easy way to read off the actual eigenvalues from this representation of the eigenvectors? In other words, I can see that we have, for example

$$\lambda_i=\frac{\sum_{j=1}^{mn} L_{1j} (F_n \otimes F_m)_{ji}}{(F_n \otimes F_m)_{1i}}$$

but does this have some simple explicit formula?

Answer 1

Yes, I believe the eigenvalues are of the form $$4 - 2 \cos \left( \frac{2 \pi j}{n} \right) - 2 \cos \left( \frac{2 \pi k}{m} \right)$$ for $1 \leq j \leq n$, and $1 \leq k \leq m$.

Let's denote your graph as $G$ and let $C_n$ be the cylic graph on $n$ vertices. Note that we can write your graph as $G = C_n \ \displaystyle \square \ C_m$ where $\displaystyle \square$ denotes the Cartesian product of graphs. In general, for graphs $G$ and $H$ with Laplacian matrices $L_G$ and $L_H$, we have that $L_{G \square H} = L_G \otimes I + I \otimes L_H$ where $\otimes$ is the Kronecker product. All eigenvectors of $L_{G \square H}$ are of the form $v_G \otimes v_H$ where $v_G$ and $v_H$ are eigenvectors of $L_G$ and $L_H$, respecitvely. Moreover, the eigenvalue associated with $v_G \otimes v_H$ is $\lambda_G + \lambda_H$ where $\lambda_G$ and $\lambda_H$ are eigenvalues of $v_G$ and $v_H$ , respectively. Thus, knowing all the eigenvalues of $L_G$ and $L_H$ will exactly give us all the eigenvalues of $L_{G \square H}$.

So to find the eigenvalues of $L_G$, we need only to find the eigenvalues of the Laplacian matrix of $C_n$. You can check that the Laplacian matrix of $C_n$ is a circulant matrix and that their eigenvalues are of a special form. In this case, using $\omega_j = \exp (\frac{2 \pi i j}{n})$, we have that the eigenvalues of $L_{C_n}$ are of the form, \begin{align} \lambda_j &= 2 - \omega_j - \omega_j^{n-1} \\ &= 2 - \exp \left(\frac{2 \pi i j}{n} \right) - \exp \left( \frac{2 \pi i j (n-1)}{n} \right) \\ &= 2 - \exp \left(\frac{2 \pi i j}{n} \right) - \exp \left( -\frac{2 \pi i j}{n} \right) \\ &= 2 - 2 \cos \left( \frac{2 \pi j}{n} \right) \end{align} Using this and the fact above, we have that the eigenvalues of $G$ are of the form $$4 - 2 \cos \left( \frac{2 \pi j}{n} \right) - 2 \cos \left( \frac{2 \pi k}{m} \right)$$ for $1 \leq j \leq n$, and $1 \leq k \leq m$, as desired. Please check my work as I could have easily made a mistake and please let me know if you'd like more explanation on any of the parts.