Symmetry by permuting states

As the use of the complement in creating these examples shows, a tensor square can be further refined if the basic diagram has an isomorphism, which is to say a permutation of its nodes resulting in the same connectivity matrix; for binary automata such an isomorphism results from complementing the individual cells. For k>2 there are increasing numbers of isomorphisms, in fact, whose presence can be detected in the full de Bruijn matrix and all the other moment matrices associated with it. Nevertheless if an individual rule lacks some or all of this symmetry, it will be missing from N and its analogues.

The pair matrix of Sec. 3.4 can be rearranged along these lines, which is to say that it is equivalent to the following matrix, gotten by listing first all the pairs of the form , last all the pairs of the form , which is the only other permutation of binary values. The remaining pairs are laid out symmetrically in the middle.

As before, the possible pair matrices all conform to a common pattern, which arises for either Rule 0 or Rule 255. Since the pair links to the pair only if a links to c and b to d via the same symbol, the pairs of pairs actually linked will vary from rule to rule. Furthermore there are some additional symmetry requirements for the formation of pairs: if links to , then must link to and a similar requirement due to transitivity.

With this new ordering, the pair matrix for Rule 22 becomes: (1's belong to the actual pair matrix, while 's indicate the extent of the maximal possible matrix)


The submatrix in the upper left hand corner is always present for whatever Rule (the lower right submatrix is filled out for Rule 150, just as it would be for any other rule symmetric by conjugation), no matter what other elements are deleted from N on account of the structure of and . Accordingly, no row sum can exceed 4, so by Gerschgorin's theorem, the largest eigenvalue of N will be bounded by 4. The limit can only be reached if all row sums are equal, thus only for Rules 0 and 255 (evolution into constants).

On the other hand the diagonal submatrices have a uniform row sum of 2, which must be their largest eigenvalue; alternatively the first and last are just de Bruijn matrices, from which the same result follows. By a theorem in Gantmacher [11], this establishes a lower limit for the greatest eigenvalue of N, which must exceed the eigenvalues of any principal minor.

Of course there is an especial interest in conditions in which this lowest limit is maintained; so far it has not been possible to characterize the matrix N sufficiently to decide other than in special cases or by numerical calculation. The general result of Sec. 10 is the best known, that the minimum eigenvalue which already implies surjectivity, implies uniform distribution. The converse is not valid, most uniform distributions lead to higher eigenvalues.

Harold V. McIntosh