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