De Bruijn digraphs and affine transformations

Let Zdn be the additive group of 1×n row vectors over Zd. For an n×n matrix T over Zd and ω∈Zdn, the affine transformation FT,ω of Zdn sends x to xT+ω. Let 〈α〉 be the cyclic group generated by a vector α∈Zdn. The affine transformation coset pseudo-digraph TCP(Zdn,α,FT,ω) has the set of cosets of 〈α〉 in Zdn as vertices and there are c arcs from x+〈α〉 to y+〈α〉 if and only if the number of z∈x+〈α〉 such that FT,ω(z)∈y+〈α〉 is c. We prove that the following statements are equivalent: (a) TCP(Zdn,α,FT,ω) is isomorphic to the d-nary (n−1)-dimensional De Bruijn digraph; (b) α is a cyclic vector for T; (c) TCP(Zdn,α,FT,ω) is primitive. This strengthens a result conjectured by C.M. Fiduccia and E.M. Jacobson [Universal multistage networks via linear permutations, in: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, ACM Press, New York, 1991, pp. 380-389]. Under the further assumption that T is invertible we show that each component of TCP(Zdn,α,FT,ω) is a conjunction of a cycle and a De Bruijn digraph, namely a generalized wrapped butterfly. Finally, we discuss the affine TCP digraph representations for a class of digraphs introduced by D. Coudert, A. Ferreira and S. Perennes [Isomorphisms of the De Bruijn digraph and free-space optical networks, Networks 40 (2002) 155-164].