# Relationship Between Eigenvalue and Degree

I have a question regarding Rayleigh quotient. It's well known that maximal eigenvalue can be found by

$$\lambda_{\max}(M)=\max_{x\neq 0}\frac{x^{T}Mx}{x^{T}x}.$$

Using this how to prove that $\lambda_{\max}(A)$ is placed between average degree $\frac{1}{n}\sum d_{i}$ and maximal degree $\max d_i$.

Thanks

-

For $x=\pmatrix{1&1&\ldots&1}$ we have $^txAx=\sum_{i,j}a_{i,j}=\sum_i\sum_ja_{i,j}=\sum_id_i$ and $^txx=n$ so $\lambda_{\max }(A)\geq \frac 1n\sum_id_i$.
If $\lambda$ is an eigenvalue of $A$ and $x$ an associated eigenvector, we have for all $i$: $$|\lambda x_i|=\left|\sum_{j=1}^na_{i,j}x_j\right|\leq ||x||\sum_{j=1}^na_{i,j}=||x||d_i\leq ||x||\max_i d_i$$ and since $x\neq 0$ we have $|\lambda|\leq \max_i d_i$ so $\lambda_{\max}(A)\leq \max_id_i$.
Thank you very much, but why actually this part is true $\left|\sum_{j=1}^na_{i,j}x_j\right|\leq ||x||\sum_{j=1}^na_{i,j}$? – fog Feb 9 '12 at 8:31
Yes since $|x_j|\leq ||x||$ and $a_{i,j}\geq 0$. – Davide Giraudo Feb 9 '12 at 9:58