2005/12/07 15:50

A New Proof of the Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem

Dominique Foata and Guo-Niu Han

ABSTRACT. We propose a new proof of the quantum version of MacMahon’s Master Theorem, established by Garoufalidis, Lê and Zeilberger.

R^{}ÉSUM^{}É. Nous proposons une nouvelle démonstration de la version quantique du Master Théorème de MacMahon, établi par Garoufalidis, Lê et Zeilberger.

1. Introduction

MacMahon’s Master Theorem is still regarded as a keystone in Combinatorial Analysis. It was proved by MacMahon himself [Ma15, vol. 1, p. 93–98], who also gave numerous applications. Several other proofs are due to Good [Go62], Cartier [Ca72]. As the Master Theorem is a special case of the multivariable Lagrange Inversion Formula [Ge87], as was shown by Good [Go60] (see also Hofbauer [Ho82]), each proof of the latter formula yields a proof of this theorem. Its first noncommutative version can be found in [Fo65], which was later implemented into an appropriate algebraic set-up [CF69]. Recently Garoufalidis, Lê and Zeilberger have derived another noncommutative version [GLZ05] (called “quantum Master Theorem”) by using difference operator techniques developed by Zeilberger [Z80]. In this paper we propose a new proof of this quantum Master Theorem. As indicated in [FH05], the formal parameter q in the Garoufalidis-Lê-Zeilberger version plays no role; we will then let q = 1 in the present derivation without loss of generality.

Let r be a positive integer; the set 𝔸 = {1, 2, …, r} is referred to as the underlying alphabet. A biword on 𝔸 is a 2 × n matrix α (n ≥ 0), whose entries are in 𝔸, the first (resp. second) row being called the top word (resp. bottom word) of the biword α. The number n is the length of α; we write ℓ(α) = n. Let B be the set of all biwords on 𝔸. Each biword can also be viewed as a word of biletters \binom{x}{a} written vertically. The product of two biwords is just the concatenation of them viewed as two words of biletters. The biword of length 0 is denoted by () = 1.

Let ℤ be the ring of all integers. The set A = ℤ⟨⟨B⟩⟩ of the formal sums ∑_{α} c(α)α, where α ∈ B and c(α) ∈ ℤ for all α ∈ B, together with the above multiplication, the free addition and the free scalar product is an algebra over ℤ, called the free biword large ℤ-algebra.

The right quantum algebra R is defined to be the associative algebra, which is the quotient of A by the two-sided ideal I generated by the commutation relations

(R1)  \binom{xy}{aa} = \binom{yx}{aa},
(R2)  \binom{xy}{ab} = \binom{yx}{ab} + \binom{yx}{ba} − \binom{xy}{ba},

for all letters a, b, x, y in 𝔸 and x ≠ y. Notice that the associativity of the right quantum algebra is set by definition. In fact, the associativity is a consequence of the commutation relations (R1) and (R2), as was proved in [FH05]. All further calculations in the paper will be made in the right quantum algebra R, unless explicitly indicated. The elements of R will be called expressions. If “can” is the canonical homomorphism of A onto R, we identify can 𝔹 with 𝔹 and each biword \binom{x_{1} x_{2} ··· x_{m}}{x_{j_{1}} x_{j_{2}} ···x_{jm}} occurring in an expression from R with the product \binom{x_{i_{1}}}{x_{1}}\binom{x_{i_{2}}}{x_{2}} ⋯ \binom{x_{im}}{x_{m}} in the quotient algebra R.

For each word w let \overline{w} be its non-decreasing rearrangement. The bosonic sum is defined to be the infinite sum

Bos := ∑_{w} (\overline{w} ; w) ,

where the sum is over all words w from the free monoid 𝔸^{∗} generated by 𝔸. The fermionic sum is defined by

Ferm := ∑_{J⊂𝔸}(−1)^{|J|} ∑_{σ∈S_{J}}(−1)^{invσ} (\begin{matrix}σ(i_{1}) & σ(i_{2}) & ⋯ & σ(i_{l}) \\ i_{1} & i_{2} & ⋯ & i_{l} \end{matrix}) ,

