Skip to main content
1 of 3
M. Winter
  • 13.6k
  • 3
  • 29
  • 70

In a comment I said that large eigenspaces of the adjacency matrix may point to large symmetry or regularity in the graph. For example, let me explain why highly symmetric graphs have large eigenspaces (that is, large factors in their characteristic polynomial).

A symmetry $\sigma\in\def\Aut{\mathrm{Aut}}\Aut(G)$ is a permutation of the vertex set $V=\{1,...,n\}$. Let $P_\sigma\in\def\RR{\Bbb R}\RR^{n\times n}$ be the associated permutation matrix. The symmetries of a graph can be characterized using its adjacency matrix as follows: a permutation $\sigma\in\mathrm{Sym}(V)$ satisfies

$$\sigma\in\Aut(G)\quad\Longleftrightarrow\quad AP_\sigma=P_\sigma A.$$

But this means, for any eigenvalue $\theta\in\mathrm{Spec}(A)$, if $u\in\RR^n$ is a $\theta$-eigenvector, then so is $P_\sigma u\in\RR^n$ for all the $\sigma\in\Aut(G)$:

$$A(P_\sigma u)=(AP_\sigma) u = (P_\sigma A)u = P_\sigma (Au)=P_\sigma(\theta u)=\theta(P_\sigma u)$$

So the $\theta$-eigenspace contains $\mathrm{span}\{P_\sigma u\mid \sigma\in\Aut(G)\}$ which can be quite large, depending on $\Aut(G)$.

Another way to say this: the eigenspaces of $A$ are invariant subspaces w.r.t. $\Aut(G)$, and if $\Aut(G)$ has no small invariant subspaces then $A$ cannot have small eigenspaces.

M. Winter
  • 13.6k
  • 3
  • 29
  • 70