mindmap

permutations, their properties

$$\begin{align*} (\tau \sigma)(i) = \tau (\sigma (i)) &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 6 & 2 & 4 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 3 & 4 & 2 & 1 & 5 \end{pmatrix} = \\ &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 6 & 5 & 3 & 2 \end{pmatrix} \ \ \ \ \ \ \ \ \ (\text{right to left: } 1 \to 6 \to 4) \end{align*}$$

cycle — $\begin{pmatrix}1 & 2 & 5 \end{pmatrix}$
transposition — cycle of length two: $\begin{pmatrix}3 & 4 \end{pmatrix}$

write the permutation as a product of disjoint cycles
$\begin{align*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 4 & 1 & 7 & 3 & 6 & 2 \end{pmatrix} &= \begin{pmatrix} 1 & 5 & 3 \end{pmatrix} \begin{pmatrix} 2 & 4 & 7 \end{pmatrix} = \\ &= \begin{pmatrix} 1 & 5 & 3 \end{pmatrix} \begin{pmatrix} 2 & 4 & 7 \end{pmatrix} \begin{pmatrix} 6 \end{pmatrix} = \\ &= \begin{pmatrix} 2 & 4 & 7 \end{pmatrix} \begin{pmatrix} 1 & 5 & 3 \end{pmatrix} = \\ &= \begin{pmatrix} 2 & 4 & 7 \end{pmatrix} \begin{pmatrix} 1 & 5 & 3 \end{pmatrix} \begin{pmatrix} 6 \end{pmatrix} \end{align*}$

multiply permutations:
$\left[\begin{pmatrix} 1 & 3 & 5 \end{pmatrix} \begin{pmatrix} 2 & 4 & 6 & 7 \end{pmatrix}\right] \ \cdot \ \left[\begin{pmatrix} 1 & 4 & 7 \end{pmatrix} \begin{pmatrix} 2 & 3 & 5 & 6 \end{pmatrix}\right] = \begin{pmatrix} 1 & 6 & 4 & 2 & 5 & 7 & 3 \end{pmatrix}$

$$\begin{align*} 1 \to 4 \to 6&: \ \ \ \begin{pmatrix} 1 & 6 & \ldots \end{pmatrix} \\ 6 \to 2 \to 4&: \ \ \ \begin{pmatrix} 1 & 6 & 4 & \ldots \end{pmatrix} \\ 4 \to 7 \to 2&: \ \ \ \begin{pmatrix} 1 & 6 & 4 & 2 & \ldots \end{pmatrix} \end{align*}$$

to inverse a permutation just interchange the two lines:
$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ \boldsymbol 2 & \boldsymbol 5 & \boldsymbol 4 & \boldsymbol 3 & \boldsymbol 1 \end{pmatrix}^{-1} =\begin{pmatrix} \boldsymbol 2 & \boldsymbol 5 & \boldsymbol 4 & \boldsymbol 3 & \boldsymbol 1 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix} =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2\end{pmatrix}$

inverted cycle: $\begin{pmatrix} i_1 & \ldots & i_n \end{pmatrix}^{-1} = \begin{pmatrix} i_n & \ldots & i_1 \end{pmatrix}$

Any even permutation can be written as a product of cycles of length three:

if j = k then (i j)(k l) = (i j l) is a 3-cycle
otherwise, (i j)(k l) = (i j)(j k) (j k)(k l) = (i j k)(j k l)

parity of permutations

there are two equivalent definitions of /parity/

the parity of a permutation is the parity of number of inversions
inversion is a pair of elements $(x, \, y)$ such that $x < y$ and $\sigma(x) > \sigma(y)$

the parity of a permutation is the parity of number of transpositions in the decomposition
although such a decomposition is not unique, the parity of the number of transpositions in all decompositions is invariant, implying that the sign of a permutation is well-defined

Theorem: two definitions are equivalent

Proof: $(-1)^n$ where $n$ is number of inversions can be written as

