## 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>2there 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 fromNand 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

alinks tocandbtodvia 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)0.3em

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

Non account of the structure of and . Accordingly, no row sum can exceed4, so by Gerschgorin's theorem, the largest eigenvalue ofNwill be bounded by4. 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 ofN, 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

Nsufficiently 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

E-mail:mcintosh@servidor.unam.mx