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

The Burrows–Wheeler matrix of a word $w$ is the matrix whose rows are the conjugates (rotations) of $w$ in ascending lexicographic order. Its last column is called the Burrows–Wheeler transform of $w$, and has the property of being easier to compress when the input word is a repetitive text. For this reason, it is largely used in textual data compression, in particular in bioinformatics [21, 19, 18]. But the Burrows–Wheeler transform also has many interesting combinatorial properties (see [31, 12] for a survey). Since the Burrows–Wheeler transform is the same for any conjugate of $w$, it can be viewed as a map from the set of necklaces (conjugacy classes of words) to the set of words.

A de Bruijn word of order $d$ over an alphabet $\mathrm{\Sigma }$ is a necklace of length ${|\mathrm{\Sigma }|}^d$ such that each of the ${|\mathrm{\Sigma }|}^d$ distinct words of length $d$ occurs exactly once in it, as a cyclic factor. Since each of the ${|\mathrm{\Sigma }|}^{d-1}$ distinct words of length $d-1$ occurs as a prefix of $|\mathrm{\Sigma }|$ consecutive rows of the Burrows–Wheeler matrix of a de Bruijn word, the Burrows–Wheeler transform of a de Bruijn word is characterized (among words that are images under the Burrows–Wheeler transform) by the fact that it is a concatenation of ${|\mathrm{\Sigma }|}^{d-1}$ alphabet-permutations (de Bruijn words of order $1$). This motivates us to define a generalized de Bruijn word as one whose Burrows–Wheeler transform is a concatenation of (any number of) alphabet-permutations.

As is well known, de Bruijn words are in $1$-to-$1$ correspondence with Hamiltonian cycles in de Bruijn graphs. We show that, analogously, generalized de Bruijn words are in $1$-to-$1$ correspondence with Hamiltonian cycles in generalized de Bruijn graphs, introduced in the early $80$’s independently by Imase and Itoh [16], and by Reddy, Pradhan, and Kuhl [29] (see also [10]) in the context of network design. The generalized de Bruijn graph $\mathrm{DB}(k,n)$ has vertices $\{0,1,\mathrm{\dots },n-1\}$ and for every vertex $m$ there is an edge from $m$ to $km+imod(n)$ for every $i=0,1,\mathrm{\dots },k-1$.

In particular, we provide a new and simple interpretation of the well-known correspondence between de Bruijn words and Hamiltonian cycles in de Bruijn graphs in terms of the inverse standard permutation of the Burrows–Wheeler transform, and we show that this interpretation extends to the generalized case.

The other class of words we introduce is that of invertible necklaces. We call an aperiodic necklace over an alphabet of prime size $p$ invertible if its Burrows–Wheeler matrix is nonsingular, i.e., has determinant nonzero modulo $p$. We show that each invertible necklace of length $n$, as a set of vectors over the base field ${𝔽}_p$, corresponds to a normal base of the field ${𝔽}_{p^n}$. Invertible necklaces can also be represented by conjugacy classes of their circulant matrices, and they form an Abelian group, called the Reutenauer group $R{G}_p^n$ [11]. The set of invertible necklaces of a given length $n$ can therefore be endowed with a multiplication operation that makes it isomorphic to the $n$-th Reutenauer group.

Using a known result in abstract algebra [7], we show that every aperiodic necklace of length $n$ with non-zero weight modulo $p$ (the weight of a word is the sum of its digits) is invertible if and only if $n$ is either a power of $p$ or a $p$-rooted prime. However, it is an open problem to decide whether there are infinitely many lengths $n$, different from a power of $p$, for which every aperiodic necklace of length $n$ with non-zero weight modulo $p$ has an invertible Burrows–Wheeler matrix. This seems to be a challenging problem, as it is related to Artin’s conjecture on primitive roots.

In the last part of the paper, we show a connection between generalized de Bruijn words and invertible necklaces. Chan, Hollmann and Pasechnik [5] proved that for every prime $p$ and any $n$, one has $R{G}_p^n\cong K(\mathrm{DB}(p,n))\oplus {\mathbb{Z}}_{p-1}$, where $K(G)$ denotes the sandpile group of the graph $G$. Since the structure of the sandpile group of an Eulerian graph is determined by the invariant factors of its Laplacian matrix, Chan et al. gave the precise structure of sandpile groups of generalized de Bruijn graphs, and hence of Reutenauer groups.

In particular, when $p=2$ and $n=2^d$, we show that there is a bijection between de Bruijn words of order $d$ and binary necklaces of length $2^{d-1}$ with an odd number of $1$’s.

We begin by introducing some preliminary definitions related to strings and words. For a thorough introduction, we refer the reader to [9], and [25].

Let ${\mathrm{\Sigma }}_k=\{0,1,\mathrm{\dots },k-1\}$, $k>1$, be a sorted set of letters.

A word over the alphabet ${\mathrm{\Sigma }}_k$ is a concatenation of elements of ${\mathrm{\Sigma }}_k$. The length of a word $w$ is denoted by $|w|$. For a letter $i\in {\mathrm{\Sigma }}_k$, ${|w|}_i$ denotes the number of occurrences of $i$ in $w$. The vector $({|w|}_0,\mathrm{\dots },{|w|}_{k-1})$ is the Parikh vector of $w$.

Let $w=w_0\mathrm{\cdots }{w}_{n-2}{w}_{n-1}$ be a word of length $n>0$. The weight of $w$ is ${\sum }_{j=0}^{n-1}{w}_j$. When $n>1$, the shift of $w$ is the word $\sigma (w)=w_{n-1}{w}_0\mathrm{\cdots }{w}_{n-2}$.

For a word $w$, the $n$-th power of $w$ is the word $w^n$ obtained by concatenating $n$ copies of $w$.

Notice that an alphabet-permutation power of length $n$ has a balanced Parikh vector, i.e., a Parikh vector of the form $(\frac{n}{k},\frac{n}{k},\mathrm{\dots },\frac{n}{k})$.

In the binary case, a word $w$ is an alphabet-permutation power if and only if $w=\tau (v)$, where $v$ is a binary word of length $|w|/2$ and $\tau$ is the Thue–Morse morphism, the substitution that maps $0$ to $01$ and $1$ to $10$.

Two words $w$ and $w^{\prime }$ are conjugates if $w=uv$ and $w^{\prime }=vu$ for some words $u$ and $v$. The conjugacy class of a word $w$ can be obtained by repeatedly applying the shift operator, and contains $|w|$ distinct elements if and only if $w$ is primitive, i.e., for any nonempty word $v$ and integer $n$, $w=v^n$ implies $n=1$. A necklace (resp. aperiodic necklace) $[w]$ is a conjugacy class of words (resp. of primitive words). Necklaces are also called circular words. Notice that, given a word $w$, the weight of $w$ is invariant under shift, hence we can define the weight $wt([w])$ of the necklace $[w]$ as the weight of any of its representatives.

For example, $[1100]=\{1100,0110,0011,1001\}$ is an aperiodic necklace, while $[1010]=\{1010,0101\}$ is not aperiodic.

The number of aperiodic necklaces of length $n$ over ${\mathrm{\Sigma }}_k$ is given by

where $\mu (n)$ is the Möbius function, defined by: $\mu (1)=1$, $\mu (n)={(-1)}^j$ if $n$ is the product of $j$ distinct primes or $0$ otherwise, i.e., if $n$ is divisible by the square of a prime number.

The number of necklaces of length $n$ over ${\mathrm{\Sigma }}_k$ is given by

where $\varphi (n)$ is the Euler’s totient function. Recall that the Euler’s totient function $\varphi (n)$ counts the number of positive integers less than or equal to $n$ and coprime with $n$, i.e., the order of the multiplicative group ${\mathbb{Z}}_n^{\ast }$, and can be computed using the formula

for $n>1$, and $\varphi (1)=1$, where the product is taken over the distinct primes dividing $n$.

The Burrows–Wheeler matrix (BWT matrix) of a necklace $[w]$ is the matrix whose rows are the $|w|$ shifts of $w$ in ascending¹¹1This is the standard convention in the literature. Of course, one can also choose the descending lexicographic order, the properties are symmetric. lexicographic order. Let us denote by $F$ and $L$, respectively, the first and the last column of the BWT matrix of $[w]$. We have that $F=0^{n_0}{1}^{n_1}\mathrm{\cdots }{(k-1)}^{n_{k-1}}$, where $(n_0,\mathrm{\dots },n_{k-1})$ is the Parikh vector of $[w]$; $L$, instead, is the Burrows–Wheeler Transform (BWT) of $[w]$. The BWT is therefore a map from the set of necklaces to the set of words. As is well known, it is an injective map (we describe below how to invert it). A word is a BWT image if it is the BWT of some necklace.

