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.