Let $\Gamma$ be a finite, undirected graph. Let $A=(a_{ij})$ be its adjacency matrix (that is $a_{ij}=$number of edges from vertex $v_i$ to vertex $v_j$) and thus $A$ is symmetric. Show that if the spectral radius of $A$ is less than or equal to $1$, then $A^4=A^2$.
My try: Since $A$ is symmetric, eigenvectors $\{v_i\}_{i=1}^n$of $A$ is a basis. To show $A^4=A^2$, we only need to show that for any $i,j$,
$$
(A^4v_i,v_j)=(A^2v_i,v_j).
$$
This is equivalent to
$$
\lambda_i^4(v_i,v_j)=\lambda_i^2(v_i,v_j).
$$
If $i=j$, then we should have
$$\lambda_i^4=\lambda_i^2.$$ But why this holds?
Best Answer
According to a standard estimate, $\sqrt{d_{\max}}\leq\rho(A)$, where $d_{\max}$ is the maximal vertex degree, and $\rho$ is the spectral radius (see a proof in Spectral graph theory, p.6). Since $\rho(A)=1$ your graph has vertices of degrees only $0$ or $1$, i.e. disconnected vertices or disjoint pairs of vertices connected by an edge.
The $i,j$ entry of $A^n$ is the number of paths of length $n$ from $i$ to $j$, see adjacency matrix. The only $2$-paths and $4$-paths are from a vertex in a connected pair to itself, traveling from the vertex to its mate and back once and twice, respectively. So $A^4=A^2$, and $A=A^3$, for that matter. All odd powers are $A$ and all even ones are $A^2$.