ancestors and symbolic de Bruijn matrices

By de Bruijn matrixde Bruijn matrix we understand the connectivity matrix of the de Bruijn diagram. Actually there are several de Bruijn matrices according to whether the diagram is labelled or not, and to whether it is taken as a numerical matrix or a symbolic matrix. Accordingly, the $A$ matrix is the part of the de Bruijn matrix labelled according to evolution bearing the label 0, just as the $B$ matrix goes with the label 1. In the case of Rule 110, these matrices are:

A matrix	B matrix
$\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right]$	$\left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{array} \right].$

As we see, the A matrix is idempotent, largest eigenvalue 1, and just three nonzero elements, two of which are diagonal (00 $\rightarrow$ 00 and 11 $\rightarrow$ 11) with the other one at 10 $\rightarrow$ 00 which is only operative in non-cyclic contexts. That means, the only way to get zeroes is to have zeroes, let a solid string of ones evolve into zero, or to have 1 as a left fence without worrying what lies beyond (lots more 1's, for example).

The largest eigenvalue of $B$ is a little larger than 1.32, just less than $\surd 2$, The number of ancestors of a line of ones doubles by adding between 2 and 3 new cells.

The matrices $AB$ and $BA$ are nilpotent, so that there is no point trying to develop long sequences in which 0's and 1's alternate. So much so that 01010 turns out to be the shortest excluded sequence. Following the same route, the regular expression 00*100*10 corresponding to a pair of isolated 1's, is also ancestorless, as are numerous other sequences.

With a view toward understanding the occurrence of large triangles, consider powers of the matrix $B$, which should converge towards the product of its Perron eigenvectors. Its $14^{th}$ power, as shown in the table below, has the convenient number of 200 ancestors, readily permitting the approximate factorization also shown there.

$B^{14}$	factored, normalized
$\left[ \begin{array}{cccc} 0 & 16 & 21 & 12 \\ 0 & 21 & 28 & 16 \\ 0 & 16 & 21 & 12 \\ 0 & 12 & 16 & 9 \end{array} \right]$	$\left[ \begin{array}{c} 0.25 \\ 0.30 \\ 0.25 \\ 0.20 \end{array} \right] \left[ \begin{array}{cccc} 0.00 & 0.30 & 0.45 & 0.25 \end{array} \right].$

The one really clear conclusion is that 00 can never be the trailing edge of an ancestor of a string of 1's. The remaining possibilities are fairly evenly distributed, with a slight preference for beginning 01 and ending 10, and a significantly slimmer chance (1/3 less, roughly) of being surrounded by 11's.

The mixture does not change appreciably between even and odd chains, as would be expected from the uniqueness of the Perron eigenvalue. If the second eigenvalue had been large, an alternation of generations might have been observable in short chains.