The standard permutation of a word $u=u_0{u}_1\mathrm{\cdots }{u}_{n-1}$, $u_i\in {\mathrm{\Sigma }}_k$, is the permutation ${\pi }_u$ of $\{0,1,\mathrm{\dots },n-1\}$ such that if and only if or $u_i=u_j$ and . In other words, in one-line notation, ${\pi }_u$ orders distinct letters of $u$ lexicographically, and equal letters by occurrence order, starting from $0$. When $u$ is the BWT image of some necklace, the standard permutation is also called $LF$-mapping. As is well known, a word $u$ is a BWT image of an aperiodic necklace if and only if ${\pi }_u$ is a length-$n$ cycle.

The inverse standard permutation ${\pi }_u^{-1}$ of a word $u$, written in one-line notation, can be obtained by listing in left-to-right order the positions of $0$ in $u$, then the positions of $1$, and so on. The inverse standard permutation of a BWT image is also called $FL$-mapping.

An aperiodic necklace can be uniquely reconstructed from its BWT, using either of the standard permutation or its inverse. To do this, it is convenient to write these permutations in cycle form. Let $L$ be the BWT of $[w]$, and ${\pi }_L=(j_0{j}_1\mathrm{\cdots }{j}_{n-1})$ be the standard permutation of $L$ in cycle form, with $j_0=0$. Then, $L_{j_{n-1}}{L}_{j_{n-2}}\mathrm{\cdots }{L}_{j_0}$ is the first row of the BWT matrix of $[w]$, i.e., the lexicographically least element of the necklace $[w]$. This is also equal to $F_{i_0}{F}_{i_1}\mathrm{\cdots }{F}_{i_{n-1}}$, where ${\pi }_L^{-1}=(i_0{i}_1\mathrm{\cdots }{i}_{n-1})$ is the inverse standard permutation of $L$ in cycle form, with $i_0=0$.

The following remark will be used in later sections:

For example, the BWT of $[w]=[220120011]$ is the word $u=202001121$, whose inverse standard permutation in cycle form is ${\pi }_u^{-1}=(\mathrm{0\hspace{0.17em}1\hspace{0.17em}3\hspace{0.17em}5\hspace{0.17em}8\hspace{0.17em}7\hspace{0.17em}2\hspace{0.17em}4\hspace{0.17em}6})$. Mapping: $0,1,2$ to $0$; $3,4,5$ to $1$; $6,7,8$ to $2$, one obtains the word $001122012$, the first row of the BWT matrix of $[w]$.

Necklaces that are not aperiodic can also be reconstructed from their BWT, as a consequence of the following result:

Let $G=(V,E)$ be a finite directed graph, which may have loops and multiple edges (in this case, it is also called a multigraph in the literature). Each edge $e\in E$ is directed from its source vertex $s(e)$ to its target vertex $t(e)$.

The directed line graph (or edge graph) $ℒG=(E,E^{\prime })$ of $G$ has as vertices the edges of $G$, and as edges the set

An oriented spanning tree of $G$ is a subgraph containing all of the vertices of $G$, having no directed cycles, in which one vertex, the root, has outdegree $0$, and every other vertex has outdegree $1$. The number $\kappa (G)$ of oriented spanning trees of $G$ is sometimes called the complexity of $G$.

A directed graph is Hamiltonian if it has a Hamiltonian cycle, i.e., one that traverses each node exactly once, while it is Eulerian if it has an Eulerian cycle, i.e., one that traverses each edge exactly once. As is well known, a directed graph is Eulerian if and only if $indeg(v)=outdeg(v)$ for all vertices $v$. If a graph is Eulerian, its line graph is Hamiltonian.

We start by briefly discussing (ordinary) de Bruijn graphs and de Bruijn words, and relating them to the inverse standard permutation of the Burrows–Wheeler transform.

Recall that the de Bruijn graph $\mathrm{DB}({\mathrm{\Sigma }}_k,k^d)$ of order $d$ is the directed graph whose vertices are the words of length $d$ over ${\mathrm{\Sigma }}_k$ and there is an edge from $a_{i}w$ to $v$, where $a_i$ is a letter, if and only if $v=w{a}_j$ for some letter $a_j$. As is well known, de Bruijn graphs are Eulerian and Hamiltonian. One has $ℒ\mathrm{DB}({\mathrm{\Sigma }}_k,k^d)=\mathrm{DB}({\mathrm{\Sigma }}_k,k^{d+1})$.