$$\operatorname{sgn}(\sigma)=\frac{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})}{P(x_1,\ldots,x_n)}$$

where
$P(x_1,\ldots,x_n)=\prod_{i<j} (x_i - x_j)\;$

e.g. $P(x_1, x_2, x_3) = (x_1 - x_2)(x_1 - x_3)(x_2 - x_3)\;$

e.g. $\operatorname{sgn}(e) = 1$ and $\operatorname{sgn}(1\ 2) = -1$

$\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\cdot\operatorname{sgn}(\tau)$

because
$\begin{align*} \operatorname{sgn}(\sigma\tau) &= \frac{P(x_{\sigma(\tau(1))},\ldots,x_{\sigma(\tau(n))})}{P(x_1,\ldots,x_n)} = \\ &= \frac{P(x_{\sigma(\tau(1))},\ldots, x_{\sigma(\tau(n))})}{P(x_1,\ldots,x_n)} \cdot \frac{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})}{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})} = \\ &= \frac{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})}{P(x_1,\ldots,x_n)} \cdot \frac{P(x_{\sigma(\tau(1))},\ldots, x_{\sigma(\tau(n))})}{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})} = \\ &= \operatorname{sgn}(\sigma)\cdot\operatorname{sgn}(\tau) \end{align*}$

then if there are two representations $\sigma \ = \ a_1 \ldots a_n \ = \ b_1 \ldots b_k$
then $\operatorname{sgn}(\sigma) = (-1)^n = (-1)^k$
then $n-k$ is even
therefore
either both of them are even
or both of them are odd

End proof.

Example
is the permutation even or odd?
$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 6 & 2 & 7 & 4 & 1 & 3 \end{pmatrix}$

let’s count inversions

$\sigma(1) > \sigma(3),\,\sigma(5),\,\sigma(6),\,\sigma(7)$
$\sigma(2) > \ldots$
…

$\Updownarrow$

5 > 2,4,1,3 — 4 inversions
6 > 2,4,1,3 — 4 inversions
2 > 1 — 1 inversion
7 > 4,1,3 — 3 inversions
4 > 1,3 — 2 inversions

4 + 4 + 1 + 3 + 2 = 14 — the permutation is even

Another example:
the sign of $n$-cycle is $(-1)^{n-1}$ since
every $n$-cycle can be expressed as product of $n-1$ transpositions:
$\begin{pmatrix} 1 & 2 & \ldots & n \end{pmatrix} = \begin{pmatrix} 1 & n \end{pmatrix} \cdot \begin{pmatrix} 1 & (n-1) \end{pmatrix} \cdot \ldots \cdot \begin{pmatrix} 1 & 3 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \end{pmatrix}$
and also
$\begin{pmatrix} 1 & 2 & \ldots & n \end{pmatrix} = \begin{pmatrix} 1 & 2 \end{pmatrix} \cdot \begin{pmatrix} 2 & 3 \end{pmatrix} \cdot \ldots \cdot \begin{pmatrix} {n-1} & n \end{pmatrix}$

in practice, in order to determine whether a given permutation is even or odd, one writes the permutation as a product of disjoint cycles
$\sigma = c_1 \cdot \ldots \cdot c_n$, where $c_1, \ldots, c_n$ are cycles
$\operatorname{sgn} \sigma = (-1)^{\operatorname{parity}(c_1) + \ldots + \operatorname{parity}(c_n)}$

Also, parity is $(-1)^{\operatorname{dec}(\sigma)}$, where decrement $\operatorname{dec}(\sigma) = n - \text{number of cycles} - \text{number of fixed points} = \text{number of points} - \text{number of graph components}$

transposition changes parity of a permutation

number of even permutations is the same as number of odd permutations — multiply an even permutation by a transposition and get an odd one, this defines a bijection

the following rules follow directly from addition of numbers of transpositions:

• the composition of two even permutations is even
• the composition of two odd permutations is even
• the composition of an odd and an even permutation is odd

permutation is odd $\iff$ disjoint cycles factorization contains an odd number of odd cycles

