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.
- One stage binary matrix
- Two stage binary matrix
- Three stage binary matrix
- General de Bruijn matrix
- RC and CR factorizations
- Hamiltonian and Eulerian paths
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx