[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