Contents

group theory

# Contents

## Definition

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

(1)$\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 \;\colon\; G \longrightarrow \mathbb{C} \,,$

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

(3)$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 $c$.

For example:

• if $c$ is the characteristic function of the given set of generators of $G$, then $M_c$ (3) reduces to the adjacency matrix (1).

• if $c(g) = d(g,e)$ is the minimal number of generators needed to express $g$, then $M_c$ (3) is the graph distance-matrix of the Cayley graph – specifically the original Cayley distance matrix if $G = Sym(n)$ is a symmetric group and $S$ its subset of transpositions;

• if $c(g) = e^{- \beta d(g,e)}$ is the exponentiated graph distance, then $M_c$ (3) is the kernel matrix corresponding to the Cayley graph – specifically the Cayley distance kernel if $G = Sym(n)$ is a symmetric group and $S$ its subset of transpositions.

## Properties

### Character formula

###### Proposition

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

• indexed by the irreducible characters $\chi$ of $G$,

• given by the formula

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

• the corresponding eigenvectors are the complex conjugated component functions

$\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 $g \in G$ as unitary matrices $(\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 $G$ 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)

## References

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