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