Muestre que A4=A2A4=A2A^4=A^2 para una matriz de adyacencia con radio espectral ≤1≤1\leq1

Según una estimación estándar,$\sqrt{d_{\max}}\leq\rho(A)$, dónde$d_{\max}$es el grado máximo del vértice, y$\rho$es el radio espectral (ver una demostración en Teoría de grafos espectrales, p.6 ). Desde$\rho(A)=1$su gráfico tiene vértices de grados solamente$0$o$1$, es decir, vértices desconectados o pares disjuntos de vértices conectados por una arista.

El$i,j$entrada de$A^n$es el número de caminos de longitud$n$de$i$a$j$, véase matriz de adyacencia . El único$2$-caminos y$4$-los caminos son de un vértice en un par conectado a sí mismo, viajando desde el vértice a su pareja y de regreso una y dos veces, respectivamente. Entonces$A^4=A^2$, y$A=A^3$, para esa materia. Todas las potencias impares son$A$y todos los pares son$A^2$.