3
$\begingroup$

I'm starting to prove some of the major relations between graph problems and linear algebra. Take $G$ to be an undirected graph, and $A$ as its adjacency matrix. Let $\bar{d}$ be the average degree of the graph and $I$ to be the max degree of $G.$ I want to show that the largest eigenvalue $\tilde{\lambda}$ of $A$ is bounded by $$\bar{d} \leq \tilde{\lambda} \leq I.$$ I'm thinking that I should start by figuring out what to do with the lower bound. I understand that $\exists \vec{x}. Ax = \tilde{\lambda}x.$ If $\tilde{\lambda} < \bar{d},$ I would know that $Ax < \bar{d}x,$ and note that $deg(v_i) = \sum_{j=1}^n A_{i,j}.$ I'm kind of getting stuck on figuring out how to relate this to the average degree in order to find a contradiction. Any help would be greatly appreciated.

$\endgroup$
2
$\begingroup$

Hint: Since $A$ is an adjacency matrix, it is symmetric. Therefore, all of its eigenvalues are real.

For the upper bound: Observe that the sum of the entries in any row is at most $I$ (since a row has at most $I$ entries). Suppose that $v$ is an eigenvector. Let $i$ be the position where $v_i$ is largest, then $(Av)_i\leq Iv_i$ because it is a sum of at most $I$ terms, all of which are at most $v_i$.

For the upper bound: You can use the Rayleigh quotient. Consider the Rayleigh quotient with $x$ the vector of all $1$'s. Then $x\cdot x=n$, the number of vertices. On the other hand, since $Ax$ is the degree (valence) of each vertex, $x^TAx$ adds up the degrees and is equal to the sum of degrees of the vertices. Finally, the Rayleigh quotient is the sum of the degrees of the vertices divided by the number of vertices, in other words, $\overline{d}$. Since the maximum value of the Rayleigh quotient is the largest eigenvalue, $\widetilde{\lambda}\geq \overline{d}$.

If you don't like the Rayleigh quotient, you can proceed for the lower bound in the following way. Since $A$ is symmetric, it has an orthonormal eigenbasis, $\{w_1,\cdots,w_n\}$ with corresponding eigenvalues $\lambda_1,\cdots,\lambda_n$. Suppose that all the eigenvectors are less than $\overline{d}$. Now, consider the vector $x$ of all $1$'s. We can write $$ x=c_1w_1+\cdots+c_nw_n $$ Then, $$ Ax=\lambda_1c_1w_1+\cdots+\lambda_nc_nw_n. $$ Then (since this basis is orthonormal), $$ x^TAx=(c_1w_1+\cdots+c_nw_n)\cdot(\lambda_1c_1w_1+\cdots+\lambda_nc_nw_n)=\lambda_1c_1^2+\cdots+\lambda_nc_n^2. $$ By assumption, all of the $\lambda_i$'s are less than $\overline{d}$, so $$ x^TAx<\overline{d}(c_1^2+\cdots+c_n^2). $$ On the other hand (again by orthogonality) $$ x^Tx=(c_1w_1+\cdots+c_nw_n)\cdot(c_1w_1+\cdots+c_nw_n)=c_1^2+\cdots+c_n^2 $$ Therefore, $\frac{x^TAx}{x^Tx}<\overline{d}$, but we proved above that this ratio is equal to $\overline{d}$, a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.