The de Bruijn fragments
Once there are matrices from which the properties of counterimages may be deduced, the
deduction usually takes the form of ascertaining eigenvalues, and occasionally,
eigenvectors. For example, according to whether the largest eigenvalue 
of 
is greater than, equal,
or less than 1, the number of counterimages will inevitably increase, remain stable, or
decrease. As it lies in the range from 1 to k, the rate of increase will
range from modest to drastic.
The statistical Gerschgorin theorem, Eq. 26, estimates 
as 
(| |
denotes cardinality), which would yield a value of 1 only for balanced
counterimages. Although this estimate is subject to considerable variation, it gives a
good indication of the degree to which a configuration profits from having cells with
numerous ancestral neighborhoods.
Setting aside considerations of eigenvalues for the moment, consider the sum 
; its value for each matrix or product of matrices is
a nonnegative integer. Its least value m surely satisfies
and could well be as small as zero --- the Garden of Eden case.
Consider further a configuration whose cells were in states 
, the number of whose ancestors would therefore be 
for
The extended configuration produced by adding one additional cell at the right in state
i will have 
ancestors; then the expected
number of ancestors averaged over all such extensions is
because the 
sum up to the de Bruijn matrix,
whose eigenvector u has the eigenvalue k.
At this point, note that averages lie between the maximum and minimum of their data, reaching either extreme only if all the data are equal. This is the first part of Dubois-Violette and Rouet's [35] result. Such being the present situation, any single (and by induction, finite) extension of a minimal ancestor configuration also has a minimal number of ancestors.
In the worst case, an extended Garden of Eden is still a Garden of Eden, an observation already clear from the subset diagram, not to mention the consequence of multiplying by a zero matrix. The main point of this new result is that it is not possible to gain ancestors by taking longer configurations, then suddenly lose them; at least not for minimal configurations within a de Bruijn diagram. For others, counterexamples exist.
Although the proof shown is right sided, the left sided version is entirely similar. The proof is also completely symmetrical between maxima and minima, with the difference that a minimum is assured whereas a maximum is not.
The foregoing analysis then establishes the set 
consisting of all P for which 
takes the minimum value as a two sided ideal. By this we simply mean
that
If 
exists, it too must be a two sided ideal;
from
and taking n as the maximum number of counterimages follows
The existence of ideals makes it hard to find matrices which are not absorbed into the
ideal because those lying outside the ideal can only be formed from certain products of 
; of course when m=0 the subset diagram
provides a map showing just which matrices to choose and which to avoid. Furthermore,
multiplication by zero is a drastic action whose role in defining ideals can be readily
understood, but one might conjecture that those are the only kinds of ideals that there
are. In other words, ideals depending on m>0 would have to be null or else
encompass the whole space.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx