Misplaced Pages

MacMahon's master theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Result in enumerative combinatorics and linear algebra

In mathematics, MacMahon's master theorem (MMT) is a result in enumerative combinatorics and linear algebra. It was discovered by Percy MacMahon and proved in his monograph Combinatory analysis (1916). It is often used to derive binomial identities, most notably Dixon's identity.

Background

In the monograph, MacMahon found so many applications of his result, he called it "a master theorem in the Theory of Permutations." He explained the title as follows: "a Master Theorem from the masterly and rapid fashion in which it deals with various questions otherwise troublesome to solve."

The result was re-derived (with attribution) a number of times, most notably by I. J. Good who derived it from his multilinear generalization of the Lagrange inversion theorem. MMT was also popularized by Carlitz who found an exponential power series version. In 1962, Good found a short proof of Dixon's identity from MMT. In 1969, Cartier and Foata found a new proof of MMT by combining algebraic and bijective ideas (built on Foata's thesis) and further applications to combinatorics on words, introducing the concept of traces. Since then, MMT has become a standard tool in enumerative combinatorics.

Although various q-Dixon identities have been known for decades, except for a Krattenthaler–Schlosser extension (1999), the proper q-analog of MMT remained elusive. After Garoufalidis–Lê–Zeilberger's quantum extension (2006), a number of noncommutative extensions were developed by Foata–Han, Konvalinka–Pak, and Etingof–Pak. Further connections to Koszul algebra and quasideterminants were also found by Hai–Lorentz, Hai–Kriegk–Lorenz, Konvalinka–Pak, and others.

Finally, according to J. D. Louck, the theoretical physicist Julian Schwinger re-discovered the MMT in the context of his generating function approach to the angular momentum theory of many-particle systems. Louck writes:

It is the MacMahon Master Theorem that unifies the angular momentum properties of composite systems in the binary build-up of such systems from more elementary constituents.

Precise statement

Let A = ( a i j ) m × m {\displaystyle A=(a_{ij})_{m\times m}} be a complex matrix, and let x 1 , … , x m {\displaystyle x_{1},\ldots ,x_{m}} be formal variables. Consider a coefficient

G ( k 1 , … , k m ) = [ x 1 k 1 ⋯ x m k m ] ∏ i = 1 m ( a i 1 x 1 + ⋯ + a i m x m ) k i . {\displaystyle G(k_{1},\dots ,k_{m})\,=\,{\bigl }\,\prod _{i=1}^{m}{\bigl (}a_{i1}x_{1}+\dots +a_{im}x_{m}{\bigl )}^{k_{i}}.}

(Here the notation [ f ] g {\displaystyle g} means "the coefficient of monomial f {\displaystyle f} in g {\displaystyle g} ".) Let t 1 , … , t m {\displaystyle t_{1},\ldots ,t_{m}} be another set of formal variables, and let T = ( δ i j t i ) m × m {\displaystyle T=(\delta _{ij}t_{i})_{m\times m}} be a diagonal matrix. Then

∑ ( k 1 , … , k m ) G ( k 1 , … , k m ) t 1 k 1 ⋯ t m k m = 1 det ( I m − T A ) , {\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)}},}

where the sum runs over all nonnegative integer vectors ( k 1 , … , k m ) {\displaystyle (k_{1},\dots ,k_{m})} , and I m {\displaystyle I_{m}} denotes the identity matrix of size m {\displaystyle m} .

Derivation of Dixon's identity

Consider a matrix

A = ( 0 1 − 1 − 1 0 1 1 − 1 0 ) . {\displaystyle A={\begin{pmatrix}0&1&-1\\-1&0&1\\1&-1&0\end{pmatrix}}.}

Compute the coefficients G(2n, 2n, 2n) directly from the definition:

G ( 2 n , 2 n , 2 n ) = [ x 1 2 n x 2 2 n x 3 2 n ] ( x 2 − x 3 ) 2 n ( x 3 − x 1 ) 2 n ( x 1 − x 2 ) 2 n = ∑ k = 0 2 n ( − 1 ) k ( 2 n k ) 3 , {\displaystyle {\begin{aligned}G(2n,2n,2n)&={\bigl }(x_{2}-x_{3})^{2n}(x_{3}-x_{1})^{2n}(x_{1}-x_{2})^{2n}\\&=\,\sum _{k=0}^{2n}(-1)^{k}{\binom {2n}{k}}^{3},\end{aligned}}}

where the last equality follows from the fact that on the right-hand side we have the product of the following coefficients:

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

which are computed from the binomial theorem. On the other hand, we can compute the determinant explicitly:

det ( I − T A ) = det ( 1 − t 1 t 1 t 2 1 − t 2 − t 3 t 3 1 ) = 1 + ( t 1 t 2 + t 1 t 3 + t 2 t 3 ) . {\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 )}.}

Therefore, by the MMT, we have a new formula for the same coefficients:

G ( 2 n , 2 n , 2 n ) = [ t 1 2 n t 2 2 n t 3 2 n ] ( − 1 ) 3 n ( t 1 t 2 + t 1 t 3 + t 2 t 3 ) 3 n = ( − 1 ) n ( 3 n n , n , n ) , {\displaystyle {\begin{aligned}G(2n,2n,2n)&={\bigl }(-1)^{3n}{\bigl (}t_{1}t_{2}+t_{1}t_{3}+t_{2}t_{3}{\bigr )}^{3n}\\&=(-1)^{n}{\binom {3n}{n,n,n}},\end{aligned}}}

where the last equality follows from the fact that we need to use an equal number of times all three terms in the power. Now equating the two formulas for coefficients G(2n, 2n, 2n) we obtain an equivalent version of Dixon's identity:

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

See also

References

  1. Louck, James D. (2008). Unitary symmetry and combinatorics. Singapore: World Scientific. pp. viii. ISBN 978-981-281-472-2.
Categories: