8
$\begingroup$

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?

1 Answers 1

2

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