THE QUANTUM MACMAHON MASTER THEOREM

STAVROS GAROUFALIDIS, THANG TQ LÊ, AND DORON ZEILBERGER

Abstract. We state and prove a quantum-generalization of MacMahon’s celebrated Master Theorem, and relate it to a quantum-generalization of the boson-fermion correspondence of Physics.

1. Introduction

1.1. MacMahon’s Master Theorem. In this paper we state and prove a quantum-generalization of MacMahon’s celebrated Master Theorem, conjectured by the first two authors and proved by the third. In addition to its potential importance in knot theory (see the last section), this paper answers George Andrews’s long-standing open problem [?] of finding a natural q-analog of MacMahon’s Mater Theorem.

Recall that in r-dimensional quantum algebra we have r indeterminates x_{i} ( 1 ≤ i ≤ r), satisfying the commutation relations x_{j}x_{i} = qx_{i}x_{j} for all 1 ≤ i < j ≤ r. We also consider matrices A = (a_{ij}) of r^{2} indeterminates a_{ij}, 1 ≤ i, j ≤ r, that commute with the x_{i}’s and such that for any 2 by 2 minor of (a_{ij}), consisting of rows i and i′, and columns j and j′ (where 1 ≤ i < i′ ≤ r, and 1 ≤ j < j′ ≤ r), writing a := a_{ij}, b := a_{ij′}, c := a_{i′j}, d := a_{i′j′}, we have the commutation relations:

(1)  ba = qab, ca = qac, db = qbd, dc = qcd, cb = bc, da = ad + (q − q^{−1})bc.

We will call such matrices A quantum matrices.

Also recall that the quantum determinant, (first introduced in [?]) of any (not-necessarily quantum) r by r matrix B = (b_{ij}) may be defined by

det_{q}(B) := ∑_{π∈S_{r}}(−q)^{−inv(π)}b_{π_{1}1}b_{π_{2}2} ⋯ b_{π_{r}r},

where the sum ranges over the set of permutations, S_{r}, of {1, …, r}, and for any of its members, π, inv(π) denotes the number of pairs 1 ≤ i < j ≤ r for which π_{i} > π_{j}.

Theorem 1. (Quantum MacMahon Master Theorem) Fix a quantum matrix A of size r. For 1 ≤ i ≤ r, let X_{i} := ∑_{j=1}^{r} a_{ij}x_{j}, and for any vector (m_{1}, …, m_{r}) of non-negative integers let G(m_{1}, …, m_{r}) be the coefficient of x_{1}^{m_{1}}x_{2}^{m_{r}} … x_{r}^{m_{r}} in ∏_{i=1}^{r} X_{i}^{m_{i}}. Then

∑_{m_{1},m_{2},...,m_{r}=0}^{∞} G(m_{1}, …, m_{r}) = 1/det_{q}(I − A).

The above result is not only interesting from the combinatorial point of view, but it is also a key ingredient in a finite noncommutative formula for the colored Jones function of a knot. This will be explained in a subsequent publication, [?].

For an interpretation of the above theorem in terms of the so-called boson-fermion correspondence, see Section ??.

Date: This edition: March 25, 2003. First edition: March 24, 2003.

The authors were supported in part by NSF and BSF.

1991 Mathematics Classification. Primary 57N10, 05A30. Secondary 57M25.

Key words and phrases: Boson-fermion correspondence, MacMahon’s Master Theorem, q-difference operators .

2. Proof

The proof will make crucial use of a calculus of difference operators, developed by the third author in [?]. Difference operators act on discrete functions J, that is functions whose domain is ℕ^{r}.

Before embarking on the proof, we need the following readily-verified facts.

Fact 1: For 1 ≤ i < j ≤ r, X_{j}X_{i} = qX_{i}X_{j}.

Fact 2: For each of the a_{ij}, define the operator Q_{ij} acting on expressions P involving a_{ij} by Q_{ij}P (a_{ij}) := P (qa_{ij}). Then, for any 1 ≤ i, j ≤ r, and integer m_{i} and any expression F

x_{i}^{−m_{i}}X_{j}F = [(Q_{j1}^{−1}Q_{j2}^{−1} ⋯ Q_{j,i−1}^{−1}Q_{j,i+1} ⋯ Q_{jr})^{m_{i}}X_{j}]x_{i}^{−m_{i}}F.

Fact 3 (Column expansion with respect to the last column): Given an r by r quantum matrix (a_{ij}), let A_{i} be the minor of the entry a_{ir}, i.e. the r − 1 by r − 1 matrix obtained by deleting the i^{th} row and r^{th} column. Then

det_{q}(A) = ∑_{i=1}^{r}(−q)^{i−r} (det_{q}A_{i}) a_{ir}.

Fact 4 (Equal columns imply that det_{q} vanishes): In the notation of Fact 3, for all j ≠ r,

∑_{i=1}^{r}(−q)^{i−r} (det_{q}A_{i}) a_{ij} = 0.

We are now ready for the proof. It is a quantum-adaptation of the “operator-elimination” proof of MacMahon’s Master Theorem given in [?].

Proof. (of Theorem ??) G(m_{1}, …, m_{r}) is the coefficient of x_{1}^{0} … x_{r}^{0} in

H(m_{1}, …, m_{r}; x_{1}, …, x_{r}) := x_{r}^{−m_{r}} ⋯ x_{2}^{−m_{2}}x_{1}^{−m_{1}} ∏_{i=1}^{r} X_{i}^{m_{i}}.

We will think of H as a discrete function, that is as a function of (m_{1}, …, m_{r}) ∈ ℕ^{r}. Let t_{i} (i = 1, …, r) be a new set of variables commuting with the x_{i}’s and a_{ij}’s. Substituting a_{ij} by t_{i}a_{ij}, it follows that the theorem is equivalent to the generating-function identity:

g(t_{1}, …, t_{r}) := ∑_{m_{1},m_{2},...,m_{r}=0}^{∞} G(m_{1}, …, m_{r})t_{1}^{m_{1}} … t_{r}^{m_{r}} = 1/det_{q}(I − t_{i}a_{ij}).

Next we define the shift-operators M_{i} which act on a discrete function J(m_{1}, …, m_{r}) by

(M_{i}J)(m_{1}, …, m_{r}) := J(m_{1}, …, m_{i−1}, m_{i} + 1, m_{i+1}, …, m_{r}).

Let’s see how M_{i} acts on H. By definition,

M_{i}H(m_{1}, …, m_{r}; x_{1}, …, x_{r}) =
x_{r}^{−m_{r}} ⋯ x_{i+1}^{−m_{i+1}}x_{i}^{−m_{i}−1}x_{i−1}^{−m_{i−1}} ⋯ x_{1}^{−m_{1}}X_{1}^{m_{1}} ⋯ X_{i−1}^{m_{i−1}}X_{i}^{m_{i}+1}X_{i+1}^{m_{i+1}} ⋯ X_{r}^{m_{r}}.

By moving x_{i}^{−1} to the front and X_{i} in front of X_{1}^{m_{1}}, and using Fact 1 and x_{j}x_{i} = qx_{i}x_{j}, we have

M_{i}H(m_{1}, …, m_{r}) = q^{m_{r}+m_{r−1}+···+m_{i+1}−m_{1}−m_{2}−···−m_{i−1}}x_{i}^{−1}[x_{r}^{−m_{r}} ⋯ x_{1}^{−m_{1}}X_{i}]X_{1}^{m_{1}} ⋯ X_{r}^{m_{r}}.

By repeated use of Fact 2, this equals

