Radio espectral de un gráfico

Por el teorema de Perron-Frobenius :

• Si$A$es un$n\times n$matriz real con entradas estrictamente positivas , tiene un valor propio real positivo$r$tal que cualquier otro valor propio$\lambda$satisface$|\lambda| < r$. También hay algunas otras cosas sobre el vector propio asociado a$r$que no necesitas aquí.
• Si$A$es un$n \times n$matriz real con entradas no negativas , entonces solo podemos decir$|\lambda| \le r$para otros valores propios. el valor propio$r$podría aparecer varias veces, podríamos tener valores propios complejos con valor absoluto$r$, Etcétera.

El segundo caso se aplica en particular a las matrices de adyacencia de grafos. (Además, estos son simétricos, por lo que todos sus valores propios son reales). Entonces el radio espectral es$r$, y es tanto el valor propio más grande como el valor absoluto más grande de un valor propio: sus definiciones son equivalentes.

Como beneficio adicional, si el gráfico está conectado, entonces la matriz de adyacencia es una matriz irreducible, y el teorema de Perron-Frobenius además nos dice que el valor propio$r$es simple (solo aparece una vez, tanto algebraicamente como geométricamente). Pero no necesitamos que la gráfica esté conectada para que las definiciones sean equivalentes.

Si el valor propio de la norma más grande fuera negativo, entonces$\sum\limits_{i=1}^n \lambda_i^k$sería negativo para valores impares grandes de$k$.

Sin embargo sabemos que$\sum\limits_{i=1}^n \lambda_i^k = \operatorname{Tr}(A^k)$, y esta última cantidad es no negativa como la diagonal de$A^k$es claramente no negativo. Concluimos que no puede haber un valor propio negativo con una norma estrictamente mayor que todos los demás valores propios.