Equivalence of sparse circulants: the bipartite Ádám problem

Details Equivalence of sparse circulants: the bipartite Ádám problem Equivalence of sparse circulants: the bipartite Ádám problem

2007-06-11

arxiv.org/abs/0706.1567v1

Mathematics

Combinatorics

20 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Equivalence of sparse circulants: the bipartite Ádám problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equivalence of sparse circulants: the bipartite Ádám problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence of sparse circulants: the bipartite Ádám problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-358662