Show that $A^4=A^2$ for an adjacency matrix with spectral radius $\leq1$

Question

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?

Answer 1

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$.

Answer 2

Now $^$ matrix denotes the number of paths of length between vertices. Since, there exists at least one non-zero in matrix by assumption, then we can go back and forth between two vertices and hence if →∞ , then this entry will not converge to zero in the left hand side, but in the right hand side since <1 , the sequence will converge to zero, and this is contradiction. So, We only can have −1,0,1 as our eigenvalues. We see what happens in each case now which ∼ means they are similar matrices, () means its spectrum and is the minimal polynomial:

$\sigma(A) = \{1\} \implies \mu_A(x) = x - 1 = 0 \rightarrow A \sim I \implies A^4 = A^2 $ In this case graph is similar to $n$ vertices which each one has a loop.
$\sigma(A) = \{0\} \implies \mu_A(x) = x = 0 \rightarrow A \sim O \implies A^4 = A^2 $ In this case graph is $n$ disconnected vertices. $\sigma(A) = \{-1\} \implies \mu_A(x) = x + 1 \rightarrow A \sim -I \implies A^4 = A^2 $
$\sigma(A) = \{0, 1\} \implies \mu_A(x) = (x - 1)x \rightarrow A^2 = A \implies A^4 = A^2 $
$\sigma(A) = \{0, -1\} \implies \mu_A(x) = (x + 1)x \rightarrow A^2 = -A \implies A^4 = A^2 $
$\sigma(A) = \{-1, 1\} \implies \mu_A(x) = (x - I)(x + I) \rightarrow A^2 = I \implies A^4 = A^2 $
$\sigma(A) = \{-1,0,1\} \implies \mu_A(x) = (x - I)x(x + I) \rightarrow A^3 = A \implies A^4 = A^2 $
Which means that in all cases we have: $^4=^2$ .

Answer 3

By considering each connected component of $\Gamma$, we may assume that $\Gamma$ is either edgeless or connected. Hence $A$ is either zero or irreducible. If $A=0$, clearly $A^2=A^4$. Suppose $A$ is irreducible. Let $e$ be the vector of ones. Then $e^TAe\le\|e\|^2\rho(A)\le n$. Hence $A$ has at most $n$ nonzero elements. As $A$ is irreducible, each row/column contains at least one nonzero element. It follows that each row/column of $A$ has exactly one nonzero element, i.e., $A$ is a permutation matrix. Since $A$ is also irreducible and symmetric, the permutation must be a $1$-cycle or a $2$-cycle. In other words, $A$ must be equal to either $I_1$ or $R:=\pmatrix{0&1\\ 1&0}$ (and the original $A$, without the assumption of irreducibility, must be in the form of $I\oplus R\oplus\cdots R\oplus0$ up to a reindexing of rows and columns). Hence $A^2=A^4$.