On Matrix Product Factorization of Cayley graphs

Abstract

We study when the adjacency matrix of a Cayley graph factors as the product of two adjacency matrices of Cayley graphs. Let $G$ be a finite group and let $U\subseteq G\setminus \{e\}$ be symmetric. Writing $A(G;U)$ for the adjacency matrix of the Cayley graph of $G$ with respect to $U$, we prove that for symmetric subsets $S,T,U$ of $G\setminus \{e\}$, $A(G;U)=A(G;S)A(G;T)$ if and only if $U=ST$ and each $u\in U$ has a unique representation $u=st$, equivalently $\left({\sum }_{s\in S}s\right)\left({\sum }_{t\in T}t\right)={\sum }_{u\in U}u$ in the group algebra. When $S,T,U$ are unions of conjugacy classes, this is characterized character-theoretically by $\ddot{I}‡(U)=\ddot{I}‡(S)\ddot{I}‡(T)/\ddot{I}‡(1)$ for all $\ddot{I}‡\in \mathrm{Irr}(G)$. In addition, for abelian groups, we identify $A(G;S)A(G;T)$ with the $0-1$ convolution $1_S\ast 1_T$, so factorability is equivalent to $(S,T)$ being a Sidon pair, i.e., $(S-S)\cap (T-T)=\{0\}$. For cyclic groups, we reformulate factorability via mask polynomials and reduce to prime-power components using the Chinese Remainder Theorem. We also analyze dihedral groups $D_{2n}$, presenting infinite families of factorable generating sets, and give explicit constructions of subsets whose Cayley graphs do and do not admit such factorizations.

Comments are welcome