Properties of parity:

• $\operatorname{sgn}(\sigma \tau) = \operatorname{sgn}(\sigma) \operatorname{sgn}(\tau)$
• $\operatorname{sgn}(1) = 1$
• $\operatorname{sgn}(\sigma^{-1}) = (\operatorname{sgn}(\sigma))^{-1} = \operatorname{sgn}(\sigma)$
• $\operatorname{sgn}(i_1 \ldots i_n) = (-1)^{n-1}$
• $\operatorname{sgn}(t) = -1$

conjugation

http://unapologetic.wordpress.com/2010/09/10/conjugates/

$g \ (a_1\,\dots\,a_k) \ g^{-1} \quad = \quad (g(a_1)\,\dots\,g(a_k))$
because when $h = g \, f \, g^{-1}$
$h(g(1)) = g(f(g^{-1}(g(1)))) = g(f(1))$

Example
Any permutation can be written as a product of cycles: (1 2) (1 2 3 … n)

(1 2 3 … n)^1 (1 2) (1 2 3 … n)^{-1} = (2 3)
(1 2 3 … n)^k (1 2) (1 2 3 … n)^{-k} = (k+1 k+2)

this can be seen directly or with using properties of conjugates:
(1 2) = (1 2)(3)…(n) conjugated with (1 2 3 … n) is (2 3) (4) … (n-1) (1)

now we have (1 2), (2 3), (3 4), … , (n-1 n)
(3 7) = (3 4) (4 5) (5 6) (6 7) (6 5) (5 4) (4 3)

now we have all transpositions

http://math.berkeley.edu/~scanez/courses/math113/homework/hw3-solns.pdf
http://mathhelpforum.com/advanced-algebra/56719-permutations-1x-123-n-generate-sn.html
http://mathforum.org/library/drmath/view/51685.html

Theorem. Permutations conjugate $\iff$ they have the same cycle structure.
i.e. they consist of $n_1$ cycles of length $l_1$, … , $n_k$ cycles of length $l_k$

Begin proof.

$\boxed{\Rightarrow}$
$\sigma(i) = k$
$\left(\pi \sigma \pi^{-1}\right) \left(\pi(i)\right) = \pi(k)$

e.g.
$\pi \ \cdot \ \begin{pmatrix}1 & 2 & 3\end{pmatrix} \begin{pmatrix} 4 & 5\end{pmatrix} \ \cdot \ \pi^{-1} \ = \ \left( \begin{smallmatrix}\pi(1) & \pi(2) & \pi(3)\end{smallmatrix} \right) \left( \begin{smallmatrix}\pi(4) & \pi(5)\end{smallmatrix} \right)$

$\boxed{\Leftarrow}$
we can easily get conjugating permutation of two permutations with same structure
by just writing one under another

$$\begin{align*} \sigma &= \begin{pmatrix}1 & 2 & 3\end{pmatrix} \begin{pmatrix}4 & 5\end{pmatrix} \\ \pi \sigma \pi^{-1} &= \begin{pmatrix}1 & 5 & 2\end{pmatrix} \begin{pmatrix}3 & 4\end{pmatrix} \\ \\ \Rightarrow \pi &= \begin{pmatrix}2 & 5 & 4 & 3\end{pmatrix} \end{align*}$$

End proof.

Find number of permutations in $S_{10}$ that conjugate with (1 3 5 7 9)(2)(4)(6)(8)(10)

$\rho \tau = \tau \sigma \iff \rho = \tau \sigma \tau^-1$
permutations conjugate $\iff$ they have the same cycle structure
i.e. they consist of $n_1$ cycles of length $l_1$, … , $n_k$ cycles of length $l_k$
(1 2 3)(4 5)(6)(7)
(1 5 2)(3 4)(7)(6)

now, how many permutations $\tau$ such that $\rho = \sigma = \tau \sigma \tau^-1$?

the permutations in $S_6$ that commute with (123)(456) will either map
(123) and (456) to themselves or interchange them
because disjoint cycles commute

