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.

I am very curious about the proof of Algebraic connectivity

Algebraic connectivity:

The algebraic connectivity of a graph $G$ is the second-smallest eigenvalue of the Laplacian matrix of $G$. This eigenvalue is greater than $0$ if and only if $G$ is a connected graph.This is a corollary to the fact that the number of times $0$ appears as an eigenvalue in the Laplacian is the number of connected components in the graph.

For details : Algebraic connectivity on Wikipedia.

I found this claims very interesting, how exactly the second smallest eigenvalue can be the sign of connectivity of the graph.

Following fact not less interesting,

Denote eigenvalues by $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$, then $\lambda_1=0$.

So far I didn't the proof of Algebraic connectivity. If you have a link, I will appreciate publishing it.

Thanks!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Let $G = (V, E)$ be a finite graph and let $\Delta$ denote its Laplacian (here we take the convention that the Laplacian is positive semidefinite). For simplicity name the vertices $1, 2, ... n$. Then $\Delta$ is the matrix associated to the quadratic form $$q(x_1, ... x_n) = \sum_{(i, j) \in E} (x_i - x_j)^2$$

which one might call the Dirichlet energy. Recall that, for an appropriate change of variables, such a quadratic form can be written as $$q(z_1, ... z_n) = \sum_i \lambda_i z_i^2$$

where $\lambda_i$ are the eigenvalues of $\Delta$. Thus to determine the multiplicity of the zero eigenvalue it suffices to determine when $q$ can be zero. But from the first expression it should be clear that $q = 0$ if and only if $x_i = x_j$ whenever $(i, j) \in E$; that is, whenever $(x_1, ... x_n)$ determines a function $$x : V \to \mathbb{R}$$

which is constant on each connected component of $G$. The dimension of this space of functions is clearly the number of connected components of $G$, and the conclusion follows.

share|improve this answer
    
Thanks, quadratic form was easy to show that it works on edge. But substitution to $z$ I can't get. Could you please elaborate a little bit. And why eigenvalues shows up in the next formula –  com Dec 11 '11 at 20:56
    
@com: in vector notation, we can write the quadratic form as $\langle v, \Delta v \rangle$. By the spectral theorem, $\Delta$ has an orthonormal basis $v_1, ... v_n$ with eigenvalues $\lambda_1, ... \lambda_n$, and relative to this basis writing $v = \sum z_i v_i$ we get the desired representation. –  Qiaochu Yuan Dec 11 '11 at 21:04

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.