ON MATRIX PRODUCT FACTORIZATION OF CAYLEY GRAPHS

Allen W. Herman Department of Mathematics and Statistics University of Regina Bobby Miraftab School of Computer Science Carleton University · 2025

Read ON MATRIX PRODUCT FACTORIZATION OF CAYLEY GRAPHS by Allen W. Herman Department of Mathematics and Statistics University of Regina Bobby Miraftab School of Computer Science Carleton University (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-2512-17110.txt.

Introduction

Allen W. Herman and Bobby Miraftab study when the adjacency matrix of a Cayley graph splits as a product of two Cayley graph adjacency matrices. Cayley graphs encode a finite group through a symmetric generating set, and matrix products mirror set products in the group algebra.

They prove the split holds exactly when the target set equals the product of the two factor sets, with each element written uniquely as a product. For class-closed sets, character values give the test. In abelian groups the question becomes whether the pair is a Sidon pair. Cyclic cases reduce through mask polynomials and the Chinese Remainder Theorem, and dihedral groups yield infinite factorable families plus clear non-examples.

Catalog record

CREATORAllen W. Herman Department of Mathematics and Statistics University of Regina Bobby Miraftab School of Computer Science Carleton University
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-17110

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ON MATRIX PRODUCT FACTORIZATION OF CAYLEY GRAPHS Allen W. Herman Department of Mathematics and Statistics University of Regina Bobby Miraftab School of Computer Science Carleton University Abstract We study when the adjacency matrix of a Cayley graph factors as the product of two adjacency matrices of Cayley graphs. Let G G be a finite group and let U ⊆ G ​ \smallsetminus ​ { e } U\subseteq G\smallsetminus\{e\} be symmetric. Writing A ⁡ ( G , U ) A(G;U) for the adjacency matrix of the Cayley graph of G G with respect to U U , we prove that for symmetric subsets S , T , U S,T,U of G ​ \smallsetminus ​ { e } G\smallsetminus\{e\} , A ⁡ ( G , U ) = A ⁡ ( G , S ) ​ A ​ ( G , T ) A(G;U)=A(G;S)\,A(G;T) if and only if U = S ​ T U=ST and each u ∈ U u\in U has a unique representation u = s ​ t u=st , equivalently ( ∑ s ∈ S s ) ​ ( ∑ t ∈ T t ) = ∑ u ∈ U u \bigl(\sum_{s\in S}s\bigr)\bigl(\sum_{t\in T}t\bigr)=\sum_{u\in U}u in the group algebra. When S , T , U S,T,U are unions of conjugacy classes, this is characterized character-theoretically by χ ⁡ ( U ) = χ ⁡ ( S ) ​ χ ​ ( T ) / χ ⁡ ( 1 ) \chi(U)=\chi(S)\chi(T)/\chi(1) for all χ ∈ Irr ⁡ ( G ) \chi\in\mathrm{Irr}(G) . In addition, for abelian groups, we identify A ⁡ ( G , S ) ​ A ​ ( G , T ) A(G;S)A(G;T) with the − 1 0\!-\!1 convolution 𝟏 S ∗ 𝟏 T \mathbf{1}_{S}*\mathbf{1}_{T} , so factorability is equivalent to ( S , T ) (S,T) being a Sidon pair, i.e., ( S − S ) ∩ ( T − T ) = { 0 } (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 2 ​ n 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. 1 Introduction A classical topic in graph theory is to ask when a graph can be written as a product of smaller graphs with respect to a fixed graph product (Cartesian, tensor, strong, etc.). For instance, a graph X has a Cartesian factorization if X\cong H\,\Box\,K for some graphs H,K , see Hammack et al. 2011 for background and many results across product types. In a different direction, Manjunatha Prasad et al. 2013 introduced the matrix product of graphs: if H and K are graphs on the common vertex set [n]=\{1,\dots,n\} with adjacency matrices B and C , their matrix product HK is the (generally weighted, directed) graph whose adjacency matrix is the usual matrix product BC . We refer readers to the subsequent works for variants, constraints, and applications [ 9 , 2 , 11 ] . Throughout this paper we are interested in simple, undirected graphs, so we focus on situations where the matrix product again yields a simple 0\!-\!1 adjacency matrix. Let G be a finite group with identity e . For a subset U\subseteq G with e\notin U and U=U^{-1} , the Cayley graph \mathop{\mathsf{Cay}}(G;U) has vertex set G and edges g\mathord{\,\vrule width=12.0pt,height=3.0pt,depth=-1.5pt}\,h if and only if g^{-1}h\in U . A subset U of G is called symmetric if U^{-1}=U . Fix once and for all an enumeration G=\{g_{1},\dots,g_{n}\} and indexed matrices by this order; the adjacency matrix is A(G;U)=(a_{ij})_{1\leq i,j\leq n},\qquad a_{ij}=\mathbf{1}_{\,g_{i}^{-1}g_{j}\in U}. A central question of this paper is: When does a Cayley adjacency A(G;U) factor as a matrix product of Cayley adjacencies, A(G;U)=A(G;S)\,A(G;T)\qquad\text{with }S,T\subseteq G\smallsetminus\{e\}\text{ symmetric?} We emphasize that we are insisting that our factors and their product are Cayley graphs on the same group G under a fixed Cayley representation. Indeed, a product of two arbitrary simple graphs on G may well be a Cayley graph on G even when neither factor is. The following example over G=\mathbb{Z}_{4}=\{0,1,2,3\} illustrates this. Let H have edges \{0\!\mathord{\,\vrule width=12.0pt,height=3.0pt,depth=-1.5pt}\,\!1,\ 2\!\mathord{\,\vrule width=12.0pt,height=3.0pt,depth=-1.5pt}\,\!3\} and let K have edges \{1\!\mathord{\,\vrule width=12.0pt,height=3.0pt,depth=-1.5pt}\,\!2,\ 3\!\mathord{\,\vrule width=12.0pt,height=3.0pt,depth=-1.5pt}\,\!0\} . With respect to the order 0,1,2,3 , A(H)=\begin{pmatrix}0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0\end{pmatrix},\qquad A(K)=\begin{pmatrix}0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0\end{pmatrix}. A direct multiplication gives A(H)A(K)=\begin{pmatrix}0&0&1&0\\ 0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\end{pmatrix}, which is the adjacency of the matching \{0\!\mathord{\,\vrule width=12.0pt,height=3.0pt,depth=-1.5pt}\,\!2,\ 1\!\mathord{\,\vrule width=12.0pt,height=3.0pt,depth=-1.5pt}\,\!3\}=\mathop{\mathsf{Cay}}(\mathbb{Z}_{4};\{2\}) . However, neither H nor K is a Cayley graph on \mathbb{Z}_{4} (and no relabeling by automorphisms/right translations of \mathbb{Z}_{4} turns them into Cayley graphs on \mathbb{Z}_{4} ). On the other hand, all three of A(H) , A(K) , and A(H)A(K) above can be regarded as Cayley graphs on \mathbb{Z}_{2}\times\mathbb{Z}_{2} , and relative to this group they do give an example of a Cayley-by-Cayley factorization. Here we introduce the following: Definition 1.1 . Let G be a finite group and let S,T,U\subseteq G\smallsetminus\{e\} be symmetric subsets such that A(G;U)=A(G;S)A(G;T) . Then we say that \mathop{\mathsf{Cay}}(G;U) has a factorization . In this case, we say that (S,T,U) is factorable in G . Following de Caen et al. 1990 , a near–factorization of a finite group G is a pair (S,T) with e\notin S\cup T such that every g\in G\smallsetminus\{e\} has a unique representation g=st with s\in S , t\in T , equivalently ST=G\smallsetminus\{e\} and S\cap T=\emptyset . In our language, this is the special case U=G\smallsetminus\{e\} , for which \bigl(\sum_{s\in S}R(s)\bigr)\bigl(\sum_{t\in T}R(t)\bigr)=\sum_{g\in G}R(g)-I . This provides a useful benchmark for our sparser Cayley‑by‑Cayley factorizations. Restricting to Cayley factors leads to a rigid and tractable algebraic formulation. Writing R(g) for the right‑regular permutation matrix, we have A(G;X)=\sum_{x\in X}R(x)\qquad(X\subseteq G), so A(G;S)A(G;T)=\sum_{(s,t)\in S\times T}R(st). Since \{R(g):g\in G\} are linearly independent, the identity A(G;U)=A(G;S)A(G;T) holds iff every element of U is realized uniquely as a product st with s\in S , t\in T , and no element outside U is so realized. Equivalently, in the group algebra, \Big(\sum_{s\in S}s\Big)\Big(\sum_{t\in T}t\Big)=\sum_{u\in U}u. We note that near–factorizations of groups correspond to factorizations of J-I , but the group structure imposes additional constraints absent from arbitrary (0,1) -matrix factorizations, see de Caen et al. 1990 . 2 Cayley Factorization of General Finite Groups Throughout this paper, G denotes a finite group, and we always assume that the subsets S , T , and U are symmetric subsets of G . Lemma 2.1 . Let G,G^{\prime} be finite groups and let \varphi\colon G\to G^{\prime} be an isomorphism. Let P_{\varphi} be the n\times n permutation matrix with (P_{\varphi})_{g,\varphi(g)}=1 for all g\in G . Then for every subset X\subseteq G^{\prime} , P_{\varphi}^{\!\top}\,A(G^{\prime};X)\,P_{\varphi}\;=\;A\bigl(G;\varphi^{-1}(X)\bigr). Proof. Write A^{\prime}=A(G^{\prime};X) and A=A\bigl(G;\varphi^{-1}(X)\bigr) . For g,h\in G we have \bigl(P_{\varphi}^{\!\top}A^{\prime}P_{\varphi}\bigr)_{g,h}=A^{\prime}_{\varphi(g),\varphi(h)} . By the definition of Cayley adjacency, we have the following: A^{\prime}_{\varphi(g),\varphi(h)}=1\iff\varphi(g)^{-1}\varphi(h)\in X\iff\varphi(g^{-1}h)\in X\iff g^{-1}h\in\varphi^{-1}(X)\iff A_{g,h}=1. Hence P_{\varphi}^{\!\top}A(G^{\prime};X)P_{\varphi}=A(G;\varphi^{-1}(X)) . ∎ If \varphi is merely a bijection (not a homomorphism), the identity can fail. For example, take G=G^{\prime}=\mathbb{Z}_{3}=\{0,1,2\} (additive), let \varphi swap 0 and 1 and fix 2 , and let X=\{2\} . Then for g=1,h=0 , \bigl(P_{\varphi}^{\!\top}A(G^{\prime};X)P_{\varphi}\bigr)_{1,0}=0, while A\bigl(G;\varphi^{-1}(X)\bigr)_{1,0}=1, so the matrices are different. The preceding lemma shows that, up to isomorphism, it suffices to study factorization within the class of Cayley

Read the complete text