New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
The quantum MacMahon Master Theorem

Edited by Robion C. Kirby, University of California, Berkeley, CA, and approved July 24, 2006 (received for review July 17, 2006)
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.
In this article we state and prove a quantum generalization of MacMahon's celebrated Master Theorem conjectured by S.G. and T.T.Q.L. Our result was motivated by quantum topology. In addition to its potential importance in knot theory and quantum topology (explained in brief in ref. 4), this article answers George Andrews's longstanding open problem (1) of finding a natural qanalog of MacMahon's Master Theorem.
MacMahon's Master Theorem
Let us recall the original form of MacMahon's Master Theorem and some of its modern interpretations.
Consider a square matrix A = (a_{ij} ) of size r with entries in some commutative ring. For 1 ≤ i ≤ r, let X_{i} := Σ_{j = 1} ^{r} a_{ij}x_{j} , (where x_{i} are commuting variables) and for any vector (m_{1} , …, m_{r} ) of nonnegative integers let G(m _{1}, …, m_{r} ) be the coefficient of x _{1} ^{m1} x _{2} ^{mr} … x_{r} ^{mr} in ∏_{i = 1} ^{r} X_{i} ^{mi} . MacMahon's Master Theorem is the following identity (see ref. 2): There are several equivalent reformulations of MacMahon's Master Theorem (see, for example, ref. 3 and references therein). Let us mention one of these studies, which is of importance to physics.
Given a matrix A = (a_{ij} ) of size r with commuting entries that lie in a ring ℛ, and a nonnegative integer n, we can consider its symmetric and exterior powers S^{n} (A) and Λ^{n} (A), and their traces tr S^{n} (A), and tr Λ^{n} (A), respectively. Because the following identity in ℛ [[t]] is equivalent to Eq. 1 . In physics, Eq. 2 is called the boson–fermion correspondence, where bosons (fermions) are commuting (skewcommuting) particles corresponding to symmetric (exterior) powers.
Quantum Algebra, RightQuantum Matrices, and Quantum Determinants
In rdimensional quantum algebra we have r indeterminate variables 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, which commute with the x_{i} and such that for any 2by2 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: We will call such matrices A rightquantum matrices.
The quantum determinant, (first introduced in ref. 3) of any (not necessarily rightquantum) r by r matrix B = (b_{ij} ) may be defined by 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}.
A qVersion of MacMahon's Master Theorem
We are now ready to state our quantum version of MacMahon's Master Theorem.
Theorem 1 (Quantum MacMahon Master Theorem).
Fix a rightquantum 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 nonnegative integers let G (m _{1}, …, m_{r} ) be the coefficient of x _{1} ^{m1} x _{2} ^{mr} … x_{r} ^{mr} in ∏_{i=1} ^{r} X_{i} ^{mi} . Let where the summation is over the set of all subsets J of {1, …, r}, and A_{J} is the J by J submatrix of A, and Then When we specialize to q = 1, Theorem 1 recovers Eq. 2 , which explains why our result is a qversion of the MacMahon Master Theorem. For a motivation of Theorem 1, see Some Remarks on the Boson–Fermion Correspondence.
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 (see ref. 4).
Computer Code
The results of the article have been verified by computer code (written by D.Z.). Maple programs QuantumMACMAHON and qMM are available at www.math.rutgers.edu/∼zeilberg/programs.html. QuantumMACMAHON rigorously proves Theorem 1 for any fixed r.
Proof
Some Lemmas on Operators.
The proof will make crucial use of a calculus of difference operators developed by D.Z. (5). This calculus of difference operators predates the more advanced calculus of holonomic functions developed by D.Z. (6).
Difference operators act on discrete functions F, that is functions whose domain is ℕ^{r}. For example, consider the shiftoperators M_{i} and the multiplication operator Q_{i} , which act on a discrete function F(m _{1}, …, m _{r}) by It is easily seen that Abbreviating Q_{i} as q^{mi}, we obtain that Another example is the operator x̂_{i} , which leftmultiplies F by x_{i} . Notice that x̂_{j} x̂x_{i} = qx̂_{i} x̂_{j} for j > i. In the proof below, we will denote x̂_{i} as x_{i} . In that case, the identity x_{j} x_{i} = qx_{i} x_{j} for j > i holds in the quantum algebra in the algebra of operators.
Before embarking on the proof, we need the following readily and verified lemmas.
Lemma 1.
(Commuting X_{i} with X_{j} ): For 1 ≤ i < j ≤ r, X_{j} X_{i} = qX_{i} X_{j} .
Lemma 2.
(Commuting x_{i} with X_{j} ): 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
Lemma 3.
(Column expansion with respect to the last column): Given an r by r matrix (a_{ij} ) (not necessarily quantum), 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
Lemma 4.
If A is a matrix that satisfies Eq. 5 and A′ denotes a matrix obtained by interchanging the i and j columns of A, then det_{q}(A′) = (−q)^{−inv(ij)}det_{q}(A).
Proof.
Suppose first that we interchange two adjacent columns i and j := i + 1. Consider the involution of S_{r} that sends a permutation π to π′ = π(ij). Given π ∈ S_{r} , let (A; π) = (−1)^{−inv(π)} a _{π1} _{1} … a _{πr} _{r} denote the contribution of π in det_{q}(A). Then, det_{q}(A) = Σ_{π} (A; π). Eq. 5 implies that Summing over all permutations proves the result when j = i + 1.
Observe that when j = i + 1, the matrix A′ is no longer rightquantum since it does not satisfy Eq. 5 . However, the proof used only the fact that Eq. 5 holds for the i and i + 1 columns of A.
Thus, the proof can be iterated inv(ij) times to commute the i and j > i columns of A. The result follows.
Lemma 5.
(Equal columns imply that det_{q} vanishes): Let A be a rightquantum matrix. In the notation of Lemma 3, for all j ≠ r,
Proof.
If j = r − 1, it is easy to see that qcommutation along the entries in every column of A imply that the sum vanishes.
If j < r − 1, use Lemma 4 to reduce it to the case of j = r − 1.
Remark.
One can give an alternative proof of Lemmas 4 and 5 from the trivial 2by2 case and, by induction using the qLaplace expansion of a qdeterminant that is completely analogous to the classical case.
Proof of Theorem 1.
The proof is a quantumadaptation of the “operatorelimination” proof of MacMahon's Master Theorem given in ref. 5. Fix a rightquantum matrix A.
Observe that G(m _{1}, …, m _{r}) is the coefficient of x _{1} ^{0} … x _{r} ^{0} in We will think of H as a discrete function that is as a function of (m _{1}, …, m _{r}) ∈ ℕ^{r}. H takes values in the ring of noncommutative Laurrent polynomials in the x_{i}s, with coefficients in the ring generated by the entries of A, modulo the ideal given by Eqs. 3 – 5 .
Let us see how the shift operators M_{i} acts on H. By definition, By moving x _{i} ^{−1} to the front and X_{i} in front of X _{1} ^{m1}, and using Lemma 1 and x_{j} x_{i} = qx_{i} x_{j} , we have By moving X_{i} next to x _{i} ^{−1} and using Lemma 2 this equals to which is equal to 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): Now comes a nice surprise. Let us define b_{ij} to be the coefficient of x_{j} in 𝒫_{i} . For example, for r = 3 we have
Lemma 7.
B is a rightquantum matrix.
Proof.
It is easy to see that the entries in each column of B qcommute. To prove Eq. 5 , consider the following three cases for a 2by2 submatrix C of B: C contains two (resp. one, resp. zero) diagonal entries of B, and prove it case by case, using the fact that the operators M_{i} and q^{mj} commute with the a_{ij} and satisfy the commutation relations of Eq. 6 .
Now we eliminate x _{1}, x _{2}, …, x _{r−1} by leftmultiplying 𝒫_{i} by the minor of b_{ir} in B = (b_{ij} ) × (−q)^{i−r}, for each i = 1, 2, …, r, and adding them all up. Since B is rightquantum (by Lemma 7), Lemma 5 implies that the coefficients of x _{1}, …, x _{r−1} all vanish, and det_{q}(B)x_{r}H = 0. After leftmultiplying by x _{r} ^{−1}, which commutes with the entries in B, we obtain that Since the entries of B do not contain any x_{i} , it follows that det_{q}(B) annihilates every coefficient of H, in particular its constant term. Taking the constant term yields Here comes the next surprise.
Lemma 8.
(i) We have where J̄ = {1, …, r} − J and M_{J} = ∏_{j∈J} M _{j}.
(ii) In particular,
Proof.
Let us expand det_{q}(B) as a sum over permutations π ∈ S_{r} . We have where inv(π, i) is the number of j > i such that π_{i} > π_{j}. Now, b_{ij} = δ_{ij} M_{i} − q_{ij} a_{ij} , where q_{ij} is a monomial in the variables q^{mk} , and ∏_{i} q _{πi} _{i} = 1. Moreover, if π_{i} = i, then for each j with i < j ≠ π_{j}, the exponent of q^{mi} in q_{ij} is 2 if π_{j} < i and 0 if π_{j} > i.
Since ∏_{i} q _{πii} = 1, we can move the monomials q_{ij} in the left of ∏_{i}(−q)^{−inv(π,i)} b _{πi} _{i} and then cancel them. The monomials commute with all entries of the matrix b_{ij} , except with the diagonal ones. Commuting q ^{2mi} with b_{ii} = δ_{πi} _{i} M_{ii} − q _{πi} _{i} a _{πi} _{i} gives b_{ii}q ^{2mi} = q ^{2mi}(δ_{πi} _{i} q ^{2} M _{ii} − q _{πi} _{i} a _{πi} _{i}). In other words, commuting replaces M_{i} by q ^{2} M_{i} . Thus, we have: Now, rearrange the summation. Observe that every permutation π of {1, …, r} gives rise to a permutation π′ on the set {1, …, r} − Fix (π), where Fix (π) is the fixed point set of π. Moreover, inv (π′, i) = inv (π, i) − {j ∈ J : j > i}. Using this, part i follows. Part ii follows from part i and the definition of Ferm (A).
Hence, Summing over ℕ^{r}, we get For a subset J = {k _{1}, …, k _{j}} of {1, …, r}, we denote by G_{J} (m _{k1}, …, m_{kj} ) the evaluation G(m _{1}, …, m _{r}) at m_{i} = 0 for all i ∉ J, and we define Using telescoping cancellation, the inclusion–exclusion principle, and Lemma 8 (part ii), the above equation becomes Using induction (with respect to r), together with S _{∅} = 1, we obtain that Ferm(A)S _{{1, …, r}} = 1.
Some Remarks on the Boson–Fermion Correspondence
Let us give some motivation for Theorem 1 from the point of view of quantum topology.
For a reference on quantum space and quantum algebra, see Chapter IV of ref. 7 and ref. 8.
Recall that a vector (column or row) of r indeterminate entries x _{1}, …, x_{r} lies in rdimensional quantum space A ^{r0} if its entries satisfy for all 1 ≤ i < j ≤ r.
Recall that a right (left) endomorphism of A ^{r0} 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 ^{r0} and in addition, Ax (left, x^{T} A) lie in A ^{r0}. Recall also that an endomorphism of A ^{r0} is one that is right and left endomorphism.
It is easy to see (e.g., in theorem IV.3.1 of ref. 7) that A is a rightquantum (i.e., a rightendomorphism) if for every 2by2 submatrix
The algebra M _{q}(r) has interesting and important structure. M _{q}(r) is Noetherian and has no zero divisors; in addition, a basis for the underlying vector space is given by the set of sorted monomials {∏_{i,j} a_{ij} ^{nij} n_{ij} ≥ 0}, where the product is taken lexicographically. An important quotient of M _{q}(r) is the quantum group SL _{q}(r) := M _{q}(r)/(det_{q} − 1), which is a Hopf algebra (see theorem IV.4.1 in ref. 7) whose representation theory gives rise to the quantum group invariants of knots, such as the celebrated Jones Polynomial.
Observing that Theorem 1 implies that
Theorem 2.
If A is in M_{q} (r), then 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 ref. 9 for several proofs of the MacMahon Master Theorem. We hope to return to this alternative point of view in the near future.
Acknowledgments
We thank the anonymous referee who pointed out an error in an earlier version of the manuscript, and Martin Loebl for enlightening conversations. This work was supported in part by the National Science Foundation.
Footnotes
 ^{†}To whom correspondence should be addressed. Email: stavros{at}math.gatech.edu

Author contributions: S.G., T.T.Q.L., and D.Z. performed research.

The authors declare no conflict of interest.

This paper was submitted directly (Track II) to the PNAS office.
 © 2006 by The National Academy of Sciences of the USA
References

↵
 Andrews GE
 Aseky R

↵
 MacMahon PA

↵
 Fadeev L ,
 Reshetikhin N ,
 Takhtadjian L

↵
 Huynh V ,
 Lê TTQ
 ↵
 ↵

↵
 Kassel C

↵
 Manin Y
 ↵