de Bruijn diagram

  

Figure: The de Bruijn diagram for (3,1/2) automata has three nodes and nine links. The self-links at quiescent nodes in this diagram are inconspicuous.

The basic objects are labelled de Bruijn diagrams, whose properties have been studied both numerically and symbolically. One of the first things to be done with the evolution-labelled diagram is to decompose its matrix into a sum of matrices according to the evolution. The uniform multiplicity principle will require each one of these fragments to be stochastic, as well as requiring minimum variance for the second moment matrix.

Consultation of the evolution table shown in Figure 4 reveals three de Bruijn fragments,

$$\begin{array}{rclrclrcl} A & = & \left[\begin{array}{ccc} 1... ... 1 & 0\\ 0 & 0 & 0\\ 1 & 0 & 1 \end{array}\right], \end{array}$$ (32)

whose sum is the de Bruijn matrix:

$$\left[\begin{array}{ccc} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \end{array}\right],$$ D = (33)

which satisfies D²=3D. This is a typical result for de Bruijn matrices because in a shift register of lemgth n, there is exactly one way to replace one sequence of n symbols by another; any sequence at all can be so transformed.

The table of powers for the individual fragments is

$$\begin{array}{c\vert ccc} {\rm power} & A & B & C \\ \hline ... ... 0 & 0\\ 0 & 0 & 0\\ 1 & 1 & 1 \end{array}\right] \end{array},$$

each of which satisfies M³=M². B even satisfies B²=B. Each matrix is idempotent, which is surprising at first sight, yet consistent with the rule of uniform multiplicity.

The fact that all these matrices are idempotent, a very suggestive relation which was noticed empirically while working out some particular examples. Inasmuch as it is not a common property of matrices, but central to understanding reversibility, it is worth exploring its origins in the algebraic properties of the connection matrices.

We can begin with one immediate consequence of the uniform multiplicity theorem by introducing the vector $<\!u\,\vert$ defined by

$$<\!u\,\vert \left[ \begin{array}{c} 1 \\ 1 \\ \cdots \\ 1 \end{array} \right]$$ = (34)

and recalling that the number of 1's in the de Bruijn fragments is the number of ancestors, which ought to be the same in each fragment. Products describe the ancestors of sequences of states corresponding to the choice of fragments that were multiplied together, within which the sum of the elements still represents the number of ancestors, always the same constant. The ancestor count for M has the simple matrix equivalent,

$$\nu <\!u\,\vert M\vert u\!>$$ = (35)

. Suppose now that we have the matrix form of the characteristic polyn0mial of one of these matrices,

$$\chi(M) M^n + c_1M^{n-1} + c_2M^{n-2} + \ldots + c_n{\bf 1}$$ = (36)

. By forming the ancestor counting inner product, we conclude

$$<\!u\,\vert\chi(M)\vert u\!> <\!u\,\vert M^n\vert u\!> + c_1<\!u\,\vert M^{n-1}\vert u\!> + c_2<\!u\,\vert M^{n-2}\vert u\!> + \ldots + c_n<\!u\,\vert{\bf 1}\vert u\!>$$ = (37)

$$\nu\ (1 + c_1 + c_2 + \ldots + c_n)$$ = (38)

$$\nu\ \chi(1).$$ = (39)

From this we conclude that any connection matrix obeying uniform multiplicity necessarily has 1 as an eigenvalue.

Common sense argues that the eigenvalues should not be greated than 1, just because small matrices cannot have large eigenvalues. If a connection matrix had an eigenvalue greater than 1 in absolute value, its powers would have ever greater eigenvalues, and eventually require at least one large Gerschgorin disk to hold them. That would imply some large matrix elements to provide an ample radius, which would go against the fact that the connection matrix only has positive (or zero) integer elements, and their sum is fixed, whatever the power, at the uniform value of the multiplicity.

There is then a question of possible eigenvalues in the range between zero and one, for which the answer seems to be that between these limits it would be hard to maintain the constancy of the ancestor count with all the different combinations of powers and eigenvalues that would be found. Beginning with Sylvester's formula in its full generality,

$$\sum_{\rm eigenvalues} \sum_{\rm multiplicity} \frac{1}{j!}f^{(j)}(\lambda_i)N_i^j$$ f(M) = (40)

the formula for the ancestor count of a repeating sequence,

$$<\!u\,\vert M^n\vert u\!> \sum_{\rm eigenvalues} \sum_{\rm multiplicity} \frac{1}{j!}\lambda_i^{n-j}<\!u\,\vert N_i^j\vert u\!>$$ = (41)

By varying the power n, we have a series of equations which relate the inner product of a constant vector whose components are the matrix elements of the idempotents and nilpotents, and a series of vectors whose components depend on varying powers of a fixed set of eigenvectors. Up to a certain point such a relationship may be feasible, but if it continues there must be restrictions which need to be examined. Of course, if different powers of the $\lambda$'s were equal, only possible for $\lambda = 0$ or $\lambda = 1$, there would be no problem, and all such matrices would be idempotent or nilpotent.