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.

We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem? How do we know that this works in reality?Is there any proof of that sort?

share|improve this question
1  
Is this true? $K_{4,1}$ and $C_4 \cup K_1$ are isospectral, but have a different number of components. See here. –  draks ... Apr 5 '12 at 13:42
1  
user997704: The multiplicity of the eigenvalue zero is the number of connected components. I think the intuition is just that it's not hard to see what the corresponding eigenvectors are! $$\phantom{ asdf}$$ @drask: They're isospectral with respect to the adjacency matrix, not the Laplacian matrix. –  Cam McLeman Apr 5 '12 at 14:24
    
Well I know it works in reality but i'm not getting its intuition anyone can please suggest introductory book on spectral graph theory? –  user997704 Apr 6 '12 at 9:44

1 Answer 1

I'm a little confused by your series of questions. If we "know" something, as in your first sentence, that by definition means we know it works "in reality," and also means we have a proof of that result.

In any case, the key step in the intuition is understanding how the Laplacian matrix acts on a graph, which is probably too long to fully develop here. Here's the basics: Suppose $G$ is a graph on $n$ vertices, which we arbitrarily label $1,2,\ldots,n$. Now imagine an arbitrary $n$-vector $w$ as being an assignment of a weight to each vertex, with $w_i$ the weight on the $i$-th vertex. This perspective makes it easy to visualize the action of the Laplacian matrix on the graph in terms of moving weights from one vertex to another. Seriously, pick a small graph $G$, a vector/weight-assignment $w$, and see if you can predict what will happen to the weights once you hit that vector with the Laplacian matrix $L$. (In short, the new weight on a vertex is the degree of the vertex minus the sum of the previous weights of all adjacent vertices).

Once you've got that down, eigenvectors become much less mysterious -- they're just weight assignments $w$ such that after you do the weight-transporting procedure described above, you get a new weight assignment $\lambda w$ in which each weight got scaled by the same factor $\lambda$. In particular, an eigenvector corresponding to the eigenvalue $\lambda=0$ is just a weight assignment such that the new weights (i.e., degree minus sum of incoming weights) is zero on each vertex.

If your graph has multiple components, here's a trivial such weight-assignment: Stick a 1 on every vertex of a given connected component, and zero everywhere else. Repeat for each of the $n$ connected components and you've got an eigenbasis for the eigenvalue zero.

share|improve this answer

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.