HackMD - Collaborative Markdown Knowledge Base

## permutation **Warning: This is a draft! Has a lot of errors and typos** Consider an element in $S_4$ $$ \sigma(1)=4,\qquad \sigma(2)=2\qquad \sigma(3)=1,\qquad \sigma(4)=3 $$ **How many order-reversing paris are there?** What are they $$(1,2)\mapsto(4,2)$$ $$(1,3)\mapsto(4,1)$$ $$(1,4)\mapsto(4,3)$$ $$(2,3)\mapsto(2,1)$$ $$ \sigma(2)=2,\sigma(3)=1 $$ $$ \sigma(3)=1,\sigma(2)=2 $$ $$ 1\mapsto 4\mapsto 3\mapsto 1 $$ $$ 2\mapsto 2 $$ #### Let us write this $\sigma$ into a permuted list, then let's see what is the order-reversing pairs mean $$[4,2,1,3]$$ decreasing sub-pairs: $(4,2),(4,1),(4,3),(2,1)$ That means, the permutation corresponding to $4,2,1,3$ is an even permutation. ### Now let us change two elements in the list and let's see how the parity update #### I want to change the position of 2 and 3 **Old permuted list**: 4,2,1,3 **New permuted list**: 4,3,1,2 **To see how the parity change**, we wish to know how the decreasing sub-pairs change. **Classify original sub-pairs into the following classes** $(4,2)$, $(4,3)$: sub-pair that 4 is not an affected number, 2 is affected number, and 4 is **not between** affected numbers 2 and 3. the order would not change $(4,1)$: sub-pair that does not have any affected numbers. do not change the order $(2,1)$: sub-pair that has one affected number, but the other number is **between two affected numbers**. Then **It's order would change definitely** $(2,1)\mapsto(1,2)$ it changes the order!!! $(1,3)$: sub-pair that has one affected number, but the other number is **between two affected numbers**. Then **It's order would change definitely** $(1,3)\mapsto(3,1)$ it changes the order!!! $(2,3)$ : sub-pair that both numbers are affected it must change its order $(2,3)\mapsto (3,2)$ ### Excercise Now think about if I have a permuted list $$ (1,3,2,5,7,8,9,6,4) $$ I want to change the $3,6$, after I change it, it become $$ (1,6,2,5,7,8,9,3,4) $$ Tell me : How many sub-pairs has changed its order. ## Conclusion After I switch any two elements of the permuted list, the parity of the permutation MUST CHANGE ### Let's see Previously we know that $(4,2,1,3)$ is an even permutation by counting how counting how many decreasing paris are there, now let us use the easiest method to do so. $$\sigma(1)=4$$ $$\sigma(2)=2$$ $$\sigma(3)=1$$ $$\sigma(4)=3$$ Let's just draw the cycles $$ 1\mapsto 4\mapsto 3\mapsto 1\text{ cycle of size 3} $$ $$ 2\mapsto 2 \text{ cycle of size 1} $$ How many even-sized cycle are there? 0-- Even number . So it is an even permutation. ### Excercise For the permuted list as the following $$(3,4,1,7,8,2,5,9,6)$$ Is this corresponds to an odd or even permutation? What are sizes of the cycles? Two cycles, 1 cycle of size 2, another cycle of size 7 $$\sigma(1)=3$$ $$\sigma(2)=4$$ $$\sigma(3)=1$$ $$\sigma(4)=7$$ $$\sigma(5)=8$$ $$\sigma(6)=2$$ $$\sigma(7)=5$$ $$\sigma(8)=9$$ $$\sigma(9)=6$$ $$ 1\mapsto 3 \mapsto 1 \text{ cycle of size 2} $$ $$ 4\mapsto 7\mapsto 5\mapsto 8\mapsto 9\mapsto 6\mapsto 2\mapsto 4 \text{ cycle of size 7} $$ Let 's see why switching two rows will switch the sign of $f$ $$ f\begin{pmatrix} {\color{red}1}&2&3\\4&5&{\color{red}6}\\7&{\color{red}8}&9\\ \end{pmatrix} $$ Tell me which permutation is corresponding to this selection of elements. $1\times 6\times 8$ This is corresponding to permutation $(1,3,2)$ $$ f\begin{pmatrix} 4&5&{\color{red}6}\\{\color{red}1}&2&3\\7&{\color{red}8}&9\\ \end{pmatrix} $$ In this, tell me which permutation is corresponding to the term $6\times 1\times 8$ $(3,1,2)$