[posted by Jim Propp, Fall 1999]
PART 1
Are people aware that numbers-walls (a la Conway and Lunnon) and number-
friezes (a la Conway and Coxeter) are both special cases of a lovely rule
for evaluating determinants called "condensation", developed by Charles
Lutwidge Dodgson (aka Lewis Carroll)?
Dodgson condensation begins with an n-by-n matrix and then successively
computes k-by-k matrices with k going from n-1 down to 1. The 1-by-1
matrix that you get at the end is the answer (that is, the determinant
of the original matrix). It's helpful to imagine these matrices stacked
to form a square pyramid, with the original n-by-n matrix at the base,
resting on an (n+1)-by-(n+1) matrix consisting entirely of 1's (this
is handy for getting the inductive construction of the pyramid going).
Then the rule for constructing an entry in the kth level from the top
is simple: take the determinant of the 2-by-2 submatrix that sits just
below it in the (k+1)st level, and divide it by the entry that sits
just below that submatrix in the (k+2)nd level.
Thus, to take the determinant of the upper 4-by-4 square of entries in
Pascal's triangle, we proceed like this:
1 1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 2 3 4 1 1
1 1 1 1 1 1 3 6 1
1 3 6 10 1 4
1 1 1 1 1 1 6 20
1 4 10 20
1 1 1 1 1
(E.g., in the last step we take the determinant 1*4-1*1 = 3 and divide it
by the 3 in the level below to get 1.)
What's fun about this method for taking determinants of integer matrices
by hand is that the divisons give you a way to check your arithmetic as
you go.
If you specialize to matrices like
e f g h i
d e f g h
c d e f g
b c d e f
a b c d e
in which all the entries along a diagonal are constant, and convert the
three-dimensional picture into a two-dimensional one (taking advantage
of the redundancy), you get the algorithm for number-walls.
If you instead specialize to matrices like
a 1 0 0 0
1 b 1 0 0
0 1 c 1 0
0 0 1 d 1
0 0 0 1 e
in which all the entries adjacent to the diagonal are 1's and all the
other non-diagonal entries are 0's, and again reduce from 3 dimensions
to 2, you get the algorithm for frieze patterns. (For an introduction
to frieze patterns, see Coxeter and Rigby's article "Frieze Patterns,
Triangulated Polygons and Dichromatic Symmetry" in the book "The Lighter
Side of Mathematics", edited by Richard K. Guy and Robert E. Woodrow,
pages 15 to 27.)
There are two scandals here: One of them is that Dodgson's method hasn't
become better known. The other scandal (which partly explains the first
scandal) is that Dodgson's method is incomplete, because it sometimes
leads to expressions of the form 0/0. I have not been able to find any
expositions of Dodgson's method that deal with this problem in a satisfying
way.
Here I should digress and reveal that for all k between 1 and n, the k-by-k
matrix obtained by Dodgson's algorithm is just the matrix consisting of all
k^2 of the (n-k+1)-by-(n-k+1) "connected minors" of the original matrix.
That is, if you choose n-k+1 adjacent rows of the matrix (which you can do
in k ways) and any n-k+1 adjacent columns of the matrix (which you can do
in k ways), you can take the determinant of the resulting matrix; forming
all k^2 such determinants, we obtain the matrix at the kth level from the
top of the square pyramid.
So, we can now see where Dodgson's method will fail: precisely when some
of the connected minors are singular. In particular, the method will
fail if any of the original entries are 0.
Dodgson (see Proceedings of the Royal Society of London, volume 15, 1866,
pp. 150-155) deals with this through the rather clumsy dodge of cyclically
shifting the rows and columns and re-starting the algorithm (this could
conceivably need to be done several times).
Since folks (i.e. Lunnon and Conway) are working on getting straight the
details of number walls, I thought I should encourage people to do the same
for more general determinants, using Dodgson's basic idea as the conceptual
core. A generalized Dodgson procedure might conceivably be competitive with
standard determinant-evaluation algorithms when the entries are integers
or symbolic quantities. Note also that such an algorithm would probably be
highly suited to parallel computation.
A side remark: Robbins and Rumsey, in their study of Dodgson condensation,
(D.P. Robbins and H. Rumsey, Jr., Determinants and alternating sign matrices,
Advances in Mathematics 62 (1986), 169--184) noticed that a modification of
the algorithm gives rise to something they called the "lambda-determinant"
of a matrix, where lambda is a free parameter. This is not a polynomial in
the entries of the matrix, but rather a Laurent polynomial, where the
coefficients are polynomials in lambda. The ordinary determinant corresponds
to the case lambda = -1 (though it can be argued that the convention should
undergo a sign-flip before it gets hardened by usage). I suspect that there
are many interesting lambda-determinant identities awaiting discovery. The
lambda-analogue idea can be applied in both the number-frieze and number-wall
contexts. For number-friezes, it amounts to setting 2-by-2 subdeterminants
equal to minus lambda. For number-walls, it corresponds to replacing the
recurrence
North * South = Middle * Middle - East * West
by
North * South = Middle * Middle + lambda * East * West
One still gets entries in the table to be polynomials (in terms of
the entries in the row immediately under the top row of 1's).
Finally, since alternating-sign matrices were mentioned recently in this
mail-group (in connection with a different interest of Fred's), I thought
I should mention that they arose from the study of Dodgson condensation.
See the opening pages of "How the Alternating Sign Matrix Conjecture
Was Solved" by David Bressoud and myself, a draft of which is available
at http://www-math.mit.edu/~propp/hidden/asm.html .
Jim Propp
Department of Mathematics
University of Wisconsin
PART 2
John Conway writes:
> Well, I learned of Lewis Carroll's method at the age of about 16,
>long before I learned (from Fred Lunnon) about "number walls" or (from
>Coxeter via Geoffrey Sheppard) about frieze patterns. As soon as I
>learned about the latter I produced several generalizations of them.
>However, I still haven't learned of a sense in which Frieze patterns
>and number walls are "particular cases of condensation" ...
Consider a finite number wall that starts with these two rows:
1 1 1 1 1 1 1
a b c d e
The three entries in the next row will be the bb-ac, cc-bd, and dd-ce,
which we can recognize as the determinants of the 2-by-2 matrices
b c c d d e
a b , b c , c d ,
and the entry in the row after that will be the determinant of the 3-by-3
matrix
c d e
b c d
a b c .
More generally, if we start with a number wall consisting of a row of 1's
above a row of numbers a_1, a_2, ..., a_(2n-1), then the numbers in each
successive row are just the determinants of the connected minors of the
matrix
a_n ... a_(2n-1)
. .
. .
. .
a_1 ... a_n
(with constant entries along the diagonal). Computing these minors by
Dodgson condensation is tantamount to the implementing the number-wall
recurrence.
Similar remarks apply to number friezes: all the entries in the frieze
can be interpreted as determinants of connected minors of a matrix of
the form
a 1 0 0 0
1 b 1 0 0
0 1 c 1 0
0 0 1 d 1
0 0 0 1 e
Note that in this case, naive Dodgson condensation won't work, since
we would end up dividing 0 by 0. Here's a kludge we can use: replace
the matrix by
a t^0 t^1 t^3 t^6
t^0 b t^0 t^1 t^3
t^1 t^0 c t^0 t^1
t^3 t^1 t^0 d t^0
t^6 t^3 t^1 t^0 e
(where the exponents of t are successive triangular numbers). If we
apply Dodgson condensation to this matrix and then truncate the
(polynomial) entries of the resulting matries by setting t=0, we get
precisely the numbers that occur in the frieze pattern.
Jim
PART 3
Here's more on the analogy between Dodgson condensation and frieze patterns,
in which bit-strings appear as a kind of "baby" version of ASMs (with a
connection with continued fraction expansion):
Working together at a cafe a month ago, Henry and I (re-?)discovered a nice
phenomenon: Given two staggered rows of numbers
a_1 a_2 a_3 ...
b_1 b_2 b_3 ...
we form new rows as shown:
a_1 a_2 a_3 ...
b_1 b_2 b_3 ...
* * * ...
* * ...
* * ...
* ...
* ...
...
where the *'s denote new numbers that we have to find, subject to the rule
that in each 2-by-2 square, "top times bottom minus left times right equals
1". (Note that this is not quite the usual frieze-pattern rule; we've changed
the sign.) Let X_1 be the first entry in the first new row, X_2 the first
entry in the second new row, and so on. (We also put X_0 = b_1.) Note that
it suffices to find formulas for the X_n's, since the other entries in their
rows are obtained via a shift of indices. In fact, if we let S denote the
shift-operator, then the X_n's can be compactly defined by the non-linear
recurrence X_(n+1) = (1 + X_n S(X_n)) / S(X_(n-1)).
However, we also have a kind of linear recurrence for the X_n's (albeit one
in which the coefficients depend on n):
1 a_(n-1) b_(n+1)
X_n = ( ------- + ------- + ------- ) X_(n-1) - X_(n-2)
a_n b_n b_n a_n
We also have an explicit expansion for each X_n as a Laurent polynomial with
"Fibonacci-many" terms. The terms for X_n are in one-to-one correspondence
with "compatible pairs" of bit-strings alpha and beta, where alpha is of
length n-1, beta is of length n, and alpha and beta are compatible if the
interleaving
beta_1 alpha_1 beta_2 alpha_2 ... beta_(n-1) alpha_(n-1) beta_n
contains no two consecutive 1's. For each compatible pair (alpha,beta),
define P(alpha) to be the product of a_i a_(i+1) over all i's for which
alpha_i = 1, and P(beta) to be the product of b_i b_(i+1) over all i's
for which beta_i = 1. Then X_n equals the sum, over all compatible pairs
(alpha,beta), of
P(alpha) P(beta)
----------- -----------
a_1 ... a_n b_2 ... b_n
^ ^
[sic]
This idea of interleaving "compatible" bit-strings is very analogous
to the way on superimposes compatible ASMs in the study of Dodgson
condensation.
Something similar happens when one does ordinary frieze patterns, but
signs come into play. This is essentially the theory of continued
fractions in a somewhat unfamiliar guise.
Jim