Use of the pair matrix

Most of these conclusions can be summarized by referring to the pair matrix once again. Nasu [8] outlines such a process, referring also to the concept of definite automata [37], which is explained at some length in Zvi Kohavi's textbook [38] on automata theory. He uses the unordered pair matrix, but the conclusions are the same.

If a path is started in the subset of distinct pairs, it may remain within that subset or it may wander into the subset of identical pairs; if it does so there must be no possibility of returning to the original starting point. Otherwise the pair matrix would not have the minimum eigenvalue required for zero variance and surjectivity.

In the case that the path remains within , it must eventually close into a loop, demonstrating that there must exist configurations with two different ancestors. No matter that some paths may wander into ; the rule cannot be injective. The alternative, that no path originating in remains in , means that it is eventually trapped in . Subsequent return to would force a second visit to , in violation of zero variance. For such automata, cannot be two ancestors, distinct except for their initial and terminal segments. This is the true case of injectivity.

Rules which are not injective, but lack the full multiplicity which is theoretically possible can be detected by using a diagram of triples or higher multiples; whether there are subsets of degenerate multiples which trap the trajectories must be investigated.

Harold V. McIntosh