Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Partition algebra
open-in-new
<h2 id="definition">Definition</h2> <h3>Diagrams</h3> <p>A partition of 2 k {\displaystyle 2k} elements labelled 1 , 1 ¯ , 2 , 2 ¯ , … , k , k ¯ {\displaystyle 1,{\bar {1}},2,{\bar {2}},\dots ,k,{\bar {k}}} is represented as a diagram, with lines connecting elements in the same subset. In the following example, the subset { 1 ¯ , 4 ¯ , 5 ¯ , 6 } {\displaystyle \{{\bar {1}},{\bar {4}},{\bar {5}},6\}} gives rise to the lines 1 ¯ − 4 ¯ , 4 ¯ − 5 ¯ , 5 ¯ − 6 {\displaystyle {\bar {1}}-{\bar {4}},{\bar {4}}-{\bar {5}},{\bar {5}}-6} , and could equivalently be represented by the lines 1 ¯ − 6 , 4 ¯ − 6 , 5 ¯ − 6 , 1 ¯ − 5 ¯ {\displaystyle {\bar {1}}-6,{\bar {4}}-6,{\bar {5}}-6,{\bar {1}}-{\bar {5}}} (for instance). </p><p>For n ∈ C {\displaystyle n\in \mathbb {C} } and k ∈ N ∗ {\displaystyle k\in \mathbb {N} ^{*}} , the partition algebra P k ( n ) {\displaystyle P_{k}(n)} is defined by a C {\displaystyle \mathbb {C} } -basis made of partitions, and a multiplication given by diagram concatenation. The concatenated diagram comes with a factor n D {\displaystyle n^{D}} , where D {\displaystyle D} is the number of connected components that are disconnected from the top and bottom elements. </p> <h3>Generators and relations</h3> <p>The partition algebra P k ( n ) {\displaystyle P_{k}(n)} is generated by 3 k − 2 {\displaystyle 3k-2} elements of the type </p><p>These generators obey relations that include<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> s i 2 = 1 , s i s i + 1 s i = s i + 1 s i s i + 1 , p i 2 = n p i , b i 2 = b i , p i b i p i = p i {\displaystyle s_{i}^{2}=1\quad ,\quad s_{i}s_{i+1}s_{i}=s_{i+1}s_{i}s_{i+1}\quad ,\quad p_{i}^{2}=np_{i}\quad ,\quad b_{i}^{2}=b_{i}\quad ,\quad p_{i}b_{i}p_{i}=p_{i}} <p>Other elements that are useful for generating subalgebras include </p><p>In terms of the original generators, these elements are </p> e i = b i p i p i + 1 b i , l i = s i p i , r i = p i s i {\displaystyle e_{i}=b_{i}p_{i}p_{i+1}b_{i}\quad ,\quad l_{i}=s_{i}p_{i}\quad ,\quad r_{i}=p_{i}s_{i}} <h3>Properties</h3> <p>The partition algebra P k ( n ) {\displaystyle P_{k}(n)} is an <a href="/facts/Associative_algebra/DRfoF6KV">associative algebra</a>. It has a multiplicative identity </p><p>The partition algebra P k ( n ) {\displaystyle P_{k}(n)} is <a href="/facts/Semisimple_algebra/JIXNLzck">semisimple</a> for n ∈ C − { 0 , 1 , … , 2 k − 2 } {\displaystyle n\in \mathbb {C} -\{0,1,\dots ,2k-2\}} . For any two n , n ′ {\displaystyle n,n'} in this set, the algebras P k ( n ) {\displaystyle P_{k}(n)} and P k ( n ′ ) {\displaystyle P_{k}(n')} are isomorphic.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>The partition algebra is finite-dimensional, with dim P k ( n ) = B 2 k {\displaystyle \dim P_{k}(n)=B_{2k}} (a <a href="/facts/Bell_number/LXzHyaIF">Bell number</a>). </p> <h2 id="subalgebras">Subalgebras</h2> <h3>Eight subalgebras</h3> <p>Subalgebras of the partition algebra can be defined by the following properties:<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <ul><li>Whether they are planar i.e. whether lines may cross in diagrams.</li> <li>Whether subsets are allowed to have any size 1 , 2 , … , 2 k {\displaystyle 1,2,\dots ,2k} , or size 1 , 2 {\displaystyle 1,2} , or only size 2 {\displaystyle 2} .</li> <li>Whether we allow top-top and bottom-bottom lines, or only top-bottom lines. In the latter case, the parameter n {\displaystyle n} is absent, or can be eliminated by p i → 1 n p i {\displaystyle p_{i}\to {\frac {1}{n}}p_{i}} .</li></ul> <p>Combining these properties gives rise to 8 nontrivial subalgebras, in addition to the partition algebra itself:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <table><tbody><tr><th>Notation</th><th>Name</th><th>Generators</th><th>Dimension</th><th>Example</th></tr><tr><td> P k ( n ) {\displaystyle P_{k}(n)} </td><td>Partition</td><td> s i , p i , b i {\displaystyle s_{i},p_{i},b_{i}} </td><td> B 2 k {\displaystyle B_{2k}} </td><td></td></tr><tr><td> P P k ( n ) {\displaystyle PP_{k}(n)} </td><td>Planar partition</td><td> p i , b i {\displaystyle p_{i},b_{i}} </td><td> 1 2 k + 1 ( 4 k 2 k ) {\displaystyle {\frac {1}{2k+1}}{\binom {4k}{2k}}} </td><td></td></tr><tr><td> R B k ( n ) {\displaystyle RB_{k}(n)} </td><td>Rook Brauer</td><td> s i , e i , p i {\displaystyle s_{i},e_{i},p_{i}} </td><td> ∑ ℓ = 0 k ( 2 k 2 ℓ ) ( 2 ℓ − 1 ) ! ! {\displaystyle \sum _{\ell =0}^{k}{\binom {2k}{2\ell }}(2\ell -1)!!} </td><td></td></tr><tr><td> M k ( n ) {\displaystyle M_{k}(n)} </td><td>Motzkin</td><td> e i , l i , r i {\displaystyle e_{i},l_{i},r_{i}} </td><td> ∑ ℓ = 0 k 1 ℓ + 1 ( 2 ℓ ℓ ) ( 2 k 2 ℓ ) {\displaystyle \sum _{\ell =0}^{k}{\frac {1}{\ell +1}}{\binom {2\ell }{\ell }}{\binom {2k}{2\ell }}} </td><td></td></tr><tr><td> B k ( n ) {\displaystyle B_{k}(n)} </td><td><a href="/facts/Brauer_algebra/5vS27l8c">Brauer</a></td><td> s i , e i {\displaystyle s_{i},e_{i}} </td><td> ( 2 k − 1 ) ! ! {\displaystyle (2k-1)!!} </td><td></td></tr><tr><td> T L k ( n ) {\displaystyle TL_{k}(n)} </td><td><a href="/facts/Temperley-Lieb_algebra/04FUNK32">Temperley–Lieb</a></td><td> e i {\displaystyle e_{i}} </td><td> 1 k + 1 ( 2 k k ) {\displaystyle {\frac {1}{k+1}}{\binom {2k}{k}}} </td><td></td></tr><tr><td> R k {\displaystyle R_{k}} </td><td>Rook</td><td> s i , p i {\displaystyle s_{i},p_{i}} </td><td> ∑ ℓ = 0 k ( k ℓ ) 2 ℓ ! {\displaystyle \sum _{\ell =0}^{k}{\binom {k}{\ell }}^{2}\ell !} </td><td></td></tr><tr><td> P R k {\displaystyle PR_{k}} </td><td>Planar rook</td><td> l i , r i {\displaystyle l_{i},r_{i}} </td><td> ( 2 k k ) {\displaystyle {\binom {2k}{k}}} </td><td></td></tr><tr><td> C S k {\displaystyle \mathbb {C} S_{k}} </td><td><a href="/facts/Symmetric_group/RUksK5l5">Symmetric group</a></td><td> s i {\displaystyle s_{i}} </td><td> k ! {\displaystyle k!} </td><td></td></tr></tbody></table> <p>The symmetric group algebra C S k {\displaystyle \mathbb {C} S_{k}} is the <a href="/facts/Group_ring/TJlkt5Te">group ring</a> of the <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a> S k {\displaystyle S_{k}} over C {\displaystyle \mathbb {C} } . The Motzkin algebra is sometimes called the dilute Temperley–Lieb algebra in the physics literature.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h3>Properties</h3> <p>The listed subalgebras are <a href="/facts/Semisimple_algebra/JIXNLzck">semisimple</a> for n ∈ C − { 0 , 1 , … , 2 k − 2 } {\displaystyle n\in \mathbb {C} -\{0,1,\dots ,2k-2\}} . </p><p>Inclusions of planar into non-planar algebras: </p> P P k ( n ) ⊂ P k ( n ) , M k ( n ) ⊂ R B k ( n ) , T L k ( n ) ⊂ B k ( n ) , P R k ⊂ R k {\displaystyle PP_{k}(n)\subset P_{k}(n)\quad ,\quad M_{k}(n)\subset RB_{k}(n)\quad ,\quad TL_{k}(n)\subset B_{k}(n)\quad ,\quad PR_{k}\subset R_{k}} <p>Inclusions from constraints on subset size: </p> B k ( n ) ⊂ R B k ( n ) ⊂ P k ( n ) , T L k ( n ) ⊂ M k ( n ) ⊂ P P k ( n ) , C S k ⊂ R k {\displaystyle B_{k}(n)\subset RB_{k}(n)\subset P_{k}(n)\quad ,\quad TL_{k}(n)\subset M_{k}(n)\subset PP_{k}(n)\quad ,\quad \mathbb {C} S_{k}\subset R_{k}} <p>Inclusions from allowing top-top and bottom-bottom lines: </p> R k ⊂ R B k ( n ) , P R k ⊂ M k ( n ) , C S k ⊂ B k ( n ) {\displaystyle R_{k}\subset RB_{k}(n)\quad ,\quad PR_{k}\subset M_{k}(n)\quad ,\quad \mathbb {C} S_{k}\subset B_{k}(n)} <p>We have the isomorphism: </p> P P k ( n 2 ) ≅ T L 2 k ( n ) , { p i ↦ n e 2 i − 1 b i ↦ 1 n e 2 i {\displaystyle PP_{k}(n^{2})\cong TL_{2k}(n)\quad ,\quad \left\{{\begin{array}{l}p_{i}\mapsto ne_{2i-1}\\b_{i}\mapsto {\frac {1}{n}}e_{2i}\end{array}}\right.} <h3>More subalgebras</h3> <p>In addition to the eight subalgebras described above, other subalgebras have been defined: </p> <ul><li>The totally propagating partition subalgebra prop P k {\displaystyle {\text{prop}}P_{k}} is generated by diagrams whose blocks all propagate, i.e. partitions whose subsets all contain top and bottom elements.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> These diagrams from the dual symmetric inverse monoid, which is generated by s i , b i p i + 1 b i + 1 {\displaystyle s_{i},b_{i}p_{i+1}b_{i+1}} .<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li> <li>The quasi-partition algebra Q P k ( n ) {\displaystyle QP_{k}(n)} is generated by subsets of size at least two. Its generators are s i , b i , e i {\displaystyle s_{i},b_{i},e_{i}} and its dimension is 1 + ∑ j = 1 2 k ( − 1 ) j − 1 B 2 k − j {\displaystyle 1+\sum _{j=1}^{2k}(-1)^{j-1}B_{2k-j}} .<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></li> <li>The uniform block permutation algebra U k {\displaystyle U_{k}} is generated by subsets with as many top elements as bottom elements. It is generated by s i , b i {\displaystyle s_{i},b_{i}} .<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li></ul> <p>An algebra with a half-integer index k + 1 2 {\displaystyle k+{\frac {1}{2}}} is defined from partitions of 2 k + 2 {\displaystyle 2k+2} elements by requiring that k + 1 {\displaystyle k+1} and k + 1 ¯ {\displaystyle {\overline {k+1}}} are in the same subset. For example, P k + 1 2 {\displaystyle P_{k+{\frac {1}{2}}}} is generated by s i ≤ k − 1 , b i ≤ k , p i ≤ k {\displaystyle s_{i\leq k-1},b_{i\leq k},p_{i\leq k}} so that P k ⊂ P k + 1 2 ⊂ P k + 1 {\displaystyle P_{k}\subset P_{k+{\frac {1}{2}}}\subset P_{k+1}} , and dim P k + 1 2 = B 2 k + 1 {\displaystyle \dim P_{k+{\frac {1}{2}}}=B_{2k+1}} .<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p><p>Periodic subalgebras are generated by diagrams that can be drawn on an annulus without line crossings. Such subalgebras include a translation element u = {\displaystyle u=} such that u k = 1 {\displaystyle u^{k}=1} . The translation element and its powers are the only combinations of s i {\displaystyle s_{i}} that belong to periodic subalgebras. </p> <h2 id="representations">Representations</h2> <h3>Structure</h3> <p>For an integer 0 ≤ ℓ ≤ k {\displaystyle 0\leq \ell \leq k} , let D ℓ {\displaystyle D_{\ell }} be the set of partitions of k + ℓ {\displaystyle k+\ell } elements 1 , 2 , … , k {\displaystyle 1,2,\dots ,k} (bottom) and 1 ¯ , 2 ¯ , … , ℓ ¯ {\displaystyle {\bar {1}},{\bar {2}},\dots ,{\bar {\ell }}} (top), such that no two top elements are in the same subset, and no top element is alone. Such partitions are represented by diagrams with no top-top lines, with at least one line for each top element. For example, in the case k = 12 , ℓ = 5 {\displaystyle k=12,\ell =5} : </p><p>Partition diagrams act on D ℓ {\displaystyle D_{\ell }} from the bottom, while the symmetric group S ℓ {\displaystyle S_{\ell }} acts from the top. For any <a href="/facts/Specht_module/wNyeJcj6">Specht module</a> V λ {\displaystyle V_{\lambda }} of S ℓ {\displaystyle S_{\ell }} (with therefore | λ | = ℓ {\displaystyle |\lambda |=\ell } ), we define the representation of P k ( n ) {\displaystyle P_{k}(n)} </p> P λ = C D | λ | ⊗ C S | λ | V λ . {\displaystyle {\mathcal {P}}_{\lambda }=\mathbb {C} D_{|\lambda |}\otimes _{\mathbb {C} S_{|\lambda |}}V_{\lambda }\ .} <p>The dimension of this representation is<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> dim P λ = f λ ∑ ℓ = | λ | k { k ℓ } ( ℓ | λ | ) , {\displaystyle \dim {\mathcal {P}}_{\lambda }=f_{\lambda }\sum _{\ell =|\lambda |}^{k}\left\{{k \atop \ell }\right\}{\binom {\ell }{|\lambda |}}\ ,} <p>where { k ℓ } {\displaystyle \left\{{k \atop \ell }\right\}} is a <a href="/facts/Stirling_number_of_the_second_kind/qg5UrHmk">Stirling number of the second kind</a>, ( ℓ | λ | ) {\displaystyle {\binom {\ell }{|\lambda |}}} is a <a href="/facts/Binomial_coefficient/Tsx7eY5h">binomial coefficient</a>, and f λ = dim V λ {\displaystyle f_{\lambda }=\dim V_{\lambda }} is given by the <a href="/facts/Hook_length_formula/IsoYm5Mt">hook length formula</a>. </p><p>A basis of P λ {\displaystyle {\mathcal {P}}_{\lambda }} can be described combinatorially in terms of set-partition tableaux: <a href="/facts/Young_tableaux/e5lI4bck">Young tableaux</a> whose boxes are filled with the blocks of a set partition.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p><p>Assuming that P k ( n ) {\displaystyle P_{k}(n)} is semisimple, the representation P λ {\displaystyle {\mathcal {P}}_{\lambda }} is irreducible, and the set of irreducible finite-dimensional representations of the partition algebra is </p> Irrep ( P k ( n ) ) = { P λ } 0 ≤ | λ | ≤ k . {\displaystyle {\text{Irrep}}\left(P_{k}(n)\right)=\left\{{\mathcal {P}}_{\lambda }\right\}_{0\leq |\lambda |\leq k}\ .} <h3>Representations of subalgebras</h3> <p>Representations of non-planar subalgebras have similar structures as representations of the partition algebra. For example, the <a href="/facts/Brauer_algebra/5vS27l8c">Brauer-Specht modules</a> of the Brauer algebra are built from Specht modules, and certain sets of partitions. </p><p>In the case of the planar subalgebras, planarity prevents nontrivial permutations, and Specht modules do not appear. For example, a <a href="/facts/Temperley%25E2%2580%2593Lieb_algebra/04FUNK32">standard module</a> of the Temperley–Lieb algebra is parametrized by an integer 0 ≤ ℓ ≤ k {\displaystyle 0\leq \ell \leq k} with ℓ ≡ k mod 2 {\displaystyle \ell \equiv k{\bmod {2}}} , and a basis is simply given by a set of partitions. </p><p>The following table lists the irreducible representations of the partition algebra and eight subalgebras.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <table><tbody><tr><th>Algebra</th><th>Parameter</th><th>Conditions</th><th>Dimension</th></tr><tr><td> P k ( n ) {\displaystyle P_{k}(n)} </td><td> λ {\displaystyle \lambda } </td><td> 0 ≤ | λ | ≤ k {\displaystyle 0\leq |\lambda |\leq k} </td><td> f λ ∑ ℓ = | λ | k { k ℓ } ( ℓ | λ | ) {\displaystyle f_{\lambda }\sum _{\ell =|\lambda |}^{k}\left\{{k \atop \ell }\right\}{\binom {\ell }{|\lambda |}}} </td></tr><tr><td> P P k ( n ) {\displaystyle PP_{k}(n)} </td><td> ℓ {\displaystyle \ell } </td><td> 0 ≤ ℓ ≤ k {\displaystyle 0\leq \ell \leq k} </td><td> ( 2 k k + ℓ ) − ( 2 k k + ℓ + 1 ) {\displaystyle {\binom {2k}{k+\ell }}-{\binom {2k}{k+\ell +1}}} </td></tr><tr><td> R B k ( n ) {\displaystyle RB_{k}(n)} </td><td> λ {\displaystyle \lambda } </td><td> 0 ≤ | λ | ≤ k {\displaystyle 0\leq |\lambda |\leq k} </td><td> f λ ( k | λ | ) ∑ m = 0 ⌊ k − | λ | 2 ⌋ ( k − | λ | 2 m ) ( 2 m − 1 ) ! ! {\displaystyle f_{\lambda }{\binom {k}{|\lambda |}}\sum _{m=0}^{\left\lfloor {\frac {k-|\lambda |}{2}}\right\rfloor }{\binom {k-|\lambda |}{2m}}(2m-1)!!} </td></tr><tr><td> M k ( n ) {\displaystyle M_{k}(n)} </td><td> ℓ {\displaystyle \ell } </td><td> 0 ≤ ℓ ≤ k {\displaystyle 0\leq \ell \leq k} </td><td> ∑ m = 0 ⌊ k − ℓ 2 ⌋ ( k ℓ + 2 m ) { ( ℓ + 2 m m ) − ( ℓ + 2 m m − 1 ) } {\displaystyle \sum _{m=0}^{\left\lfloor {\frac {k-\ell }{2}}\right\rfloor }{\binom {k}{\ell +2m}}\left\{{\binom {\ell +2m}{m}}-{\binom {\ell +2m}{m-1}}\right\}} </td></tr><tr><td> B k ( n ) {\displaystyle B_{k}(n)} </td><td> λ {\displaystyle \lambda } </td><td> 0 ≤ | λ | ≤ k | λ | ≡ k mod 2 {\displaystyle {\begin{array}{c}0\leq |\lambda |\leq k\\|\lambda |\equiv k{\bmod {2}}\end{array}}} </td><td> f λ ( k | λ | ) ( k − | λ | − 1 ) ! ! {\displaystyle f_{\lambda }{\binom {k}{|\lambda |}}(k-|\lambda |-1)!!} </td></tr><tr><td> T L k ( n ) {\displaystyle TL_{k}(n)} </td><td> ℓ {\displaystyle \ell } </td><td> 0 ≤ ℓ ≤ k ℓ ≡ k mod 2 {\displaystyle {\begin{array}{c}0\leq \ell \leq k\\\ell \equiv k{\bmod {2}}\end{array}}} </td><td> ( k k + ℓ 2 ) − ( k k + ℓ + 2 2 ) {\displaystyle {\binom {k}{\frac {k+\ell }{2}}}-{\binom {k}{\frac {k+\ell +2}{2}}}} </td></tr><tr><td> R k {\displaystyle R_{k}} </td><td> λ {\displaystyle \lambda } </td><td> 0 ≤ | λ | ≤ k {\displaystyle 0\leq |\lambda |\leq k} </td><td> f λ ( k | λ | ) {\displaystyle f_{\lambda }{\binom {k}{|\lambda |}}} </td></tr><tr><td> P R k {\displaystyle PR_{k}} </td><td> ℓ {\displaystyle \ell } </td><td> 0 ≤ ℓ ≤ k {\displaystyle 0\leq \ell \leq k} </td><td> ( k ℓ ) {\displaystyle {\binom {k}{\ell }}} </td></tr><tr><td> C S k {\displaystyle \mathbb {C} S_{k}} </td><td> λ {\displaystyle \lambda } </td><td> | λ | = k {\displaystyle |\lambda |=k} </td><td> f λ {\displaystyle f_{\lambda }} </td></tr></tbody></table> <p>The irreducible representations of prop P k {\displaystyle {\text{prop}}P_{k}} are indexed by partitions such that 0 < | λ | ≤ k {\displaystyle 0<|\lambda |\leq k} and their dimensions are f λ { k | λ | } {\displaystyle f_{\lambda }\left\{{k \atop |\lambda |}\right\}} .<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> The irreducible representations of Q P k {\displaystyle QP_{k}} are indexed by partitions such that 0 ≤ | λ | ≤ k {\displaystyle 0\leq |\lambda |\leq k} .<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> The irreducible representations of U k {\displaystyle U_{k}} are indexed by sequences of partitions.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> </p> <h2 id="schur-weyl-duality">Schur-Weyl duality</h2> <p>Assume n ∈ N ∗ {\displaystyle n\in \mathbb {N} ^{*}} . For V {\displaystyle V} a n {\displaystyle n} -dimensional vector space with basis v 1 , … , v n {\displaystyle v_{1},\dots ,v_{n}} , there is a natural action of the partition algebra P k ( n ) {\displaystyle P_{k}(n)} on the vector space V ⊗ k {\displaystyle V^{\otimes k}} . This action is defined by the matrix elements of a partition { 1 , 1 ¯ , 2 , 2 ¯ , … , k , k ¯ } = ⊔ h E h {\displaystyle \{1,{\bar {1}},2,{\bar {2}},\dots ,k,{\bar {k}}\}=\sqcup _{h}E_{h}} in the basis ( v j 1 ⊗ ⋯ ⊗ v j k ) {\displaystyle (v_{j_{1}}\otimes \cdots \otimes v_{j_{k}})} :<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> </p> ( ⊔ h E h ) j 1 , j 2 , … , j k j 1 ¯ , j 2 ¯ , … , j k ¯ = 1 r , s ∈ E h ⟹ j r = j s . {\displaystyle \left(\sqcup _{h}E_{h}\right)_{j_{1},j_{2},\dots ,j_{k}}^{j_{\bar {1}},j_{\bar {2}},\dots ,j_{\bar {k}}}=\mathbf {1} _{r,s\in E_{h}\implies j_{r}=j_{s}}\ .} <p>This matrix element is one if all indices corresponding to any given partition subset coincide, and zero otherwise. For example, the action of a Temperley–Lieb generator is </p> e i ( v j 1 ⊗ ⋯ ⊗ v j i ⊗ v j i + 1 ⊗ ⋯ ⊗ v j k ) = δ j i , j i + 1 ∑ j = 1 n v j 1 ⊗ ⋯ ⊗ v j ⊗ v j ⊗ ⋯ ⊗ v j k . {\displaystyle e_{i}\left(v_{j_{1}}\otimes \cdots \otimes v_{j_{i}}\otimes v_{j_{i+1}}\otimes \cdots \otimes v_{j_{k}}\right)=\delta _{j_{i},j_{i+1}}\sum _{j=1}^{n}v_{j_{1}}\otimes \cdots \otimes v_{j}\otimes v_{j}\otimes \cdots \otimes v_{j_{k}}\ .} <h3>Duality between the partition algebra and the symmetric group</h3> <p>Let n ≥ 2 k {\displaystyle n\geq 2k} be integer. Let us take V {\displaystyle V} to be the <a href="/facts/Representation_theory_of_the_symmetric_group/ht0T7JNt">natural permutation representation</a> of the <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a> S n {\displaystyle S_{n}} . This n {\displaystyle n} -dimensional representation is a sum of two irreducible representations: the standard and trivial representations, V = [ n − 1 , 1 ] ⊕ [ n ] {\displaystyle V=[n-1,1]\oplus [n]} . </p><p>Then the partition algebra P k ( n ) {\displaystyle P_{k}(n)} is the <a href="/facts/Centralizer/AKhrEUGR">centralizer</a> of the action of S n {\displaystyle S_{n}} on the tensor product space V ⊗ k {\displaystyle V^{\otimes k}} , </p> P k ( n ) ≅ End S n ( V ⊗ k ) . {\displaystyle P_{k}(n)\cong {\text{End}}_{S_{n}}\left(V^{\otimes k}\right)\ .} <p>Moreover, as a bimodule over P k ( n ) × S n {\displaystyle P_{k}(n)\times S_{n}} , the tensor product space decomposes into irreducible representations as<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> </p> V ⊗ k = ⨁ 0 ≤ | λ | ≤ k P λ ⊗ V [ n − | λ | , λ ] , {\displaystyle V^{\otimes k}=\bigoplus _{0\leq |\lambda |\leq k}{\mathcal {P}}_{\lambda }\otimes V_{[n-|\lambda |,\lambda ]}\ ,} <p>where [ n − | λ | , λ ] {\displaystyle [n-|\lambda |,\lambda ]} is a Young diagram of size n {\displaystyle n} built by adding a first row to λ {\displaystyle \lambda } , and V [ n − | λ | , λ ] {\displaystyle V_{[n-|\lambda |,\lambda ]}} is the corresponding <a href="/facts/Specht_module/wNyeJcj6">Specht module</a> of S n {\displaystyle S_{n}} . </p> <h3>Dualities involving subalgebras</h3> <p>The duality between the symmetric group and the partition algebra generalizes the original <a href="/facts/Schur-Weyl_duality/tcHlbYKr">Schur-Weyl duality</a> between the general linear group and the symmetric group. There are other generalizations. In the relevant tensor product spaces, we write V n {\displaystyle V_{n}} for an irreducible n {\displaystyle n} -dimensional representation of the first group or algebra: </p> <table><tbody><tr><th>Tensor product space</th><th>Group or algebra</th><th>Dual algebra or group</th><th>Comments</th></tr><tr><td> ( V n − 1 ⊕ V 1 ) ⊗ k {\displaystyle \left(V_{n-1}\oplus V_{1}\right)^{\otimes k}} </td><td> S n {\displaystyle S_{n}} </td><td> P k ( n ) {\displaystyle P_{k}(n)} </td><td>The duality for the full partition algebra</td></tr><tr><td> ( V n − 2 ⊕ V 1 ⊕ V 1 ) ⊗ k {\displaystyle \left(V_{n-2}\oplus V_{1}\oplus V_{1}\right)^{\otimes k}} </td><td> S n − 1 {\displaystyle S_{n-1}} </td><td> P k + 1 2 ( n ) {\displaystyle P_{k+{\frac {1}{2}}}(n)} </td><td>Case of a partition algebra with a half-integer index<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a></td></tr><tr><td> V n ⊗ k {\displaystyle V_{n}^{\otimes k}} </td><td> G L n ( C ) {\displaystyle GL_{n}(\mathbb {C} )} </td><td> S k {\displaystyle S_{k}} </td><td>The original Schur-Weyl duality</td></tr><tr><td> V n ⊗ k {\displaystyle V_{n}^{\otimes k}} </td><td> O ( n ) {\displaystyle O(n)} </td><td> B k ( n ) {\displaystyle B_{k}(n)} </td><td>Duality between the <a href="/facts/Orthogonal_group/jKWM1KDM">orthogonal group</a> and the <a href="/facts/Brauer_algebra/5vS27l8c">Brauer algebra</a></td></tr><tr><td> ( V n ⊕ V 1 ) ⊗ k {\displaystyle \left(V_{n}\oplus V_{1}\right)^{\otimes k}} </td><td> O ( n ) {\displaystyle O(n)} </td><td> R B k ( n + 1 ) {\displaystyle RB_{k}(n+1)} </td><td>Duality between the orthogonal group and the rook Brauer algebra<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a></td></tr><tr><td> V n ⊗ k {\displaystyle V_{n}^{\otimes k}} </td><td> R n {\displaystyle R_{n}} </td><td> prop P k {\displaystyle {\text{prop}}P_{k}} </td><td>Duality between the rook algebra and the totally propagating partition algebra<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a><a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a></td></tr><tr><td> V 2 ⊗ k {\displaystyle V_{2}^{\otimes k}} </td><td> g l ( 1 | 1 ) {\displaystyle gl(1|1)} </td><td> P R k − 1 {\displaystyle PR_{k-1}} </td><td>Duality between a <a href="/facts/Lie_superalgebra/c1oxUoEl">Lie superalgebra</a> and the planar rook algebra<a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a></td></tr><tr><td> V n − 1 ⊗ k {\displaystyle V_{n-1}^{\otimes k}} </td><td> S n {\displaystyle S_{n}} </td><td> Q P k ( n ) {\displaystyle QP_{k}(n)} </td><td>Duality between the symmetric group and the quasi-partition algebra<a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a></td></tr><tr><td> V n ⊗ r ⊗ ( V n ∗ ) ⊗ s {\displaystyle V_{n}^{\otimes r}\otimes \left(V_{n}^{*}\right)^{\otimes s}} </td><td> G L n ( C ) {\displaystyle GL_{n}(\mathbb {C} )} </td><td> B r , s ( n ) {\displaystyle B_{r,s}(n)} </td><td>Duality involving the <a href="/facts/Brauer_algebra/5vS27l8c">walled Brauer algebra</a>.<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a></td></tr></tbody></table> <h2 id="further-reading">Further reading</h2> <ul><li>Kauffman, Louis H. (1991). <a href="https://books.google.com/books?id=av05vRwIKIwC"><i>Knots and Physics</i></a>. World Scientific. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-981-02-0343-6.</li> <li>Kauffman, Louis H. (1990). <a href="https://www.ams.org/tran/1990-318-02/S0002-9947-1990-0958895-7/">"An invariant of regular isotopy"</a>. <i>Transactions of the American Mathematical Society</i>. 318 (2): 417–471. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0002-9947-1990-0958895-7">10.1090/S0002-9947-1990-0958895-7</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0002-9947">0002-9947</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Halverson, Tom; Jacobson, Theodore N. (2020). "Set-partition tableaux and representations of diagram algebras". Algebraic Combinatorics. 3 (2): 509–538. arXiv:1808.08118v2. doi:10.5802/alco.102. ISSN 2589-5486. S2CID 119167251. <a href="https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0" target="_blank">https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Halverson, Tom; Ram, Arun (2005). "Partition algebras". European Journal of Combinatorics. 26 (6): 869–921. arXiv:math/0401314v2. doi:10.1016/j.ejc.2004.06.005. S2CID 1168919. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Halverson, Tom; Jacobson, Theodore N. (2020). "Set-partition tableaux and representations of diagram algebras". Algebraic Combinatorics. 3 (2): 509–538. arXiv:1808.08118v2. doi:10.5802/alco.102. ISSN 2589-5486. S2CID 119167251. <a href="https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0" target="_blank">https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Colmenarejo, Laura; Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike (2020). "An insertion algorithm on multiset partitions with applications to diagram algebras". Journal of Algebra. 557: 97–128. arXiv:1905.02071v2. doi:10.1016/j.jalgebra.2020.04.010. S2CID 146121089. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0021869320301873" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0021869320301873</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Halverson, Tom; Jacobson, Theodore N. (2020). "Set-partition tableaux and representations of diagram algebras". Algebraic Combinatorics. 3 (2): 509–538. arXiv:1808.08118v2. doi:10.5802/alco.102. ISSN 2589-5486. S2CID 119167251. <a href="https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0" target="_blank">https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Colmenarejo, Laura; Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike (2020). "An insertion algorithm on multiset partitions with applications to diagram algebras". Journal of Algebra. 557: 97–128. arXiv:1905.02071v2. doi:10.1016/j.jalgebra.2020.04.010. S2CID 146121089. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0021869320301873" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0021869320301873</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Jacobsen, Jesper Lykke; Ribault, Sylvain; Saleur, Hubert (2022). "Spaces of states of the two-dimensional O(n) and Potts models". arXiv:2208.14298. {{cite journal}}: Cite journal requires |journal= (help) <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Mishra, Ashish; Srivastava, Shraddha (2021). "Jucys–Murphy elements of partition algebras for the rook monoid". International Journal of Algebra and Computation. 31 (5): 831–864. arXiv:1912.10737v3. doi:10.1142/S0218196721500399. ISSN 0218-1967. S2CID 209444954. <a href="https://www.worldscientific.com/doi/abs/10.1142/S0218196721500399" target="_blank">https://www.worldscientific.com/doi/abs/10.1142/S0218196721500399</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Maltcev, Victor (2007-03-16). "On a new approach to the dual symmetric inverse monoid I*X". arXiv:math/0703478v1. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Daugherty, Zajj; Orellana, Rosa (2014). "The quasi-partition algebra". Journal of Algebra. 404: 124–151. arXiv:1212.2596v1. doi:10.1016/j.jalgebra.2013.11.028. S2CID 117848394. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0021869314000477" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0021869314000477</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike (2021-12-27). "Plethysm and the algebra of uniform block permutations". arXiv:2112.13909v1 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Halverson, Tom; Ram, Arun (2005). "Partition algebras". European Journal of Combinatorics. 26 (6): 869–921. arXiv:math/0401314v2. doi:10.1016/j.ejc.2004.06.005. S2CID 1168919. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Halverson, Tom; Jacobson, Theodore N. (2020). "Set-partition tableaux and representations of diagram algebras". Algebraic Combinatorics. 3 (2): 509–538. arXiv:1808.08118v2. doi:10.5802/alco.102. ISSN 2589-5486. S2CID 119167251. <a href="https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0" target="_blank">https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Halverson, Tom; Jacobson, Theodore N. (2020). "Set-partition tableaux and representations of diagram algebras". Algebraic Combinatorics. 3 (2): 509–538. arXiv:1808.08118v2. doi:10.5802/alco.102. ISSN 2589-5486. S2CID 119167251. <a href="https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0" target="_blank">https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Colmenarejo, Laura; Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike (2020). "An insertion algorithm on multiset partitions with applications to diagram algebras". Journal of Algebra. 557: 97–128. arXiv:1905.02071v2. doi:10.1016/j.jalgebra.2020.04.010. S2CID 146121089. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0021869320301873" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0021869320301873</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Mishra, Ashish; Srivastava, Shraddha (2021). "Jucys–Murphy elements of partition algebras for the rook monoid". International Journal of Algebra and Computation. 31 (5): 831–864. arXiv:1912.10737v3. doi:10.1142/S0218196721500399. ISSN 0218-1967. S2CID 209444954. <a href="https://www.worldscientific.com/doi/abs/10.1142/S0218196721500399" target="_blank">https://www.worldscientific.com/doi/abs/10.1142/S0218196721500399</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Daugherty, Zajj; Orellana, Rosa (2014). "The quasi-partition algebra". Journal of Algebra. 404: 124–151. arXiv:1212.2596v1. doi:10.1016/j.jalgebra.2013.11.028. S2CID 117848394. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0021869314000477" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0021869314000477</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike (2021-12-27). "Plethysm and the algebra of uniform block permutations". arXiv:2112.13909v1 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Halverson, Tom; Ram, Arun (2005). "Partition algebras". European Journal of Combinatorics. 26 (6): 869–921. arXiv:math/0401314v2. doi:10.1016/j.ejc.2004.06.005. S2CID 1168919. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Halverson, Tom; Jacobson, Theodore N. (2020). "Set-partition tableaux and representations of diagram algebras". Algebraic Combinatorics. 3 (2): 509–538. arXiv:1808.08118v2. doi:10.5802/alco.102. ISSN 2589-5486. S2CID 119167251. <a href="https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0" target="_blank">https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Halverson, Tom; Ram, Arun (2005). "Partition algebras". European Journal of Combinatorics. 26 (6): 869–921. arXiv:math/0401314v2. doi:10.1016/j.ejc.2004.06.005. S2CID 1168919. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Halverson, Tom; delMas, Elise (2014-01-02). "Representations of the Rook-Brauer Algebra". Communications in Algebra. 42 (1): 423–443. arXiv:1206.4576v2. doi:10.1080/00927872.2012.716120. ISSN 0092-7872. S2CID 38469372. <a href="http://www.tandfonline.com/doi/abs/10.1080/00927872.2012.716120" target="_blank">http://www.tandfonline.com/doi/abs/10.1080/00927872.2012.716120</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Kudryavtseva, Ganna; Mazorchuk, Volodymyr (2008). "Schur–Weyl dualities for symmetric inverse semigroups". Journal of Pure and Applied Algebra. 212 (8): 1987–1995. arXiv:math/0702864. doi:10.1016/j.jpaa.2007.12.004. S2CID 13564450. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0022404908000169" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0022404908000169</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Mishra, Ashish; Srivastava, Shraddha (2021). "Jucys–Murphy elements of partition algebras for the rook monoid". International Journal of Algebra and Computation. 31 (5): 831–864. arXiv:1912.10737v3. doi:10.1142/S0218196721500399. ISSN 0218-1967. S2CID 209444954. <a href="https://www.worldscientific.com/doi/abs/10.1142/S0218196721500399" target="_blank">https://www.worldscientific.com/doi/abs/10.1142/S0218196721500399</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>Benkart, Georgia; Moon, Dongho (2013-05-28). "Planar Rook Algebras and Tensor Representations of 𝔤𝔩(1 | 1)". Communications in Algebra. 41 (7): 2405–2416. arXiv:1201.2482v1. doi:10.1080/00927872.2012.658533. ISSN 0092-7872. S2CID 119125305. <a href="http://www.tandfonline.com/doi/abs/10.1080/00927872.2012.658533" target="_blank">http://www.tandfonline.com/doi/abs/10.1080/00927872.2012.658533</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>Daugherty, Zajj; Orellana, Rosa (2014). "The quasi-partition algebra". Journal of Algebra. 404: 124–151. arXiv:1212.2596v1. doi:10.1016/j.jalgebra.2013.11.028. S2CID 117848394. <a href="https://linkinghub.elsevier.com/retrieve/pii/S0021869314000477" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/S0021869314000477</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>Cox, Anton; Visscher, De; Doty, Stephen; Martin, Paul (2007-09-06). "On the blocks of the walled Brauer algebra". arXiv:0709.0851v1 [math.RT]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> </ol>