Counting counterimages
A vector subset diagram whose links have been labelled according to the evolution of an automaton allows the gathering of fairly subtle information. Its powers classify the counterimages they are counting exactly by initial and terminal partial neighborhoods, in addition to lumping them into subsets as the scalar matrix does.
Often this is a more elaborate classification than is needed; what really count are the de Bruijn fragments comprising the submatrices, classifying ancestors according to their initial and final partial neighborhoods. Generally further sorting by subsets of partial neighborhoods only serves to identify and count the Garden of Eden configurations quickly.
For example, continuing to use the example from Rule 126, the de Bruijn product for the
sequence 
is
0.50em
which makes it clear that an infinite quiescent configuration has exactly two
ancestors, itself and 
; in any event, 01 and 10
are excluded both as initial sequences and as final sequences from finite configurations
such as on a ring. Of course, this information can also be elicited from the scalar subset
matrix by looking at all the paths originating from unit classes.
Counterimages can be counted three ways: quiescent at infinity, cyclic, or completely
general. Let 
be a typical product of de Bruijn
fragments generating the counterimages of a configuration; then
where q is the completely quiescent partial neighborhood, yields the number of
counterimages quiescent at infinity. The single nonzero element of the projection operator
occupies the qth position on the
diagonal; the trace formulation provides a uniformity of treatment for all three cases.
For a cyclic automaton, it is appropriate to recognize that a cycle must begin and end on the same partial neighborhood by calculating (for unit matrix I)
Finally, the appropriate unrestricted formula would be
where u is a vector, U a matrix, solidly filled with 1's. In fact, all three counts can be described by either a trace or an inner product, both of which are linear functionals for matrices.
Taking into account all possible products representing ancestors of a configuration of length n requires evaluating
but a+b=D, the de Bruijn matrix which satisfies DU=kU and 
. Altogether, then,
The unsurprising average of ancestors per configuration being 
, whenever some configuration has fewer, another must have more. When the
imbalance is sufficiently severe, Garden of Eden configurations are required to compensate
the configurations with multiple ancestors---a trivial result for finite automata but with
interesting consequences for infinite automata.
The second and higher moments of the distribution of counterimages can be obtained from
some additional matrix algebra. In the following sequence of substitutions, let P
be one of the 
(noncommuting) factors in the
expansion of 
.
If 
is the dominant eigenvalue of 
, a term proportional to 
will result for large n.
Higher moments will depend on higher tensor powers of a and b, while the
same formula persists with a suitably subscripted 
and 
; for example
In another direction, if the connectivity matrix had been decomposed into three classes of links a, b, and c, the second moment would have taken the form
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx