Mathematical Aspects


Transition and cycle matrices

Suppose that a certain Life pattern is cyclic with period N. Suppose also that the pattern is viewed in The Rainbow game with a given initial black and white distribution. Let furthermore the colour of each cell in each generation be represented by a colour index vn[j], where n represents the generation and j the cell number. It is assumed that the cells in each generation has a given ordering such that corresponding cells N generation s apart (when the pattern has resumed its original appearence) have the same cell number. The totality of all colour indices in a given generation n can then be represented by a vector vn of dimension rn, where rn is the number of cells in the nth generation. v0 is the initial distribution.
From the colouring rule it follows that there is a linear relation between the vectors vn and vn+1 which can be expressed by means of a transition matrix Tn such that
vn+1 = Tnvn.
Hence Tn is a rn+1 x rn-dimensional matrix.
The rows of transition matrices for the Game of Life are either of type:
one 1 entry in the diagonal and 0 elsewhere, or:
three 1/3 entries and 0 elsewhere.
Hence all row sums are equal to 1, a property which is preserved under multiplication with other transition matrices.


It should be clear that the present linear algebraic approach is applicable also to other cellular automata.
Here is a simple Life example.

Since the period of the pattern is supposed to be N it suffices to study the N transition matrices T0,...,TN-1.
Let A = TN-1TN-2...T0. (product of matrices).
Then we have v' = Av, where v' represents the colour indices of the same pattern as v after the completion of a full cycle. A is called the cycle matrix of the pattern and contains important information on the genetic aspects. It is quadratic with dimensions r0 x r0.

Matrices with the property that the row sums are=1 are also known as stochastic matrices in the theory of Markov chains, where the matrix components are interpreted as probabilities.

Note, however, that in this application the matrices are not used as transitions of probabilities as in the theory of Markov chains. The difference is that the transitions here are defined as v' = Av whereas in the stochastic Markov chain case the transitions are defined by
v' = vTA     (v being a column vector).



Cell types [slightly revised 040309]

The four types of cells mentioned in the genetic section can be defined in terms of the cycle matrix (note that the nth cell corresponds to the nth row (and the nth column) of the cycle matrix and could be identified with the nth diagonal element): Before we treat the rotor cells we introduce the following usage:
A cell k (of the given ordering) is a cycle parent of the cell j if the matrix component Ajk is nonzero. (Remember that Ajk represents the entry of the jth row and the kth column.)
Note that a cell may be a cycle parent of itself. (The term (proper) parent of a cell should be reserved for the three cells in the preceding generation that have generated the cell in question.) Because of the identfication of corresponding cells after full cycles the cycle parent relation can be thought of as a relation between cells of the same generation.
A cell k is an ancestor of a cell j if there is a chain of cells (of the same generation) starting with k and ending with j such that each cell in the chain is a cycle parent of the following cell.
Equivalently, the cell j is subordinate to the cell k (of the given ordering) if k is an ancestor of j.
A set of cells is a communicating set if each cell in the set is subordinate to all the other cells in the set.
In terms of a matrix a communicating set is characterized by a closed cycle of 'column jumps'. A jump from column k to column j is allowed if the component Ajk (in the kth column of the matrix) is nonzero. If there is a column jump cycle starting and ending in the same column and comprising all columns related to the set, the set is communicating.

A set of cells is primary if it is a communicating set and no cell in the set has an ancestor cell outside the set.



Representation of the cycle matrix.[slightly revised 040309 and 081023]

The above definitions are used in the following representation of the cycle matrix A:
Each cell can be identified with a diagonal element in the cycle matrix.
Nonzero components in the same row indicate cycle parents whereas nonzero elements in the same column indicate cycle offspring.
Here I is the block corresponding to the stator cells . I is an identity matrix with as many rows as there are stator cells. The blocks to the right of I must be zero since the row sums are = 1 in a stochastic matrix.

P is quadratic and corresponds to the primary rotor cells. P consists of as many diagonal subblocks as there are communicating sets. The zero blocks to the left and right of P are motivated by the fact that the primary rotor cells have no cycle parents outside the set. Hence P has row sums = 1 and is therefore a stochastic matrix.

S is quadratic and corresponds to the secondary rotor cells (S-cells). From the definition it follows that each communicating block in S has at least one cell with a cycle parent outside the block (inside and/or outside S). At least one S-cell has a cycle parent outside S. This means that there is at least one nonzero component of the submatrix G or H. Hence not all row sums of S are = 1.

Neither P nor S contain any 1 entries.

The blocks G and H account for the genetic impact of stator cells and the primary rotor cells respectively. More precisely, a nonzero entry in G means that some secondary rotor cell has a cycle parent among the stator cells. Similarly, a nonzero entry in H means that some secondary rotor cell has a primary cycle parent.
The dimensions of G and H are uniquely defined by those of I, P and S.


The limit matrix

It can be proved that for stochastic matrices A with entries of the number 1 only in the diagonals, the matrix sequence A, A2,...,An,... converges to a limit matrix B.
To be precise: One also need the condition that each block of P must be primitive , a condition which is satisfied if the block is communicating (which it is by definition) and if there is some nonzero diagonal element in the block.
Conjecture: This is the case for every cycle matrix of a GoL oscillator.

In the blinker example the limit matrix B is easily computed. This fact shows that the limit problem always has a solution. I.e. if B is the limit matrix of the sequence above, it is always possible to determine the asymptotic colour indices for each cell when the initial distribution is v0.

The asymptotic colour index vector V can be computed by:

V = Bvo,
where B is the limit matrix and vo is the initial vector.

The limit matrix B can be computed explicitly in terms of the given blocks of A.
The result is:

        where

G* = (IS - S)-1G , where IS is the identity matrix of S:s size, and
H* = (IS - S)-1(HP*).
It can be proved that the limit matrix S* of the block S is the zero matrix (which implies that the inverse matrix (IS - S)-1 exists.)

P* is determined by the limit matrices P*j of the diagonal blocks Pj that build up P. Each P*j is a so called -matrix, i.e. a matrix with identical rows. The generic row of P*j is the uniquely determined positive vector bj which
(i) is an eigenvector of Pj:s transpose PTj, corresponding to the eigenvalue 1 , and
(ii) has component sum = 1.

The condition above that the communicating P-blocks be primitive is needed ta ascertain the existence of the limit matrix P*.

Properties of the limit matrix and the diffusion principle.

The result that Sn converges to the zero matrix reflects the fact that the secondary cells have zero genetic impact, i.e. a single initial black secondary rotor cell results asymptotically in an all white pattern.
Note however that a secondary rotor cells often get offspring lines that not necessarily die out (as in the case of casing stators). But their competitive power are insufficient to create durable genetic impact. This property characterizes the secondary rotor cells and could be used as an alternative definition of this type of cells.

Note also that the fact that P* is built up by diagonal blocks that are -matrices implies that the primary cells asymptotically get different gray hues, one for each communicating set, and that the colours of cells within the same communicating set tend to a common shade.

In case of the spaceships (that have no stator) it turns out that if the secondary sets can be divided into sets where the members in each set are subordinate to the same unique primary unit, even H* is built up by blocks that are -matrices. The generic row of each H*-block is the same as the generic row of the corresponding block in P* .
This means that a set of secondary cells that are subordinate to only one set of communicating primary cells asymptotically gets the same colour as the cells in the primary set.
This effect is seen in the glider and in the three standard spaceships.

A similar principle holds also if a set of secondary cells is subordinate to only one bushing stator cell. Then this set asymptotically gets the same colour as the unchanging stator cell.
This behaviour is seen in the blinker. The two outer cells, that are secondary, asymptotically get the same colour as the middle stator cell.

These observations are all in agreement with the proposed diffusion principle (in the Genetic Aspects).

Some examples of solutions to the limit problem (the glider and the toad) are found here.