Let us start with , which is a matrix (showing a border identifying the 1-blocks which have been linked).
.5em
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.