マクマホンのマスター定理

数学において、マクマホンのマスター定理（MMT ）は、列挙的組合せ論と線型代数学における帰結です。パーシー・マクマホンによって発見され、彼の著書『組合せ解析』（1916年）で証明されました。二項式恒等式、特にディクソンの恒等式を導く際によく用いられます。

背景

マクマホンはモノグラフの中で、自身の研究結果の応用範囲が非常に広く、それを「順列理論におけるマスター定理」と呼んだ。彼はそのタイトルを次のように説明した。「マスター定理とは、他の方法では解決が難しい様々な問題を、見事かつ迅速に扱うことから名付けられた。」

この結果は（帰属表示付きで）何度も再導出されているが、最も有名なのは IJ Goodによるもので、彼はこれをラグランジュの逆定理の多重線型一般化から導出している。MMTはまた、指数級数版を発見したCarlitzによっても普及した。1962年、GoodはMMTからDixonの恒等式の簡潔な証明を見つけた。1969年、CartierとFoataは、代数的および単射的なアイデア（Foataの論文に基づく）と、単語の組合せ論へのさらなる応用を組み合わせ、痕跡の概念を導入することで、MMTの新しい証明を見つけた。それ以来、MMTは列挙組合せ論における標準的なツールとなっている。

クラッテンターラー・シュロッサー拡張（1999年）を除き、様々なq-ディクソン恒等式が数十年前から知られていましたが、MMTの適切なq-類似体は未だ解明されていませんでした。ガロウファリディス・レー・ツァイルバーガーによる量子拡張（2006年）の後、フォアタ・ハン、コンヴァリンカ・パク、エティンゴフ・パクによって多くの非可換拡張が開発されました。コシュル代数や準行列式とのさらなる関連性も、ハイ・ローレンツ、ハイ・クリーク・ローレンツ、コンヴァリンカ・パクらによって発見されました。

最後に、JD Louckによれば、理論物理学者ジュリアン・シュウィンガーは、多粒子系の角運動量理論における生成関数アプローチの文脈でMMTを再発見した。Louckは次のように書いている。

マクマホンマスター定理は、より基本的な構成要素から構成される二成分系における複合系の角運動量特性を統一するものである。^[1]

声明

を複素行列とし、を形式変数とする。任意の非負整数列に対して、対応する多項式の係数を考える。 $A=(a_{ij})_{m\times m}$ $x_{1},\ldots ,x_{m}$ $k_{1},\dots ,k_{m}$

G(k_{1},\dots ,k_{m})\,=\,{\bigl [}x_{1}^{k_{1}}\cdots x_{m}^{k_{m}}{\bigr ]}\,\prod _{i=1}^{m}\left(\sum _{j=1}^{m}a_{ij}x_{j}\right)^{k_{i}}.

（ここで、という表記は「における単項式の係数」を意味します。）を別の形式変数の集合とし、を対角行列とします。すると、 $[f]g$ $f$ $g$ $t_{1},\ldots ,t_{m}$ $T=\mathrm {diag} (t_{1},\dots ,t_{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$

組み合わせ解釈

を計算するには、次の繰り返し行列を構築します。ここで、の - 行目は回繰り返されます。次に、各行につき 1 つの要素だけを選択するすべての可能な方法を構築します。つまり、第 1 列の要素は回選択され、第 2 列の要素は回選択され、というように繰り返します。最後に、各方法について、選択された要素を乗算し、これらの積の合計はとなります。 $G(k_{1},\dots ,k_{m})$ $A={\begin{bmatrix}{\begin{bmatrix}a_{11}&\cdots &a_{1m}\\\vdots &&\vdots \\a_{11}&\cdots &a_{1m}\end{bmatrix}}\\\vdots \\{\begin{bmatrix}a_{m1}&\cdots &a_{mm}\\\vdots &&\vdots \\a_{m1}&\cdots &a_{mm}\end{bmatrix}}\end{bmatrix}}$ $i$ $A$ $k_{i}$ $k_{1}$ $k_{2}$ $G(k_{1},\dots ,k_{m})$

アプリケーション

が恒等式であるとき、これは多変数等比級数の恒等式を与える。を設定すると、次の式が得られる。とすると、は語の順序の入れ替えの数、すなわちの記号を並べ替える方法の数であり、これによって各が、以前にまたはなどが占めていた位置に配置される。マクマホンのマスター定理により、 $A$ $\prod _{i=1}^{m}{\frac {1}{1-t_{i}}}=\sum _{k_{1},\ldots ,k_{m}\geq 0}t_{1}^{k_{1}}\cdots t_{m}^{k_{m}}$ $t_{1},\dots ,t_{m}=1$ $\sum _{(k_{1},\dots ,k_{m})}G(k_{1},\dots ,k_{m})\,=\,{\frac {1}{\det(I_{m}-A)}}$ $A={\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}}$ $G(n,n,n)=\left[x_{1}^{n}x_{2}^{n}x_{3}^{n}\right]\left(x_{2}+x_{3}\right)^{n}\left(x_{1}+x_{3}\right)^{n}\left(x_{1}+x_{2}\right)^{n}$ $x_{1}^{n}x_{2}^{n}x_{3}^{n}$ $3n$ $x_{1}^{n}x_{2}^{n}x_{3}^{n}$ $x_{1}$ $x_{2}$ $x_{3}$ $G(n,n,n)=\sum _{k=0}^{n}{\binom {n}{k}}^{3}=[t_{1}^{n}t_{2}^{n}t_{3}^{n}]{\frac {1}{1-t_{1}t_{2}-t_{1}t_{3}-t_{2}t_{3}-2t_{1}t_{2}t_{3}}}$

ディクソンの正体

行列を考えてみましょう

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

したがって、MMTによれば、同じ係数に対して新しい式が得られます。

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

ここで最後の等式は、べき乗の3つの項を全て同じ回数使用する必要があるという事実から導かれます。係数G (2 n , 2 n , 2 n )の2つの式を等しくすると、ディクソンの恒等式と同等の式が得られます。

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

参照

永続

参考文献

^ Louck, James D. (2008).ユニタリー対称性と組合せ論. シンガポール: World Scientific. pp. viii. ISBN 978-981-281-472-2。

PAマクマホン、「組み合わせ分析」、第1巻および第2巻、ケンブリッジ大学出版局、1915-16年。
グッド、IJ (1962) 「マクマホンの『マスター定理』の簡潔な証明」ケンブリッジ哲学協会紀要. 58 (1): 160.書誌コード:1962PCPS...58..160G. doi :10.1017/ S0305004100036318 . S2CID 124876088. Zbl 0108.25104.
グッド、IJ (1962)。「マクマホンの『マスター定理』によるいくつかの『二項式』恒等式の証明」ケンブリッジ哲学協会紀要. 58 (1): 161– 162.書誌コード:1962PCPS...58..161G. doi :10.1017/ S030500410003632X . S2CID 122896760. Zbl 0108.25105.
P. Cartierおよび D. Foata、交換と配置の問題の組み合わせ、数学の講義ノート、第 1 号。 85、シュプリンガー、ベルリン、1969 年。
L. Carlitz、「マクマホンのマスター定理の応用」、SIAM Journal on Applied Mathematics 26 (1974)、431–436。
IP GouldenとDM Jackson、「Combinatorial Enumeration」、John Wiley、ニューヨーク、1983 年。
C. Krattenthalerと M. Schlosser、「多重 q 級数への応用を伴う新しい多次元行列逆行列」、Wayback Machineに 2011-07-24 でアーカイブ、Discrete Mathematics 204 (1999)、249–279。
S. Garoufalidis、TTQ Lê、D. Zeilberger、「量子マクマホンマスター定理」、米国科学アカデミー紀要103 (2006)、第 38 号、13928–13931 (eprint)。
M. Konvalinka とI. Pak、「マクマホンマスター定理の非可換拡張」、Advances in Mathematics 216 (2007)、第 1 号 (eprint)。
D. Foata と G.-N. Han、「Garoufalidis-Lê-Zeilberger 量子マクマホンマスター定理の新しい証明」、 Journal of Algebra 307 (2007)、第 1 号、424–431 (eprint)。
D. Foata と G.-N. Han、「量子マクマホンマスター定理の特殊化と拡張」、線形代数とその応用423 (2007)、第 2 ～ 3 号、445 ～ 455 (eprint)。
PH HaiとM. Lorenz、「Koszul代数と量子マクマホンマスター定理」、 Bull. Lond. Math. Soc. 39 (2007), no. 4, 667–676. (eprint).
P. Etingofと I. Pak、「マクマホンマスター定理の代数的拡張」、 アメリカ数学会紀要 136 (2008)、第 7 号、2279–2288 (eprint)。
PH Hai, B. Kriegk, M. Lorenz, N同次超代数, J. Noncommut. Geom. 2 (2008) 1–51 (eprint).
JD Louck、「ユニタリ対称性と組み合わせ論」、World Sci.、ハッケンサック、ニュージャージー、2008 年。

[1] Louck, James D. (2008).ユニタリー対称性と組合せ論. シンガポール: World Scientific. pp. viii. ISBN 978-981-281-472-2。