giving total $3^2 \cdot 2!$ different permutations $\tau$ that commute with our (1 2 3)(4 5 6)

illustration for the method

(1 2 3)(4 5 6)
(2 3 1)(4 5 6)
(3 1 2)(4 5 6)

(1 2 3)(5 6 4)
(2 3 1)(5 6 4)
(3 1 2)(5 6 4)

(1 2 3)(5 6 4)
(2 3 1)(5 6 4)
(3 1 2)(5 6 4)

and the same if we interchange them — (4 5 6)(1 2 3)

and in general
$\sigma \ = \ \prod \ n_i \ \text{cycles of length} \ l_i$
then the centralizer
$|C_\sigma| \ = \ \prod {l_i}^{n_i} \, {n_i}!$

algorithm — number of inversions
how to get number of inversions in an array in $O(n \log n)$
The only moment when inversions are removed is when algorithm takes element from the right side of an array and merge it to the main array.
The number of inversions removed by this operation is the number of elements left from the the left array to be merged.
| merged | left | right | comment |
| ( ) | (1 3 5 8) | (2 4 6 7 9 11) | |
| (1) | (3 5 8) | (2 4 6 7 9 11) | |
| (1 2) | (3 5 8) | (4 6 7 9 11) | all elts in left array where greater that 2, then 3 inversions removed |

you can do the same with quicksort, but it’s $O(n^2)$ in the worst case

Superlearn

• Q: How to get number of inversions in an array in $O(n \log n)$?

• Q: Properties of parity
  • $\operatorname{sgn}(\sigma \tau) = ?$
  • $\operatorname{sgn}(1) = ?$
  • $\operatorname{sgn}(\sigma^{-1}) = ?$
  • $\operatorname{sgn}(i_1 \ldots i_n) = ?$
  • $\operatorname{sgn}(t) = ?$

• Q: Number of vertices minus number of cycles minus number of fixed points. Which is number of vertices minus number of components if drawn as graph.

• Q: There exists exactly one function $\operatorname{sgn}: S_n \to {\pm 1}$ not equivalent to one, with properties $\operatorname{sgn}(\sigma \tau) = \operatorname{sgn}(\sigma) \operatorname{sgn}(\tau)$

• Q: $\prod_{\sigma \in S_n} \operatorname{sgn}(\sigma) = ?$

• A: It equals to number of odd permutations, which is half of all permutations.

• Q: Any even permutation can be written as a product of these cycles: (1 2 3), (1 2 4), … , (1 2 n):

• Q: Any even permutation can be written as a product of cycles of length three: (a k l)
• A:
  we’ve got these elementary cycles:
  (1 2 3), (1 3 2) = (1 2 3)^2
  (1 2 4), (1 4 2) = (1 2 4)^2
  …..
  (1 2 n), (1 n 2) = (1 2 n)^2

then (1 k l) = (1 2 l) (1 k 2) =
= (1 2 l) (2 1 k)

put a instead of 1:
(a k l) = (a 2 l) (a k 2) =
= (2 l a) (2 a k) = interchange 1 and 2 in (1 k l)
= (2 1 a) (1 2 l) (2 1 k) (1 2 a)

• Q: Solve $\sigma^2 = (1 \ 2 \ 3)(4 \ 5 \ 6)$
  A: <file:///Users/alex/Dropbox/hse_math/linear_algebra 04 – Comments_permtation_root.pdf>

• Q: Compute $\sigma^{2019}$
  A: Disjoint cycles decomposition, then $(1 \ \ldots \ n)^k = ()()()$ — it breaks into $\frac{n}{\operatorname{gcd}(n, k)}$ parts, with $\operatorname{gcd}(n, k)$ elements in each part.
  $(1 \ 2 \ 3 \ 4 \ 5 \ 6)^2 = (1 \ 3 \ 5)(2 \ 4 \ 6)$

• Q: https://en.wikipedia.org/wiki/Vandermonde_matrix

