Equivalence of sparse circulants: the bipartite \'Ad\'am problem

arXiv0706.1567MaRDI QIDQ6205877FDOQ6205877

Publication date: 11 June 2007

Abstract: We consider n-by-n circulant matrices having entries 0 and 1. Such matrices can be identified with sets of residues mod n, corresponding to the columns in which the top row contains an entry 1. Let A and B be two such matrices, and suppose that the corresponding residue sets S_A and S_B have size at most 3. We prove that the following are equivalent: (1) there are integers u,v mod n, with u a unit, such that S_A = uS_B + v; (2) there are permutation matrices P,Q such that A=PBQ. Our proof relies on some new results about vanishing sums of roots of unity. We give examples showing this result is not always true for denser circulants, as well as results showing it continues to hold in some situations. We also explain how our problem relates to the Adam problem on isomorphisms of circulant directed graphs.

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Trigonometric and exponential sums (general theory) (11L03)

This page was built for publication: Equivalence of sparse circulants: the bipartite \'Ad\'am problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6205877)