MacMahons mastersats

Inom matematik är MacMahons mastersats ( MMT ) ett resultat i uppräkningskombinatorik och linjär algebra . Det upptäcktes av Percy MacMahon och bevisades i hans monografi Combinatory analysis (1916). Det används ofta för att härleda binomiala identiteter, framför allt Dixons identitet .

Bakgrund

I monografin hittade MacMahon så många tillämpningar av sitt resultat, att han kallade det "ett huvudteorem i teorin om permutationer." Han förklarade titeln på följande sätt: "en Master Theorem från det mästerliga och snabba sättet på vilket det behandlar olika frågor som annars är besvärliga att lösa."

Resultatet härleddes om (med tillskrivning) ett antal gånger, framför allt av IJ Good som härledde det från sin multilinjära generalisering av Lagranges inversionssats . MMT populariserades också av Carlitz som hittade en exponentiell kraftserieversion . 1962 hittade Good ett kort bevis på Dixons identitet från MMT. 1969 Cartier och Foata ett nytt bevis på MMT genom att kombinera algebraiska och bijektiva idéer (byggda på Foatas avhandling) och ytterligare tillämpningar på kombinatorik på ord , vilket introducerade begreppet spår . Sedan dess har MMT blivit ett standardverktyg inom enumerativ kombinatorik.

Även om olika q -Dixon-identiteter har varit kända i decennier, förutom en Krattenthaler-Schlosser-förlängning (1999), förblev den korrekta q-analogen av MMT svårfångad. Efter Garoufalidis–Lê–Zeilbergers kvantförlängning (2006 ) utvecklades ett antal icke-kommutativa förlängningar av Foata–Han, Konvalinka–Pak och Etingof–Pak. Ytterligare kopplingar till Koszul-algebra och kvasideterminanter hittades också av Hai–Lorentz, Hai–Kriegk–Lorenz, Konvalinka–Pak och andra.

Slutligen, enligt JD Louck, återupptäckte den teoretiske fysikern Julian Schwinger MMT i samband med sin genererande funktionsmetod till vinkelmomentteorin för många-partikelsystem . Louck skriver:

Det är MacMahon Master Theorem som förenar rörelsemängdsegenskaperna hos sammansatta system i den binära uppbyggnaden av sådana system från mer elementära beståndsdelar.

Exakt uttalande

Låt $A=(a_{ij})_{m\times m}$ vara en komplex matris, och låt $x_{1 },\ldots ,x_{m}$ är formella variabler. Tänk på en koefficient

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

(Här betyder notationen $[f]g$ "koefficienten för monomial $f$ i $g$ ".) Låt $​​{\displaystyle t_ {1},\ldots ,t_{m}}$ vara en annan uppsättning formella variabler, och låt $T=(\delta _{ij}t_{i}) _{m\times m}$ vara en diagonal matris . Sedan

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

där summan löper över alla icke-negativa heltalsvektorer $(k_{1},\dots ,k_{m})$ , och $I_{m}$ anger identitetsmatris av storlek $m$ .

Härledning av Dixons identitet

Tänk på en matris

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

Beräkna koefficienterna G (2 n , 2 n , 2 n ) direkt från definitionen:

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

där den sista likheten följer av att vi på höger sida har produkten av följande koefficienter:

$[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},$

som beräknas från binomialsatsen . Å andra sidan kan vi beräkna determinanten explicit :

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

Därför, med MMT, har vi en ny formel för samma koefficienter:

${\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{ Justerat}}$

där den sista likheten följer av att vi behöver använda lika många gånger alla tre termerna i potensen. Genom att nu likställa de två formlerna för koefficienterna G (2 n , 2 n , 2 n ) får vi en ekvivalent version av Dixons identitet:

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

Se även

• Permanent

• PA MacMahon, Combinatory analysis , vols 1 och 2, Cambridge University Press, 1915–16.
•    Bra, IJ (1962). "Ett kort bevis på MacMahons 'Master Theorem'" . Proceedings of the Cambridge Philosophical Society . 58 (1): 160. Bibcode : 1962PCPS...58..160G . doi : 10.1017/S0305004100036318 . S2CID 124876088 . Zbl 0108.25104 .
•    Bra, IJ (1962). "Bevis på vissa 'binomiala' identiteter med hjälp av MacMahons 'Master Theorem'" . Proceedings of the Cambridge Philosophical Society . 58 (1): 161–162. Bibcode : 1962PCPS...58..161G . doi : 10.1017/S030500410003632X . S2CID 122896760 . Zbl 0108.25105 .
• P. Cartier och D. Foata, Problèmes combinatoires de commutation et réarrangements , Lecture Notes in Mathematics , nr. 85, Springer, Berlin, 1969.
• L. Carlitz , An Application of MacMahons Master Theorem, SIAM Journal on Applied Mathematics 26 (1974), 431–436.
• IP Goulden och DM Jackson , Combinatorial Enumeration , John Wiley, New York, 1983.
• C. Krattenthaler och M. Schlosser, En ny multidimensionell matris invers med tillämpningar på flera q -serier , Discrete Mathematics 204 (1999), 249–279.
• S. Garoufalidis, TTQ Lê och D. Zeilberger , The Quantum MacMahon Master Theorem , Proceedings of the National Academy of Sciences of the United States of America 103 (2006), nr. 38, 13928–13931 ( eprint ).
• M. Konvalinka och I. Pak , Non-commutative extensions of the MacMahon Master Theorem, Advances in Mathematics 216 (2007), nr. 1. ( eprint ).
• D. Foata och G.-N. Han, Ett nytt bevis på Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem, Journal of Algebra 307 (2007), nr. 1, 424–431 ( eprint ).
• D. Foata och G.-N. Han, Specialiseringar och utökningar av kvant-MacMahon Master Theorem, Linjär algebra och dess tillämpningar 423 (2007), nr. 2–3, 445–455 ( eprint ).
• PH Hai och M. Lorenz, Koszul algebras och kvantMacMahons mastersats, Bull. Lond. Matematik. Soc. 39 (2007), nr. 4, 667-676. ( eprint ).
• P. Etingof och I. Pak, An algebraic extension of the MacMahon master theorem, Proceedings of the American Mathematical Society 136 (2008), nr. 7, 2279–2288 ( eprint ).
• PH Hai, B. Kriegk och M. Lorenz, N -homogena superalgebras, J. Noncommut. Geom. 2 (2008) 1–51 ( eprint ).
• JD Louck, Unitary symmetry and combinatorics , World Sci., Hackensack, NJ, 2008.