Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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. –  Alejandro Aug 9 '11 at 19:37
    
Oh, I was confused as to which was $k$ and which was $u$. I think I have it right now. –  David Speyer Aug 9 '11 at 19:40

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.

share|improve this answer
    
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. –  Alejandro Aug 9 '11 at 18:33
    
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. –  Qiaochu Yuan Aug 9 '11 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.