MacMahon Master theorem
Encyclopedia
The MacMahon Master theorem (MMT) is a result in enumerative combinatorics
and linear algebra
, both branches of mathematics
. It was discovered by Percy MacMahon
and proved in his monograph Combinatory analysis (1916). It is often used to derive binomial identities, most notably Dixon's identity
.
who derived it from his mulilinear generalization of the Lagrange inversion theorem
. MMT was also popularized by Carlitz
who found an exponential power series version. In 1962, Good found a short proof of Dixon's identity from MMT. In 1969, Cartier
and Foata found a new proof of MMT by combining algebra
ic and bijective
ideas (built on Foata's thesis), and further applications to combinatorics on words
. 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
of MMT remained elusive. After Garoufalidis–Lê–Zeilberger's quantum
extension (2006), a number of noncommutative
extensions were developed by Foata–Han, Konvalinka–Pak, and Etingof–Pak. Further connections to Koszul algebra
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
re-discovered the MMT in the context of his generating function
approach to the angular momentum
theory of many-particle systems. Louck writes:
be a complex matrix, and let 
be formal variables. Consider a coefficient
Let
be another set of formal variables, and let 
be a diagonal matrix
. Then
where the sum runs over all nonnegative integer vectors
,
and
denotes the identity matrix
of size
.
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
. On the other hand, we can compute the determinant
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:
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. GoodI. 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 coefficientCoefficient
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 matrixDiagonal 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 matrixIdentity 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 matrixCompute 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: