NOTES ON STATISTICS, PROBABILITY and MATHEMATICS

How to read out permutations:

From here:

The \(S_8\) permutation

\[(1\; 8 \; 7 \; 2)\]

can be expressed in stack form as position \(\color{red} 1\) will end up in position \(\color{magenta} 8,\) while \(\color{magenta} 8\) will end up in position \(\color{blue}7\) and so on:

\[\begin{matrix} \color{red}1 \quad \color{orange}2 \quad 3 \quad 4 \quad 5 \quad 6 \quad \color{blue} 7 \quad \color{magenta}8 \\ \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \\ \color{orange} 2 \quad \color{blue}7 \quad 3 \quad 4 \quad 5 \quad 6 \quad \color{magenta} 8 \quad \color{red} 1 \end{matrix}\]

This is the way that Matthew Salomone teaches it in here, which could be thought of as “trading chairs; keeping your number.”

However, another (and more intuitive) way of reading it would be: \(\color{red}1\) goes to \(\color{magenta}8,\) while \(\color{magenta} 8\) goes to \(\color{blue}7\) and so on:

\[\begin{matrix} \color{red}1 \quad \color{orange}2 \quad 3 \quad 4 \quad 5 \quad 6 \quad \color{blue}7 \quad \color{magenta}8 \\ \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \quad \downarrow \\ \color{magenta} 8 \quad \color{red}1 \quad 3 \quad 4 \quad 5 \quad 6 \quad \color{orange}2 \quad \color{blue} 7 \end{matrix}\]

This is how Wolfram Alpha does it: Permutation(1,8,7,2) yields:

It could be thought of as “trading numbers; keeping your chair.”

Both result in the same cycle expression.

Simplifying permutations:

Two permutations \((1\; 3 \; 2 \; 5) \, (1\; 8 \; 7 \; 2)\) can be simplified (using the trading chairs stack notation) as in here:

\[(1\; 8 \; 7 \; 2) = \begin{pmatrix} 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \\ \color{red}{2 \quad 7 \quad 3 \quad 4 \quad 5 \quad 6 \quad 8 \quad 1 } \end{pmatrix}\]

\[(1\; 3 \; 2 \; 5) = \begin{pmatrix} 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \\ 5 \quad 3 \quad 1 \quad 4 \quad 2 \quad 6 \quad 7 \quad 8 \end{pmatrix}\]

The idea is to use the result of the first permutation as the input of the second, although this step is omitted, or struck out in the final expression:

\[(1\; 3 \; 2 \; 5)\,(1\; 8 \; 7 \; 2) = \begin{pmatrix} 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \\ \text{trade seats = first permutation on the right:}\\ \color{red}{2 \quad 7 \quad 3 \quad 4 \quad 5 \quad 6 \quad 8 \quad 1 } \\ \text{pass on the result to the input for the second permutation:}\\ 1_{\color{red}{2}} \quad 2_{\color{red}{7}} \quad 3_{\color{red}{3}} \quad 4_{\color{red}{4}} \quad 5_{\color{red}{5}} \quad 6_{\color{red}{6}} \quad 7_{\color{red}{8}} \quad 8_{\color{red}{1}} \\ \text{trade seat = second permutation:}\\ 5_{\color{red}{5}} \quad 3_{\color{red}{3}} \quad 1_{\color{red}{2}}\quad 4_{\color{red}{4}}\quad 2_{\color{red}{7}} \quad 6_{\color{red}{6}} \quad 7_{\color{red}{8}} \quad 8_{\color{red}{1}} \\ \text{replace the numbers in each seat with the input numbers:}\\ \color{red}{5 \quad 3 \quad 2 \quad 4 \quad 7 \quad 6 \quad 8 \quad 1 } \end{pmatrix}\]

or

\[(1\; 3 \; 2 \; 5)\,(1\; 8 \; 7 \; 2) = \begin{pmatrix} 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \\ \color{red}{5 \quad 3 \quad 2 \quad 4 \quad 7 \quad 6 \quad 8 \quad 1 } \end{pmatrix}\]

which in cycle notation is

\[(1\; 3 \; 2 \; 5)\,(1\; 8 \; 7 \; 2) = (1 \; 8 \; 7 \; 5)\;(2 \; 3)\]

Using the “trading numbers; keeping seats” system we just follow the numbers down the trail:

\[(1\; 3 \; 2 \; 5)\,(1\; 8 \; 7 \; 2) = \begin{pmatrix} 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \\ \text{trade numbers = first permutation on the right:}\\ \color{red}{8 \quad 1 \quad 3 \quad 4 \quad 5 \quad 6 \quad 2 \quad 7 } \\ \text{pass on the result to the input for the second permutation}\\ \text{following the number matches - location has no info:}\\ \text{so realigning vertically the second cycle to coincide with output:}\\ 8 \quad 1 \quad 3 \quad 4 \quad 5 \quad 6 \quad 2 \quad 7 \\ \color{red}{8 \quad 3 \quad 2 \quad 4 \quad 1 \quad 6 \quad 5 \quad 7 } \end{pmatrix}\]

or

\[(1\; 3 \; 2 \; 5)\,(1\; 8 \; 7 \; 2) = \begin{pmatrix} 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \\ \color{red}{8 \quad 3 \quad 2 \quad 4 \quad 1 \quad 6 \quad 5 \quad 7 } \end{pmatrix}\]

which yields the same cycle notation as with the trading places system.

This is simply following the numbers vertically (no need to actually reshuffle to match them as above):

\[(1\; 3 \; 2 \; 5)\,(1\; 8 \; 7 \; 2) = \begin{pmatrix} \bbox[5px,border:2px solid red]1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \\ \color{red}{8\downarrow}\quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 2 \quad 7 \\ \color{red}{\rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow} \\ 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \color{red}{\quad \downarrow 8} \\ 3 \quad 5 \quad 2 \quad 4 \quad 1 \quad 6 \quad 7 \quad \bbox[5px,border:2px solid red]8 \end{pmatrix}\]

Conjugation of permutations:

From here:

The permutation

can be expressed as \[(1 \, 4 \, 3)\;(2 \, 5)\]

in cycle notation, which visually is more clear if we rearrange the permutation graph as

which would allow us to see at once that this permutation is up-to-relabeling identical to

or \[(1 \, 2 \, 3)\;(4 \, 5)\]

They both have the same cycle type, and the first permutation can be turned into the second via a re-labeling map:

which can be expressed as

\[\tau \sigma \tau^{-1}\]

Both \(\tau\) and \(\sigma\) belong to the symmetric group \(S_5,\) and \(\tau\) could have been any other element (or permutation) in \(S_5.\)

The new mapping, i.e. \(\tau \sigma \tau^{-1}\) will be another element of \(S_5\) of the same cycle type as \(\sigma,\) and the operation \(\tau \sigma \tau^{-1}\) is conjugation.

How can we write the cycle decomposition of \(\tau \sigma \tau^{-1}\) by relabeling the domain and co-domain of \(\sigma\) as

and note that since permutations are bijections writing \(\tau\) or \(\tau^{-1}\) makes no difference. In cycle notation, the new \(\tau \sigma \tau^{-1}\) permutation would be

\[\left( \tau(1) \, \tau(2) \tau(3) \right )\;\left (\tau(4) \, \tau(5)\right)\]

Exercise from an example here:

For this to be concordant with the card game on the presentation the first row (first permutation given) should be understood as \(0\) moves to slot number \(3\); \(1\) moves to slot number \(2\); \(2 \to 0; \quad 3 \to 4; \quad 4 \to 1:\)

which would result in

\[ \sigma = \begin{pmatrix} 0\; 1 \; 2 \; 3 \; 4 \\ 3 \; 2 \; 0 \; 4 \; 1 \end{pmatrix} \]

or in cycle notation:

\[\sigma=(0\,3\,4\,1\,2)\]

And, similarly,

\[ \tau\sigma\tau^{-1} = \begin{pmatrix} 0\; 1 \; 2 \; 3 \; 4 \\ 4 \; 0 \; 3 \; 1 \; 2 \end{pmatrix}\\ \]

or in cycle notation:

\[\tau\sigma\tau^{-1}=(0\,4\,2\,3\,1)\]

Tau can be obtained by stacking up

\[\begin{bmatrix}\begin{align}\sigma= (0\,3\,4\,1\,2)\\\tau\sigma\tau^{-1}=(0\,4\,2\,3\,1) \end{align}\end{bmatrix}\implies \tau =(0)\,(3\,4\,2\,1) \]

and reading the entries in cycle notation column wise. So \(\tau\) is constructed in cycle form by reading \(0→0, 3→4, 4→2, 1→3, 2→1,\)

Here is the proof in “trading numbers stacked notation” (Wolfram Alpha style):

\[\begin{align} \tau^{-1}=(0)\,(3\,1\,2\,4))&= \begin{pmatrix} 0 & 1 & 2 & 3 & 4 \\ 0 & 2 & 4 & 1 & 3 \end{pmatrix} \\ \sigma=(0\,3\,4\,1\,2) &= \begin{pmatrix} 0& 1 & 2 & 3 & 4 \\ 3 & 2 & 0 & 4 & 1 \end{pmatrix} \\ \tau=(0)\,(3\,4\,2\,1) &= \begin{pmatrix} 0 & 1 & 2 & 3 & 4 \\ 0 & 3 & 1 & 4 & 2 \end{pmatrix} \\ \hline \tau \sigma \tau^{-1} &= \begin{pmatrix} 0 & 1 & 2 & 3 & 4 \\ 4 & 0 & 3 & 1 & 2 \end{pmatrix} \end{align} \]

Home Page

NOTE: These are tentative notes on different topics for personal use - expect mistakes and misunderstandings.