MacMahon's master theorem

For a basic result in analysis of algorithms, see Master theorem.

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.

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 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 algebraic and bijective ideas (built on Foata's thesis), and further applications to combinatorics on words. 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 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:

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 $A=(a_{ij})_{m\times m}$ be a complex matrix, and let $x_{1},\ldots ,x_{m}$ be formal variables. Consider a coefficient

$G(k_{1},\dots ,k_{m})\,=\,{\bigl [}x_{1}^{k_{1}}\cdots x_{m}^{k_{m}}{\bigr ]}\,\prod _{i=1}^{m}{\bigl (}a_{i1}x_{1}+\dots +a_{im}x_{m}{\bigl )}^{k_{i}}.$

Let $t_{1},\ldots ,t_{m}$ be another set of formal variables, and let $T=(\delta _{ij}t_{i})_{m\times m}$ be a diagonal matrix. Then

$\sum _{(k_{1},\dots ,k_{m})}G(k_{1},\dots ,k_{m})\,t_{1}^{k_{1}}\cdots t_{m}^{k_{m}}\,=\,{\frac {1}{\det(I_{m}-TA)}},$

where the sum runs over all nonnegative integer vectors $(k_{1},\dots ,k_{m})$, and $I_{m}$ denotes the identity matrix of size $m$.

Linear algebra reformulation and proof

The identity can be reformulated as follows.

$\sum _{l=0,...,\infty }Trace_{Sym^{l}(V)}((TA)^{sym(l)})={\frac {1}{\det(I_{m}-TA)}},$

here V is n-dimensional complex vector space with basis x_k and TA can be considered as linear operator V->V, Sym^lV is l-th symmetric tensor power, (TA)^sym(l) is induced operator $Sym^{l}(V)\to Sym^{l}(V)$.

Indeed, this reformulation is almost by definition of symmetric tensor power Sym^lV, which can be identified with the space of polynoms of degree l in x_k, k=1,...n . The expression

$\prod _{i=1}^{m}{\bigl (}a_{i1}x_{1}+\dots +a_{im}x_{m}{\bigl )}^{k_{i}}.$

Is precisely the action of A on the Sym^l(V). Multiplication on $t_{1}^{k_{1}}...t_{n}^{k_{n}}$ corresponds to the action of T on the Sym^l(V).

Thus one concludes that

$G(k_{1},\dots ,k_{m})t_{1}^{k_{1}}\cdots t_{m}^{k_{m}}$

is exactly the diagonal element of the matrix $(TA)^{sym(l)}$ corresponding to basic element $x_{1}^{k_{1}}...x_{n}^{k_{n}}\in Sym^{l}(V)$, with $l=\sum _{i=1,...,n}k_{i}$. And hence the sum of all diagonal elements gives the trace - as it is written in the formula above.

Derivation of Dixon's identity

Consider a matrix

$A={\begin{pmatrix}0&1&-1\\-1&0&1\\1&-1&0\end{pmatrix}}.$

Compute the coefficients G(2n, 2n, 2n) directly from the definition:

$G(2n,2n,2n)={\bigl [}x_{1}^{2n}x_{2}^{2n}x_{3}^{2n}{\bigl ]}(x_{2}-x_{3})^{2n}(x_{3}-x_{1})^{2n}(x_{1}-x_{2})^{2n}\,=\,\sum _{k=0}^{2n}(-1)^{k}{\binom {2n}{k}}^{3},$

where the last equality follows from the fact that on the r.h.s. we have the product of the following coefficients:

$[x_{2}^{k}x_{3}^{2n-k}](x_{2}-x_{3})^{2n},\ \ [x_{3}^{k}x_{1}^{2n-k}](x_{2}-x_{3})^{2n},\ \ [x_{1}^{k}x_{2}^{2n-k}](x_{1}-x_{2})^{2n},$

which are computed from the binomial theorem. On the other hand, we can compute the determinant explicitly:

$\det(I-TA)\,=\,\det {\begin{pmatrix}1&-t_{1}&t_{1}\\t_{2}&1&-t_{2}\\-t_{3}&t_{3}&1\end{pmatrix}}\,=\,1+{\bigl (}t_{1}t_{2}+t_{1}t_{3}+t_{2}t_{3}{\bigr )}.$

Therefore, by the MMT, we have new formula for the same coefficients:

$G(2n,2n,2n)\,=\,{\bigl [}t_{1}^{2n}t_{2}^{2n}t_{3}^{2n}{\bigl ]}(-1)^{3n}{\bigl (}t_{1}t_{2}+t_{1}t_{3}+t_{2}t_{3}{\bigr )}^{3n}\,=\,(-1)^{n}{\binom {3n}{n,n,n}},$

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:

$\sum _{k=0}^{2n}(-1)^{k}{\binom {2n}{k}}^{3}\,=\,(-1)^{n}{\binom {3n}{n,n,n}}.$

References

• P.A. MacMahon, Combinatory analysis, vols 1 and 2, Cambridge University Press, 1915–16.
• I.J. Good, A short proof of MacMahon's ‘Master Theorem’, Proc. Cambridge Philos. Soc. 58 (1962), 160.
• I.J. Good, Proofs of some `binomial' identities by means of MacMahon's ‘Master Theorem’. Proc. Cambridge Philos. Soc. 58 (1962), 161–162.
• 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 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, Disc. Math. 204 (1999), 249–279.
• S. Garoufalidis, T. T. Q. Lê and D. Zeilberger, The Quantum MacMahon Master Theorem, Proc. Natl. Acad. of Sci. 103 (2006), no. 38, 13928–13931 (eprint).
• M. Konvalinka and I. Pak, Non-commutative extensions of the MacMahon Master Theorem, Adv. Math. 216 (2007), no. 1. (eprint).
• D. Foata and G.-N. Han, A new proof of the Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem, J. Algebra 307 (2007), no. 1, 424–431 (eprint).
• D. Foata and G.-N. Han, Specializations and extensions of the quantum MacMahon Master Theorem, Linear Algebra Appl 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, Proc. Amer. Math. Soc. 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.
• T. Umeda, Application of Koszul complex to Wronski relations for U(gl_n), Comm. Math. Helvetici, 78 (2003), 4, 663-680 (paper)

• A. Isaev, O. Ogievetsky, P. Pyatov, On quantum matrix algebras satisfying the CayleyHamilton-Newton identities, J. Phys. A, 32 (1999), no. 9, L115–L121 (eprint)