• Q: Every $n$-cycle can be expressed as product of $n−1$ transpositions.

• Q: How to find parity of a permutation?
  A: Using disjoing cycles, using decremtn.

• Q: Solve $(1 \ 2) \sigma (3 \ 4) = ((1\ 2\ 3)(4\ 5))^{17}$.

• Q: prove that permutations conjugate $\iff$ they have the same cycle structure
  A:
  $\boxed{\Rightarrow}$

  $\sigma(i) = k$
  $\left(\pi \sigma \pi^{-1}\right) \left(\pi(i)\right) = \pi(k)$

  e.g.
  $\pi \ \cdot \ \begin{pmatrix}1 & 2 & 3\end{pmatrix} \begin{pmatrix} 4 & 5\end{pmatrix} \ \cdot \ \pi^{-1} \ = \ \left( \begin{smallmatrix}\pi(1) & \pi(2) & \pi(3)\end{smallmatrix} \right) \left( \begin{smallmatrix}\pi(4) & \pi(5)\end{smallmatrix} \right)$

  $\boxed{\Leftarrow}$

  we can easily get conjugating permutation of two permutations with same structure
  by just writing one under another

$$\begin{align*} \sigma &= \begin{pmatrix}1 & 2 & 3\end{pmatrix} \begin{pmatrix}4 & 5\end{pmatrix} \\ \pi \sigma \pi^{-1} &= \begin{pmatrix}1 & 5 & 2\end{pmatrix} \begin{pmatrix}3 & 4\end{pmatrix} \\ \\ \Rightarrow \pi &= \begin{pmatrix}2 & 5 & 4 & 3\end{pmatrix} \end{align*}$$

multiply permutations [$]\begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\ 3 &amp; 5 &amp; 1 &amp; 6 &amp; 2 &amp; 4 \end{pmatrix} \cdot \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\ 6 &amp; 3 &amp; 4 &amp; 2 &amp; 1 &amp; 5 \end{pmatrix} \ = \ ?[/$]
[$](\tau \sigma)(i) = \tau (\sigma (i)) = \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\ 3 &amp; 5 &amp; 1 &amp; 6 &amp; 2 &amp; 4 \end{pmatrix} \cdot \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\ 6 &amp; 3 &amp; 4 &amp; 2 &amp; 1 &amp; 5 \end{pmatrix} = \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\ 4 &amp; 1 &amp; 6 &amp; 5 &amp; 3 &amp; 2 \end{pmatrix} \ \ \ \ \ \ \ \ \ (\text{right to left: } 1 \to 6 \to 4)[/$]
algebra example permutations

write the permutation as a product of disjoint cycles<div>
</div><div>[$]\begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\ 5 &amp; 4 &amp; 1 &amp; 7 &amp; 3 &amp; 6 &amp; 2 \end{pmatrix}[/$]</div>
[$]\begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\ 5 &amp; 4 &amp; 1 &amp; 7 &amp; 3 &amp; 6 &amp; 2 \end{pmatrix} = \begin{pmatrix} 1 &amp; 5 &amp; 3 \end{pmatrix} \begin{pmatrix} 2 &amp; 4 &amp; 7 \end{pmatrix} = \begin{pmatrix} 1 &amp; 5 &amp; 3 \end{pmatrix} \begin{pmatrix} 2 &amp; 4 &amp; 7 \end{pmatrix} \begin{pmatrix} 6 \end{pmatrix} = \begin{pmatrix} 2 &amp; 4 &amp; 7 \end{pmatrix} \begin{pmatrix} 1 &amp; 5 &amp; 3 \end{pmatrix} = \begin{pmatrix} 2 &amp; 4 &amp; 7 \end{pmatrix} \begin{pmatrix} 1 &amp; 5 &amp; 3 \end{pmatrix} \begin{pmatrix} 6 \end{pmatrix}[/$]
algebra example permutations

permutations:<div>
</div><div>what is cycle and what is transposition?</div>

