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)
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 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
E-mail:mcintosh@servidor.unam.mx