!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (firstname.lastname@example.org), CBLU, University of Leeds >
Figure: Three stage binary de Bruijn matrix and diagram.
This time the minimal equation is
The general result is that is a matrix whose minimal equation is
and which exhibits the Jordan canonical form for k > 2.
This result shows that it takes at most n links to get from one node to another in an n-stage de Bruijn diagram; in terms of shift register sequences this is precisely the shift required to completely replace one sequence by another. If the node labels have internal symmetry, a smaller shift and hence a shorter path through the diagram may exist.
Although the form of the minimal equation can be conjectured readily enough by inspection, an instructive proof can be given, whose elements will be useful later on. We begin with two factorizations of the de Bruijn matrix, motivated by the observation that it would be block diagonal if only its rows were rearranged.