# Eigenstructure of discrete Laplacian on uniform grid

The discrete Laplacian of a graph is the matrix $L = D - A$ where $D$ is a diagonal matrix with $d_{ii}$ being the degree of $v_i$, and $A$ is the usual adjacency matrix.

Is there anything known about the eigenstructure of the discrete Laplacian of the uniform $d$-dimensional grid (it can be thought of as an infinite graph) ?

I believe that in the limit this becomes the continuous Laplacian (the Laplace-Beltrami operator on $R^d$) but I don't know what the eigenpairs of that operator are either and would be interested in an answer to that.

-

It's completely known. I prefer to define the Laplacian as $A - D$. This more closely imitates the behavior of the continuous Laplacian, which is negative-semidefinite.

Let $G, H$ be two locally finite graphs with Laplacians $L_G, L_H$. The Cartesian product $G \Box H$ is again locally finite and has Laplacian the Kronecker sum $L_G \otimes I + I \otimes L_H$, which has eigenvectors of the form $v \otimes w$ where $v$ is an eigenvector of $L_G$ and $w$ is an eigenvector of $L_H$. If $\lambda_v, \lambda_w$ are the corresponding eigenvalues, then the eigenvalue associated to $v \otimes w$ is $\lambda_v + \lambda_w$. Observe now that the $d$-dimensional grid is just the Cartesian product of $d$ copies of the $1$-dimensional grid, so it suffices to answer the question for $d = 1$. (An analogous statement is true in the continuous case.)

When $d = 1$, an eigenvector of the Laplacian with eigenvalue $\lambda$ is a sequence $a_n, n \in \mathbb{Z}$ such that $$a_{n+1} - 2a_n + a_{n-1} = \lambda a_n.$$

If $\lambda = 0$ then these are precisely the linear sequences $a_n = an + b$, and if $\lambda = -4$ then these are precisely the sequences of the form $$a_n = (an + b)(-1)^n + cn + d.$$

Otherwise, the characteristic polynomial $t^2 - (2 + \lambda) t + 1$ is separable, so we get sequences of the form $$a_n = a r^n + b s^n$$

where $r, s$ are the two roots of the characteristic polynomial, so $$r, s = \frac{2 + \lambda \pm \sqrt{\lambda^2 + 4 \lambda}}{2}.$$

It is more typical, I think, to restrict attention to the bounded eigenvectors. We only get these if $r, s$ have absolute value at most $1$, which requires $2 + \lambda = 2 \cos \theta$ for some $\theta$. In this case we have $r, s = e^{ \pm i \theta}$, hence $$a_n = a \cos n \theta + b \sin n \theta.$$

In the continuous case we want functions $f(x), x \in \mathbb{R}$ such that $$f''(x) = \lambda f(x).$$

If $\lambda = 0$ then these are the linear functions $f(x) = ax + b$. If $\lambda < 0$ then setting $\lambda = - \omega^2$ we get the functions $$f(x) = a \cos \omega x + b \sin \omega x.$$

If $\lambda > 0$ then we get the functions $$f(x) = a e^{\sqrt{\lambda} x} + b e^{-\sqrt{\lambda} x}.$$

Again if we restrict our attention to bounded eigenvectors we only get the periodic ones. To get eigenvectors in higher dimensions we take the Cartesian product: for example in two dimensions we get eigenvectors of the form $$f(x, y) = a \cos \omega_1 x \cos \omega_2 y + b \cos \omega_1 x \sin \omega_2 y + ....$$

A concise way to write these down is to introduce the standard inner product on $\mathbb{R}^n$: then $f(\mathbf{x}) = e^{i \langle \mathbf{v}, \mathbf{x} \rangle }$ is an eigenvector with eigenvalue $- \langle \mathbf{v}, \mathbf{v} \rangle$. I am reasonably certain that these are all the "nice" eigenvectors (how hard this is to prove depends on what you mean by "nice").

-
Nice. Thanks a lot ! – Suresh Venkat May 2 '12 at 6:34