A de Bruijn word of order $d$ over ${\mathrm{\Sigma }}_k$ is a necklace over ${\mathrm{\Sigma }}_k$ containing as a circular factor each of the ${\mathrm{\Sigma }}_k^d$ words of length $d$ over ${\mathrm{\Sigma }}_k$ exactly once. De Bruijn words correspond to Hamiltonian cycles in $\mathrm{DB}({\mathrm{\Sigma }}_k,k^d)$, as they can be obtained by concatenating the first letter of the labels of the vertices it traverses.

Now, since the vertex labels of $\mathrm{DB}({\mathrm{\Sigma }}_k,k^d)$ are the base-$k$ representations of the integers in $\{0,1,\mathrm{\dots },k^d-1\}$ on $d$ digits (padded with leading zeroes), the de Bruijn graph of order $d$ over ${\mathrm{\Sigma }}_k$ can be equivalently defined as the one having vertex set $\{0,1,\mathrm{\dots },k^d-1\}$ and containing an edge from $m$ to $km+imod(k^d)$ for every $i=0,1,\mathrm{\dots },k-1$. We let $\mathrm{DB}(k,k^d)$ denote this equivalent representation of the de Bruijn graph of order $d$. A Hamiltonian cycle in $\mathrm{DB}(k,k^d)$ is then a cyclic permutation of $\{0,1,\mathrm{\dots },k^d-1\}$. The relation between a de Bruijn word of order $d$ over ${\mathrm{\Sigma }}_k$, i.e., a Hamiltonian cycle in $\mathrm{DB}({\mathrm{\Sigma }}_k,k^d)$, and the corresponding Hamiltonian cycle in $\mathrm{DB}(k,k^d)$, is given in the following lemma.

In this section, we define invertible necklaces and highlight their connections with abstract algebra.

In [35] (see also the related paper [30]), the authors used BWT matrix multiplication to obtain a group structure on important classes of binary words (namely, Christoffel words and balanced words) that have an invertible BWT matrix. Following this idea, we define invertible necklaces:

As observed in [35], the product of two BWT matrices is not, in general, a BWT matrix; but the author suggests replacing BWT matrices by circulant matrices. As we will see, using circulant matrices, we can define the product between any two invertible necklaces.

Let $w$ be a word over ${\mathrm{\Sigma }}_k$. The circulant matrix of $w$ is the square matrix ${𝒞}_w$ whose $(i+1)$th row is ${\sigma }^i(w)$. For example, the circulant matrix of $011$ is ${𝒞}_{011}=\left(\begin{array}{c}\mathrm{0\hspace{0.17em}1\hspace{0.17em}1}\\ \mathrm{1\hspace{0.17em}0\hspace{0.17em}1}\\ \mathrm{1\hspace{0.17em}1\hspace{0.17em}0}\end{array}\right)$.

One can immediately observe that, since the circulant matrix of a word can be obtained by permuting the rows of its BWT matrix, a necklace is invertible if and only if any (and then, every) of its associated circulant matrices is invertible.

Recall that for every prime $p$ and any positive integer $n$, there is a unique finite field with $p^n$ elements, denoted ${𝔽}_{p^n}$, and its multiplicative group ${𝔽}_{p^n}^{\ast }$ is cyclic. The set of invertible $n\times n$-circulant matrices over ${𝔽}_p$ forms, with respect to matrix multiplication, an Abelian group $C(p,n)$. We consider the group $C(p,n)/⟨Q_n⟩$, where $Q_n$ is the permutation matrix of the cycle $(\mathrm{0\hspace{0.17em}1}\mathrm{\dots }n-1)$. This group is called the Reutenauer group $R{G}_p^n$ in [11]. Intuitively, an element of the Reutenauer group corresponds to an equivalence class of invertible circulant matrices, where two circulant matrices are equivalent if and only if they are the circulant matrices of two conjugated words. Thus, $R{G}_p^n$ is in natural bijection with the set of invertible necklaces of length $n$ over ${\mathrm{\Sigma }}_p$, and one can write ${𝒞}_{[w]}=\{{𝒞}_v,v\in [w]\}\in R{G}_p^n$ for the class of circulant matrices associated with a given invertible necklace $[w]$ of length $n$ over ${\mathrm{\Sigma }}_p$. In particular, this induces a group structure on the set of such invertible necklaces, isomorphic to $R{G}_p^n$, namely with respect to the multiplication defined by $[u]\cdot [v]=[w]$ where $[w]$ is such that ${𝒞}_{[u]}\cdot {𝒞}_{[v]}={𝒞}_{[w]}$. This multiplication does not depend on the choice of representatives for each necklace (equivalently, for each matrix). The trace of a matrix is defined as the sum of its diagonal coefficients. For a word $w$, one can observe that ${𝒞}_w$ has trace $wt(w)$. Since $wt(w)$ is invariant under rotation, one can define the trace of a class of circulant matrices ${𝒞}_{[w]}$ as $\mathrm{Tr}{𝒞}_{[w]}=wt([w])modp$.

