0
$\begingroup$

The eigenvectors of the Laplacian of a Ring graph with $n$ vertices are:

$x_k(u) = \sin(2\pi ku/n)$ and

$y_k(u) = \cos(2\pi ku/n)$

for $1\leq k \leq n/2$. The explanation according to Spielman's lecture notes is:

The best way to see that $x_k$ and $y_k$ are eigenvectors is to plot the graph on the circle using these vectors as coordinates. That they are eigenvectors is geometrically obvious.

Why is this "geometrically obvious"? I can see that embedding the graph into the plane using $x_k$ and $y_k$ as coordinates places the vertices uniformly over the unit circle. What I cannot understand is why the eigenvectors of the Laplacian must produce this embedding.

2 Answers 2

5

I think the following is what Spielman is referring to. Let $z(u)$ be the point $(x_k(u), y_k(u))$ in $\mathbb{R}^2$. Consider the vector $z(u-1) - 2 z(u) + z(u+1)$. By the reflection symmetry of the picture, it is parallel to $z(u)$; let $$z(u-1) - 2 z(u) + z(u+1) = \lambda z(u)$$ for some scalar $\lambda$. Moreover, by rotational symmetry, the constant $\lambda$ is independent of $u$.

Taking the first coordinates of this equation, $$x_{k}(u-1) - 2 x_k(u) + x_{k}(u+1) = \lambda x_k(u)$$ This exactly says that the vector $x_k$ is an eigenvector for $D$, with eigenvalue $\lambda$. Looking at the second coordinate, we get the same conclusion for $y_k$.

  • 0
    Thanks! I think I get the idea. One question: When you say $z_k$ what you mean is $z_k(u)$? $x_k$ and $y_k$ are vectors of length $n$, so $(x_k,y_k)$ is not a point. $(x_k(u),y_k(u))$ is a point though.2011-08-09
  • 0
    Oh, I was confused as to which was $k$ and which was $u$. I think I have it right now.2011-08-09
2

The ring graph with $n$ vertices has a dihedral symmetry by $D_n$, so the action of $D_n$ commutes with the Laplacian. It follows that the eigenspaces of the Laplacian divide up into irreducible representations of $D_n$, which include direct sums of irreducible representations of $C_n$ and their duals. Laplacian eigenvectors in these representations are given by sinusoids. The whole picture behaves exactly the way you'd expect in the $n \to \infty$ limit.

I'm not sure exactly what Spielman is referring to, though. There is a connection between nice embeddings of graphs into $\mathbb{R}^n$ and eigenvectors but I wasn't aware that it goes in the direction that Spielman claims.

  • 0
    At least I am not the only one confused by this being "geometrically obvious". I think that the eigenvectors are sinusoids can also be explained by the fact that the Laplacian of a Ring graph is a circulant matrix, and it follows that the eigenvectors are the "roots of unity". But I don't see any geometric intuition behind this explanation.2011-08-09
  • 0
    Because the embedding exhibits $D_n$ as linear operators, the vectors defining it form an irreducible subrepresentation of $D_n$, and by the above argument any irreducible subrepresentation is contained in an eigenspace of the Laplacian. Maybe Spielman has something more directly geometric in mind, though.2011-08-09