q^{m_{r}+m_{r−1}+···+m_{i+1}−m_{1}−m_{2}−···−m_{i−1}}x_{i}^{−1}·
[(Q_{i2} ⋯ Q_{ir})^{m_{1}}(Q_{i1}^{−1}Q_{i3} ⋯ Q_{ir})^{m_{2}}(Q_{i1}^{−1}Q_{i2}^{−1}Q_{i4} ⋯ Q_{ir})^{m_{3}} ⋯ (Q_{i1}^{−1}Q_{i2}^{−1} ⋯ Q_{i,r−1}^{−1})^{m_{r}}X_{i}]·
x_{r}^{−m_{r}} ⋯ x_{1}^{−m_{1}}X_{1}^{m_{1}} … X_{r}^{m_{r}},

which is equal to

q^{m_{r}+m_{r−1}+···+m_{i+1}−m_{1}−m_{2}−···−m_{i−1}}x_{i}^{−1}·

(q^{−m_{2}−m_{3}−···−m_{r}}a_{i1}x_{1} + q^{m_{1}−m_{3}−···−m_{r}}a_{i2}x_{2} + ⋯ + q^{m_{1}+m_{2}+···+m_{r−1}}a_{ir}x_{r}) H(m_{1}, …, m_{r}; x_{1}, …, x_{r})

Multiplying out and rearranging, we get that the discrete function H(m_{1}, …, m_{r}; x_{1}, …, x_{r}) is annihilated by the r operators (i = 1, 2, …, r)

P_{i} := ∑_{j=1}^{i−1} −q^{−m_{j}−2m_{j+1}−···−2m_{i−1}−m_{i}}a_{ij}x_{j} + (M_{i} − a_{ii})x_{i} + ∑_{j=i+1}^{r} −q^{m_{i}+2m_{i+1}+···+2m_{j−1}+m_{j}}a_{ij}x_{j}.

Now comes a nice surprise. Defining b_{ij} to be the coefficient of x_{j} in P_{i}, it is immediately checked (using the fact that M_{i}q^{m_{i}} = q(q^{m_{i}})M_{i}) that b_{ij} is also a quantum matrix! In other words it obeys the quantum commutation relations. Now we eliminate x_{1}, x_{2}, …, x_{r−1} by left-multiplying P_{i} by the minor of b_{ir} in B = (b_{ij}) times (−q)^{i−r}, for each i = 1, 2, …, r, and adding them all up. By Fact 4, the coefficients of x_{1}, …, x_{r−1} all vanish, and we are left with (after right-multiplying by x_{r}^{−1}) det_{q}(B)H(m_{1}, …, m_{r}) = 0. Now using the definition of the quantum-determinant, it is readily seen that all the powers of q disappear! Hence

det_{q}(M_{i}δ_{ij} − a_{ij})H(m_{1}, …, m_{r}; x_{1}, ….x_{r}) = 0.

What’s nice about the partial recurrence operator det_{q}(M_{i}δ_{ij} − a_{ij}) is that it does not depend on the x′_{i}s, hence it also annihilates each and every single coefficient of H, in particular its constant term. Taking the constant term yields

det_{q}(M_{i}δ_{ij} − a_{ij})G(m_{1}, …, m_{r}) = 0.

But this is equivalent to the statement that the coefficient of a typical monomial t_{1}^{α_{1}} ⋯ t_{r}^{α_{r}}, with all the α_{i} strictly positive, in the formal power series

det_{q}(I − t_{i}a_{ij})g(t_{1}, …, t_{r}),

vanishes. By induction (with respect to r), we already know that it is also true when some of the α_{i} are zero, except when they are all zero, in which case the coefficient of t_{1}^{0} ⋯ t_{r}^{0} is obviously 1. Hence

det_{q}(I − t_{i}a_{ij})g(t_{1}, …, t_{r}) = 1.

□

3. Boson-fermion correspondence

Given a matrix A = (a_{ij}) of size r with commuting indeterminate entries which lie in a ring R, the following identity

(2)  \frac{1}{det(I − tA)} = ∑_{n=0}^{∞} tr S^{n}(A)t^{n}

in R[[t]] in Combinatorics is called the MacMahon Master Theorem Identity (see [?]) and in Physics it is called the boson-fermion correspondence. We may observe that

det(I − tA) = ∑_{n=0}^{∞}(−1)^{n} tr Λ^{n}(A)t^{n}