As shown in [11], the Reutenauer group acts on the set of all aperiodic necklaces as follows: Let $[v]$ be an aperiodic necklace of length $n$ over ${\mathrm{\Sigma }}_p$. For any ${𝒞}_{[w]}\in R{G}_p^n$, we define ${𝒞}_{[w]}\cdot [v]$ as the necklace of ${𝒞}_w\cdot v^T$. In particular, this operation does not depend on the choice of a representative. For example, ${𝒞}_{[11010]}\cdot [11000]=[11110]$ since $\left(\begin{array}{c}\mathrm{1\hspace{0.17em}1\hspace{0.17em}0\hspace{0.17em}1\hspace{0.17em}0}\\ \mathrm{0\hspace{0.17em}1\hspace{0.17em}1\hspace{0.17em}0\hspace{0.17em}1}\\ \mathrm{1\hspace{0.17em}0\hspace{0.17em}1\hspace{0.17em}1\hspace{0.17em}0}\\ \mathrm{0\hspace{0.17em}1\hspace{0.17em}0\hspace{0.17em}1\hspace{0.17em}1}\\ \mathrm{1\hspace{0.17em}0\hspace{0.17em}1\hspace{0.17em}0\hspace{0.17em}1}\end{array}\right)\cdot \left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\end{array}\right)=01111$.

The orbit of an aperiodic necklace $[v]$ is therefore $O_{[v]}=\{[{𝒞}_{[w]}\cdot [v]]\mid {𝒞}_{[w]}\in R{G}_p^n\}$.

We now recall some classical results and definitions in abstract algebra (see, for example, [23] for a more detailed presentation), which have a strong connection with circulant matrices and invertible necklaces.

It is well known that the number of irreducible polynomials over ${𝔽}_p$ of degree $n$ is equal to the number of aperiodic necklaces of length $n$ over ${\mathrm{\Sigma }}_p$, but there is no known canonical bijection between the two sets. The minimal polynomial of a nonzero element $\alpha$ of ${𝔽}_{p^n}$ is the (unique) monic polynomial $f\in {𝔽}_p[X]$ with the least degree for which $\alpha$ is a root. This polynomial has as roots all the $m$ distinct elements of the form $\alpha ,{\alpha }^p,\mathrm{\dots },{\alpha }^{p^{m-1}}$, where $m$ is the least integer such that ${\alpha }^{p^m}=\alpha$, i.e., the distinct roots of $f$ are the orbit of $\alpha$ under the application of the Frobenius automorphism $\alpha \mapsto {\alpha }^p$. Thus, $f$ has degree $m$ and can be factored as

The sum of all roots of $f$ is called the trace of $f$.

But ${𝔽}_{p^n}$ is also a vector space over ${𝔽}_p$. An element $\gamma$ of ${𝔽}_{p^n}$ is called normal if $\{\gamma ,{\gamma }^p,\mathrm{\dots },{\gamma }^{p^{n-1}}\}$ forms a vector space basis for ${𝔽}_{p^n}$ over ${𝔽}_p$, called a normal basis.

The minimal polynomial of a normal element of ${𝔽}_{p^n}$ over ${𝔽}_p$ is called a normal polynomial. Normal polynomials have non-zero trace (modulo $p$).

