Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the characteristic polynomial of $A_G$. In some graphs that came up in my work, the adjacency polynomials $P_G(X)$ have a lot of factors in $\mathbb Z[X]$, many of them repeated factors. So my questions are:
-
Is it common for the adjacency polynomial of a regular graph to be highly factorizable in $\mathbb Z[X]$, and to have many repeated factors?
-
If not, what are the graph-theoretic consequences of having many small-degree factors?
-
If not, what are the graph-theoretic consequences of having factors appearing to power greater than 1?
To give an idea of the numbers involved, one example was a connected 3-regular graph with 64 vertices, and
$$
P_G(X) =
(x – 3)x^{3}(x + 1)^{3}(x^2 – 3 x + 1)^{3}(x^2 – x – 3)^{3}(x^2 – x – 1)^{6}
(x^2 + x – 3)^{3}(x^3 – 3 x^2 – x + 4)^{2}(x^3 – 4 x + 1)
(x^6 – x^5 – 11 x^4 + 9 x^3 + 31 x^2 – 19 x – 8)^{3}
$$
I've looked at a couple of references and tried a Google search, but didn't find anything relevant.
Best Answer
Expanding on Richard's comment: let me rename your graph to $S$ and consider the adjacency matrix $A$ abstractly as a linear operator acting on the free vector space $\mathbb{C}[S]$ on (the vertices of) $S$, and let $G$ be its automorphism group (this is why I wanted a new name). Then $\mathbb{C}[S]$ is a completely reducible representation of $G$ and $A$ is an endomorphism of this representation. Hence if we write
$$\mathbb{C}[S] \cong \bigoplus_i n_i V_i$$
where $V_i$ are the irreducibles, then $A$ is an element of the endomorphism algebra
$$\text{End}_G(\mathbb{C}[S]) \cong \prod_i M_{n_i}(\mathbb{C}).$$
This means more explicitly that $A$ is conjugate over $\mathbb{C}$ to a block diagonal matrix with a block for each isotypic component (hence its characteristic polynomial factors accordingly). In the nicest possible case the decomposition above is multiplicity-free in which case the endomorphism algebra is a product of copies of $\mathbb{C}$ and we just have that $A$ must act by a scalar $\lambda_i$ on each $V_i$ that occurs in the decomposition, which contributes a multiplicity of $\dim V_i$ to $\lambda_i$ as a root of the characteristic polynomial and hence, over $\mathbb{Q}$, contributes a multiplicity of $\dim V_i$ to the minimal polynomial of $\lambda_i$ as a factor of the characteristic polynomial.
(I think the result of this analysis comes out the same if you work over $\mathbb{Q}$ from the beginning but it's more annoying to describe.)
I work through a few examples of this in my old blog post The Schrodinger equation on a finite graph, where I was trying to understand via a toy model the quantum mechanical phenomenon of group symmetries introducing "degeneracies," which is physics speak for eigenvalues (of the Hamiltonian in this case) of multiplicity greater than $1$.
The "most degenerate" case is the complete graph $S = K_n$, where $G = S_n$ and the corresponding representation is a copy of the trivial representation and an irreducible representation of degree $n-1$. This means the adjacency matrix $A$ must have at most two eigenvalues, one with multiplicity $1$ and one with multiplicity $n-1$, which turn out to be $n-1$ and $-1$ respectively (this is easily computed by computing $\text{tr}(A)$ and $\text{tr}(A^2)$, or just finding all the eigenvectors of $A + I$), inducing a factorization
$$\det (tI - A) = (t - n + 1)(t + 1)^{n-1}$$
with a factor of multiplicity $n-1$.
One of the "least degenerate" cases where the automorphism group still acts transitively on vertices is $S = C_n$ the cycle graph, where $G = D_n$ is the dihedral group and the corresponding representation splits up into mostly $2$-dimensional irreps. This reflects the fairly mild degeneracies of the eigenvalues of the adjacency matrix, which are $2 \cos \frac{2\pi k}{n}, k = 0, \dots n-1$, and/but which also organize themselves into nontrivial Galois orbits coming from the action of the Galois group of $\mathbb{Q}(\zeta_n)$.