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.