where J = {i_{1} < i_{2} < ⋯ < i_{l}} and S_{J} is the permutation group acting on the set J. Both bosonic and fermionic sums will be regarded as elements of R using the above identification. The quantum Master Theorem [GLZ05] is stated next.

Theorem 1. The identity

Ferm × Bos = 1

holds in the right quantum algebra R.

Our proof of Theorem 1 is based on specific techniques of Circuit Calculus (Section 2) and determinantal identities in the context of the right quantum algebra (Section 3). The end of the proof is made in Section 4.

2. Real and imaginary expressions

A circuit is a biword whose top word is a rearrangement of its bottom word. Each formal sum E = ∑_{α} c(α)α ∈ A is said to be imaginary (resp. real), if c(α) = 0 for all circuits α (resp. non-circuits α). If E, E′ ∈ A and E′ ≡ E (mod I), then E′ is imaginary (resp. real) if and only if E is imaginary (resp. real), as easily verified by considering the commutation relations (R1) and (R2). Accordingly, it makes sense to say that an expression in R is imaginary (resp. real). Notice that 0 is both real and imaginary. The terminology is directly inspired from Complex Analysis. The following properties, although easy to verify, are essential for the proof of the theorem.

(P1) Each expression E ∈ R can be decomposed in a unique way as a sum of a real expression ℜ(E) and an imaginary expression ℑ(E):

E = ℜ(E) + ℑ(E).

(P2) The real part operator ℜ and the imaginary part operator ℑ are linear. This means that for any two expresssions E, E′ and scalars c, c′ we have

\begin{aligned}ℜ(cE + c′E′) & = cℜ(E) + c′ℜ(E′), \\ ℑ(cE + c′E′) & = cℑ(E) + c′ℑ(E′). \end{aligned}

(P3) The real part operator ℜ and the imaginary part operator ℑ are idempotent and orthogonal to each other. This means that for every expresssion E we have

ℜ(ℜ(E)) = ℜ(E), ℑ(ℑ(E)) = ℑ(E) and ℜ(ℑ(E)) = ℑ(ℜ(E) = 0.

(P4) If E, E′ are two nonzero expressions from R and if E is real, then E × E′ is real (resp. imaginary) if and only if E′ is real (resp. imaginary).

Lemma 2. If E, E′ are two nonzero expressions from R and if E is real, then

ℜ(E × E′) = E × ℜ(E′).

Proof. From the above properties we have

ℜ(E × E′) = ℜ(E × (ℜ(E′) + ℑ(E′)))
= ℜ(E × ℜ(E′) + E × ℑ(E′))
= ℜ(E × ℜ(E′)) + ℜ(E × ℑ(E′))
= E × ℜ(E′).

Now, define the universe “Univ” to be the sum of all biwords whose top words are nondecreasing, that is,

Univ := ∑_{u,w} \binom{u}{w},

where u (resp. w) runs over the set of all nondecreasing words (resp. all words) and where u and w are of the same length: |u| = |w|. Both Boson and Fermion are sums of circuits. Moreover, ℜ(Univ) = Bos. By Lemma 2 the quantum Master Theorem is equivalent to the following theorem.

Theorem 3. The following identity

ℜ(Ferm × Univ) = 1

holds in the right quantum algebra R.

3. Determinantal Calculus

Let A = (a_{i,j})_{1≤i,j≤r} be a square matrix whose entries are expressions from R. We define the determinant of A to be

det(A) = ∑_{σ}(−1)^{invσ}a_{σ_{1},1}a_{σ_{2},2} ⋯ a_{σ_{r},r}.

In this formula σ runs over the permutation group S_{𝔸} of the set 𝔸. The ordering of the factors a_{σ_{1},1}, a_{σ_{2},2}, …, a_{σ_{r},r} matters, as the underlying algebra is noncommutative. However, several classical properties of the determinant still hold.

Property 4 (Linearity). When writing matrices as sequences of their r columns (c_{1}, c_{2}, …, c_{r}), we have

det(c_{1}, …, c_{i}, …, c_{r}) + det(c_{1}, …, c′_{i}, …, c_{r}) = det(c_{1}, …, c_{i} + c′_{i}, …, c_{r}).

Property 5 (Cofactor expansion). Let A = (a_{i,j})_{1≤i,j≤r} be a matrix of expressions and A_{ij} be the matrix obtained from A by deleting the i-th row and j-th column. Then

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

In the above identity we recognize the usual expansion of det(A) by cofactors of the rightmost column.

Let a_{i}, b_{i}, c_{i} (i = 1, 2, …, r) and x, y be scalars and form the r × rmatrix

A = ( \begin{matrix}⋯ & a_{1} + b_{1}\binom{1}{x} & c_{1} + b_{1}\binom{1}{y} & … \\ ⋯ & a_{2} + b_{2}\binom{2}{x} & c_{2} + b_{2}\binom{2}{y} & … \\ ... & ⋮ & ⋮ & ... \\ ⋯ & a_{r} + b_{r}\binom{r}{x} & c_{r} + b_{r}\binom{r}{y} & … \end{matrix} ) ,

where besides the two consecutive columns explicitly displayed the other columns are arbitrary. Let B denote the matrix derived from A by transposing those two consecutive columns.

Property 6 (Interchanging two columns). Let A and B be the two matrices just defined. Then det A = − det B.

Proof. In the expansion of det A the sum of the two terms

S_{ij} := ± ⋯ (a_{i} + b_{i}\binom{i}{x})(c_{j} + b_{j}\binom{j}{y}) ⋯ ∓ ⋯ (a_{j} + b_{j}\binom{j}{x})(c_{i} + b_{i}\binom{i}{y}) ⋯

may be put in a one-to-one correspondence with the sum

T_{ij} := ± ⋯ (c_{i} + b_{i}\binom{i}{y})(a_{j} + b_{j}\binom{j}{x}) ⋯ ∓ ⋯ (c_{j} + b_{j}\binom{j}{y})(a_{i} + b_{i}\binom{i}{x}) ⋯

in the expansion of det B. But

S_{ij} = ± ⋯ (a_{i}c_{j} + a_{i}b_{j}\binom{j}{y} + c_{j}b_{i}\binom{i}{x} + b_{i}b_{j}\binom{ij}{xy}

− a_{j}c_{i} − a_{j}b_{i}\binom{i}{y} − c_{i}b_{j}\binom{j}{x} − b_{i}b_{j}\binom{ji}{xy}) ⋯

T_{ij} = ± ⋯ (c_{i}a_{j} + c_{i}b_{j}\binom{j}{x} + b_{i}a_{j}\binom{i}{y} + b_{i}b_{j}\binom{ij}{yx}

− c_{j}a_{i} − c_{j}b_{i}\binom{i}{x} − b_{j}a_{i}\binom{j}{y} − b_{i}b_{j}\binom{ji}{yx}) · · · .

Because of the identity \binom{ij}{xy} − \binom{ji}{xy} = −(\binom{ij}{yx} − \binom{ji}{yx}) and the fact that the commutation relations can be made at any position within each biword (using the associativity property of the right quantum algebra) we conclude that S_{ij} = −T_{ij}.

It is worth noticing that Property 6 is only stated for very special matrices. In general, the column interchanging property does not hold for arbitrary matrices with entries in R.

Consider the r × r-matrix B^{(r)} = ( \binom{i}{j} )_{1≤i,j≤r}. Notice that every entry in B^{(r)} is a biletter. Define the fermion-matrix to be the matrix F^{(r)} = I − B^{(r)}. Using Property 4 (linearity) we have

Ferm = det(F^{(r)}) = det ( \begin{matrix}1 − \binom{1}{1} & −\binom{1}{2} & … & −\binom{1}{r} \\ −\binom{2}{1} & 1 − \binom{2}{2} & … & −\binom{2}{r} \\ ⋮ & ⋮ & ... & ⋮ \\ −\binom{r}{1} & −\binom{r}{2} & … & 1 − \binom{r}{r} \end{matrix} ) .

Let i ≤ r − 1 and replace the rightmost column in F^{(r)} by the i-th column of F^{(r)}. Let F_{i} be the resulting matrix, so that F_{i} has two identical columns.

Lemma 7. We have: det(F_{i}) = 0.

Proof. Permute columns i and i + 1, then columns i + 1 and i + 2, ⋯, finally columns r − 2 and r − 1, We obtain a matrix A whose rightmost two columns are identical. Property 6 implies that det(A) = 0 and also det(F_{i}) = ± det(A) = 0.

4. The proof

First, define

\begin{aligned}S_{i} = S_{i}^{(r)} & := \binom{i}{1} + \binom{i}{2} + ⋯ + \binom{i}{r}; \\ K_{i} = K_{i}^{(r)} & := \frac{1}{1 − S_{i}} = ∑_{n≥0} S_{i}^{n}. \end{aligned}

Lemma 8. The universe defined in Section 2 is equal to

Univ = K_{1}K_{2} ⋯ K_{r}.

Proof. By definition of “Univ” we have

Univ = ∑_{u,w} \binom{u}{w} = ∑_{w_{1},w_{2},···,w_{r}} \binom{11 ⋯ 1}{w_{1}}\binom{22 ⋯ 2}{w_{2}} ⋯ \binom{rr ⋯ r}{w_{r}}

= ∑_{w_{1}} \binom{11 ⋯ 1}{w_{1}} ∑_{w_{2}} \binom{22 ⋯ 2}{w_{2}} ⋯ ∑_{w_{r}} \binom{rr ⋯ r}{w_{r}}

= K_{1}K_{2} ⋯ K_{r}.

Lemma 9. We have: S_{i}S_{j} = S_{j}S_{i} and K_{i}K_{j} = K_{j}K_{i}.

Proof. Grouping the biwords by pairs if necessary we have:

S_{i}S_{j} = ∑_{a<b}(\binom{ij}{ab} + \binom{ij}{ba}) + ∑_{a} \binom{ij}{aa}

= ∑_{a<b}(\binom{ji}{ab} + \binom{ji}{ba}) + ∑_{a} \binom{ji}{aa}

= S_{j}S_{i}.

Proof of Theorem 3. Let M be the matrix obtained from the fermionmatrix F^{(r)} by adding all the leftmost r − 1 columns to the rightmost column:

M = ( \begin{matrix}1 − \binom{1}{1} & −\binom{1}{2} & … & 1 − S_{1} \\ −\binom{2}{1} & 1 − \binom{2}{2} & … & 1 − S_{2} \\ ⋮ & ⋮ & ... & ⋮ \\ −\binom{r}{1} & −\binom{r}{2} & … & 1 − S_{r} \end{matrix} )

By Property 4 and Lemma 7: det(M) = det(F^{(r)}) = Ferm. Let

E^{(r)} := Ferm × Univ = det(M) × Univ

By Lemmas 8 and 9

E^{(r)} = det ( \begin{matrix}1 − \binom{1}{1} & −\binom{1}{2} & … & (1 − S_{1}) × Univ \\ −\binom{2}{1} & 1 − \binom{2}{2} & … & (1 − S_{2}) × Univ \\ ⋮ & ⋮ & ... & ⋮ \\ −\binom{r}{1} & −\binom{r}{2} & … & (1 − S_{r}) × Univ \end{matrix} )

= det ( \begin{matrix}1 − \binom{1}{1} & −\binom{1}{2} & … & K_{2}K_{3} ⋯ K_{r} \\ −\binom{2}{1} & 1 − \binom{2}{2} & … & K_{1}K_{3} ⋯ K_{r} \\ ⋮ & ⋮ & ... & ⋮ \\ −\binom{r}{1} & −\binom{r}{2} & … & K_{1}K_{2} ⋯ K_{r−1} \end{matrix} ) .

Now applying Property 5 to the above determinant yields

E^{(r)} =(−1)^{r+1} det(M_{1r})K_{2}K_{3} ⋯ K_{r}
(−1)^{r+2} det(M_{2r})K_{1}K_{3} ⋯ K_{r} + ⋯
+ det(M_{rr})K_{1}K_{2} ⋯ K_{r−1},

where, as in Property 5, M_{ij} denotes the minor at position (i, j). For each biword occurring in F_{1} := det(M_{1r})K_{2}K_{3} ⋯ K_{r} there is a letter 1 in the bottom, but none in the top. This means that F_{1} does not contain any circuit. Thus ℜ(F_{1}) = 0. This argument is also valid for the other terms in the above summation of E^{(r)}, except for the last term. When taking the real part of the E^{(r)} we obtain:

ℜ(E^{(r)}) = ℜ(det(M_{rr})K_{1}K_{2} ⋯ K_{r−1}).

When expanding the product det(M_{rr})K_{1}K_{2} ⋯ K_{r−1} we get a sum of biwords. Those biwords containing biletters \binom{i}{r} with 1 ≤ i ≤ r − 1 vanish under the application ℜ. Therefore, each K_{i} can be replaced by K_{i}^{(r−1)}. Hence

ℜ(E^{(r)}) = ℜ(det(F^{(r−1)})K_{1}^{(r−1)}K_{2}^{(r−1)} ⋯ K_{r−1}^{(r−1)}) = ℜ(E^{(r−1)}).

Then, by iteration

ℜ(E^{(r)}) = ℜ(E^{(r−1)}) = ⋯ = ℜ(E^{(1)}) = ℜ((1 − \binom{1}{1})K_{1}^{(1)}) = 1.

Acknowledgement. The authors should like to thank the referee for his careful reading and knowledgeable remarks.

References

[Ca72] P. Cartier. — La série génératrice exponentielle, Applications probabilistes et algébriques, Publ. I.R.M.A., Université Louis Pasteur, Strasbourg, 1972, 68 pages.

[CF69] P. Cartier, D. Foata. — Problèmes combinatoires de commutations et réarrangements, Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85).

[Fo65] D. Foata. — Etude algébrique de certains problèmes d’Analyse Combinatoire et du Calcul des Probabilités, Publ. Inst. Statist. Univ. Paris, 14 (1965), pp. 81– 241.

[FH05] D. Foata, G.-N. Han. — A basis for the right quantum algebra and the “1 = q” principle, preprint, 2005.

[GLZ05] S. Garoufalidis, T. Tq Lê, D. Zeilberger. — The Quantum MacMahon Master Theorem, to be appear in Proc. Natl. Acad. Sci., 2005.

[Ge87] I. M. Gessel. — A Combinatorial Proof of the Multivariable Lagrange Inversion Formula, J. Comb. Theory, Ser. A, 45 (1987), pp. 178–195.

[Go60] I. J. Good. — Generalizations of several variables of Lagrange’s expansion with applications to stochastic processes, Proc. Cambridge Philos. Soc., 56 (1960), pp. 367–380.

[Go62] I. J. Good. — A short proof of MacMahon’s “Master Theorem” , Proc. Cambridge Philos. Soc., 58 (1962), pp. 360.

[Ho82] J. Hofbauer. — Lagrange Inversion, Séminaire Lotharingien de Combinatoire,

B06a, 1982, 28 pages, (http://www.mat.univie.ac.at/∼slc).

[Ma15] P. A. MacMahon. — Combinatory Analysis vol. I, II, Cambridge Univ. Press, 1915. Reprinted by Chelsea, New York, 1960.

[Z80] D. Zeilberger. — The algebra of linear partial difference operators and its applications, SIAM J. Math. Anal., 11, no. 6 (1980), pp. 919–932.

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

foata@math.u-strasbg.fr

Guo-Niu Han

I.R.M.A. UMR 7501

Université Louis Pasteur et CNRS 7, rue René-Descartes F-67084 Strasbourg, France

                       guoniu@math.u-strasbg.fr