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?

  • $\begingroup$ Put the 1D analog in your question to see how much you can repeat the same process. $\endgroup$ – AHusain Jun 16 '16 at 21:37
  • $\begingroup$ @AHusain Done. Does it help? $\endgroup$ – Ian Jun 16 '16 at 22:18
  • $\begingroup$ So you have essentially answered your own question now. You have a guess for the eigenvectors and now you just check their eigenvalues. $\endgroup$ – AHusain Jun 16 '16 at 23:01
  • $\begingroup$ @AHusain You are right, I have done most of the problem. But is there any chance of a simple explicit formula for the eigenvalues? The above is a formula in terms of the entries, but I am not especially comfortable with the Kronecker product so I am not so sure if there is a simple formula for the five relevant entries of $(F_n \otimes F_m)$ (for a given $i$). $\endgroup$ – Ian Jun 16 '16 at 23:07

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.

  • $\begingroup$ Looks good. I think in your final simplification you made a simple mistake: you should have $\lambda_{j,k}(L_{G \square H})=\lambda_j(L_G)+\lambda_k(L_H)=4-\omega_n^j-\omega_n^{j(n-1)}-\omega_m^k-\omega_m^{k(m-1)}$, where $\omega_n=\exp(2 \pi i/n)$. Also these can be simplified to be expressed in terms of cosine: since $\omega_n^n=\omega_m^m=1$ you have $4-2\cos(2 \pi j/n)-2\cos(2 \pi k/m)$. $\endgroup$ – Ian Jun 17 '16 at 0:54
  • $\begingroup$ Anyway, with this correction the result matches up with numerical tests including with a case of $m \neq n$. So once you make this modification I will accept. Thanks for your help. Also thanks for giving your help in a "generalizable" form (i.e. it is clear how to extend this to more than two dimensions). $\endgroup$ – Ian Jun 17 '16 at 0:59
  • $\begingroup$ Sure thing - glad I could help! It looks like we both had the same answer for the eigenvalues but different definitions for $\omega_k$, which led to the confusion. I added a bit of working out the eigenvalue at the end, along with your nice simplification! $\endgroup$ – Chris Harshaw Jun 17 '16 at 1:16
  • $\begingroup$ You still haven't adjusted the denominators to be $m$, which you do need to do in some places. (That is why I changed the notation, I needed the denominator and the exponent to both be variables.) $\endgroup$ – Ian Jun 17 '16 at 1:17
  • $\begingroup$ whoops! That copy and paste will get you every time :) thanks for pointing that out $\endgroup$ – Chris Harshaw Jun 17 '16 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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