Spectra and eigenspaces of non-normal Cayley graphs
Yang Chen, Xuanrui Hu · 2025
Read Spectra and eigenspaces of non-normal Cayley graphs by Yang Chen, Xuanrui Hu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04134.txt.
Introduction
Yang Chen and Xuanrui Hu constructed non-normal Cayley graphs in twenty twenty-five and computed their spectra exactly. Cayley graphs turn a group and a generating set into a network; their eigenvalues govern how walks spread on them. Most studied cases are normal, where the generating set is closed under conjugation. The authors build examples outside that class. Using representation theory of finite groups, they give full spectra and eigenspaces explicitly, supplying worked cases where exact spectral data are usually out of reach.
Catalog record
| CREATOR | Yang Chen, Xuanrui Hu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 14 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-04134
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Spectra and eigenspaces of non-normal Cayley graphs Yang Chen, Xuanrui Hu Abstract . In this paper, we construct some non-normal Cayley graphs and explicitly provide their spectra and eigenspaces using representation theory of finite groups. Keywords: Cayley graph, spectrum, eigenspace, split extension, representation theory. AMS Subject Classification: 05C25, 05C50. 1. Introduction The spectra and eigenspaces of the adjacency matrices of graphs are important algebraic invariants. Graphs with strong symmetry properties are of particular interest in this regard. Lovász [ 9 ] determined the spectrum of a graph with transitive automorphism group in terms of group characters. Babai [ 2 ] gave a more handy formula of the spectrum of a Cayley graph by different methods. However, their formulas cannot enable us to explicitly compute eigenvalues of all Cayley graphs, and does not gave eigenspaces. It is worth mentioning that the adjacency matrix of a Cayley color graph is the transpose of a special group matrix, and its characteristic polynomial is the group determinant proposed by Frobenius [ 7 , 8 ] , which motivated Frobenius to introduce characters of finite groups (see [ 4 ] ). From this, we can analyze the spectrum of a Cayley color graph by Frobenius determinant theorem, which describes the factorization of the group determinant for a finite group. In fact, Lovász and Babai’s results are contained in the Peter-Weyl theorem (see Theorem 2.1 ) generalizing the significant facts about the decomposition of the regular representation of any finite group, discovered by Frobenius and Schur. A Cayley graph is called normal if the connection set is closed under conjugation, that is, it is the union of conjugacy classes of the group. Note that the term normal Cayley graph has been used also by Xu [ 12 ] to denote a different graph construction. The spectra of the normal Cayley graphs can be explicitly calculated using the irreducible characters of the underlying group, see Diaconis and Shahshahani [ 6 ] and Zieschang [ 13 ] . These results were then applied to other research areas. In 2022, Sin and Sorci [ 11 ] studied continuous-time quantum walks on normal Cayley graphs of extraspecial groups. In 2023, Árnadóttir and Godsil [ 1 ] proved an upper bound on the number of pairwise strongly cospectral vertices in a normal Cayley graph in terms of the multiplicities of its eigenvalues. However, the discussion becomes more complicated in the non-normal case, and there are few relevant research results. Since the dimensions of the irreducible representations of the dihedral group are less than or equal to 2 , Cao, Chen and Ling [ 3 ] could study perfect state transfer on non-normal Cayley graphs of dihedral groups by direct calculations. We would like to give a formular for explicitly calculating spectra and eigenspaces of all non-normal Cayley graphs, but this seems impossible. From a basic algebraic point of view, we consider using group extension to study non-normal Cayley graphs. That is, normal Cayley graphs of subgroups and quotient groups are used to construct non-normal Cayley graphs. In this paper, we construct some non-normal Cayley graphs for split group extension and exactly give spectra and eigenspaces of these graphs. 2. Preliminaries Firstly, we recall some definitions and related results concerning Cayley color graphs and representation theory of finite groups. Let \mathbb{C} denote the field of complex numbers. A color graph is a pair \Gamma=(V;c) , where V=\{v_{1},\ldots,v_{n}\} is the vertex set and c:V\times V\rightarrow\mathbb{C} is a function, associating a color with each directed edge. Non-edges can be interpreted as ones having color 0. The adjacency matrix of \Gamma is defined as \text{adj}(\Gamma)=(a_{ij})_{i,j=1}^{n},\text{ where }a_{ij}=c(v_{i},v_{j}). The spectrum of \Gamma is that of its adjacency matrix. For G a group and \alpha:G\rightarrow\mathbb{C} a function, the Cayley color graph \Gamma(G;\alpha) is defined on the vertex set V(\Gamma)=G by c(g,g^{\prime})=\alpha(g^{\prime}g^{-1}) , g,g^{\prime}\in G . If \alpha(g)\in\{0,1\},g\in G and the set S=\{g|\alpha(g)=1\} generates G , then \Gamma is a Cayley digraph of G with connection set S , denoted by \Gamma(G,S) . When S is inverse-closed (i.e. S=S^{-1} ) and does not contain the identity element, \Gamma(G,S) can be represented as a simple undirected graph called the Cayley graph . The reader is referred to [ 10 ] for representation theory of finite groups. Let G be a finite group of order n . We denonte by \mathbb{C}G the algebra of G over \mathbb{C} . Each element f of \mathbb{C}G can then be uniquely written in the form f=\sum_{g\in G}f_{g}g,f_{g}\in\mathbb{C}, and multiplication in \mathbb{C}G extends that in G . The group algebra \mathbb{C}G is isomorphic to its dual L(G) , which is the set of complex-valued functions on G with the convolution product. For f\in L(G) and \rho a representation of G , the Fourier transform of f with respect to \rho is defined to be \mathcal{F}_{\rho}(f)=\hat{f}(\rho)=\sum_{g\in G}f(g)\rho(g). Let \rho_{\rm reg} denote the left regular representation of G . Clearly, the adjacency matrix of the Cayley color graph \Gamma(G;\alpha) is \text{adj}(\Gamma(G;\alpha))=(\hat{\alpha}(\rho_{\rm reg}))^{T}=\sum_{g\in G}\alpha(g)(\rho_{\rm reg}(g))^{T}, where T indicates the usual transpose. The following result can be obtained by the Peter-Weyl theorem for a finite group, see also [ 5 , Chapter 3, E] . Theorem 2.1 . Suppose that G=\{g_{1},\ldots,g_{n}\} is a finite group of order n with irreducible unitary representations \rho_{1},\ldots,\rho_{r} of degrees d_{1},\ldots,d_{r} . Let (\rho_{k})_{ij}=\sqrt{\frac{d_{k}}{n}}((\rho_{k}(g_{1}))_{ij},\ldots,(\rho_{k}(g_{n}))_{ij})^{T},1\leq i,j\leq d_{k},1\leq k\leq r, and P=((\rho_{1})_{11},\ldots,(\rho_{1})_{d_{1}1},(\rho_{1})_{12},\ldots,(\rho_{1})_{d_{1}d_{1}},(\rho_{2})_{11},\ldots,(\rho_{2})_{d_{2}d_{2}},\ldots,(\rho_{r})_{d_{r}d_{r}}). If f is a complex-valued function on G , then the Fourier transform of f at \rho_{\rm reg} can be written as \hat{f}(\rho_{\rm reg})=\bar{P}{\rm diag}(I_{d_{1}}\otimes\hat{f}(\rho_{1}),\ldots,I_{d_{r}}\otimes\hat{f}(\rho_{r}))\bar{P}^{-1}, where \bar{} denotes the conjugate. A function f on G is called a class function if f(gg^{\prime}g^{-1})=f(g^{\prime}) for all g,g^{\prime}\in G . If \rho is irreducible of character \chi , by Schur’s lemma we know that \hat{f}(\rho) is a homothety of ratio \lambda given by \lambda=\frac{1}{\chi(1)}\sum_{g\in G}f(g)\chi(g). For a class function \alpha and irreducible characters \chi_{1},\ldots,\chi_{r} of G , the spectrum of the Cayley color graph \Gamma(G;\alpha) is given by \lambda_{k}=\frac{1}{\chi_{k}(1)}\sum_{g\in G}\alpha(g)\chi_{k}(g),1\leq k\leq r, and the corresponding eigenspaces are (\rho_{k})_{ij}=\sqrt{\frac{\chi_{k}(1)}{n}}((\rho_{k}(g_{1}))_{ij},\ldots,(\rho_{k}(g_{n}))_{ij})^{T},1\leq i,j\leq\chi_{k}(1),1\leq k\leq r independent of the choice of \alpha . Let S be the union of some conjugacy classes of G and the class function \alpha(g)=\left\{\begin{matrix}1,&g\in S,\\ 0,&g\notin S.\end{matrix}\right. Then spectra and eigenspaces of the normal Cayley graph \Gamma(G,S)=\Gamma(G;\alpha) can be explicitly drawn from the above formulas. 3. Construction of non-normal Cayley graphs Let K=\{e=k_{1},k_{2},\ldots,k_{m}\} be a subgroup of G and H=\{e=h_{1},h_{2},\ldots,h_{l}\} a set of all left coset representatives of K in G , called a left transversal . Arranging the vertices of \Gamma(G;\alpha) as e,k_{2},\ldots,k_{m};h_{2},h_{2}k_{2},\ldots,h_{2}k_{m};\dots;h_{l},h_{l}k_{2},\dots,h_{l}k_{m}, the adjacency matrix with respect to the above ordering is a block matrix \{\text{adj}(\Gamma(K;\beta_{ij}))\}_{i,j=1}^{l},\text{ where }\beta_{ij}(k)=\alpha(h_{j}kh_{i}^{-1}),\forall k\in K. If H is a subgroup of G and G is a semidirect product of K and H denoted by K\rtimes H , then G is called a split extension of H by K . Let \rho_{1}^{H},\ldots,\rho_{r}^{H} be irreducible unitary representations of degrees d_{1}^{H},\ldots,d_{r}^{H} of H with characters \chi_{1}^{H},\ldots,\chi_{r}^{H} , and respectively \rho_{1}^{K},\ldots,\rho_{s}^{K} irreducible unitary representations of degrees d_{1}^{K},\ldots,d_{s}^{K} of K with characters \chi_{1}^{K},\ldots,\chi_{s}^{K} . Let C_{i},1\leq i\leq r be the conjugacy classes of H and h_{C_{i}}\in C_{i} . We can obtain the following main result. Theorem 3.1 . Suppose that G=K\rtimes H , and the function \alpha on G satisfies \alpha(hgkg^{-1})=\alpha(hk),\alpha(h^{\prime}hh^{\prime-1}k)=\alpha(hk),\forall g\in G,\forall k\in K,\forall