next up previous contents
Next: Up: The de Bruijn Previous: The de Bruijn

Let us start with , which is a matrix (showing a border identifying the 1-blocks which have been linked).


Figure: Single stage binary de Bruijn matrix and diagram. 

The simple structure is due to the fact no matter whether 0 or 1 is dropped from a 1-block, or whether 0 or 1 is added to the block, the maneuver is feasible; thus all positions of the matrix are filled with a one. By inspection, we see that

which is the characteristic equation for . It has eigenvalues . Since it is symmetric it has an orthogonal eigenvector matrix, which is:

The coefficient rather than is chosen because we will presently use probability vectors, which are normed by sums of absolute values rather than sums of squares.

Harold V. McIntosh