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:
As we see, the A matrix is idempotent, largest eigenvalue 1, and just three
nonzero elements, two of which are diagonal (00 
00 and 11
11) with the other one at 10 
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
, so that the number of ancestors of a line of ones doubles every
time between 2 and 3 new cells are added.
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. In fact, 01010 turns out to be the shortest excluded sequence