Test procedure

It is evidently possible to check the powers of more and more complex words to see whether there is a possibility of inversion; If admits inversion for some particular values of n, can be tested, then , and so on, always noting the least common multiple of the admissible values. Eventually enough combinations may be examined to reach a decision: some word is impossible to resolve, or enough words have been analyzed to know that there is a length of neighborhood for which the ancestor is unconditionally unique, and the inverse Rule can be read off according to the sequences of s and s in which the unique values occur---e.g., if the middle letter in each element of the symbolic matrix is 0, for inverse evolutionary function .

Fortunately there is an upper bound to the lengths of words which must be tested, making eventuality a certainty. Consider the matrix product corresponding to a particular counterimage; given that the pth letter is the same for all the words in the full product, let be the pth factor. Decompose into a sum in which contains the symbols which will be lost, and those which will survive; must vanish leaving . There may be symbols common to and , but must contain one and only one of them, 0 say.

We are interested in showing that an excessively long or can be shortened; such a demonstration would be akin to shrinking a long path through the vector subset diagram by excising loops, whereby a loop free path would be minimal. But that is not the way to our proof, which is independent of the diagram. Rather, note that our matrices are sparse, in their numerical version all matrix elements are zeroes or ones, with exactly k ones per matrix. All their possible products are postulated to have the same property; yet there can only be just so many such matrices of a given dimension.

Some of them are original de Bruijn fragments, others exist only as products, but each of them will have a product of shortest length generating it. Let N be the maximum length of the shortest products generating the multiplicative closure of the de Bruijn fragments. Now replace both and by minimal equivalents through the process of converting them to numerical form, finding the minimal product, and forming the symbolic product all over again. This will naturally shorten and alter any ancestors being represented; call the new products and .

The important property of these new chains is

since the vanishing of the products depends on the placement of their nonzero elements and not their value, even when it is symbolic. In turn new position is guaranteed for which every matrix element

has the same symbol for its th letter, all within a neighborhood of no greater length than 2N+1.

It may still happen that every ancestor has a position with a unique ancestor, but that the positions do not coincide. But then padding may be inserted to extend the neighborhood either to the right or to the left in such a way as to give them all a common centering. Should this be necessary one will simply have an inverse rule which is insensitive to the values of certain cells.

In practice none of this rearrangement has to be carried out; the possibility that it can be done simply shows that there is nothing in a very long or irregular neighborhood whose equivalent would not already have been encountered in a systematic sweep through short neighborhoods.

Harold V. McIntosh