The second moment

To obtain an ancestor census directly, it necessary to deal with k different matrices together with all their possible products; their compliance with the general properties of nonnegative matrices is frequently complicated by their reducibility. Fortunately the single matrix N characterizing the second moment subsumes the properties of all these individual matrices and their products; discovering its general properties avoids most of the more detailed calculations, although its own reducibility is still a possibility.

The basic conclusion that the eigenvalues of N lie in the range from to is quite easily established.

The lower limit follows from the fact that the diagram of identical pairs, is a subdiagram of the diagram of arbitrary pairs, . The de Bruijn matrix of the former, whose maximum eigenvalue is , is a principal submatrix of the pair matrix, whose maximal eigenvalue must therefore be equal to or greater than . Since the lower limit corresponds to zero variance, it can only be reached when each of the matrices contains exactly links (and thus N contains exactly links); a necessary but not sufficient condition.

The upper limit follows from Gerschgorin's theorem, taking into account the fact that there are at most incoming (or outgoing) links from any node in the pair diagram. However, if each node has that many links, all neighborhoods must evolve into the same state, so that the upper limit is associated with automata evolving to a constant field within one generation.

The tables of Sec. 9 confirm these limits, as well as showing a general distribution of eigenvalues reflecting the number of ways that the total number of states of any given cell can be partitioned amongst the individual states.

---

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