Skip to main content
5 of 7
Tried to improve presentation...
ARG
  • 4.4k
  • 1
  • 25
  • 46

There is no generating set for which this is possible (actually this is true for any graph with an infinite connected component).

Remark: There are 2 conventions for the Laplacian with opposite sign, so $\Delta = -L$ has positive spectrum (in $\ell^2$) and $L$ has negative spectrum.

Let $I$ be the identity. Let $P$ be the random walk operator, $\Delta = I-P$ so $P = I+L$, or, more simply $P = \displaystyle \frac{1}{|S|} \sum_{g \in S} g$.

Denote by $P^i$ the $i^\text{th}$ iterate of $P$ (for example: $P^2 = P P$) and $P^0 = I$)

Let $g_n = \displaystyle \sum_{i=0}^n P^n \delta_x$ where $\delta_x$ is a Dirac mass at some vertex $x$. Since $P^i \delta_x$ is the probability distribution of the random walk at time $i$, $\|P^i\delta_x\|_{\ell^1} =1$. (In fact, $P$ preserves the $\ell^1$-norm of positive fucntions.) Next, since all the $P^i\delta_x$ are positive functions, their norm add up in $\ell^1$: hence $\| g_n\|_{\ell^1}= n+1$

On the other hand, $L = P-I$ and so $$ L g_n = P\bigg( \sum_{i=0}^n P^n \delta_x\bigg) - \bigg( \sum_{i=0}^n P^n \delta_x\bigg) = P^{n+1} \delta_x -\delta_x $$ So $\| L g_n\|_{\ell^1} \leq \|\delta_x\|_{\ell^1} + \| P^{n+1} \delta_x\|_{\ell^1} = 2$ by the triangle inequality.

This shows that $\displaystyle \frac{ \|L g_n\|_{\ell^1}}{\|g_n\|_{\ell^1}} \leq \frac{2}{n+1}$ which obviously tends to 0. So 0 is in the spectrum and the Laplacian cannot be inverted $\ell^1$.

Note the argument is true in any graph (without finite connected components).

Also the image of the Laplacian is not dense (it is weak$^*$ dense as the sequence $g_n$ above shows). It's easy to check that its image lies in $\ell^1_0X = \lbrace f \in \ell^1X \mid \sum_{x \in X} f(x) =0 \rbrace$. One can further check that $\overline{\mathrm{Im} \Delta} = \ell^1_0 X$ if and only if the graph has no non-constant bounded harmonic functions. Non-amenable groups always have non-constant bounded harmonic functions so that the closure of the image of $\Delta$ is strict subspace of $\ell^1_0 X$.

ARG
  • 4.4k
  • 1
  • 25
  • 46