# Two formulas for the minimal eigenvalue of a graph

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?

-

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