Factorization of the characteristic polynomial of the adjacency matrix of a graph

Question

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:

1. 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?

2. If not, what are the graph-theoretic consequences of having many small-degree factors?

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

Answer 1

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

Answer 2

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 (irreducible) invariant subspaces then $A$ cannot have small eigenspaces.

---

On the other hand, generic regular graphs do probably not have integer eigenvalues. So there is no reason for any such adjacency polynomial to factor over $\Bbb Z$ into many small factors (ignoring the trivial factor). So I would say this points to some structure in your graph, but it is hard to say what it is whitout knowing more about the graph.

Answer 3

Consider the category $Gph$ whose objects are directed graphs. That is the topos defined on the small category $C$ which has two objects $0,1$ and two morphisms $s,t:0\rightarrow 1$. A directed graph is thus defined by by a contravariant functor $D:C\rightarrow Set$ where we call $D(0)$ the set of nodes and $D(1)$ the set of arrows, $D(s)$ is the source map and $D(t)$ is the target map. An example of graphs is the $n$-cycle directed graph.

I have constructed with Bisson a Quillen model on the category $Gph$ such that a morphism $f:X\rightarrow Y$ is a weak equivalene if and only if for every $n>0$ the induced map $Hom(C_n,X)\rightarrow Hom(C_n,Y)$ is bijective.

Let $X$ is and $Y$ be finite graphs, we say that they are almost isospectral if the characteristic polynomial of their adjecency matrices have the same non zero eigenvalues.

The following conditions are equivalent:

1. Two finite directed graphs for the Quillen model above are weakly equivalent.

2. Two finite directed graphs have the same Zeta serie.

3. Two finite directed graphs are almost isospectral.

The third condition implies that two finite graphs are weakly equivalent for the Quillen model if the factors of their characteristic polynomial distinct of $X^p$ are equal.

We have also computed the homotopy category of this closed model and showed that it is equivalent to the category of periodic $\mathbb{Z}$-sets.

This shows that a finite graph is equivalent to finite set of cycles and enables to relate the degree of the factors of the characteristic polynomial of the finite graph $X$ to its image in the homotopy category which is a set of cycles.

For example, for this model, acyclic object are trees, and the characteristic polynomial of a tree is of the form $X^n$. In fact in this model if $X^p$ is a non trivial factor of the characteristic polynomial of the graph $G$, there is a weak cofibration $c:G'\rightarrow G$ (a whiskering) which is defined by attaching trees to $G'$.

https://arxiv.org/pdf/0802.3859.pdf

https://arxiv.org/pdf/0906.4087.pdf

Answer 4

Corollary 2.7 of Norman Biggs's book Algebraic Graph Theory says that if $d$ is the diameter of the graph, then it has at least $d+1$ distinct eigenvalues. (This bound is tight, and is achieved for example by distance-regular graphs.) So in particular, having a lot of repeated eigenvalues does not necessarily indicate a lot of automorphisms; it might just mean that the diameter is small. For example, a strongly regular graph has only three distinct eigenvalues but often has trivial automorphism group.

Answer 5

An observation about graph isomorphism (GI) since you ask about powers greater than 1.

GI is polynomial time solvable for graphs with bounded eigenvalues multiplicity (the largest exponent in the factorization of your polynomial).

I suspect random graphs to have bounded multiplicities and random non-isomorphic graphs to have different polynomials.

A very extreme examples are Paley graphs:

sage: g1=graphs.PaleyGraph(37);factor(g1.characteristic_polynomial())
(x - 18) * (x^2 + x - 9)^18

Answer 6

If the characteristic polynomial factors (over $\mathbb{Q}$) into polynomials of degrees $d_1,d_2,\ldots,d_r$, where $d_1$ is the degree of the polynomial that the largest eigenvalue is a root of, then the controllability matrix $\begin{pmatrix}\mathbf{b} & \mathbf{Ab} & \mathbf{A}^2\mathbf{b} & \ldots & \mathbf{A}^{n-1}\mathbf{b}\end{pmatrix}$ with respect to any nonzero $0$-$1$ indicator vector $\mathbf{b}$ has rank $d_1+\sum_{i=2}^r c_id_i$, where $c_i=0$ or $1$ for all $2\leq i\leq r$. (Here, $\mathbf{A}$ is the adjacency matrix.)

In particular, if the characteristic polynomial is irreducible over $\mathbb{Q}$, then the controllability matrix is invertible for all nonzero $\mathbf{b}$.

Also note that for regular graphs, one of the factors will be $(x-\rho)$ where $\rho$ is the common degree of the graph, and this $\rho$ will be the largest eigenvalue of $\mathbf{A}$. Hence the above result would state that the rank of any controllability matrix as defined previously is $1+\sum_{i=2}^r c_id_i$ where $c_i=0$ or $1$ for all $2\leq i\leq r$. In particular for the case when $\mathbf{b}$ is the vector of all ones, it is well-known that $c_2=c_3=\cdots=c_r=0$ and the rank of the controllability matrix will be $1$.