cycle --- [$]\begin{pmatrix} 1 & 2 & 5 & 6 \end{pmatrix}[/$]

transposition --- cycle of length two: [$]\begin{pmatrix}3 & 4 \end{pmatrix}[/$]

algebra example permutations

multiply permutations:<div>
</div><div>[$]\left[\begin{pmatrix} 1 &amp; 3 &amp; 5 \end{pmatrix} \begin{pmatrix} 2 &amp; 4 &amp; 6 &amp; 7 \end{pmatrix}\right] \ &nbsp;\cdot \ \left[\begin{pmatrix} 1 &amp; 4 &amp; 7 \end{pmatrix} \begin{pmatrix} 2 &amp; 3 &amp; 5 &amp; 6 \end{pmatrix}\right] \ = \ \ ?[/$]</div>

[$$]\left[\begin{pmatrix} 1 & 3 & 5 \end{pmatrix} \begin{pmatrix} 2 & 4 & 6 & 7 \end{pmatrix}\right] \  \cdot \ \left[\begin{pmatrix} 1 & 4 & 7 \end{pmatrix} \begin{pmatrix} 2 & 3 & 5 & 6 \end{pmatrix}\right] = \begin{pmatrix} 1 & 6 & 4 & 2 & 5 & 7 & 3 \end{pmatrix}[/$$]

[latex]

\begin{align*}

1 \to 4 \to 6&: \ \ \ \begin{pmatrix} 1 & 6 & \ldots \end{pmatrix} \\

6 \to 2 \to 4&: \ \ \ \begin{pmatrix} 1 & 6 & 4 & \ldots \end{pmatrix} \\

4 \to 7 \to 2&: \ \ \ \begin{pmatrix} 1 & 6 & 4 & 2 & \ldots \end{pmatrix}

\end{align*}

[/latex]

algebra example permutations

is the permutation even or odd?

[$$]\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 6 & 4 & 7 & 2 & 1 & 3 \end{pmatrix}[/$$]

inversion is a pair of elements [$](x, \, y)[/$] such that [$]x < y[/$] and [$]\sigma(x) > \sigma(y)[/$]

let's count inversions

[$]\sigma(1) > \sigma(3),\,\sigma(5),\,\sigma(6),\,\sigma(7)[/$]

[$]\sigma(2) > \ldots[/$]

...

  

[$]\Updownarrow[/$]

5 > 4,2,1,3 --- 4 inversions

6 > 4,2,1,3 --- 4 inversions

4 > 2,1,3 --- 3 inversions

7 > 2,1,1 --- 3 inversions

2 > 1 --- 1 inversion

  

4 + 4 + 3 + 3 + 1 = 15 --- the permutation is odd

algebra example permutations

is the permutation even or odd?

[$$]\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 6 & 2 & 7 & 4 & 1 & 3 \end{pmatrix}[/$$]

inversion is a pair of elements [$](x, \, y)[/$] such that [$]x < y[/$] and [$]\sigma(x) > \sigma(y)[/$]

let's count inversions

[$]\sigma(1) > \sigma(3),\,\sigma(5),\,\sigma(6),\,\sigma(7)[/$]

[$]\sigma(2) > \ldots[/$]

...

  

[$]\Updownarrow[/$]

5 > 2,4,1,3 --- 4 inversions

6 > 2,4,1,3 --- 4 inversions

2 > 1 --- 1 inversion

7 > 4,1,3 --- 3 inversions

4 > 1,3 --- 2 inversions

  

4 + 4 + 1 + 3 + 2 = 14 --- the permutation is even

algebra example permutations

get the inversed permutation:<div>
</div><div>[$]\begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\ 2 &amp; 5 &amp; 4 &amp; 3 &amp; 1 \end{pmatrix}^{-1}[/$]</div>

to inverse a permutation just interchange the two lines:

