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.

Hello again everybody,

I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm having difficulty justifying it. Below, I'll explain everything and state my question precisely.

Let $G=(V,E)$ be a graph and let $d_v$ denote the degree of $v\in V$. Let $T$ denote the diagonal matrix whose $(v,v)^{\text{th}}$ entry is $d_v$. The Laplacian $\mathcal{L}$ of $G$ is the matrix defined by $$ \mathcal{L}_{i,j} := \Bigg\{ \begin{array}{cc} 1 & \text{if } u=v \\ -1/\sqrt{d_v d_u} & \text{if } \{u,v\} \in E \\ 0 & \text{otherwise} \end{array} $$ The eigenvalues $\lambda_0 \leq \lambda_1 \leq \dots \leq \lambda_{n-1}$ of $\mathcal{L}$ are called the eigenvalues of $G$. Since it's not too hard to show that $0=\lambda_0$ for every graph, we call $\lambda_1$ the minimal eigenvalue of $G$.

Since $\mathcal{L}$ is Hermitian, its eigenvalues are all nonnegative reals and the minimal eigenvalue is determined by the Rayleigh-Ritz ratio (see, e.g. Theorem 4.2.2 of Horn & Johnson): $$ \lambda_1 = \min \frac{\langle g,\mathcal{L}g \rangle}{\langle g,g\rangle} $$ Here the minimum is taken over all $g : V\rightarrow \mathbb{R}$ not identically $0$, which we think of as length-#$V$ real vectors. With some algebraic manipulation that ratio becomes $$ \lambda_1 = \inf \frac{\sum_{\{u,v\}\in E} (f(u)-f(v))^2}{\sum_v f(v)^2d_v} $$ where $g=T^{-1/2} f$ and the infimum is taken over all functions $f$ such that $f \bot T1$ where $1$ is the all-$1$ vector.

That formula makes sense, I think. However, later (in the proof of theorem 2.2) she states that $$ \lambda_1 = \frac{\sum_{v \in V_+} f(v) \sum_{\{u,v\}\in E_+} (f(v)-f(u))}{\sum_{v\in V_+} f^2(v) d_v} $$ where $V_+ := \{ v : f(v) \geq 0\}$ and $E_+ := \{ \{u,v\} \in E : u \text { or } v \in V_+\}$.

I can't understand why these two formulas for $\lambda_1$ are equivalent. Chung's silence on this point may be because the equivalence is obvious. But could someone shed light on this for me?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

As I understand it:

Let $f$ be chosen to achieve the infimum, and let $h(v)$ equal $\sum_u f(v)-f(u)$, where the sum is taken over all $u$ adjacent to $v$. The expression you wrote for $\lambda_1$ coming "with some algebraic manipulation" can be expanded out as : $$ \lambda_1= \frac{\sum_v f(v) h(v)}{\sum_v f(v)^2 d_v}$$

The key fact that is being used by Chung here is that not only is the whole fraction equal to $\lambda_1$, but it is also equal to $\lambda_1$ "term by term", in the sense that for every $v$ with $f(v) \neq 0$ we have $$\lambda_1=\frac{f(v)h(v)}{f(v)^2 d_v}=\frac{h(v)}{d_v f(v)}.$$

This is stated as Lemma 1.10 in the book, where it is proven using a variational argument. From this, it follows that we get the same ratio summing over any subset of the vertices, $$\lambda_1 = \frac{\sum_{v \in S} f(v) h(v)}{\sum_{v \in S} f(v)^2 d_v}.$$

The second form you had up there comes from taking $S=V_+.$

share|improve this answer
    
Thanks for this helpful answer! –  Dimitrije Kostic Dec 7 '11 at 18:05
add comment

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.