Основная теорема Мак-Магона

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

Предыстория

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

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

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

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

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

Точное утверждение

Позволять $A=(a_{ij})_{m\times m}$ — комплексная матрица, и пусть $x_{1},\ldots ,x_{m}$ быть формальными переменными. Рассмотрим коэффициент

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

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

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

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

Происхождение Диксона

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

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

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

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

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

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

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

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

Таким образом, по ММТ мы имеем новую формулу для тех же коэффициентов:

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

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

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

См. также

• Постоянный

Ссылки

• П.А. МакМахон, Комбинаторный анализ , тома 1 и 2, издательство Кембриджского университета, 1915–16.
• Хорошо, Эй Джей (1962). «Краткое доказательство «Главной теоремы» Мак-Магона ». Труды Кембриджского философского общества . 58 (1): 160. Бибкод : 1962PCPS...58..160G . дои : 10.1017/S0305004100036318 . S2CID   124876088 . Збл   0108.25104 .
• Хорошо, Эй Джей (1962). «Доказательство некоторых «биномиальных» тождеств посредством «Главной теоремы» Мак-Магона ». Труды Кембриджского философского общества . 58 (1): 161–162. Бибкод : 1962PCPS...58..161G . дои : 10.1017/S030500410003632X . S2CID   122896760 . Збл   0108.25105 .
• П. Картье и Д. Фоата, Комбинаторные задачи переключения и перестановок , Конспект лекций по математике , вып. 85, Шпрингер, Берлин, 1969.
• Л. Карлитц , Применение главной теоремы Мак-Магона, SIAM Journal on Applied Mathematics 26 (1974), 431–436.
• И. П. Гулден и Д. М. Джексон , Комбинаторное перечисление , Джон Уайли, Нью-Йорк, 1983.
• К. Краттенталер и М. Шлоссер, Новая многомерная обратная матрица с применением к множественным q -рядам , Discrete Mathematics 204 (1999), 249–279.
• С. Гаруфалидис, TTQ Ле и Д. Зейлбергер , Квантовая основная теорема Мак-Магона , Труды Национальной академии наук Соединенных Штатов Америки 103 (2006), вып. 38, 13928–13931 ( электронная печать ).
• М. Конвалинка и И. Пак , Некоммутативные расширения Главной теоремы Мак-Магона, Успехи в математике 216 (2007), вып. 1. ( электронная печать ).
• Д. Фоата и Г.-Н. Хан, Новое доказательство квантовой главной теоремы Мак-Магона Гаруфалидис-Ле-Зейлбергера, Journal of Algebra 307 (2007), вып. 1, 424–431 ( электронная печать ).
• Д. Фоата и Г.-Н. Хан, Специализации и расширения квантовой главной теоремы Мак-Магона, Линейная алгебра и ее приложения 423 (2007), вып. 2–3, 445–455 ( электронная печать ).
• П.Х. Хай и М. Лоренц, Алгебры Кошуля и квантовая основная теорема Мак-Магона, Bull. Лонд. Математика. Соц. 39 (2007), вып. 4, 667–676. ( электронная печать ).
• П. Этингоф и И. Пак, Алгебраическое расширение основной теоремы Мак-Магона, Труды Американского математического общества 136 (2008), вып. 7, 2279–2288 ( электронная печать ).
• П.Х. Хай, Б. Кригк и М. Лоренц, N -однородные супералгебры, J. Noncommut. Геом. 2 (2008) 1–51 ( электронная печать ).
• Дж. Д. Лоук, Унитарная симметрия и комбинаторика , World Sci., Хакенсак, Нью-Джерси, 2008.