The de Bruijn matrix

The topological matrix of a de Bruijn diagram is quite regular, although it is asymmetrical and differs from circulant matrices, tridiagonal matrices, or other specialized forms which have been extensively analyzed in the literature. De Bruijn matrices or for short, are characterized by k, the number of symbols from which sequences may be formed, and s---the number of stages---which is the length of the sequence. In these terms, there will be k links entering each node, as well as k links leaving each node. In turn there will be nodes, with altogether links to join them, corresponding to sequences of length s+1.

The uniform distribution of the numbers of incoming and outgoing links means that the topological matrix has constant row sums as well as constant column sums; therefore divided by k would be a doubly stochastic matrix with maximum eigenvalue 1 having a uniform probability distribution for its eigenvector.

It is worth presenting one or two examples and then the general case.





Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx