Transposition

王子鉴 计算机科学与技术系

2021 3 17

Preview

  • Proof
  • Extension
  • Reverse quickly

Problem

  • Show that any cycle can be written as the product of transpositions:
(a_1, a_2, \dots, a_n) = (a_1a_n) ( a_1a_{n-1})\dots (a_1a_3) (a_1a_2)
(1,2,3) = (1,3) (1,2)

Simpler case

(1, 2, 3) (1,3) (1,2)
1 2 2
2 3 3
3 1 1

longer?

Mathematical Induction

Proof

  • Base case ( n = 3 ) was proved
  • Suppose that when n = k is right
(a_1, a_2, \dots, a_k) = (a_1a_k) ( a_1a_{k-1})\dots (a_1a_3) (a_1a_2)
\to (a_1, a_2, \dots, a_{k+1}) = (a_1a_{k+1}) ( a_1a_{k})\dots (a_1a_3) (a_1a_2)

Proof

  • Base case ( n = 3 ) was proved
  • Suppose that when n = k is right
(a_1, a_2, \dots, a_k, a_{k+1}) a_k = a_{k+1}
(a_1a_{k+1}) (a_1a_k) (a_1a_{k-1})\dots (a_1a_3) (a_1a_2) a_k
=(a_1, a_{k+1}) a_1 = a_{k+1}
= (a_1,a_{k+1}) (a_1,a_2,\dots,a_k) a_k
(a_1, a_2, \dots, a_k, a_{k+1}) a_{k+1} = a_1
(a_1a_{k+1}) (a_1a_k) (a_1a_{k-1})\dots (a_1a_3) (a_1a_2) a_{k+1}
= (a_1,a_{k+1}) (a_1,a_2,\dots,a_k) a_{k+1}
=(a_1, a_{k+1}) a_{k+1} = a_1
\forall i < k, (a_1, a_2, \dots, a_k, a_{k+1}) a_i = a_{i+1}
(a_1a_{k+1}) (a_1a_k) (a_1a_{k-1})\dots (a_1a_3) (a_1a_2) a_i
= (a_1,a_{k+1}) (a_1,a_2,\dots,a_k) a_i
=(a_1, a_{k+1}) a_{i+1} = a_{i+1}

Proof

  • Base case ( n = 3 ) was proved
  • Suppose that when n = k is right

n = k + 1 is right

Proved !

Extension 0

(a_{1,1},a_{1,2},\dots,a_{1,b_1}) (a_{2,1},\dots,a_{2,b_2})\dots(a_{n,1},\dots,a{n,b_n})
=\prod\limits_{j=b_1}^2(a_{11}a_{1j})\prod\limits_{j=b_2}^2(a_{21}a_{2j})\dots \prod\limits_{j=b_n}^2(a_{n1}a_{nj})
=\prod\limits_{i=1}^n\prod\limits_{j=b_i}^2(a_{i1}a_{ij})

Extension 1 : (a)

Any cycle can be written as the product of following permutation

(1,2), (1,3)\dots (1,n)

Only need to prove any transposition can be written as the product of former permutations

Extension 1 : (a)

(23)(12) = (23)(21) = (213) = (132) = (12)(13)
\to (23) = (23)(12)(12) = (12)(13)(12)
(a_ia_j) (1a_i) = (a_i1a_j) = (1a_ja_i)= (1a_i)(1a_j)
\to (a_ia_j) = (a_ia_j)(1a_i)(1a_i) = (1a_i)(1a_j)(1a_i)

Extension 1 : (a)

With extension 0, any production of any cycle can be written as the product of 

(1,2), (1,3)\dots (1,n)

Extension 2 : (b)

Any cycle can be written as the product of following permutation

(1,2), (2,3)\dots (n-1,n)

Only need to prove any transposition can be written as the product of former permutations

Or

(1,2), (1,3)\dots (1,n)

Extension 2 : (b)

(13)(23) = (321) = (213) = (23)(21)
\to (13) = (13)(23)(23) = (23)(12)(23)
(1n) = (n-1,n)(1,n-1)(n-1,n)
=\dots
=\prod\limits_{i=n}^3(i-1,i) \cdot(12)\cdot\prod\limits_{i=3}^{n}(i-1,i)
= (n-1,n)(n-2,n-1)(1,n-2)(n-2,n-1)(n-1,n)

Extension 3 : prove by switching

(a_1, a_2, \dots, a_n) \leftrightarrow (a_1, a_2), (a_1, a_3),\dots, (a_1, a_n)
(a_1, a_2, \dots, a_n) \leftrightarrow (1, 2), (1, 3),\dots, (1, m)
(a_1, a_2, \dots, a_n) \leftrightarrow (1, 2), (2, 3),\dots, (m-1, m)

Extension 4 : (c)

Any cycle can be written as the product of following permutation

(1,2), (1,2,\dots,n)

Notice that

(123\dots n)^n = (1)

Switching !

Extension 3 : (c)

(i, i+1) = (123\dots n)(i-1, i)(123\dots n)^{-1}
left right
i i + 1 i+1
i + 1 i i
other same same
(m, m+1) = (123\dots n)^{m-1}(1, 2)(123\dots n)^{-m+1}

Reverse

(a_1a_2\dots a_n)^{-1} = (a_na_{n-1}\dots a_1)
((a_1a_2)(b_1b_2))^{-1}=(b_1b_2)(a_1a_2)
\left[\prod\limits_{i=1}^n(\prod\limits_{j=1}^{m_i} a_{ij})\right] ^{-1} =\prod\limits_{i=n}^1(\prod\limits_{j=m_i}^{1} a_{ij})

Thanks for listening