[$$]

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ \boldsymbol 2 & \boldsymbol 5 & \boldsymbol 4 & \boldsymbol 3 & \boldsymbol 1 \end{pmatrix}^{-1}

      =\begin{pmatrix} \boldsymbol 2 & \boldsymbol 5 & \boldsymbol 4 & \boldsymbol 3 & \boldsymbol 1 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}

      =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2\end{pmatrix}

[/$$]

algebra example permutations

what is the parity of cycle<div>
</div><div>[$]\begin{pmatrix} 1 & 2 & \ldots & n \end{pmatrix}[/$]</div>

the sign is [$](-1)^{n-1}[/$] since there are [$](n-1)[/$] transpositions:

[$]\begin{pmatrix} 1 & 2 & \ldots & n \end{pmatrix} = \begin{pmatrix} 1 & n \end{pmatrix} \cdot \begin{pmatrix} 1 & n-1 \end{pmatrix} \cdot \ldots \cdot \begin{pmatrix} 1 & 3 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \end{pmatrix}[/$]

algebra example permutations

definition of parity of a permutation

two equivalent definitions based on:

number of inversions

number of transpositions

algebra definition permutations

how does multiplying a permutation by transposition affects the parity?
it will change the sign
algebra example permutations

definition of order of a permutation
order of [$]\sigma[/$] is the least positive integer [$]m[/$] such that [$]\sigma^m=1[/$]<div>
</div><div>
</div><div>
</div><div>
</div><div>
</div><div>if the permutation is written as a product of disjoint cycles, then it’s order is the LCM of the lengths of it’s cycles</div>
algebra definition permutations

how to get number of inversions in an array in [$]O(n \log n)[/$]
merge sort<div>
</div><div>
</div><div>the number of inversions removed while merging is the number of elements left from the the left array to be merged</div>
algebra algorithm permutations

do even permutations or odd permutations form a subgroup of [$]S_n[/$]?

even permutations form a subgroup of [$]S_n[/$]

odd permutations cannot form a subgroup, since the composite of two odd permutations is even

algebra example permutations

prove that any even permutation can be written as a product of cycles of length three
even permutation can be written as a product of even number transpositions<div>
</div><div><div>(i j)(k l) = (i j l) when j=k</div><div>otherwise, (i j)(k l) = (i j)(j k) (j k)(k l) = (i j k)(j k l)</div></div>
algebra example permutations

prove that any even permutation can be written as a product of these cycles: (1 2 3), (1 2 4), … , (1 2 n)
any even permutation can be written as a product of cycles of length three: (a k l)<div>
</div><div>(1 k l) = (1 2 l) (1 2 k)^2</div><div>
</div><div><div>just like the above: (a k l) = (a 2 l) (a k 2) = (2 l a) (2 a k)</div></div><div>and interchange 2 and 1 in (2 l a) and (2 a k)</div>
algebra example permutations

write this cycle as a product of transpositions
<div>
</div><div><div>[$]\begin{pmatrix} 1 & 2 & \ldots & n \end{pmatrix}[/$]</div></div>

[$]\begin{pmatrix} 1 & 2 & \ldots & n \end{pmatrix} = \begin{pmatrix} 1 & n \end{pmatrix} \cdot \begin{pmatrix} 1 & (n-1) \end{pmatrix} \cdot \ldots \cdot \begin{pmatrix} 1 & 3 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \end{pmatrix}[/$]

and also

[$]\begin{pmatrix} 1 & 2 & \ldots & n \end{pmatrix} = \begin{pmatrix} 1 & 2 \end{pmatrix} \cdot \begin{pmatrix} 2 & 3 \end{pmatrix} \cdot \ldots \cdot \begin{pmatrix} {n-1} & n \end{pmatrix}[/$]

algebra example permutations

how to get the parity of a permutation if it’s written as a product of disjoint cycles?

[$]\sigma = c_1 \cdot \ldots \cdot c_n[/$]

[$]\operatorname{sgn} \sigma = (-1)^{\operatorname{parity}(c_1) + \ldots + \operatorname{parity}(c_n)}[/$]

algebra permutations