If $\gamma$ is a normal element of ${𝔽}_{p^n}$, every element of ${𝔽}_{p^n}$ can be written as a linear combination of elements in the normal basis $\{\gamma ,{\gamma }^p,\mathrm{\dots },{\gamma }^{p^{n-1}}\}$. That is, we can write all the elements of ${𝔽}_{p^n}$ as $n$-length words, or $n$-length vectors. More precisely, if $\alpha =w_0\gamma +w_1{\gamma }^p+\mathrm{\dots }+w_{n-1}{\gamma }^{p^{n-1}}$, $w_j\in {𝔽}_p$ for every $j=0,\mathrm{\dots },n-1$, we can represent $\alpha$ with the word $w=w_0{w}_1\mathrm{\cdots }{w}_{n-1}$. The application of the Frobenius automorphism to an element of the field corresponds to the shift of the corresponding word, and an orbit to a conjugacy class, i.e., to a necklace. This necklace is aperiodic if and only if the orbit is maximal, i.e., has size $n$.

Fixing a normal element $\gamma$ and writing elements of ${𝔽}_{p^n}$ in the induced normal basis, the orbit of $\gamma$ corresponds to the necklace $[{10}^{n-1}]$. There may be other orbits constituted by normal elements. For example, the orbit corresponding to the necklace $[1110]$ is another orbit of normal elements in ${𝔽}_{2^4}$.

The number of normal elements of ${𝔽}_{p^n}$ is counted by ${\mathrm{\Phi }}_p(n)$, the generalized Euler’s totient function. Equivalently, ${\mathrm{\Phi }}_p(n)$ counts the number of polynomials over ${𝔽}_p$ of degree smaller than $n$ and coprime with $X^n-1$. It can be computed using the formula

for $n>1$, where ${\lambda }_p(n)$ is the largest power of $p$ dividing $n$, and ${\mathrm{ord}}_p(d)$ is the multiplicative order of $d$ modulo $p$. The first mention of this formula seems to come from [13], and a more recent study can be found in [15].

The first few values of the sequences ${\mathrm{\Phi }}_2(n)$ and ${\mathrm{\Phi }}_3(n)$ are presented in Table 3.

Let $p$ be a prime, and consider words in ${\mathrm{\Sigma }}_p^n$ as vectors in the vector space ${𝔽}_{p^n}$.

An $n\times n$-circulant matrix over ${𝔽}_p$ is in $C(p,n)$ if and only if it is invertible (or non-singular), if and only if its determinant is non-zero modulo $p$; or, equivalently, if its rows form a normal basis of ${𝔽}_{p^n}$.

Since every element of a normal basis can be chosen as the first row of a corresponding invertible circulant matrix, the order of $C(p,n)$ is ${\mathrm{\Phi }}_p(n)$, and the order of $R{G}_p^n$ (hence, the number of invertible necklaces) is ${\mathrm{\Phi }}_p(n)/n$.

We therefore arrive at the following characterization:

So, the set of aperiodic necklaces of length $n$ over ${\mathrm{\Sigma }}_p$ with invertible BWT matrix forms an abelian group isomorphic to the Reutenauer group $R{G}_p^n$, but the multiplication has to be carried out with the circulant matrices rather than with BWT matrices. This was also speculated in a remark we recently found at the end of [35] (see also the related paper [30]).

In this section, we further explore the connection between the content of Sections 3 and 4. Specifically, we show that over an alphabet whose size is a prime number, generalized de Bruijn words and invertible necklaces are linked not only through their relationship with the Burrows–Wheeler transform, but also via an isomorphism of abelian groups.

First, recall that every finite abelian group $G$ is isomorphic to the direct sum of cyclic groups, i.e., $G\cong {⨁}_i{\mathbb{Z}}_{d_i}$. One has, for example, $R{G}_2^4\cong {\mathbb{Z}}_2$ and $R{G}_2^8\cong {\mathbb{Z}}_2^2\oplus {\mathbb{Z}}_4$ (remember that the order of $R{G}_p^n$ is ${\mathrm{\Phi }}_p(n)/n$).

Chan, Hollmann and Pasechnik [5] proved that the structure of Reutenauer groups can be found by means of an isomorphism with the sandpile groups of generalized de Bruijn graphs, as reported in the next theorem.

As a consequence of Theorem 21, we arrive at a remarkable fact: the structure of the Reutenauer groups is entirely determined by the structure of the generalized de Bruijn graphs. An illustrative example is provided in Table 4. We point out that the (reduced) Laplacian matrix of a generalized de Bruijn graph (as well as its Smith Normal Form and invariant factors) can be derived directly from the arithmetic definition of the graph, without the need to construct it explicitly.