Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 12 down vote accepted

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").

share|improve this answer
    
Nice. Thanks a lot ! –  Suresh Venkat May 2 '12 at 6:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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