Next: Evolution of a Up: Cycles in space Previous: Evolution for Rule

# Evolutionary diagrams and matrices

These evolutionary sequences could be represented by diagrams, which makes them considerably easier to visualize. According to the presentation, either the rings of cells or their symmetry classes are represented by nodes in a diagram. Nodes are linked according to whether the node at the head of the arrow has evolved from the node at the tail of the arrow or not. The result is what would technically be called trees rooted on cycles. Zero, one, or more arrows may enter a node according to the number of its ancestors. Only one arrow can leave each node, because evolution is unique, and so is the symmetry class of the descendant. However, cycles are possible because a ring could evolve either into itself or one of its ancestors.

A numerical, or at least matricial, representation of these sequences is also possible. The dimension of the square matrix is equal to the number of nodes of the diagram; its elements are to be zeroes or ones. Call the matrix M, its matrix elements ; then its elements will be zeroes or ones according to whether the row nodes are linked to the column nodes. A variant of the Kronecker delta represents this alternative numerically.

Such matrices are sparse, meaning that the non-zero elements are usually few and far between. Nevertheless, even if they are not constructed explicitly, they are very useful for expounding certain properties of diagrams. To begin with, the well-known formula for matrix multiplication, together with the property that zero annihilates any product in which it participates, shows that

Thus has zeroes except for those elements for which the row index is connected to the column index by two links. Generally, the elements of the power of M show where there are connecting paths of exactly p steps. Of course, the non-zero elements of some of these powers may be integers greater than one, but that simply means that there are multiple paths between those pairs of nodes.

Other properties of M and its powers:

• the row sums give the number of chains leaving a node,
• the column sums give the number of chains entering a node,
• the diagonal elements tell how many loops contain that node,
• the trace gives the total number of loops.

Normally neither M nor its powers are symmetric matrices, which complicates using Sylvester's theorem to represent them. Nevertheless, since all their elements are non-negative, the classical results of Frobenius and Perron[41] apply. The principal conclusions are that:

• a largest positive eigenvalue is bounded by both row sums and column sums;
• there is an nonzero eigenvector belonging to the largest eigenvalue, none of whose elements is negative;
• under certain circumstances this eigenvalue is unique, with a unique normalized eigenvector.

These results can be used for estimating the behavior of large powers of M, and thus the general characteristics of long chains.

Next: Evolution of a Up: Cycles in space Previous: Evolution for Rule

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