Problema de Biggs teoría de grafos

Question

De Norman Biggs, Algebraicas Teoría de grafos, 2ª edición, 1993, pág. 13, ejercicio 2i:

2i. Una cota superior para el mayor autovalor. Supongamos que los autovalores de a $\Gamma$ $\lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1}$ donde $\Gamma$ $n$ vértices y $m$ bordes. A partir de 2h obtenemos $\sum \lambda_i = 0$$\sum \lambda_i^2 = 2m$. De ello se desprende que $$\lambda_0 \leq \left(\dfrac{2m\left(n-1\right)}{n}\right)^{\frac{1}{2}}.$$

He tratado de solucionar este problema, pero simplemente no puedo. La matriz de un grafo en $n$ vértices es $n\times n$ con todas las entradas $0$ o $1$, y en diagonal $0$.

Mi intento: sabemos que para dicha matriz $|\lambda_0|\leq n-1$. \begin{eqnarray*} \lambda_{0}^{2} & = & \frac{\lambda_{0}^{2}}{n}+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\ & = & \frac{\left|\lambda_{0}\right|^{2}}{n}+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\ & \leq & \left|\sum_{1\leq i}\lambda_{i}\right|\left(\frac{n-1}{n}\right)+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\ & \leq & \sum_{1\leq i}\left|\lambda_{i}\right|\left(\frac{n-1}{n}\right)+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\ & \leq & \sum_{1\leq i}\lambda_{i}^{2}\left(\frac{n-1}{n}\right)+\lambda_{0}^{2}\left(\frac{n-1}{n}\right)\\ & = & \sum\lambda_{i}^{2}\left(\frac{n-1}{n}\right)\\ & = & \frac{2m(n-1)}{n} \end{eqnarray*}

Creo que está todo ok hasta el último $\leq$. Esto sería cierto si todos los autovalores fueron enteros, pero como alguien señaló, los autovalores de las matrices no tienen que ser enteros.

Answer 1

Tenemos que mostrar que $\lambda_0 \leq \left(\dfrac{2m\left(n-1\right)}{n}\right)^{\frac{1}{2}}$. Es claramente suficiente para probar que $\left|\lambda_0\right| \leq \left(\dfrac{2m\left(n-1\right)}{n}\right)^{\frac{1}{2}}$. En otras palabras, tenemos que mostrar que $n \lambda_0^2 \leq 2m \left(n-1\right)$. En otras palabras, tenemos que mostrar que $n \lambda_0^2 \leq \left(\sum_i \lambda_i^2\right) \left(n-1\right)$ (desde $\sum_i \lambda_i^2 = 2m$). La reescritura de $\sum_i \lambda_i^2$$\lambda_0^2 + \sum_{i\geq 1} \lambda_i^2$, podemos transformar este en $n \lambda_0^2 \leq \left(\lambda_0^2 + \sum_{i\geq 1} \lambda_i^2\right) \left(n-1\right)$. En otras palabras, tenemos que demostrar que el $n \lambda_0^2 \leq \left(n-1\right) \left(\lambda_0^2 + \sum_{i\geq 1} \lambda_i^2\right)$. Al restar de $\left(n-1\right)\lambda_0^2$, esto se simplifica a $\lambda_0^2 \leq \left(n-1\right) \sum_{i\geq 1} \lambda_i^2$. Desde $0 = \sum_i \lambda_i = \lambda_0 + \sum_{i\geq 1}\lambda_i$, $\lambda_0 = - \sum_{i\geq 1}\lambda_i$ e lo $\lambda_0^2 = \left(\sum_{i\geq 1}\lambda_i\right)^2$. Por lo tanto, la desigualdad que hay que demostrar, que es, $\lambda_0^2 \leq \left(n-1\right) \sum_{i\geq 1} \lambda_i^2$, reescribe como $\left(\sum_{i\geq 1}\lambda_i\right)^2 \leq \left(n-1\right) \sum_{i\geq 1} \lambda_i^2$. Pero esto se sigue inmediatamente de la de Cauchy-Schwarz desigualdad.