We continue our commentary on Andrew Wuensche and Mike Lesser's new book, ``The Global Dynamics of Cellular Automata.'' Addison-Wesley, 1992 (ISBN 0-201-55740-1). In previous episodes, the role of diagrams in describing the evolution of automata has been mentioned, especially the evolution diagram, (of which their computer program generates the nice examples shown in the Atlas), and the de Bruijn diagram, which they do not mention, but which can be used to calculate ancestors.
For Wolfram's (2,1) Rule 22, this leads to a pair of 
matrices,
Note that both are partially diagonal, although in different ways. For A this says that a zero neighborhood is a counterimage of zero, but then if you try to extend it, you can't ever have any ones. Of course; ones are expansive for Rule 22. The other component has maximum eigenvalue 1.459, which is the growth factor for long configurations which vanish instantly. The configurations which it generates had better not have pairs of zeroes. The greatest growth factor for any rule is 2.0, the maximum row or column sum for these 4x4 de Bruijn matrices.
The second matrix, B, has a cube root of the unit matrix in its upper left hand corner. This means that you can never use the neighborhood 111 in a counterimage of pure ones, and that the fragments 01, 10, and 00 must always run in cyclic order. The eigenvalues of this corner have absolute value 1, so the number of counterimages of pure 1's is always the same, no matter how long or short the ring.
In general, it is arbitrary configurations whose ancestors are sought, not pure strings. However, we know that there is a norm for matrices, related to the absolute value of their largest eigenvalue, following which the norm of a product is always less than the product of the norms (but equal when the factors commute). This means that the state with the largest fraction of ancestors is always going to get the lion's share of the ancestors, exponentially following that majority's share of the configuration. So it is, that configurations in Rule 22 have few ancestors unless they have lots of zeroes, as we see by turning to page 96 of the Atlas. .
The de Bruijn pair for the famed stochastic Rule 30 is
Note that Rule 30 is a one-bit mutant of Rule 22, differing only in the behavior of neighborhood 011, and thus the assignment of the link 01 - 11. However, the Perron Eigenvalues of both matrices are 1, so that the number of ancestors will be expected to remain constant for all configuration lengths. Compare the attraction basins on page 144 of the Atlas.
Now we have set the stage for thinking of the possible relation of the Z-parameter and Langton's lambda parameter to the matrices derived from the de Bruijn diagram. Nevertheless we should introduce the characters and outline the plot before proceeding with the show.
The nodes in the de Bruijn diagram are called ``start strings'' in section 3.4.1 of the Atlas, left or right according to the direction of arrows connecting them. In all ancestor calculations, the possible variety of start strings lends an ambiguity which tends to persist; reversible rules are only possible when this ambiguity can be shown to be irrelevant, even when all the other factors are favorable.
When every row (alternatively, every column) of a de Bruijn diagram contains a single 1, we have one of the ``limited preimage rules.'' By Gerschgorin's theorem, the eigenvalues of such matrices are bounded by 1 (and according to Perron, the maximum eigenvalue is exactly 1), all of which is in accordance with the experience that counterimages not proliferate excessively, thereby justifying the adjective chosen in the Atlas.
Note that the eigenvalues represent an asymptotic rate of growth, and that boundary conditions have to be taken into account. Thus there are Gardens of Eden in the Atlas even when growth factors are unity. Generally we would expect that if some populations grow, others languish, to maintain constant the total number of configurations. But in finite systems, the constraints are more exacting, and can produce an occasional vanishment which might not be found in an infinite system.
Cyclic boundary conditions correspond to the diagonal of the de Bruijn matrices, because the ``start string'' is the same as the ``stop string.'' Individual matrix elements correspond to choosing one particular start, and one particular stop. For infinite chains all elements must be considered, whereas for configurations which are ``quiescent at infinity,'' the (q,q) element is the relevant one (q the quiescent state).
It should be explained that the theory here outlined is inherent in the
Atlas' list of references, particularly in the work of Erica Jen
there cited, and in articles of Stephen Wolfram, also cited. The principal
difference is that Jen's work is phrased in terms of recursion relations,
not matrix theory (although she exhibits them and describes their use).
Furthermore, the nicest theorems do not seem to result from matrix theory
alone. The advantage of a matrix-oriented point of view is that it leads
naturally to eigenvalues and eigenvectors, or whatever it is that they
signify in the particular application. Here, it is rates of growth in the
number of counterimages with respect to the length of the ring of cells.
Eigenvectors are less important (the principal eigenvector can be scaled
to get positive real probabilities), but they would have exact rates of
growth.
More commentary will follow.