From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Sat Jul 10 1993 - 02:47:54 UTC
Commentary related to Andrew Wuensche and Mike Lesser's book, 'The Global
Dynamics of Cellular Automata.' Addison-Wesley, 1992 (ISBN 0-201-55740-1)
continues. The time has come to investigate Z.
We are basing our commentary on the A and B matrices into which the de Bruijn
connectivity matrix for any binary rule splits. Consider Rule 193, featured
in the text on page 40 of the Atlas; its AB pair is:
0 1 0 0 1 0 0 0
A = 0 0 1 1 B = 0 0 0 0
1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1
For A, the vector of column sums is (1 2 1 1), of row sums it is (1 2 2 0).
The column average is 5/4 = 1.25, the second moment is 7/4 = 1.75, giving a
sigma(c) = 0.433. For rows the average is also 5/4 = 1.25, with second
moment 9/4 = 2.25 and sigma(r) = 0.81 approximately. Using columns seems
preferable.
Earlier we stated a 'Statistical Gershgorin Theorem' (erroneously writing
var for the greek sigma that was in the original source):
lambda = gamma + n sigma(c) sigma(x) cos(theta)
where lambda is an eigenvalue (NOT Langton's parameter) of a matrix such as
A, gamma is 1/n th the sum of the elements of the matrix (and IS double Langton's parameter when the majority state is quiescent). N is the number
of rows in the matrix, here 4, the sigmas refer respectively to column sums
and the eigenvector, and theta is the angle between their vectors of residuals.
Interestingly, this angle must be EXACTLY 90 degrees for reversible automata.
Up until now, we have drawn some conclusions based on using gamma while
discarding the companion term; but all discrepancies noted are exclusively
due to the correction. The discrepancies seem to follow a regular pattern,
small but typically non-zero.
It will be noted that the A and B matrices have three kinds of rows (and
columns as well). They can be zero, unit vectors, or contain a pair of ones.
The general format is forced by the structure of the de Bruijn diagram,
being just the number of out links (in links) per start string (stop string).
Given more states than a binary automaton possesses, there will be more links,
and so a greater variety of rows or columns; but the unit vectors signal
situations in which just one single continuation is possible.
The unit vectors are significant, being what the Atlas calls deterministic;
the fraction of them taking both A and B into consideration is Z. One is
allowed to choose between rows or columns, so as to get the larger of the
two numbers.
For Rule 193, there are altogether 2 unit rows and 6 unit columns. Therefore
Z = 6/8, or 0.75, whereas the (Langton's) lambda is 5/8, or 0.625, yielding
the lambda ratio 0.75 duly recorded in the Atlas, page 157.
Estimating the largest eigenvalue of A produces 1.324, which can be compared
to the quotient of maximum preimaging for 15 and 14 member rings (p. 157),
which is 68/51 = 1.333. Again, the agreement is exemplary.
Comparing fairly modest powers of A reveals the eigenvectors of this
eigenvalue; normalized they are: column, (0.246, 0.323, 0.430, 0.000),
row, (0.184, 0.323, 0.246, 0.246).
Residuals for the column sum are (-0.25, 0.75, -0.25, -0.25), residuals
for the column eigenvector are (-0.004, 0.073, 0.180, -0.250). The inner
product of these two vectors give directly the correction to gamma, and
is 0.072. Almost exactly what is expected, 1.250 + 0.072 = 1.322, the tiny
discrepancy is surely due to the care (or lack thereof) taken in arriving
at these numbers.
The L^2 norm of zero-average vectors is their standard deviation without
averaging, which accounts for the factor n in the statistical theorem, so
we quickly arrive at a value of cos(theta) of 0.271, or a theta of about 74
degrees. We already knew sigma(c) = 0.433; we readily calculate sigma(x) = 0.157, so we have identified all the quantities in the formula.
1,322 = 1.250 + 4 * 0.433 * 0.157 * 0.271
There is an interesting, although possibly trivial, way to place Z in this
formula. Create the supermatrix from A and B that was once mentioned:
0 1 0 0 . . . .
0 0 1 1 . . . .
1 1 0 0 . . . .
A . 0 0 0 0 . . . .
. B = . . . . 1 0 0 0
. . . . 0 0 0 0
. . . . 0 0 0 0
. . . . 0 0 1 1
It is not such an artificial creation as might be feared: from graph
theory it is the connectivity matrix of the least upper bound (union) of
two graphs; one is the de Bruijn diagram with 0-ancestor links, the other
is the de Bruijn diagram with 1-ancestor links. Nodes in a union are
linked when there are links in either one (or both) of its two constituents.
The vector of column sums is (1 2 1 1 1 0 1 1). The average of column sums
is 1, composed from 0's, 1's, and 2's; every 0 is paired with a 2. Thus the
vector of residuals, (0 1 0 0 0 -1 0 0) will contain -1's, 0's, and 1's; the
sum of their squares will be eight minus the number of columns which were unit
vectors, so the average of the sum is 1-Z. Sigma squared is the second moment
taken with respect to residuals, so sigma(c) = sqrt(1-Z). When Z=1, as for
reversible Rules, the standard deviation is zero; when Z=0, as for the Zero
Rule, the standard deviation is 1.
The supermatrix now encompasses both maximum and minimum rates of growth;
being partially diagonal its eigenvectors are those of its blocks, extended
to the other block with zeroes, and the statistical theorem still applies to
all eigenvalues. Because of the increased dimension, each eigenvector will
be the same as before, but its mean will be reduced by half (to 1/8) because
of all the new zeroes, while its second moment s^2 will be shifted by 1/64
and scaled by 1/2. Finally, the supermatrix has eight rows and always has
eight ones distributed throughout. So the new formula is
lambda = 1 + 8 sqrt(1-Z) sqrt(0.5*s^2 + .01561) cos(theta*)
where we still have to contend with a new angle theta* whose cosine we
calculate to be 0.482 (about 61 degrees). The equality is nearly as good,
1.321 = 1.000 + 8.000 * 0.500 * 0.167 * 0.482
Just as the extended eigenvector is gotten by filling with zeroes, the
extended vector of sums is gotten by adjoining 2u-x (making for the average
of 1 and variance Z), where u is a vector of 1's and x is the vector to be
extended. The extended vectors of the Union Matrix therefore have the same
inner product as the original vectors. Nevertheless, the residual vectors,
from which theta* is calculated, are slightly different; anyone who wanted
an explicit relation between theta and theta* could work out the algebra.
Critics may question the utility of the formulas that have been displayed;
it remains to be seen to what extent the standard deviations and angles are
consistent within families of automata, or whether they can be transferred
from one automaton to another.
Nevertheless we have constructed a framework into which Langton's parameter
and Z both fit, as algebraic quantities relating to the growth factor for
maximal counterimaging.
More commentary will follow.
Harold V. McIntosh |Depto. de Aplicaci'on de Microcomputadoras
mcintosh@redvax1.dgsca.unam.mx |Instituto de Ciencias/UAP
mcintosh@redvax1.bitnet |Apdo. Postal 461
(+52+22)43-6330 |72000 Puebla, Pue., MEXICO
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:18 UTC