Dodgson’s Determinant-Evaluation Rule Proved by TWO-TIMING MEN and WOMEN

Doron ZEILBERGER^{1}

Bijections are where it’s at —Herb Wilf

Dedicated to Master Bijectionist Herb Wilf, on finishing 13/24 of his life

I will give a bijective proof of the Reverend Charles Lutwidge Dodgson’s Rule([D]):

det [(a_{i,j})_{{1≤i≤n \atop 1≤j≤n}} ] · det [(a_{i,j})_{{2≤i≤n−1 \atop 2≤j≤n−1}} ] =
det [(a_{i,j})_{{1≤i≤n−1 \atop 1≤j≤n−1}} ] · det [(a_{i,j})_{{2≤i≤n \atop 2≤j≤n}} ] − det [(a_{i,j})_{{1≤i≤n−1 \atop 2≤j≤n}} ] · det [(a_{i,j})_{{2≤i≤n \atop 1≤j≤n−1}} ] . (Alice)

Consider n men, 1, 2, …, n, and n women 1′, 2′ …, n′, each of whom is married to exactly one member of the opposite sex. For each of the n! possible (perfect) matchings π, let

weight(π) := sign(π) ∏_{i=1}^{n} a_{i,π(i)} ,

where sign(π) is the sign of the corresponding permutation, and for i = 1, …, n, Mr. i is married to Ms. π(i)′.

Except for Mr. 1, Mr. n, Ms. 1′ and Ms. n′ all the persons have affairs. Assume that each of the men in {2, …, n − 1} has exactly one mistress amongst {2′, …, (n − 1)′} and each of the women in {2′, …, (n − 1)′} has exactly one lover amongst {2, …, n − 1}^{2}. For each of the (n − 2)! possible (perfect) matchings σ, let

weight(σ) := sign(σ) ∏_{i=2}^{n−1} a_{i,σ(i)} ,

where sign(σ) is the sign of the corresponding permutation, and for i = 2, …, n − 1, Mr. i is the lover of Ms. σ(i)′.

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg   ftp://ftp.math.temple.edu/pub/zeilberg .

Supported in part by the NSF. Version of May 8, 1996. First Version: April 16, 1996. Submitted to the Wilf (Electronic) Festschrifft.

Thanks are due to Bill Gosper for several corrections.

2 Somewhat unrealistically, a man’s wife may also be his mistress, and equivalently, a woman’s husband may also be

her lover.

Let A(n) be the set of all pairs [π, σ] as above, and let weight([π, σ]) := weight(π)weight(σ). The left side of (Alice) is the sum of all the weights of the elements of A(n).

Let B(n) be the set of pairs [π, σ], where now n and n′ are unmarried but have affairs, i.e. π is a matching of {1, …, n − 1} to {1′, …, (n − 1)′}, and σ is a matching of {2, …, n} to {2′, …, n′}, and define the weight similarly.

Let C(n) be the set of pairs [π, σ], where now n and 1′ are unmarried and 1 and n′ don’t have affairs. i.e. π is a matching of {1, …, n − 1} to {2′, …, n′}, and σ is a matching of {2, …, n} to {1′, …, (n − 1)′}, and now define weight([π, σ]) := −weight(π)weight(σ).

The right side of (Alice) is the sum of all the weights of the elements of B(n) ∪ C(n).

Define a mapping

T : A(n) → B(n) ∪ C(n) ,

as follows. Given [π, σ] ∈ A(n), define an alternating sequence of men and women: m_{1} := n, w_{1}, m_{2}, w_{2}, …, m_{r}, w_{r} = 1′ or n′, such that w_{i} :=wife of(m_{i}), and m_{i+1} :=lover of(w_{i}). This sequence terminates, for some r, at either w_{r} = 1′, or w_{r} = n′, since then m_{r+1} is undefined, as 1′ and n′ are lovers-less women. To perform T, change the relationships (m_{1}, w_{1}), (m_{2}, w_{2}), …, (m_{r}, w_{r}) from marriages to affairs (i.e. Mr. m_{i} and Ms. w_{i} get divorced and become lovers, i = 1, …, r), and change the relationships (m_{2}, w_{1}), (m_{3}, w_{2}), …, (m_{r}, w_{r−1}) from affairs to marriages. If w_{r} = 1′ then T ([π, σ]) ∈ C(n), while if w_{r} = n′ then T ([π, σ]) ∈ B(n).

The mapping T is weight-preserving. Except for the sign, this is obvious, since all the relationships have been preserved, only the nature of some of them changed. I leave it as a pleasant exercise to verify that also the sign is preserved.

It is obvious that T : A(n) → B(n) ∪ C(n) is one-to-one. If it were onto, we would be done. Since it is not, we need one more paragraph.

Call a member of B(n) ∪ C(n) bad if it is not in T (A(n)). I claim that the sum of all the weights of the bad members of B(n) ∪ C(n) is zero. This follows from the fact that there is a natural bijection S, easily constructed by the readers, between the bad members of C(n) and those of B(n), such that weight(S([π, σ])) = −weight([π, σ]). Hence the weights of the bad members of B(n) and C(n) cancel each other in pairs, contributing a total of zero to the right side of (Alice).

A small Maple package, alice, containing programs implementing the mapping T, its inverse, and the mapping S from the bad members of C(n) to those of B(n), is available from my Home Page

http://www.math.temple.edu/~zeilberg.

Reference

[D] C.L. Dodgson, Condensation of Determinants, Proceedings of the Royal Society of London 15(1866), 150-155.