Next: ancestors (5) Up: Ancestors: Commentaries on The Previous: ancestors (3)

# ancestors (4)

Commentary on Andrew Wuensche and Mike Lesser's new book, ``The Global Dynamics of Cellular Automata.'' Addison-Wesley, 1992 (ISBN 0-201-55740-1) continues. We have discussed how to form a de Bruijn diagram for a cellular automaton rule, its connectivity matrix, and how evolution splits the matrix into submatrices, which can be used to count ancestors. The rows and columns of the de Bruijn matrix are labelled by Wuensche and Lersser's ``start strings,'' but the columns are really ``stop strings.''

To fix ideas, consider the two matrices for Wolfram's (2,1) Rule 252, which is associated with rules 3, 17, 63, 119, 238, 192, and 236 in the Atlas, on pages 128 and 129.

At first sight, the basins for Rules 3 and 252 look completely different, but an examination of these matrices shows why it is sensible to consider them jointly (actually, to pair 252 and 192) - their only difference lies in exchanging the A and the B matrices. Therefore, they will have identical statistics, with 1's and 0's exchanged. In other words, ancestors will proliferate similarly, although their cycles and periods may be different.

The other two operations which the authors consider, reflection and complementation, also have their repercussions. For example, reflection exchanges the start neighborhoods 01 and 10, while complementation does this, exchanges 00 with 11, and exchanges A with B. None of these things changes norms or eigenvalues. Persons familiar with matrix theory will see that the matrices representing these exchanges will commute with the A, B pair, and that they will constitute a symmetry group. A sort of supersymmetry can be achieved by making a bigger matrix having A and B as submatrices, but we will not make further use of the possibility.

There is an extensive theory of positive matrices, just as there is of integer matrices. Matrices in general can be associated with graphs; their nodes are the indices, which are linked according to whether the matrix elements are zero or not. This means that nonzero elements in the product of matrices are associated with chains in the diagram. The relationship is useful when some properties are more evident in one context than in the other. For example, the matrix is partially diagonal when the graph consists of two disjoint parts. Blocks of zeroes correspond to attractors (into which links may enter but cannot leave) and dispersors (links leave but do not enter). Conversely, statistics concerning the graph often have nice matrix formulas, and in general properties of graphs can be worked out in a computer whenever they have a formulation via matrix algebra.

Two important properties of matrices are, on the one hand, their eigenvalues and eigenvectors, and on the other, their norms. The two are related, but the relationship is more complicated when the matrices are not symmetric, so that attractors and dispersors can be present. The norm is not a perfect ``absolute value'' because the norm of a product is only less, not necessarily equal, to the product of norms. For purposes of analysis and calculating limits, the inequality is entirely satisfactory, but it is less favorable when exact counts are required.

The matrices A and B count the ancestors of a single cell, and catalog them according to the start and stop strings constituting the neighborhood. It is a fundamental reality of cellular automata theory that there are always more cells amongst the neighborhoods than the number of cells being considered; this shows itself when we use a matrix rather than a scalar to do our counting. If A and B count the ancestors of a single cell, we expect their products to count the ancestors of a sequence of cells. A matrix is still called for, because marginal cells always remain, however long the chain.

The de Bruijn matrices for (2,1) automata have both norm 2, and largest eigenvalue 2, and these quantities are always larger than those of any of the fragments into which the matrices decompose. The value 2 corresponds to doubling the total number of configurations every time a single cell is added to the automaton.

Consider the formulas for counting (within the limits of pure ASCII). If M is the connectivity matrix of a graph, let u be a vector of ones, and i be a unit vector in the coordinate. Let designate trasnspose. Then i Mj is the element, the number of links from i to j, while i Mi is the number of loops starting at i. Their sum is the Trace of M, yielding the number of loops altogether (with a possible multiplicity according to their length). The product u Mu is the number of links altogether, no restriction. q Mq is the number of paths beginning and ending with a quiescent state, q.

All three of these formulae can be written as traces, in the form Tr( GM), with a suitable metric matrix G. To count everything, G= uu; for periodicboundary conditions, G= I, the unit matrix, and for configurations quiescent at infinity, G= qq. Among other things, this means that the choice of a boundary condition is not very essential to a calculation. It only enters at the last moment, in the selection of the metric matrix. But the essential qualities of the matrix, as represented by its eigenvalues and eigenvectors, expressing such things as rates of growth, are not affected by the boundary condition.

Suppose that we want to count configurations. We must add A and B, which always results in the de Bruijn matrix D (which has a rather simple characteristic equation - , because , ). So, for cyclic boundary conditions in a ring of circumference s, , which is so unsurprising that it might be considered boring. But it is almost the only result that we are going to get free.

Counting is good for getting averages. But suppose we want variances. Then it is necessary to sum squares. That is where matrix theory is really going to shine. We need , which turns out to be , which in turn is . Extracting the constant factor , we have to calculate . Here indicates a tensor product, which is a way of compounding matrices that will be found in books on matrix theory.

A certain amount algebraic manipulation ends us up with a formula for the second moment when the de Bruijn matrix is split into A and B; namely we need a trace involving , (rather than ) in a ring of circumference s. These commentaries aren't the place for mathematical derivations, but the details are available in a pair of preprints that anyone can have by sending a mailing address (including zip code, city, country, etc).

A tensor square has an interpretation as a graph; it is nothing other than the graph of ordered pairs taken from the graph of the original matrix. (There is also a symmetrized tensor square, and an unordered-pair graph). This relationship is intimately related to Niall Graham ( niall@nmsu.edu)'s assertion of 21 Jun 93 14:55:27:

>
> A 1-dim CA is reversible iff the pair digraph of its
> associated finite automaton is acyclic.
>

More commentary will follow.

Next: ancestors (5) Up: Ancestors: Commentaries on The Previous: ancestors (3)

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx