5
$\begingroup$

Given a graph with an adjacency matrix $\bf A$, powers of this matrix give the number of walks from vertices. That is, $({\bf A}^k)_{ij}$ gives the number of walks from nodes $i$ to $j$ in $k$ steps. Is there any nice physical iterpertation for the powers of the Laplacian matrix?

1 Answers 1

6

In my opinion, it is not natural to take powers of the Laplacian in isolation. That is, the Laplacian should not be thought of as a linear operator that one is interested in iterating. There are two points of view that I know of about what the Laplacian "is":

  • It's the matrix representation of the quadratic form $\sum_{(v, w) \in E} (f(v) - f(w))^2$ where $f$ is a function on the vertices. Matrices of quadratic forms are not meant to be composed.
  • It generates a one-dimensional Lie algebra acting on the space of functions on the vertices. This perspective is relevant to the answer I gave to this math.SE question, where by using the Laplacian to define certain differential equations it becomes natural to exponentiate, rather than take powers of, the Laplacian. The powers appear in the exponential, but indirectly.
  • 0
    Thanks Qiaochu, I had read that answer before and I have seen the use of the Laplacian in the mapping of DE to graphs. The idea of L as an operator (rather then a plain matrix) seems to validate the study of it's eigenvalues more so then the adj. matrix. However, by looking at the matrix exponential as a kind of series expansion, can't one point to one of the terms and ask what they mean? You are allowed to do so in a normal series expansion of one-dimensional function (and it makes sense there), why not in this case?2011-02-11
  • 0
    @Hooked: sure, but I'm not sure this gets you anything with as direct an interpretation as the powers of the adjacency matrix.2011-02-11