get inverted cycle<div>
</div><div>[$]\begin{pmatrix} i_1 & \ldots & i_n \end{pmatrix}^{-1}[/$]</div>
[$]\begin{pmatrix} i_1 & \ldots & i_n \end{pmatrix}^{-1} = \begin{pmatrix} i_n & \ldots & i_1 \end{pmatrix}[/$]
algebra example permutations

prove that number of even permutations is the same as number of odd permutations
multiply an even permutation by a transposition and get an odd one, this defines a bijection
algebra example permutations

prove that any permutation can be written as a product of these cycles: (1 2), (1 2 3 … n)

(1 2 3 ... n)^1 (1 2) (1 2 3 ... n)^{-1} = (2 3)

(1 2 3 ... n)^k (1 2) (1 2 3 ... n)^{-k} = (k+1 k+2)

now we have (1 2), (2 3), (3 4), ... , (n-1 n)

(3 7)  =  (3 4) (4 5) (5 6) (6 _7_)   (6 5) (5 4) (4 3)

now we have all transpositions

algebra example permutations

find number of permutations in [$]S_{10}[/$] that commute with (1 3 5 7 9)

     [$]\rho \tau = \tau \sigma \iff \rho = \tau \sigma \tau^-1[/$]

     permutations conjugate [$]\iff[/$] they have the same cycle structure

     i.e. they consist of [$]n_1[/$] cycles of length [$]l_1[/$], ... , [$]n_k[/$] cycles of length [$]l_k[/$]

     (1 2 3)(4 5)(6)(7)

     (1 5 2)(3 4)(7)(6)

     

     

     

     

     now, how many permutations [$]\tau[/$] such that [$]\rho = \sigma = \tau \sigma \tau^-1[/$]?

     

     the permutations in [$]S_6[/$] that commute with (123)(456) will either map 

     (123) and (456) to themselves or interchange them

     because disjoint cycles commute

     

     giving total [$]3^2 \cdot 2![/$] different permutations [$]\tau[/$] that commute with our (1 2 3)(4 5 6)

     

     [$]\sigma \ = \  \prod \ n_i \  \text{cycles of length} \  l_i[/$]

     then the centralizer

     [$]|C_\sigma| \  = \  \prod {l_i}^{n_i} \, {n_i}![/$]

algebra example permutations

prove that permutations conjugate [$]\iff[/$] they have the same cycle structure

   [$]\boxed{\Rightarrow}[/$]

   [$]\sigma(i) = k[/$]

   [$]\left(\pi \sigma \pi^{-1}\right) \left(\pi(i)\right) = \pi(k)[/$]  

 

   e.g.

   [$]\pi \ \cdot \ \begin{pmatrix}1 & 2 & 3\end{pmatrix} \begin{pmatrix} 4 & 5\end{pmatrix} \ \cdot \ \pi^{-1} \ = \ \left( \begin{smallmatrix}\pi(1) & \pi(2) & \pi(3)\end{smallmatrix} \right) \left( \begin{smallmatrix}\pi(4) & \pi(5)\end{smallmatrix}  \right)[/$]

   

   [$]\boxed{\Leftarrow}[/$]

   we can easily get conjugating permutation of two permutations with same structure

   by just writing one under another

[latex]

   \begin{align*}

   \sigma &= \begin{pmatrix}1 & 2 & 3\end{pmatrix} \begin{pmatrix}4 & 5\end{pmatrix} \\

   \pi \sigma \pi^{-1} &= \begin{pmatrix}1 & 5 & 2\end{pmatrix} \begin{pmatrix}3 & 4\end{pmatrix} \\

   \\

   \Rightarrow \pi &=  \begin{pmatrix}2 & 5 & 4 & 3\end{pmatrix}

   \end{align*}

[/latex]

algebra permutations

write (2 5) using transpositions (1 2), (2 3), (3 4), …, (n-1 n)
(2 5)   =   (2345)   (234)^{-1}   =   (2 3) (3 4) (4 5)   (4 3) (3 2)
algebra example permutations