Теорема Мак-Магона Мастер - MacMahon Master theorem

В математике основная теорема Мак-Магона ( MMT ) является результатом перечислительной комбинаторики и линейной алгебры . Он был открыт Перси Мак-Магоном и доказан в его монографии « Комбинаторный анализ» (1916). Он часто используется для получения биномиальных идентичностей, в первую очередь личности Диксона .

Задний план

В монографии Мак-Магон нашел столько приложений своего результата, что назвал его «основной теоремой теории перестановок». Он объяснил название следующим образом: «Основная теорема, основанная на мастерском и быстром способе решения различных вопросов, которые иначе было бы трудно решить».

Результат был повторно получен (с указанием авторства) несколько раз, в первую очередь И. Дж. Гудом, который получил его из своего полилинейного обобщения теоремы об обращении Лагранжа . MMT также популяризировал Карлитц, который нашел версию с экспоненциальным степенным рядом . В 1962 году Гуд нашел короткое доказательство личности Диксон в MMT. В 1969 году Картье и Фоата нашли новое доказательство ММТ, объединив алгебраические и биективные идеи (основанные на тезисе Фоата) и дальнейшие приложения к комбинаторике слов , введя понятие следов . С тех пор MMT стал стандартным инструментом в перечислительной комбинаторике.

Хотя различные q- тождества Диксона были известны на протяжении десятилетий, за исключением расширения Krattenthaler – Schlosser (1999), правильный q-аналог MMT оставался неуловимым. После квантового расширения Гаруфалидиса – Ле – Зейлбергера (2006) Фоата – Хан, Конвалинка – Пак и Этингоф – Пак разработали ряд некоммутативных расширений. Дальнейшие связи с алгеброй Кошуля и квазидетерминантами также нашли Хай – Лоренц, Хай – Кригк – Лоренц, Конвалинка – Пак и другие.

Наконец, согласно Дж. Д. Луку, физик-теоретик Джулиан Швингер повторно открыл ММТ в контексте своего подхода к производящей функции в теории углового момента систем многих частиц . Лук пишет:

Это основная теорема Мак-Магона, которая объединяет свойства углового момента составных систем в бинарном построении таких систем из более элементарных составляющих.

Точное заявление

Позвольте быть сложной матрицы, и пусть быть формальными переменными. Рассмотрим коэффициент${\ Displaystyle А = (а_ {ij}) _ {м \ раз м}}$${\ displaystyle x_ {1}, \ ldots, x_ {m}}$

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

(Здесь обозначение означает «коэффициент монома в ».) Позвольте быть другим набором формальных переменных, и пусть будет диагональной матрицей . потом ${\ displaystyle [f] g}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle t_ {1}, \ ldots, t_ {m}}$${\ displaystyle T = (\ delta _ {ij} t_ {i}) _ {m \ times m}}$

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

где сумма проходит по всем неотрицательным целочисленным векторам и обозначает единичную матрицу размера . ${\ Displaystyle (к_ {1}, \ точки, к_ {м})}$${\ displaystyle I_ {m}}$${\ displaystyle m}$

Вывод личности Диксон

Рассмотрим матрицу

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

Вычислите коэффициенты G (2 n , 2 n , 2 n ) непосредственно из определения:

${\ displaystyle {\ begin {align} 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 {align}}}$

где последнее равенство следует из того, что в правой части стоит произведение следующих коэффициентов:

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

которые вычисляются по биномиальной теореме . С другой стороны, мы можем вычислить определитель явно:

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

Таким образом, согласно MMT, у нас есть новая формула для тех же коэффициентов:

${\ displaystyle {\ begin {align} 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 {выровнено}}}$

где последнее равенство следует из того, что нам нужно использовать равное количество раз все три члена в степени. Приравнивая две формулы для коэффициентов G (2 n , 2 n , 2 n ), мы получаем эквивалентную версию тождества Диксона:

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

Смотрите также

• Постоянный

Рекомендации

• П. А. Мак-Магон, Комбинаторный анализ , тома 1 и 2, Cambridge University Press, 1915–16.
• Хорошо, Эй Джей (1962). «Краткое доказательство« Главной теоремы » Мак-Магона ». Proc. Cambridge Philos. Soc. 58 : 160. Zbl   0108.25104 . CS1 maint: обескураженный параметр ( ссылка )
• Хорошо, Эй Джей (1962). «Доказательства некоторых« биномиальных »тождеств с помощью« основной теоремы » Мак-Магона ». Proc. Cambridge Philos. Soc. 58 : 161–162. Zbl   0108.25105 . CS1 maint: обескураженный параметр ( ссылка )
• П. Картье и Д. Фоата, Проблемы, связанные с коммутацией и перестановками , Лекционные заметки по математике , вып. 85, Шпрингер, Берлин, 1969 г.
• Л. Карлитц , Применение основной теоремы Мак-Магона, Журнал SIAM по прикладной математике 26 (1974), 431–436.
• И. П. Гоулден и Д. М. Джексон , Комбинаторное перечисление , Джон Вили, Нью-Йорк, 1983.
• К. Краттенталер и М. Шлоссер, Новая многомерная обратная матрица с приложениями к нескольким q- рядам , Дискретная математика. 204 (1999), 249–279.
• С. Гаруфалидис, TTQ Ле, Д. Зейлбергер , Квантовая основная теорема Мак-Магона , Proc. Natl. Акад. наук. 103 (2006), нет. 38, 13928–13931 ( eprint ).
• М. Конвалинка, И. Пак , Некоммутативные расширения основной теоремы Мак-Магона, Adv. Математика. 216 (2007), нет. 1. ( eprint ).
• Д. Фоата и Г.-Н. Хан, Новое доказательство квантовой основной теоремы Мак-Магона Гаруфалидиса-Ле-Зейльбергера, J. Algebra 307 (2007), no. 1, 424–431 ( eprint ).
• Д. Фоата и Г.-Н. Хан, Специализации и расширения квантовой основной теоремы Мак-Магона, Linear Algebra Appl 423 (2007), вып. 2–3, 445–455 ( eprint ).
• PH Хай и М. Лоренц, алгебры Кошуля и квантовая основная теорема Мак-Магона, Бюлл. Лондон. Математика. Soc. 39 (2007), нет. 4, 667–676. ( eprint ).
• П. Этингоф и И. Пак, Алгебраическое расширение основной теоремы Мак-Магона, Proc. Амер. Математика. Soc. 136 (2008), нет. 7, 2279–2288 ( eprint ).
• Хай, Б. Кригк и М. Лоренц, N -однородные супералгебры, J. Noncommut. Геом. 2 (2008) 1–51 (электронный отпечаток ).
• Дж. Д. Лук, Унитарная симметрия и комбинаторика , Мировые науки, Хакенсак, Нью-Джерси, 2008.