令A是含有n个元素的集合 , S_n={σ|σ是A上的双射} ,

一般地 , 我们称S_n中的元素为n元置换 ,

令集合A={1 , 2 , ⋯ , n} , 则属于S_n 的任意置换σ均可以表示成如下形式 :

$$\sigma = \left( \begin{array}{r} \begin{matrix} \ \ \ \ \ 1\ \ \ \ \ & \ \ \ 2\ \ \ \ \end{matrix}\ \ \ \begin{matrix} \cdots & \ \ \ n\ \end{matrix}\ \ \ \ \ \ \\ \begin{matrix} \sigma(1) & \sigma(2) \end{matrix}\ \ \ \ \begin{matrix} \cdots & \sigma(n) \end{matrix} \end{array} \right)$$

又由于σ是A上的双射 , 所以σ(1) , σ(2) , ⋯ , σ(n)是1 , 2 , ⋯ , n的一个全排列 ,

反之 , 对1 , 2 , ⋯ , n的任意一个全排列i₁ , i₂ , ⋯ , i_n 都能给出一个置换

$$\left( \begin{array}{r} \begin{matrix} \ \ 1 & \ 2 \end{matrix}\ \ \ \ \ \begin{matrix} \cdots & n \end{matrix}\ \ \ \ \\ \begin{matrix} i_{1} & i_{2} \end{matrix}\ \ \ \ \begin{matrix} \cdots & i_{n} \end{matrix} \end{array} \right)$$

并且对不同的全排列给出不同的置换 , 所以S_n 含有n!个元素 ,

特别地 , 当n=1时 , S_n只含有一个元素 , 即恒等变换1 ,

在以下的讨论中 , 我们总假定n>1

例2.1 设$\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$ , $\varphi = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}$ , $\tau = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$ , 试计算σφ和φτσ

解: 我们先来求σφ , 因为σφ(1)=σ(2)=3 , σφ(2)=σ(1)=2 , σφ(3)=σ(3)=1 ,

因此 , σφ=$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$

实际上 , 这个过程可以用下式表示: σφ=$\left( \begin{array}{r} \begin{matrix} 1 & 2 \end{matrix}\ \ \ \ \begin{matrix} 3 & \end{matrix} \\ \begin{matrix} \downarrow & \downarrow \end{matrix}\ \ \ \ \begin{matrix} \downarrow & \varphi \end{matrix} \\ \begin{matrix} 2 & 1 \end{matrix}\ \ \ \ \begin{matrix} 3 & \end{matrix} \\ \begin{matrix} \downarrow & \downarrow \end{matrix}\ \ \ \ \begin{matrix} \downarrow & \sigma \end{matrix} \\ \begin{matrix} 3 & 2 \end{matrix}\ \ \ \ \begin{matrix} 1 & \end{matrix} \end{array} \right)$

类似地 , 我们可以求φτσ , 如下式: $\varphi\tau\sigma = \left( \begin{array}{r} \begin{matrix} 1 & 2 \end{matrix}\ \ \ \ \ \begin{matrix} 3 & \end{matrix} \\ \begin{matrix} \downarrow & \downarrow \end{matrix}\ \ \ \ \ \begin{matrix} \downarrow & \sigma \end{matrix} \\ \begin{matrix} 2 & 3 \end{matrix}\ \ \ \ \ \begin{matrix} 1 & \end{matrix} \\ \begin{matrix} \downarrow & \downarrow \end{matrix}\ \ \ \ \ \begin{matrix} \downarrow & \tau \end{matrix} \\ \begin{matrix} 2 & 1 \end{matrix}\ \ \ \ \ \begin{matrix} 3 & \end{matrix} \\ \begin{matrix} \downarrow & \downarrow \end{matrix}\ \ \ \ \ \begin{matrix} \downarrow & \varphi \end{matrix} \\ \begin{matrix} 1 & 2 \end{matrix}\ \ \ \ \ \begin{matrix} 3 & \end{matrix} \end{array} \right)$

因此 , φτσ=$\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$=id

定义2.1 设σ属于S_n , 若在集合{1 , 2 , ⋯ , n}中存在t个不同的数i₁ , i₂ , ⋯ , i_t ,

使得σ(i₁ )=i₂ , σ(i₂ )=i₃ , ⋯ , σ(i_i‒1)=i_i , σ(i_t )=i₁ ,

并且对于{i₁ , i₂ , ⋯ , i_t }之外的n‒t个元素(如果存在的话) ,

在σ的作用下都保持不变 , 即σ(i)=i ,

