Here's an outline of a short talk I gave at an "open mike" session of the 
MIT combinatorics seminar back in 1987.  It's a condensed version of a 
longer talk I'd considered giving back in September (and might give day) 
entitled "From Dodgson to Dominoes (and Back?)".

In the talk I'll describe my current state of knowledge, and confusion, 
concerning the algebraic significance of an identity governing a certain 
family of sparse matrices.  I'd be grateful if any readers of this list 
could shed light on the matter. 


The determinant of an n-by-n matrix is a sum of n! terms:

    ( a   b   c   d )
    (               )
    ( e   f   g   h )
Det (               ) = afkp + ... + dgjm
    ( i   j   k   l )
    (               )
    ( m   n   o   p )

Divide the matrix into blocks as shown:

      1    n-2    1

 1  ( a | b   c | d )   [ A |   B   | C ]
    (---|-------|---)   [---|-------|---]
    ( e | f   g | h )   [   |       |   ]
n-2 (   |       |   ) = [ D |   E   | F ]
    ( i | j   k | l )   [   |       |   ]
    (---|-------|---)   [---|-------|---]
 1  ( m | n   o | p )   [ G |   H   | I ]

The Desnanot-Jacobi identity relates six sub-determinants of this matrix:

	one (n-2)-by-(n-2) determinant,
	four (n-1)-by-(n-1) determinants, and
	one n-by-n determinant.

   [A   B   C]
   [         ]             [A   B]    [E   F]      [B   C]    [D   E]
Det[D   E   F] Det[E] = Det[     ] Det[     ] - Det[     ] Det[     ]
   [         ]             [D   E]    [H   I]      [E   F]    [G   H]
   [G   H   I]

Desnanot-Jacobi identity --> Dodgson condensation 
                         --> Alternating sign matrices (Mills, Robbins, Rumsey)
                         --> Compatible pairs of ASM's
                         --> Domino tilings of Aztec diamonds (Elkies et al.)
                         --> Perfect matchings of Aztec diamond graphs

If we have an Aztec diamond graph of order n with arbitrary edge-weights,
the sum of the weights of all the perfect matchings (where the weight of
a matching is the product of the weights of its constituent edges) is a
sum of 2^{n(n+1)/2} terms:

      (  /\    /\  )
      ( a  b  c  d )
      (/    \/    \)
      (\    /\    /)
      ( e  f  g  h )
Match (  \/    \/  ) = achinp + ... + bdelmo
      (  /\    /\  )
      ( i  j  k  l )
      (/    \/    \)
      (\    /\    /)
      ( m  n  o  p )
      (  \/    \/  )

Divide the graph into blocks as shown:

      (  /\|   /\   |/\  )
      ( /  |  /  \  |  \ )
      (/   |\/    \/|   \)
      (\   |/\    /\|   /)
      (----|--------|----)
      (  \/|   \/   |\/  )
      (  /\|   /\   |/\  )     [ A  B  C ]
      ( /  |  /  \  |  \ )     [         ]
      (/   |\/    \/|   \)  =  [ D  E  F ]
      (\   |/\    /\|   /)     [         ]
      ( \  |  \  /  |  / )     [ G  H  I ]
      (  \/|   \/   |\/  )
      (  /\|   /\   |/\  )
      (----|--------|----)
      (/   |\/    \/|   \)
      (\   |/\    /\|   /)
      ( \  |  \  /  |  / )
      (  \/|   \/   |\/  )

so that the lines carve out an Aztec diamond graph of order n-2
in the middle.

Kuo's formula:

     [A  B  C]
     [       ]                    [A  B]      [E  F]
Match[D  E  F] Match[E] =    Match[    ] Match[    ] Match[C] Match[G]
     [       ]                    [D  E]      [H  I]
     [G  H  I]
                                  [B  C]      [D  E]
                          +  Match[    ] Match[    ] Match[A] Match[I]
                                  [E  F]      [G  H]

Note resemblance to Desnanot-Jacobi identity: minus becomes plus 
and two extra factors get introduced in each of the two terms.

PROBLEM: Interpret/prove Kuo's formula via linear algebra (a combinatorial
proof is already known) so as to clarify its true relation to the Desnanot-
Jacobi identity.  It might help to know of a combinatorial interpretation/
proof of the latter.

One start towards solving the problem is provided by the Kasteleyn-Percus 
method:

      (  /\    /\  )         (a   e   0   0   0   0)
      ( a  b  c  d )         (                     )
      (/    \/    \)         (b  -f   0   c   g   0)
      (\    /\    /)         (                     )
      ( e  f  g  h )         (0   0   0   d  -h   0)
Match (  \/    \/  ) = +- Det(                     )
      (  /\    /\  )         (0   i   m   0   0   0)
      ( i  j  k  l )         (                     )
      (/    \/    \)         (0   j  -n   0   k   o)
      (\    /\    /)         (                     )
      ( m  n  o  p )         (0   0   0   0   l  -p)

In general: the sum of the weights of the perfect matchings of an Aztec 
diamond graph of order n can be written as the determinant of a sparse
n(n+1)-by-n(n+1) matrix (up to sign).

Dividing the graph into (3)(3) = 9 regions corresponds to dividing the
Kasteleyn-Percus matrix into (9)(9) = 81 blocks (many of which are
empty in the n=2 example shown above).  Kuo's formula expresses a
relationship between ten determinants obtained by grouping these blocks:

	four 1-by-1 determinants,
	one (n-1)(n-2)-by-(n-1)(n-2) determinant,
	four n(n-1)-by-n(n-1) determinant, and
	one (n+1)n-by-(n+1)n determinant.

Is the Kuo formula something like the tensor square, symmetric square,
or exterior square of the Desnanot-Jacobi identity?

--- Jim Propp