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
    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
    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