Non-diagonalizable digraphs

Background results

Let \(X = (V,E)\) be an undirected graph. Since the adjacency matrix of \(X\) is symmetric, it is diagonalizable, and its eigenvalues are real. If we replace \(X\) with a digraph, then its adjacency matrix need not be diagonalizable. For instance, the digraph with adjacency matrix

is not diagonalizable. If the adjacency matrix of a digraph is diagonalizable, then we say that the graph is diagonalizable.

In the 1980s, Peter J. Cameron [1] asked whether whether all arc-transitive digraphs are diagonalizable. Godsil [2] showed later that if \(A\) is an integral matrix, then there is vertex-transitive digraph whose minimal polynomial is divisible by that of \(A\). In 1985, Babai [3]extended this result for arc-transitive digraphs, and therefore gave a negative answer to Cameron’s question. In [3], Babai additionally asked whether one can construct examples of non-diagonalizable \(s\)-arc-transitive digraphs and vertex-primitive digraphs

Non-diagonalizable vertex-primitive digraphs

Recently, Li et al [4] constructed an infinite family of non-diagonalizable \(s\)-arc-transitive digraphs, for \(s\geq 2\), and an infinite family of non-diagonalizable vertex-primitive digraphs. Both constructions involve finding a Cayley digraph with the desired property, and then using the tensor product of digraphs. In fact, if either \(X\) or \(Y\) is non-diagonalizable digraphs, then the tensor product \(X \times Y\) is non-diagonalizable.

Cayley digraphs are ‘‘easier’’ to deal with since their entire spectra can be obtained, in theory, from the regular representation of the underlying group. Vertex-primitive digraphs that are not Cayley digraphs are much harder to handle since there is no obvious framework to study their eigenvalues. In [4], Li et al. gave other examples of non-diagonalizable vertex-primitive digraphs that are non-Cayley. The smallest of these was a digraph arising from the action of \(PSL_2(17)\) on the \(2\)-subsets of points in \(PG_1(17)\). It turns out that this example is one of the two smallest non-diagonalizable vertex-primitive digraphs with valency \(24\).

Theorem. The smallest non-diagonalizable vertex-primitive digraphs with least valency arise from \(PSL_2(17)\) acting on the \(2\)-subsets of \(PG_1(17)\).

Association schemes

If \(G\leq Sym(\Omega)\) is a transitive group, then the orbitals of \(G\) form an association scheme, which is not always commutative, called the orbital scheme of \(G\). This scheme is commutative if and only if the point-stabilizer \(G_\omega\) is a multiplicity-free subgroup, that is, the character \(\operatorname{Ind}^G(\mathbf{1}_{G_\omega})\), where \(\mathbf{1}_{G_\omega}\) is the trivial character of \(G_\omega\), is a sum of distinct irreducible characters of \(G\).

Commutativity in association schemes gives a nice way to show diagonalizability. Indeed, if \(A_0,A_1,\ldots,A_d\) are the adjacency matrices of digraphs in a commutative association scheme, then \(\{A_0,A_1,\ldots,A_d\}\) is set of commuting normal matrices. Therefore, they are simultaneously diagonalizable. We can deduce from this fact that if \(G\leq Sym(\Omega)\) is transitive, and the point-stabilizer \(G_\omega\) is multiplicity free, then every digraph admitting \(G\) as a subgroup of automorphism is diagonalizable.

Therefore, we may only consider the primitive groups whose point-stabilizers are not multiplicity free. The group \(PSL_2(17)\) acting on $2$-subsets of $PG_1(17)$ has degree \(153\). The primitive groups of degree up to $153$ whose point-stabilizers are multiplicity free are given below.

References

[1] P. Cameron (1983). Automorphism groups of graphs. Selected topics in graph theory 2.

[2] C. Godsil (1982) Eigenvalues of graphs and digraphs. Linear Algebra Appl., 46, 43–50

[3] L. Babai (1985) Arc transitive covering digraphs and their eigenvalues. J. Graph Theory, 9 (3), 363–370

[4] Y. Li, B. Xia, S. Zhou, and W. Zhu (2024) A solution to Babai’s problem on digraphs with non-diagonalizable adjacency matrix Combinatorica, 44: 179–203