Averages
In fact there are three ways the sum yielding the number of counterimages can be carried out. If no importance is attached to the boundary cells of the sequence, all the elements should be summed. If the sequence is supposed to be cyclical, then the partial neighborhood with which the sequence starts should be the one with which it ends, and only the diagonal elements should be summed. Finally, if some specific boundaries are required, such as a quiescent partial neighborhood, then only that particular matrix element should be taken into consideration.
All of the summation techniques can be taken into account by choosing appropriate formulas from matrix algebra. Let
be a row vector all of whose components are ones,
its transpose, and
the matrix, all of whose elements are ones. Finally
could be a unit vector whose
component is the only one which is non-zero. Then the sum
of all elements of the matrix M is realized by the formulas
the diagonal sum
corresponds to
and the quiescent sum, assuming that q is the quiescent state, is given by
The trace formulas are especially convenient.
The average number of ancestors of a configuration of length n can be obtained from summing all the possible products of matrices representing sequences of cells forming the configuration. Such a collection is simply the result of multiplying out the ordered (because of matrix noncommutativity) product
Given that the de Bruijn matrix
for k states and l stages (l=2r by our conventions) satisfies the minimal equation
and additionally that
, from which
we have the eminently credible results that independently of n,
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx