MacMahon Master theorem

The MacMahon Master theorem (MMT) is a result in enumerative combinatorics

Enumerative combinatorics

Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations...

 and linear algebra

Linear algebra

Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...

, both branches of mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

. It was discovered by Percy MacMahon

Percy Alexander MacMahon

Percy Alexander MacMahon was a mathematician, especially noted in connection with the partitions of numbers and enumerative combinatorics.-Early life:...

 and proved in his monograph Combinatory analysis (1916). It is often used to derive binomial identities, most notably Dixon's identity

Dixon's identity

In mathematics, Dixon's identity is any of several different but closely related identities proved by A. C. Dixon, some involving finite sums of products of three binomial coefficients, and some evaluating a hypergeometric sum...

.

Background

In the monograph, MacMahon found so many applications of his result, he called it "a master theorem in the Theory of Permutations." The result was re-derived (with attribution) a number of times, most notably by I. J. Good

I. J. Good

Irving John Good was a British mathematician who worked as a cryptologist at Bletchley Park with Alan Turing. After World War II, Good continued to work with Turing on the design of computers and Bayesian statistics at the University of Manchester...

 who derived it from his mulilinear generalization of the Lagrange inversion theorem

Lagrange inversion theorem

In mathematical analysis, the Lagrange inversion theorem, also known as the Lagrange-Bürmann formula, gives the Taylor series expansion of the inverse function of an analytic function.-Theorem statement:...

. MMT was also popularized by Carlitz

Leonard Carlitz

Leonard Carlitz was an American mathematician. Carlitz supervised 44 Doctorates at Duke University and published over 770 papers.- Chronology :* 1907 Born Philadelphia, PA, USA* 1927 BA, University of Pennsylvania...

 who found an exponential power series  version. In 1962, Good found a short proof of Dixon's identity from MMT. In 1969, Cartier

Pierre Cartier (mathematician)

Pierre Cartier is a mathematician. An associate of the Bourbaki group and at one time a colleague of Alexander Grothendieck, his interests have ranged over algebraic geometry, representation theory, mathematical physics, and category theory....

 and Foata found a new proof of MMT by combining algebra

Algebra

Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...

ic and bijective

Bijective proof

In combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of...

 ideas (built on Foata's thesis), and further applications to combinatorics on words

Combinatorics on words

Combinatorics on words is a branch of mathematics which applies combinatorics to words and formal languages. The study of combinatorics on words arose independently within several branches of mathematics, e.g. number theory, group theory and probability...

. Since then, MMT became a standard tool in enumerative combinatorics.

Although various q-Dixon identities have been known for decades, except for a Krattenthaler–Schlosser extension (1999), the proper q-analog

Q-analog

Roughly speaking, in mathematics, specifically in the areas of combinatorics and special functions, a q-analog of a theorem, identity or expression is a generalization involving a new parameter q that returns the original theorem, identity or expression in the limit as q → 1...

 of MMT remained elusive. After Garoufalidis–Lê–Zeilberger's quantum

Quantum algebra

Quantum algebra is one of the top-level mathematics categories used by the arXiv.Subjects include:*Quantum groups*Skein theories*Operadic algebra*Diagrammatic algebra*Quantum field theory-External links:**R. Jagannathan,...

 extension (2006), a number of noncommutative

Noncommutative geometry

Noncommutative geometry is a branch of mathematics concerned with geometric approach to noncommutative algebras, and with construction of spaces which are locally presented by noncommutative algebras of functions...

 extensions were developed by Foata–Han, Konvalinka–Pak, and Etingof–Pak. Further connections to Koszul algebra

Koszul algebra

In abstract algebra, a Koszul algebra R is a graded k-algebra over which the residue field k has a linear minimal graded free resolution, i.e., there exists an exact sequence:...

 and quasideterminants were also found by Hai–Lorentz, Hai–Kriegk–Lorenz, Konvalinka–Pak, and others.

Finally, according to J. D. Louck, theoretical physicist Julian Schwinger

Julian Schwinger

Julian Seymour Schwinger was an American theoretical physicist. He is best known for his work on the theory of quantum electrodynamics, in particular for developing a relativistically invariant perturbation theory, and for renormalizing QED to one loop order.Schwinger is recognized as one of the...

 re-discovered the MMT in the context of his generating function

Generating function

In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...

 approach to the angular momentum

Angular momentum

In physics, angular momentum, moment of momentum, or rotational momentum is a conserved vector quantity that can be used to describe the overall state of a physical system...

 theory of many-particle systems. Louck writes:

It is the MacMahon Master Theorem that unifies the angular momentum properties of composite systems in the binary build-up of such systems from more elementary constituents.

Precise statement

Let be a complex matrix, and let be formal variables. Consider a coefficient

Coefficient

In mathematics, a coefficient is a multiplicative factor in some term of an expression ; it is usually a number, but in any case does not involve any variables of the expression...

Let be another set of formal variables, and let be a diagonal matrix

Diagonal matrix

In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The diagonal entries themselves may or may not be zero...

. Then
where the sum runs over all nonnegative integer vectors ,
and denotes the identity matrix

Identity matrix

In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...

 of size .

Derivation of Dixon's identity

Consider a matrix
Compute the coefficients G(2n, 2n, 2n) directly from the definition:
where the last equality follows from the fact that on the r.h.s. we have the product of the following coefficients:
which are computed from the binomial theorem

Binomial theorem

In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power n into a sum involving terms of the form axbyc, where the exponents b and c are nonnegative integers with , and the coefficient a of...

. On the other hand, we can compute the determinant

Determinant

In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

explicitly:
Therefore, by the MMT, we have new formula for the same coefficients:
where the last equality follows from the fact that we need use an equal number of times the all three terms in the power. Now equating two formulas for coefficients G(2n, 2n, 2n) we obtain an equivalent version of Dixon's identity: