The basic diagrammatic tool is called a de Bruijn diagram[44,98],
whose 
nodes represent the possible sequences of s symbols
chosen from amongst a collection of k; making the convenient choice
of integers modulo k for symbols, the nodes become simply s-digit
numbers to the base k.
Two nodes are to be linked if the first ends with the same s-1 digit
sequence with which the second begins; in other words, if they represent
overlapping sequences. Since there is no restriction on the symbols which
can be placed at the free ends, each node will have k incoming links and
k outgoing links. Having chosen numbers as symbols, the linkage rule is
expressible in a simple arithmetic form; namely, that node i is linked
to nodes 
. Since there are 
nodes in all, the foregoing sums are to be taken modulo S. Indeed the
most straightforward representation of a de Bruijn diagram is through the
vertices of an S-gon inscribed in a circle, chords marked according to
the links present. It can also be represented by a connectivity matrix
whose block diagonal structure models this circle.
Since those nodes are linked which differ by shifting their label, dropping the digit on the left and inserting a new digit on the right, de Bruijn diagrams are frequently used in shift register theory. Here, the shift register is simply a moving window which can be used to scan a long chain for the neighborhoods needed by the evolutionary rule of a cellular automaton. Any chain can be reconstructed from the windows by following a path through the diagram, recording the digit associated with each link as one moves along.
Now we need to examine de Bruijn matrices in detail, but to give
concrete examples we will stick to low order matrices over the binary
alphabet. Let 
denote the connectivity matrix for a de Bruijn
diagram for k symbols and n stages; write 
for 
.