Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Skew and direct sums of permutations
open-in-new
<h2 id="examples">Examples</h2> <p>The skew sum of the permutations <i>π</i> = 2413 and <i>σ</i> = 35142 is 796835142 (the last five entries are equal to <i>σ</i>, while the first four entries come from shifting the entries of <i>π</i>) while their direct sum is 241379586 (the first four entries are equal to <i>π</i>, while the last five come from shifting the entries of <i>σ</i>). </p> <h2 id="sums-of-permutations-as-matrices">Sums of permutations as <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrices</a></h2> <p>If <i>M</i><i>π</i> and <i>M</i><i>σ</i> are the <a href="/facts/Permutation_matrix/xC1ran5s">permutation matrices</a> corresponding to <i>π</i> and <i>σ</i>, respectively, then the permutation matrix M π ⊖ σ {\displaystyle M_{\pi \ominus \sigma }} corresponding to the skew sum π ⊖ σ {\displaystyle \pi \ominus \sigma } is given by </p> M π ⊖ σ = [ 0 M π M σ 0 ] {\displaystyle M_{\pi \ominus \sigma }={\begin{bmatrix}0&M_{\pi }\\M_{\sigma }&0\end{bmatrix}}} , <p>and the permutation matrix M π ⊕ σ {\displaystyle M_{\pi \oplus \sigma }} corresponding to the direct sum π ⊕ σ {\displaystyle \pi \oplus \sigma } is given by </p> M π ⊕ σ = [ M π 0 0 M σ ] {\displaystyle M_{\pi \oplus \sigma }={\begin{bmatrix}M_{\pi }&0\\0&M_{\sigma }\end{bmatrix}}} , <p>where here the symbol "0" is used to represent rectangular blocks of zero entries. Following the example of the preceding section, we have (suppressing all 0 entries) that </p> M 2413 = [ 1 1 1 1 ] {\displaystyle M_{2413}={\begin{bmatrix}&1&&\\&&&1\\1&&&\\&&1&\end{bmatrix}}} , M 35142 = [ 1 1 1 1 1 ] {\displaystyle M_{35142}={\begin{bmatrix}&&1&&\\&&&&1\\1&&&&\\&&&1&\\&1&&&\end{bmatrix}}} , M 2413 ⊖ 35142 = M 796835142 = [ 1 1 1 1 1 1 1 1 1 ] {\displaystyle M_{2413\ominus 35142}=M_{796835142}={\begin{bmatrix}&&&&&&1&&&\\&&&&&&&&1\\&&&&&1&&&\\&&&&&&&1&\\&&1&&&&&&\\&&&&1&&&&\\1&&&&&&&&\\&&&1&&&&&\\&1&&&&&&&\end{bmatrix}}} <p>and </p> M 2413 ⊕ 35142 = M 241379586 = [ 1 1 1 1 1 1 1 1 1 ] {\displaystyle M_{2413\oplus 35142}=M_{241379586}={\begin{bmatrix}&1&&&&&&&\\&&&1&&&&&\\1&&&&&&&&\\&&1&&&&&&\\&&&&&&1&&\\&&&&&&&&1\\&&&&1&&&&\\&&&&&&&1&\\&&&&&1&&&\end{bmatrix}}} . <h2 id="role-in-pattern-avoidance">Role in pattern avoidance</h2> <p>Skew and direct sums of permutations appear (among other places) in the study of <a href="/facts/Pattern_avoidance/ytUU2b91">pattern avoidance</a> in permutations. Breaking permutations down as skew and/or direct sums of a maximal number of parts (that is, decomposing into indecomposable parts) is one of several possible techniques used to study the structure of, and so to enumerate, pattern classes.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>Permutations whose decomposition by skew and direct sums into a maximal number of parts, that is, can be built up from the permutations (1), are called <a href="/facts/Separable_permutations/GNS7FeHj">separable permutations</a>;<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> they arise in the study of sortability theory, and can also be characterized as permutations avoiding the <a href="/facts/Permutation_pattern/ytUU2b91">permutation patterns</a> 2413 and 3142. </p> <h2 id="properties">Properties</h2> <p>The skew and direct sums are <a href="/facts/Associative_property/EQX8lV6r">associative</a> but not <a href="/facts/Commutative_property/WaYxJLxd">commutative</a>, and they do not associate with each other (i.e., for permutations π {\displaystyle \pi } , σ {\displaystyle \sigma } and τ {\displaystyle \tau } we typically have π ⊕ ( σ ⊖ τ ) ≠ ( π ⊕ σ ) ⊖ τ {\displaystyle \pi \oplus (\sigma \ominus \tau )\neq (\pi \oplus \sigma )\ominus \tau } ). </p><p>Given permutations π {\displaystyle \pi } and <i>σ</i>, we have </p> ( π ⊕ σ ) − 1 = π − 1 ⊕ σ − 1 {\displaystyle (\pi \oplus \sigma )^{-1}=\pi ^{-1}\oplus \sigma ^{-1}} and ( π ⊖ σ ) − 1 = σ − 1 ⊖ π − 1 {\displaystyle (\pi \ominus \sigma )^{-1}=\sigma ^{-1}\ominus \pi ^{-1}} . <p>Given a permutation π {\displaystyle \pi } , define its <i>reverse</i> rev ( π ) {\displaystyle \operatorname {rev} (\pi )} to be the permutation whose entries appear in the opposite order of those of π {\displaystyle \pi } when written in <a href="/facts/One-line_notation/JSw9ukmv">one-line notation</a>; for example, the reverse of 25143 is 34152. (As permutation matrices, this operation is reflection across a horizontal axis.) Then the skew and direct sums of permutations are related by </p> π ⊕ σ = rev ( rev ( σ ) ⊖ rev ( π ) ) {\displaystyle \pi \oplus \sigma =\operatorname {rev} (\operatorname {rev} (\sigma )\ominus \operatorname {rev} (\pi ))} . <ul><li><a href="/facts/Sergey_Kitaev/TDjolyXv">Kitaev, Sergey</a> (2011). <i>Patterns in permutations and words</i>. Monographs in Theoretical Computer Science. An EATCS Series. Berlin: <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-17332-5. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1257.68007">1257.68007</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Michael Albert and M. D. Atkinson, Pattern classes and priority queues, arXiv:1202.1542v1 <a href="/wiki/Michael_H._Albert" target="_blank">/wiki/Michael_H._Albert</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>M. D. Atkinson, Bruce E. Sagan, Vincent Vatter, Counting (3+1)-Avoiding permutations, European Journal of Combinatorics, arXiv:1102.5568v1 <a href="/wiki/Michael_D._Atkinson" target="_blank">/wiki/Michael_D._Atkinson</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Michael Albert and M. D. Atkinson Simple permutations and pattern restricted permutations. Discrete Math. 300, 1-3 (2005), 1–15. <a href="/wiki/Michael_H._Albert" target="_blank">/wiki/Michael_H._Albert</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Kitaev, S. (2011) p.57 <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>