nLab Cayley graph spectrum



Group Theory

Linear algebra

homotopy theory, (∞,1)-category theory, homotopy type theory

flavors: stable, equivariant, rational, p-adic, proper, geometric, cohesive, directed

models: topological, simplicial, localic, …

see also algebraic topology



Paths and cylinders

Homotopy groups

Basic facts




Given a finite group GG with a set of generators SS, its Cayley graph is, just as any undirected graph, encoded by its adjacency matrix

(1)({1 ifg 1g 2 1S 0 otherwise) g 1,g 2G \left( \left\{ \array{ 1 &if \; g_1 g_2^{-1} \in S \\ 0 & otherwise } \right. \right)_{g_1, g_2 \in G}

and the eigenvalues of this matrix are referred to as the spectrum of the Cayley graph.

More generally, any coloring function

(2)c:G, c \;\colon\; G \longrightarrow \mathbb{C} \,,

namely a function from the underlying set of GG to the complex numbers (for definiteness), induces the matrix

(3)M c(c(g 1g 2 1)) g 1,g 2G M_c \;\coloneqq\; \big( c(g_1 g_2^{-1}) \big)_{g_1, g_2 \in G}

and the eigenvalues of this matrix are the Cayley graph spectrum for coloring cc.

For example:


Character formula


(character formula for Cayley graph spectra)
If the coloring function cc (2) is a class function, then the eigenvalues EVEV of the color matrix (3) are

  • indexed by the irreducible characters χ\chi of GG,

  • given by the formula

    EV χ=1χ(e)gGc(g)χ(g), EV_\chi \;=\; \frac{1}{\chi(e)} \underset{ g \in G }{\sum} c(g) \, \chi(g) \,,
  • appear with multiplicity (χ(e)) 2(\chi(e))^2;

  • the corresponding eigenvectors are the complex conjugated component functions

    (ρ¯ ij(g)) gG[G] \big(\bar \rho_{i j}(g)\big)_{g \in G} \;\; \in \;\; \mathbb{C}[G]

    of the complex irreducible representations ρ\rho whose characters are the χ\chi, regarded for each gGg \in G as unitary matrices (ρ(g)) i,j{1,χ(e)}Mat χ(e)×χ(e)()(\rho(g))_{i,j \in \{1, \chi(e)\}} \;\in\; Mat_{\chi(e) \times \chi(e)}(\mathbb{C}).

(Diaconis & Shahshahani 81, Cor. 3, Rockmore, Kostelec, Hordijk & Stadler 02, Thm. 1.1, Foster-Greenwood & Kriloff 16, Thm. 4.3, see also Liu & Zhou 18, Thm. 2.6; in the special case that GG is an abelian group the result is due to Lovász 1975, Babai 79, Cor. 3.2; a comprehensive account is in Kaski 02, Sec. 2 & 4, Cor. 5.4)


Last revised on April 30, 2021 at 08:52:29. See the history of this page for a list of all contributions to it.