Teorema mestre de MacMahon

En matemàtiques, el teorema mestre de MacMahon (TMM) és un resultat en combinatòria enumerativa i àlgebra lineal. Va ser descobert per Percy MacMahon i provat en la seva monografia Anàlisi combinada (1916). S'utilitza sovint per obtenir identitats binomials, sobretot la identitat de Dixon.

Antecedents

A la monografia, MacMahon va trobar tantes aplicacions del seu resultat, que el va anomenar «un teorema mestre en la teoria de les permutacions». Va explicar el títol de la manera següent: «Un teorema mestre per la manera magistral i ràpida en què tracta diverses qüestions que tinguin problemes per resoldre».

El resultat va ser derivat (amb atribució) diverses vegades, sobretot per I. J. Good, que el va derivar de la seva generalització multilineal del teorema d'inversió de Lagrange. El TMM també va ser popularitzat per Carlitz, qui va trobar una versió en una sèrie de potències exponencial. El 1962, Good va trobar una prova breu de la identitat de Dixon del TMM. El 1969, Cartier i Foata van trobar una nova prova de TMM combinant idees algebraiques i bijectives (basades en la tesi de Foata) i altres aplicacions a la combinatòria de les paraules, introduint el concepte de traces. Des de llavors, el TMM s'ha convertit en una eina estàndard en combinatòria enumerativa.

Tot i que des de fa dècades es coneixen diverses identitats de q-Dixon, excepte una extensió de Krattenthaler–Schlosser (1999), el q-anàleg adequat del TMM va romandre evasiu. Després de l'extensió quàntica de Garoufalidis–Lê–Zeilberger (2006), una sèrie d'extensions no comunicatives van ser desenvolupades per Foata-Han, Konvalinka-Pak i Etingof-Pak. Hai-Lorentz, Hai-Kriegk-Lorenz, Konvalinka-Pak i altres han trobat també connexions amb l'àlgebra de Koszul i els quasideterminants.

Finalment, segons J. D. Louck, el físic teòric Julian Schwinger va tornar a descobrir el TMM en el context del seu enfocament de funcions generatrius a la teoria del moment angular dels sistemes de moltes partícules. Louck escriu: «És el teorema mestre de MacMahon que unifica les propietats del moment angular dels sistemes compostos en la creació binària d'aquests sistemes a partir de components més elementals».

Enunciat precís

Sigui $A=(a_{ij})_{m\times m}$ una matriu complexa i que $x_{1},\ldots ,x_{m}$ siguin variables formals. Considerem un coeficient

$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}}.$

(Aquí la notació $[f]g$ significa «el coeficient de monomi $f$ en $g$»). Sigui $t_{1},\ldots ,t_{m}$ un altre conjunt de variables formals i que $T=(\delta _{ij}t_{i})_{m\times m}$ sigui una matriu diagonal. Llavors

$\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)}},$

on la suma agrupa tots els vectors enters no-negatius $(k_{1},\dots ,k_{m})$, i $I_{m}$ denota la matriu identitat de mida $m$.

Derivació de la identitat de Dixon

Considerem la matriu

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

Calculem els coeficients G(2n, 2n, 2n) directament de la definició

${\begin{aligned}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}\\[6pt]&=\,\sum _{k=0}^{2n}(-1)^{k}{\binom {2n}{k}}^{3},\end{aligned}}$

on la darrera igualtat es deriva del fet que a la part dreta tenim el producte dels coeficients següents:

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

que es calculen a partir del teorema binomial. D'altra banda, podem calcular explícitament el determinant:

$\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 )}.$

Per tant, pel TMM, tenim una nova fórmula per als mateixos coeficients:

${\begin{aligned}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}\\[6pt]&=(-1)^{n}{\binom {3n}{n,n,n}},\end{aligned}}$

on l'última igualtat es deriva del fet que hem d'utilitzar un nombre igual de vegades els tres termes de la potència. Si equiparem les dues fórmules per als coeficients G(2n, 2n, 2n) obtenim una versió equivalent de la identitat de Dixon:

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

Bibliografia

• MacMahon, P.A. «Combinatory analysis» (en anglès). Cambridge University Press, 1, 2, 1915–1916.
• Good, I.J. «A short proof of MacMahon's ‘Master Theorem’» (en anglès). Proc. Cambridge Philos. Soc., 58, 1962, pàg. 160.
• Good, I.J. «Proofs of some binomial identities by means of MacMahon's ‘Master Theorem’». Proc. Cambridge Philos. Soc., 58, 1962, pàg. 161–162.
• Cartier, P.; Foata, D. «Problèmes combinatoires de commutation et réarrangements». Lecture Notes in Mathematics. Springer [Berlin], 85, 1969.
• Carlitz, L. «An Application of MacMahon's Master Theorem». SIAM Journal on Applied Mathematics, 26, 1974, pàg. 431–436..
• Goulden, I.P.; Jackson, D. M. «Combinatorial Enumeration». John Wiley [Nova York], 1983.
• Krattenthaler, C.; Schlosser, M. «A new multidimensional matrix inverse with applications to multiple q-series». Discrete Math, 204, 1999, pàg. 249–279. Arxivat de l'original el 2011-07-24 [Consulta: 4 abril 2020]. Arxivat 2011-07-24 a Wayback Machine.
• 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.

Vegeu també

• Permanent