28 1. Random Walk and Discrete Heat Equation

where the supremum is over all functions f on A, and ·, · denotes

the inner product

f, g =

x∈A

f(x) g(x).

Proof. If φ is an eigenvector with eigenvalue λ1, then Qφ = λ1φ and

setting f = φ shows that the supremum is at least as large as λ1.

Conversely, there is an orthogonal basis of eigenfunctions φ1,...,φN

and we can write any f as

f =

N

j=1

cj φj.

Then

Qf, f = Q

N

j=1

cj φj,

N

j=1

cj φj

=

N

j=1

cjQφj ,

N

j=1

cj φj

=

j=1

cj

2

λj φj,φj

≤ λ1

j=1

cj

2

φj,φj = λ1 f, f .

The reader should check that the computation above uses the orthog-

onality of the eigenfunctions and also the fact that φj,φj ≥ 0.

Using this variational formulation, we can see that the eigenfunc-

tion for λ1 can be chosen so that φ1(x) ≥ 0 for each x (since if φ1 took

on both positive and negative values, we would have Q|φ1|, |φ1|

φ1,φ1 ). The eigenfunction is unique, i.e., λ2 λ1, provided we

put an additional condition on A. We say that a subset A on Zd is

connected if any two points in A are connected by a nearest neighbor

path that stays entirely in A. Equivalently, A is connected if for each

x, y ∈ A there exists an n such that pn(x, y; A) 0. We leave it as

Exercise 1.23 to show that this implies that λ1 λ2.

Before stating the final theorem, we need to discuss some par-

ity (even/odd) issues. If x = (x1,...,xd) ∈

Zd

we let par(x) =