则称σ是长度为t的轮换 , 记其为σ=(i₁ i₂ ⋯i_t ) ,

特别地 , 长度为2的轮换称为对换 ,

S_n中的恒等变换称为长度是1的轮换 , 记为(1) ,

对于两个轮换(i₁ i₂ ⋯i_t )和(j₁ j₂ ⋯j_s ) ,

如果对属于{1 , 2 , ⋯ , t}的任意k , 和属于{1 , 2 , ⋯ , s}的任意l , 都有i_k ≠j_l ,

即{i₁ i₂ ⋯i_t }⋂{j₁ j₂ ⋯j_s }=⌀ , 则称这两个轮换是不相交的

显然 , 若σ=(i₁ i₂ ⋯i_t )和τ=(j₁ j₂ ⋯j_s )是S_n中两个不相交的轮换 ,

则它们的合成是可交换的 , 即(i₁ i₂ ⋯i_t )(j₁ j₂ ⋯j_s )=(j₁ j₂ ⋯j_s )(i₁ i₂ ⋯i_t ) ,

例2.2 判断置换σ = $\left( \begin{array}{r} \begin{matrix} 1 & 2 & 3 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 5 \end{matrix}\ \ \ \ \ \begin{matrix} 6 & 7 \end{matrix} \\ \begin{matrix} 1 & 3 & 7 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 6 \end{matrix}\ \ \ \ \ \begin{matrix} 2 & 5 \end{matrix} \end{array} \right)$是否是轮换 ,

解: 在集合{1 , 2 , 3 , 4 , 5 , 6 , 7}中有5个数2 , 3 , 7 , 5 , 6

满足σ(2)=3 , σ(3)=7 , σ(7)=5 , σ(5)=6和σ(6)=2 ,

而且对于余下的两个数1和4有σ(1)=1 , σ(4)=4 ,

因此 , 根据定义2.1 , σ是长度为5的轮换 , 且σ=(23756) ,

注意 , 在一般情况下 , 置换不一定是轮换 ,

例如 , 置换σ=$\left( \begin{array}{r} \begin{matrix} 1 & 2 & 3 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 5 \end{matrix} \\ \begin{matrix} 2 & 5 & 4 \end{matrix}\ \ \ \ \ \begin{matrix} 3 & 1 \end{matrix} \end{array} \right)$就不是轮换 ,

定理2.1 每一个置换可以表示成不相交的轮换的合成

证: 设σ属于S_n且σ不等于(1) ,

首先 , 取属于{1 , 2 , ⋯ , n}的i , 并要求其满足σ(i₁ )不等于i₁

由于i₁ , σ(i₁ ) , σ² (i₁ ) , ⋯属于{1 , 2 , ⋯ , n} ,

故必存在关系t₁＜t₂ , 使得$\sigma^{t_{1}}\left( i_{1} \right) = \sigma^{t_{2}}\left( i_{2} \right)$ , 即有$\sigma^{t_{2} - t_{1}}\left( i_{1} \right) = i_{1}$

若令t是满足$\sigma^{t}\left( i_{1} \right) = i_{1}$的最小正整数 , 那么从i_i 的选取方法 , 我们可知t>1

并且σ在{i₁ , σ (i₁ ) , σ ²(i₁ ) , ⋯ , σ^t‒1(i₁ )}上的限制构成一个轮换 ,

其次 , 如果{i₁ , σ (i₁ ) , σ ²(i₁ ) , ⋯ , σ^t‒1(i₁ )}之外的元素在σ作用下都保持不动 ,

那么σ=(i₁ σ (i₁ )σ ²(i₁ )⋯σ^t‒1(i₁ )) , 即σ是(单个)轮换的合成 ,

否则 ,

可以在{i₁ , σ (i₁ ) , σ ²(i₁ ) , ⋯ , σ^t‒1(i₁ )}之外选取一个在σ作用下变动的元素i₂

然后 , 对i₂ 重复上述过程 , 则存在大于1的s ,

使得σ在{i₂ , σ (i₂ ) , σ ²(i₂ ) , ⋯ , σ^s‒1(i₂)}上的限制构成一个轮换

如果{i₁ , σ (i₁ ) , σ ²(i₁ ) , ⋯ , σ^t‒1(i₁ )}⋃{i₂ , σ (i₂ ) , σ ²(i₂ ) , ⋯ , σ^s‒1(i₂)}之外的元素

在σ作用下都保持不动

那么σ=(i₁ σ (i₁ )σ ²(i₁ )⋯σ^t‒1(i₁ ))(i₂σ (i₂ )σ ²(i₂ )⋯σ^s‒1(i₂))

且(i₁ σ (i₁ )σ ²(i₁ )⋯σ^t‒1(i₁ ))与(i₂σ (i₂ )σ ²(i₂ )⋯σ^s‒1(i₂))互不相交

(注: 对属于Z的任意k , l , σ^k (i₂ )≠σ^l (i₁ ) , 否则导致i₂ =σ^l‒k(i₁ ) ,

这与i₂的选取矛盾)

即σ可以表示成不相交的两个轮换的合成 ,

否则 , 再重复上面的讨论过程 , 由于n小于无穷大 ,

所以 , 我们一定可以在有限步之内完成上述讨论 , 即得到分解式的存在性 ,

例2.3试将S₅中的置换σ=$\left( \begin{array}{r} \begin{matrix} 1 & 2 & 3 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 5 \end{matrix}\ \ \ \ \ \begin{matrix} 6 & 7 \end{matrix} \\ \begin{matrix} 1 & 7 & 2 \end{matrix}\ \ \ \ \ \begin{matrix} 6 & 5 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 3 \end{matrix} \end{array} \right)$表示成不相交的轮换的合成

解: 因为σ(2)不等于2且σ(2)=7 , σ(7)=3 , σ(3)=2 ,

因此 , σ在集合{2 , 7 , 3}上的限制是轮换(273) ,

又因为4不属于{2 , 7 , 3}且σ(4)=6 , σ(6)=4 ,

因此 , σ在集合{4 , 6}上的限制是轮换(46) ,

又因为1 , 5不属于并集{2 , 7 , 3}⋃{4 , 6} , 且σ(1)=1 , σ(5)=5 ,

所以 , 根据定理2.1知σ是不相交的两个轮换(273) 和(46)的合成 ,

即σ=(273)(46) ,

例2.4试将S₅中的置换σ=$\left( \begin{array}{r} \begin{matrix} 1 & 2 & 3 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 5 \end{matrix} \\ \begin{matrix} 2 & 5 & 4 \end{matrix}\ \ \ \ \ \begin{matrix} 3 & 1 \end{matrix} \end{array} \right)$表示成不相交的轮换的合成

解: 因为σ(1)不等于1且σ(1)= 2 , σ(2)=5 , σ(5)=1 ,

因此 , σ在集合{1 , 2 , 5}上的限制是轮换(125) ,

又因为3不属于{1 , 2 , 5}且σ(3)=4 , σ(4)=3 ,

因此 , σ在集合{3 , 4}上的限制是轮换(34) ,

另外{1 , 2 , 5}⋃{3 , 4}={1 , 2 , 3 , 4 , 5}

所以 , 根据定理2.1 , 我们知道σ是不相交的两个轮换(125)和(34)的合成 ,

即σ=(125)(34) ,

例2.5易见 , 在S₃中 , $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}$=(12) , $\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$=(13)和$\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}$=(23)

是长度为2的轮换 ,

$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$=(123)和$\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$=(132)是长度为3的轮换 ,

此外 , 容易验证, (123)=(13)(12) , (132)=(12)(13) , (1)=(12) (12) ,

即对于S₃中的元素来说 , 每个置换都是轮换且可以用对换表示 ,

即S₃={(1) , (12) , (13) , (23) , (12)(13) , (13)(12)} ,

更一般地 , 关于轮换与对换的关系 , 我们有:

例2.6设σ=(i₁i₂ ⋯i_t , )是S_n中的一个轮换 , 则容易验证

σ=(i₁i_t)(i₁i_t‒1) ⋯(i₁i₃)(i₁i₂)=(i₁i₂)(i₂i₃) ⋯(i_t‒2i_t‒1)(i_t‒1i_t) ,

即S_n中每个轮换都可以表示成对换合成的形式 ,

由此 , 再结合定理2.1 , 我们可知每个置换可以表示成对换合成的形式 ,

但表达式不唯一 ,

例2.7试将置换σ=$\left( \begin{array}{r} \begin{matrix} 1 & 2 & 3 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 5 & 6 \end{matrix} \\ \begin{matrix} 6 & 1 & 4 \end{matrix}\ \ \ \ \ \begin{matrix} 5 & 3 & 2 \end{matrix} \end{array} \right)$表示成对换合成的形式 ,

解: 我们先将置换表示成轮换合成的形式 , 然后将轮换表示成对换合成的形式

因为σ=$\left( \begin{array}{r} \begin{matrix} 1 & 2 & 3 \end{matrix}\ \ \ \ \ \begin{matrix} 4 & 5 & 6 \end{matrix} \\ \begin{matrix} 6 & 1 & 4 \end{matrix}\ \ \ \ \ \begin{matrix} 5 & 3 & 2 \end{matrix} \end{array} \right)$=(162) (345) ,

(162) = (16) (62) , (345) = (34) (45)

所以 , σ=(16) (62)(34) (45) ,

定理2.2若将置换表示成对换合成的形式 ,

则其表达式中出现的对换个数的奇偶性保持不变

证: 设σ属于S_n , n阶单位矩阵E=(e₁ , e₂ , ⋯ , e_n) ,

其中e_i(i=1 , 2 , ⋯ , n)是n维单位列向量 ,

我们规定σ(E)=$\left( e_{\sigma(1)},e_{\sigma(2)},\cdots e_{\sigma(n)} \right)$

于是若σ=σ_m⋯σ₂σ₁ , 那么det(σ(E))=(‒1)^mdet E =(‒1)^m ,

其中每个σ_i都是对换 ,

因此 , 若σ=σ_m⋯σ₂σ₁=$\sigma_{k}^{\ '}\cdots\sigma_{2}^{\ '}\sigma_{1}^{\ '}$ , 其中σ₁⋯σ_m , $\sigma_{1}^{\ '},\cdots,\sigma_{k}^{\ '}$都是对换 ,

那么有det(σ(E))=(‒1)^m=(‒1)^k , 所以m与k的奇偶性相同 ,

定义2.2如果一个置换可写成偶数个对换合成的形式 ,

那么称其为偶置换 , 否则称其为奇置换 ,

显然 , 两个偶置换的合成是偶置换 , 两个奇置换的合成是偶置换 ,

偶置换(奇置换)与奇置换(偶置换)的合成是奇置换 ,

实际上 , 如果令属于S_n的σ=σ_m⋯σ₂σ₁ , 其中每个σ_i都是对换 ,

那么可以将置换σ的符号函数定义为ε(σ)=(‒1)^m , 即ε: S_n→{1 , ‒1} , σ→ε(σ) ,

当然 , 这样定义的ε确实是映射 ,

而且偶置换的符号函数为1 , 奇置换的符号函数为‒1 ,

例2.8 设σ=(i₁i₂⋯i_t)是S_n中的一个轮换 , 则由例2.6可知ε(σ)=(‒1)^t‒1 ,

这就是说 , 长度为偶数的轮换是奇置换 , 长度为奇数的轮换是偶置换

定理2.3 若令A_n(n＞1)表示S_n中所有偶置换构成的集合 , 则$\left| A_{n} \right| = \frac{\left| S_{n} \right|}{2} = \frac{n!}{2}$

其中|A_n| , |S_n|分别表示集合A_n , S_n中所含元素的个数 ,

证: 因为A_n是S_n中偶置换构成的集合 , 所以S_n‒A_n是S_n中奇置换构成的集合 ,

若这两个集合所含元素个数相等 , 则结论得证,

令φ: A_n→(S_n‒ A_n) , σ→(12)σ , 则容易验证φ是双射 , 从而|A_n|=|S_n‒A_n| ,

命题2.1在S_n(n⩾3)中 ,

任意两个对换的合成可以表示成长度为3的轮换的合成 ,

任意偶置换可以写成长度为3的轮换的合成 ,

证: 设(ij)和(kl)是S_n(n⩾3)中两个对换 ,

若(ij)和(kl)不相交 , 则(ij)(kl)=(ij)(jk)(jk)(kl)= (ijk)(jkl) ,

若这两个对换相交 , 但不相同 ,

则不妨令它们的合成为(ij)(jk) , 则(ij)(jk)=(ijk) ,

若这两个对换相同 , 则不妨令它们的合成为(ij)(ij) ,

因为n⩾3 , 所以存在关系t≠ i , j , 使得(ij)(ij)=(ij)(it) (it)(ij)=(itj)(ijt)

即任意两个对换的合成可以表示成长度为3的轮换的合成 ,

因此任意偶置换可以写成长度为3的轮换的合成

例2.9 在S_n(n⩾3)中 ,

试将置换(1) , (12)(34) , (12)(23)表示成长度为3的轮换的合成 ,

解: (1)=(12) (12)= (132) (123) ,

(12) (34)=(123)(234) ,

(12) (23)=(123) ,

习题