Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform

Abstract

We define generalized de Bruijn words as those words having a Burrows-Wheeler transform that is a concatenation of permutations of the alphabet. We show that generalized de Bruijn words are in 1-to-1 correspondence with Hamiltonian cycles in the generalized de Bruijn graphs, introduced in the early’80s in the context of network design. When the size of the alphabet is a prime p, we define invertible necklaces as those whose BWT-matrix is non-singular. We show that invertible necklaces of length n correspond to normal bases of the finite field Fpn, and that they form an Abelian group isomorphic to the Reutenauer group RGnp. Using known results in abstract algebra, we can make a bridge between generalized de Bruijn words and invertible necklaces. In particular, we highlight a correspondence between binary de Bruijn words of order d + 1, binary necklaces of length 2d having an odd number of 1’s, invertible BWT matrices of size 2d × 2d, and normal bases of the finite field F22d.