where S^{n}(A) and Λ^{n}(A) is the nth symmetric or exterior power of A, corresponding to bosons (that is, commuting particles) and fermions (that is, anti-commuting particles) respectively.

Now, we come to a q-analogue of the above. For a reference on quantum space and quantum algebra, see [?, Chapter IV] and [?].

Recall that a vector (column or row) of r indeterminate entries x_{1}, …, x_{r} lies in r-dimensional quantum space A^{r|0} iff its entries satisfy

x_{j}x_{i} = qx_{i}x_{j}

for all 1 ≤ i < j ≤ r.

Recall that an endomorphism of A^{r|0} is a matrix A = (a_{ij}) of size r whose entries commute with the coordinates x_{i} of a vector x = (x_{1}, …, x_{r})^{T} ∈ A^{r|0} and in addition, Ax and x^{T} A lie in A^{r|0}.

This is equivalent to the condition given before the statement of Theorem ??; see [?, Thm. IV.3.1]. The set of such matrices A are the points of the r-dimensional quantum algebra M_{q}(r), which is defined to be the quotient of the free algebra in noncommuting variables x_{ij} for 1 ≤ i, j, ≤ r, modulo the left ideal generated by the commutation relations of Equation (??).

The algebra M_{q}(r) has interesting and important structure. M_{q}(r) is Noetherian, has no zero divisors, and in addition, a basis for the underlying vector space is given by the set of sorted monomials {∏_{i,j} a_{ij}^{n_{ij}}|n_{ij} ≥ 0} where the product is taken lexicographically; see [?, Thm IV.4.1]. An imporant quotient of M_{q}(r) is the quantum group SL_{q}(r) := M_{q}(r)/(det_{q} −1), which is a Hopf algebra [?, Sec.IV.6] whose representation theory gives rise to the quantum group invariants of knots, such as the celebrated Jones polynomial.

Using the language of symmetric and exterior powers, Theorem ?? becomes the following: Theorem 2. If A is in M_{q}(r), then

\frac{1}{det_{q}(I − tA)} = ∑_{n=0}^{∞} tr S^{n}(A)t^{n}

Since the algebra M_{q}(r) has a vector space basis given by sorted monomials, it should be possible to give an alternative proof of the quantum MacMahon Master Theorem using combinatorics on words, as was done in [?] for several proofs of the MacMahon Master theorem. We hope to return to this alternative point of view in the near future.

References

[A] G. E. Andrews, Problems and prospects for basic hypergeometric functions, The Theory and Applications of Special Functions (R. Aseky, Editor), Academic Press, New York, 1975, 191-224.

[FRT] L. Fadeev, N. Reshetikhin and L. Takhtadjian, Quantization of Lie groups and Lie algebras, Leningrad Math. Journal 1 (1990), 193-225.

[FZ] D. Foata and D. Zeilberger, A combinatorial proof of Bass’s evaluation of the Ihara-Selberg zeta function for graphs, Transactions Amer. Math. Soc. 351 (1999) 2257–2274.

[GL] S. Garoufalidis and TTQ Le, in preparation.

[Ka] C. Kassel, Quantum groups, GTM 155 Springer-Verlag (1995).

[MM] P. A. MacMahon, Combinatory Analysis vol. 1, Cambridge University Press, 1917. Reprinted by Chelsea, 1984.

[M] Y. Manin, Quantum groups and noncommutative geometry, Université de Montréal, Centre de Recherches Mathématiques, Montreal, QC, 1988.

[Z] D. Zeilberger, The algebra of linear partial difference operators and its applications, SIAM J. Math. Anal. 11 (1980) 919–934.

School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA, http://www.math.gatech

.edu/∼stavros
   E-mail address: stavros@math.gatech.edu

Department of Mathematics, University at Buffalo, The State University of New York, Buffalo, NY 14260-2900, USA

   E-mail address: letu@math.buffalo.edu

Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd, Piscataway, NJ 08854-8019, USA

   E-mail address: zeilberg@math.rutgers.edu