In mathematics, MacMahon's master theorem (MMT) is a result in
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. More generally, given an inf ...
and
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrix (mathemat ...
. 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
In mathematics, Dixon's identity (or Dixon's theorem or Dixon's formula) 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 ...
.
Background
In the monograph, MacMahon found so many applications of his result, he called it "a master theorem in the Theory of Permutations." He explained the title as follows: "a Master Theorem from the masterly and rapid fashion in which it deals with various questions otherwise troublesome to solve."
The result was re-derived (with attribution) a number of times, most notably by
I. J. Good who derived it from his multilinear generalization of the
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. Lagrange inversion is a special case of the inverse function ...
. MMT was also popularized by
Carlitz who found an
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
* Exponential function, also:
**Matrix exponential, the matrix analogue to the above
*Exponential decay, decrease at a rate proportional to value
* Ex ...
power series
In mathematics, a power series (in one variable) is an infinite series of the form
\sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots
where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a co ...
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
Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...
ic and
bijective
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...
ideas (built on Foata's thesis) and further applications to
combinatorics on words
Combinatorics on words is a fairly new field of mathematics, branching from combinatorics, which focuses on the study of words and formal languages. The subject looks at letters or symbols, and the sequences they form. Combinatorics on words ...
, introducing the concept of
trace
Trace may refer to:
Arts and entertainment Music
* ''Trace'' (Son Volt album), 1995
* ''Trace'' (Died Pretty album), 1993
* Trace (band), a Dutch progressive rock band
* ''The Trace'' (album), by Nell
Other uses in arts and entertainment
* ...
s. Since then, MMT has become 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
In mathematics, 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 . Typically, mathematicians are interested in ''q'' ...
of MMT remained elusive. After Garoufalidis–Lê–Zeilberger's
quantum
In physics, a quantum (: quanta) is the minimum amount of any physical entity (physical property) involved in an interaction. The fundamental notion that a property can be "quantized" is referred to as "the hypothesis of quantization". This me ...
extension (2006), a number of
noncommutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Perhaps most familiar as a p ...
extensions were developed by Foata–Han, Konvalinka–Pak, and Etingof–Pak. Further connections to
Koszul algebra
In abstract algebra, a Koszul algebra R is a graded k-algebra over which the ground field k has a linear minimal graded free resolution, ''i.e.'', there exists an exact sequence:
:\cdots \rightarrow (R(-i))^ \rightarrow \cdots \rightarrow (R(- ...
and
quasideterminant In mathematics, the quasideterminant is a replacement for the determinant for matrices with noncommutative entries. Example 2 × 2 quasideterminants are as follows:
:
\left, \begin
a_ & a_ \\
a_ & a_ \end
\_ = a_ - ...
s were also found by Hai–Lorentz, Hai–Kriegk–Lorenz, Konvalinka–Pak, and others.
Finally, according to J. D. Louck, the
theoretical physicist
Theoretical physics is a branch of physics that employs mathematical models and abstractions of physical objects and systems to rationalize, explain, and predict natural phenomena. This is in contrast to experimental physics, which uses experi ...
Julian Schwinger
Julian Seymour Schwinger (; February 12, 1918 – July 16, 1994) was a Nobel Prize-winning American theoretical physicist. He is best known for his work on quantum electrodynamics (QED), in particular for developing a relativistically invariant ...
re-discovered the MMT in the context of his
generating function
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...
approach to the
angular momentum
Angular momentum (sometimes called moment of momentum or rotational momentum) is the rotational analog of Momentum, linear momentum. It is an important physical quantity because it is a Conservation law, conserved quantity – the total ang ...
theory of
many-particle systems. Louck writes:
Statement
Let
be a complex matrix, and let
be formal variables. For any sequence of non-negative integers
, consider the associated
coefficient
In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
of a polynomial:
:
(Here the notation
means "the coefficient of monomial
in
".) Let
be another set of formal variables, and let
be a
diagonal matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagon ...
. Then
:
where the sum runs over all nonnegative integer vectors
,
and
denotes the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. It has unique properties, for example when the identity matrix represents a geometric transformation, the obje ...
of size
.
Combinatorial interpretation
To compute
, one can construct the following repeated matrix:
where the
-th row of
is repeated for
times. Then, one constructs all possible ways to pick exactly one element per row, such that elements in the first column is picked
times, elements in the second column is picked
times, and so on. Finally, for each such way, multiply the elements picked, and the sum of all these products is
.
Applications
When
is the identity, this gives a multivariate
geometric
Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
series
Series may refer to:
People with the name
* Caroline Series (born 1951), English mathematician, daughter of George Series
* George Series (1920–1995), English physicist
Arts, entertainment, and media
Music
* Series, the ordered sets used i ...
identity:
Setting
, we get an expression
where the expression on the right is due to the exp-tr-log identity.
Let
, then
is the number of
derangements of the word
, i.e. ways to permute the
symbols of
, such that each
lands in the location previously occupied by some
or
, etc. By MacMahon's master theorem,
Dixon's identity
In mathematics, Dixon's identity (or Dixon's theorem or Dixon's formula) 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 ...
Consider a matrix
:
Compute the coefficients ''G''(2''n'', 2''n'', 2''n'') directly from the definition:
:
where the last equality follows from the fact that on the right-hand side we have the product of the following coefficients:
:
which are computed from the
binomial theorem
In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, the power expands into a polynomial with terms of the form , where the exponents and a ...
. On the other hand, we can compute the
determinant
In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
explicitly:
:
Therefore, by the MMT, we have a new formula for the same coefficients:
:
where the last equality follows from the fact that we need to use an equal number of times all three terms in the power. Now equating the two formulas for coefficients ''G''(2''n'', 2''n'', 2''n'') we obtain an equivalent version of Dixon's identity:
:
See also
*
Permanent
References
* P.A. MacMahon,
Combinatory analysis', vols 1 and 2, Cambridge University Press, 1915–16.
*
* {{cite journal , zbl=0108.25105 , authorlink=I. J. Good , first=I.J. , last=Good , title=Proofs of some 'binomial' identities by means of MacMahon's 'Master Theorem' , journal=
Proceedings of the Cambridge Philosophical Society
''Mathematical Proceedings of the Cambridge Philosophical Society'' is a mathematical journal published by Cambridge University Press for the Cambridge Philosophical Society. It aims to publish original research papers from a wide range of pure ...
, volume=58 , year=1962 , issue=1 , pages=161–162 , doi=10.1017/S030500410003632X , bibcode=1962PCPS...58..161G , s2cid=122896760
*
P. Cartier and D. Foata
Problèmes combinatoires de commutation et réarrangements ''Lecture Notes in Mathematics'', no. 85, Springer, Berlin, 1969.
*
L. Carlitz, An Application of MacMahon's Master Theorem, ''
SIAM Journal on Applied Mathematics
The ''SIAM Journal on Applied Mathematics'' is a peer-reviewed academic journal in applied mathematics published by the Society for Industrial and Applied Mathematics (SIAM), with Paul A. Martin (Colorado School of Mines) as its editor-in-chief. I ...
'' 26 (1974), 431–436.
*
I.P. Goulden and
D. M. Jackson, ''Combinatorial Enumeration'', John Wiley, New York, 1983.
*
C. Krattenthaler and M. Schlosser
A new multidimensional matrix inverse with applications to multiple ''q''-series ''
Discrete Mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
'' 204 (1999), 249–279.
* S. Garoufalidis, T. T. Q. Lê and
D. ZeilbergerThe Quantum MacMahon Master Theorem ''
'' 103 (2006), no. 38, 13928–13931
eprint.
* M. Konvalinka and
I. Pak, Non-commutative extensions of the MacMahon Master Theorem, ''
Advances in Mathematics
''Advances in Mathematics'' is a peer-reviewed scientific journal covering research on pure mathematics. It was established in 1961 by Gian-Carlo Rota. The journal publishes 18 issues each year, in three volumes.
At the origin, the journal aimed ...
'' 216 (2007), no. 1.
eprint.
* D. Foata and G.-N. Han, A new proof of the Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem, ''
Journal of Algebra
''Journal of Algebra'' (ISSN 0021-8693) is an international mathematical research journal in algebra. An imprint of Academic Press, it is published by Elsevier
Elsevier ( ) is a Dutch academic publishing company specializing in scientific, te ...
'' 307 (2007), no. 1, 424–431
eprint.
* D. Foata and G.-N. Han, Specializations and extensions of the quantum MacMahon Master Theorem, ''
Linear Algebra and its Applications
''Linear Algebra and its Applications'' is a biweekly peer-reviewed mathematics journal published by Elsevier and covering matrix theory and finite-dimensional linear algebra.
History
The journal was established in January 1968 with A.J. Hoffm ...
'' 423 (2007), no. 2–3, 445–455
eprint.
* P.H. Hai and M. Lorenz, Koszul algebras and the quantum MacMahon master theorem, ''Bull. Lond. Math. Soc.'' 39 (2007), no. 4, 667–676.
eprint.
*
P. Etingof and I. Pak, An algebraic extension of the MacMahon master theorem, ''
Proceedings of the American Mathematical Society
''Proceedings of the American Mathematical Society'' is a monthly peer-reviewed scientific journal of mathematics published by the American Mathematical Society. The journal is devoted to shorter research articles. As a requirement, all articles ...
'' 136 (2008), no. 7, 2279–2288
eprint.
* P.H. Hai, B. Kriegk and M. Lorenz, ''N''-homogeneous superalgebras, ''J. Noncommut. Geom.'' 2 (2008) 1–51
eprint.
* J.D. Louck, ''Unitary symmetry and combinatorics'', World Sci., Hackensack, NJ, 2008.
Enumerative combinatorics
Factorial and binomial topics
Articles containing proofs
Theorems in combinatorics
Theorems in linear algebra