3
$\begingroup$

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

1 Answers 1

3

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

  • 0
    Yes since $|x_j|\leq ||x||$ and $a_{i,j}\geq 0$.2012-02-09