Discussion originating elsewhere concerning the construction of reversible automata and the existence of Gardens of Eden has pointed up the fact that by not taking up the AB = 44 case in any detail in our recently concluded series of commentaries ``ancestors-(n),'' we have missed a good opportunity to discuss the reversibility question. In order to make use of all the background developed in the earlier series, one could insert the present posting between ancestors-(13) and ancestors-(14).
The Uniform Multiplicity Theorem assures us that the number of ancestors of all configurations must be the same if an automaton is to be reversible. This may represent a surprise for someone who has relied on calculating the subset diagram to find out whether an automaton has a Garden of Eden, but once the theorem is known, far fewer automata have to be contemplated. For (2,1) automata, there are 8!/(4! 4!) = 70 balanced Rules, for which AB = 44 in the nomenclature of the ancestor series; this number is much less than the 256 total, and is still further reduced into 16 of Wuensche and Lesser's clusters.
The rate of growth of ``maximal preimaging'' is related to, but not necessarily equal to, the eigenvalues of the A and B matrices. When A and B are different, one of them usually dominates, the other can be disregarded, and the largest eigenvalue of the dominant member is nearly always the number sought. When the number of nonzero elements in A and B is equal or nearly equal, both are candidates, although one of them may still dominate. If that happens, there WILL be a Garden of Eden, and the situation is similar to all the others, even though growth rates will be smaller than otherwise.
The expected eigenvalue, for both A and B, is 1; even when that is true, the eigenvalue of AB or BA may be greater than 1, so there is still a Garden of Eden, but maximal preimaging will occur for strings of 010101... rather than for strings of 000000.... or 111111... And even when AB and BA have unit eigenvalue there is still AAB, ABA, ... and so on. We were unsure that such would happen before completing this analysis, but examples will be seen in the table which follows.
To interpret these results, the actual de Bruijn fragments - the A and B matrices - have to be examined. There are 16 row-stochastic pairs among them, and 16 column-stochastic pairs. That they will have maximum eigenvalue 1 and u as an eigenvector is a foregone conclusion. At the same time there are 4 doubly stochastic pairs, which are counted doubly amongst the singly stochastic matrices. Altogether, then, there are 28 stochastic matrices, almost the full complement of 30 variance-zero Rules. The remaining two come from cluster 51 consisting of Rules 51 (complementation) and 204 (identity).
The great majority of the A and B matrices in this table have eigenvalue 1, but also, they all show the Jordan form to one degree or another. There are several instances where the eigenvalue of AB or BA exceeds 1, but a similar number require longer products before matrices with strict growth factors occur.
We need a definitive assessment of the relationship between spectral radius and spectral norm. On one hand, we know that the spectral norm is the square root of the spectral radius of the product of a matrix by its transpose, and that the spectral radius is less than or equal to the spectral norm. That is because the maximum amplification of any vector bears that relation to any specific amplification, of which the eigenvalue is one example. We also know that spectral norms are convenient because there are inequalities governing sums, scalar factors, and products which can be used in computing rigorous bounds, for all of which the spectral radius may be inadequate.
Nevertheless, there exists a representation of matrices in terms of their
eigenvectors, which is Sylverster's formula. In the most general case, there
are idempotents Gi constructed from eigenvectors, and ladder operators Ni,
constructed form principal vectors, such that for a matrix A with eigenvalues
, and any function (representable by a power series) f,
The number of derivatives required is no larger than the dimension of the matrix; for estimating ancestors, the function f would be a large power. That leads to domination of the sum by the largest eigenvalue, but it will not eliminate the contributions of the derivatives, which may be of comparable magnitude to the leading term. If the largest eigenvalue is less than 1, we may correctly assume that the assemblage will tend to zero, but the fact of the matter is that for the ancestor application, the eigenvalue is 1 or larger, with especial interest in the case where it is exactly 1.
To see how this works, consider the following matrix and its powers:
The situation is completely typical of matrices in the Jordan form, and can be observed at work in the A matrix for Rule 27 in the table above, as well as in the A matrix of Rule 46.
As for the de Bruijn diagram the matrix example represents, there are two nodes, with self-loops. In addition, one of the nodes feeds into the other. The eigenvector selects the first node, which always renews itself. Any attempt to involve the second node will overload the first, which would then have to feed the second without any compensating counterflow.
From the point of view of matrix theory then, to get uniform counterimages and therefore satisfy a necessary condition for a reversible rule, we have to look for matrices with eigenvalue 1, yet beware that they also manifest Jordan form. We also know that it is sufficient to look for them amongst rules where a = b, that is, where the Rule itself has balanced counterimages.
From the point of view of graph theory, it is possible to say a little more. Given that the elements of the connectivity matrix count paths, and we want to avoid that the number of non-zero elements in powers of the connectivity matrix increase, it is necessary to avoid branching paths. More precisely, paths which branch can never return to the node at which they branched in more than one way. In short, there cannot be two intersecting loops, otherwise long paths could proliferate by mixing them.
However, if there is not at least one loop, long paths would be impossible, and the power would reduce to zero. The criterion is then, that there must be loops, but that if there are more than one, they cannot be linked. For instance, the A and B matrices of Rule 23 have 1-cycles as nodes in 3-cycles. Rules 46 and 58 have A matrices with 1-cycles which are linked in 2 steps into the other 1-cycle. All of these rules disqualify for reversibility.
Among those which do qualify, there is Rule 30: the A matrix has 2 1-cycles; the B matrix has a 3-cycle. For Rule 45, A has a single 1-cycle; B has a 1-cycle and a 2-cycle. The reason that these Rules are not reversible is seen in the pair matrix: the number of counterimages is uniform, but they can be completely different.
The additional requirement is that the entire discrepancy in multiple counterimages occur ``at infinity'' which is to say, in a limited part of the outer boundaries of the string. This requires that there be one single image of the de Bruijn diagram - the diagonal - in the pair diagram. For the Rules mentioned, there are viable loops outside the diagonal.
To confirm that the criterion is a good one, the reversible Amoroso-Patt (2,3/2) Rules may be examined: one of them is 0000 1111 0100 1011; its A and B de Bruijn fragments have a single 1-cycle.
Another example is Kari's (3,1/2) rule 001 110 222, for which the A, B, and C fragments each have a single 1-cycle.
Sadly, this charming graphical procedure is not overly amenable to being automated. That is, the computational way to find out where the loops are is to raise the connectivity matrix to powers and examine the traces. But once one is dealing with matrices in a computer, there are more direct and effective ways to utilize them.
For example, testing the pair matrix for an eigenvalue of 2 needs evaluation of the determinant of a readily constructed matrix, and gives the answer straightaway - variance zero means uniform multiplicity. (Constructed from all the fragments of the de Bruijn matrix, the pair matrix is less likely to have Jordan form, which should not be completely forgotten about)
In any event, although the (2,1) Rules do not include any ``non-trivial'' reversible rules, they contain a wide enough assortment that illustrations can be found for all the precepts of reversible automata theory; even the ``trivial'' cases are well worth examining thoroughly enough to understand them.
There are still other approaches to reversibility. Many persons have been attracted by the fact that the de Bruijn fragments form a hypercomplex number system; for some rules the fragments resemble Dirac Matrices or other interesting algebraic entities. There may or may not be interesting algebraic structures yet to be found.