近世代数理论基础10：变换群·置换群

变换群·置换群

变换

设X是非空集合,从集合X到X的所有双射所成的集合记为 $S(X)$ , $S(X)$ 中的元为X上的变换,若X为有限集合,则称为置换

变换群

易证 $S(X)$ 在映射合成的意义下构成群,单位元为恒等映射 $I_X$ ,逆元为相应的逆映射, $S(X)$ 的任一子群称为变换群,若X为有限集合,则称为置换群

若 $|X|=n$ ,则记 $S(X)=S_n$ ,称为n阶对称群

置换

若X为有限集,令 $X=\{1,2,3,\cdots,n\}$ , $\forall \sigma\in S_n$ ,若 $\sigma(1)=i_1,\sigma(2)=i_2,\cdots,\sigma(n)=i_n$ ,其中 $i_1,i_2,\cdots,i_n$ 是 $1,2,\cdots,n$ 的一个排列,则可把置换 $\sigma$ 记作

$\sigma=\begin{pmatrix}1&2&\cdots&k&\cdots&n\\ \sigma(1)&\sigma(2)&\cdots&\sigma(k)&\cdots&\sigma(n)\end{pmatrix}$

$=\begin{pmatrix}1&2&\cdots&k&\cdots&n\\ i_1&i_2&\cdots&i_k&\cdots&i_n\end{pmatrix}$

故 $S_n$ 中有 $n!$ 个元

循环置换

设置换 $\sigma\in S_n$ 满足：

1. $\sigma(i_1)=i_2,\sigma(i_2)=i_3,\cdots,\sigma(i_{r-1})=i_r,\sigma(i_r)=i_1$

2. $\sigma$ 保持其他元不变,即 $\forall i\notin \{i_1,i_2,\cdots,i_r\}$ ,有 $\sigma(i)=i$

则称 $\sigma$ 为循环置换,记作 $(i_1i_2\cdots i_r)$ ,其中r称为循环置换的长度

例：在 $S_4$ 中,令 $\sigma=\begin{pmatrix}1&2&3&4\\ 2&4&1&3\end{pmatrix}$ , $\sigma(1)=2$ , $\sigma(2)=4$ , $\sigma(4)=3$ , $\sigma(3)=1$ ,故 $\sigma=(1243)$ , $\sigma^{-1}(1)=3$ , $\sigma^{-1}(2)=1$ , $\sigma^{-1}(3)=4$ , $\sigma^{-1}(4)=2$ ,故 $\sigma^{-1}=\begin{pmatrix}1&2&3&4\\ 3&1&4&2\end{pmatrix}=(1342)$

注：循环置换的表示不是唯一的

设 $\sigma=(i_1i_2\cdots i_r)\in S_n$ 为循环置换,则 $(i_1i_2\cdots i_r)=(i_2i_3\cdots i_ri_1)=\cdots=(i_ri_1\cdots i_{r-1})$

恒等置换

在 $S_n$ 中, $(1)=(2)=\cdots=(n)$ 是恒等置换,即群的单位元

循环置换的关系

设 $\sigma=(i_1i_2\cdots i_r),\tau=(j_1j_2\cdots j_s)$ 是两个循环置换,若集合 $\{i_1,i_2,\cdots,i_r\}$ 和 $\{j_1,j_2,\cdots,j_s\}$ 的交集为空集,则称置换 $\sigma$ 和 $\tau$ 相互独立或不相交

引理：相互独立的循环置换可交换

证明：

$设X=\{1,2,\cdots,n\}$

$\sigma=(i_1i_2\cdots i_r),\tau=(j_1j_2\cdots j_s)\in S_n不相交$

$即A=\{i_1,i_2,\cdots,i_r\},B=\{j_1,j_2,\cdots,j_s\}的交集为空集$

$令C=X\backslash(A\cup B)$

$(1)a\in A时,a\notin B$

$\therefore \tau(a)=a$

$\because \sigma(a)\in A$

$\therefore \sigma(a)\notin B$

$\therefore \tau(\sigma(a))=\sigma(a)=\sigma(\tau(a))$

$即\tau\circ\sigma(a)=\sigma\circ\tau(a)$

$(2)a\in B时$

$同理可证\sigma(\tau(a))=\tau(a)=\tau(\sigma(a))$

$即\sigma\circ\tau(a)=\tau\circ\sigma(a)$

$(3)a\in C时,a\notin A,a\notin B$

$\therefore \sigma(a)=a,\tau(a)=a$

$\therefore \sigma(\tau(a))=\sigma(a)=a=\tau(a)=\tau(\sigma(a))$

$即\sigma\circ\tau(a)=\tau\circ\sigma(a)$

$综上所述,结论成立\qquad\mathcal{Q.E.D}$

定理：任意置换 $\sigma\in S_n$ 可唯一地表示成相互独立的循环置换的乘积

证明：

$先证\sigma可表成循环置换的乘积$

$若\sigma(i_1)=i_1$

$则\sigma_1=(1)即为一个循环置换$

$不妨设\sigma(i_1)=i_2,\sigma(i_2)=i_3,\cdots,$

$这样下去$

$\because X中只有n个元$

$\therefore 到某个元i_r时,\sigma(i_r)只能是i_1,i_2,\cdots,i_r中某一个$

$但\sigma为一一映射$

$\therefore \sigma(i_r)=i_1$

$得到一个循环置换\sigma_1=(i_1i_2\cdots i_r)$

$若r=n,则\sigma=\sigma_1$

$若r\lt n,则X中还有一个元j_1不在集合\{i_1,i_2,\cdots,i_r\}中$

$同理可得循环置换\sigma_2$

$\sigma_2=(j_1j_2\cdots j_p)$

$显然\sigma_1,\sigma_2相互独立$

$若r+p=n,则\sigma=\sigma_1\sigma_2$

$若r+p\lt n$

$可再得一循环置换$

$这样下去$

$\because X中只有n个元$

$\therefore 最后\sigma_s=(l_1,l_2\cdots l_q)$

$\sigma=\sigma_1\sigma_2\cdots\sigma_s$

$其中\sigma_1,\sigma_2,\cdots,\sigma_s是两两独立的循环置换$

$再证表示法的唯一性$

$设\sigma=\tau_1\tau_2\cdots\tau_t=\sigma_1\sigma_2\cdots\sigma_s$

$则i_1必在某一循环置换\tau_l中$

$不妨设在\tau_1中$

$由循环置换的定义$

$\tau_1必定含i_1,i_2,\cdots,i_r$

$且只含i_1,i_2,\cdots,i_r$

$故\tau_1=\sigma_1$

$同理可得$

$\tau_2,\cdots,\tau_t必是\sigma_2,\cdots,\sigma_s中某一个$

$\because \tau_1,\tau_2,\cdots,\tau_t中已包含所有元1,2,\cdots,n$

$\therefore s=t$

$唯一性得证\qquad\mathcal{Q.E.D}$

例：设 $\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8\\ 5&8&1&6&3&4&7&2\end{pmatrix}$ ,则 $\sigma=(153)(28)(46)(7)=(153)(28)(46)$

例：将 $\sigma=(456)(567)(671)(123)(234)(345)$ 写成互不相交的循环置换的乘积

解：

$记\sigma_1=(345),\sigma_2=(234),\sigma_3=(123)$

$\sigma_4=(671),\sigma_5=(567),\sigma_6=(456)$

$则\sigma可如下从右到左计算$

$1\overset{\sigma_1}\to 1\overset{\sigma_2}\to 1\overset{\sigma_3}\to 2\overset{\sigma_4}\to 2\overset{\sigma_5}\to 2\overset{\sigma_6}\to 2$

$2\overset{\sigma_1}\to 2\overset{\sigma_2}\to 3\overset{\sigma_3}\to 1\overset{\sigma_4}\to 6\overset{\sigma_5}\to 7\overset{\sigma_6}\to 7$

$7\overset{\sigma_1}\to 7\overset{\sigma_2}\to 7\overset{\sigma_3}\to 7\overset{\sigma_4}\to 1\overset{\sigma_5}\to 1\overset{\sigma_6}\to 1$

$3\overset{\sigma_1}\to 4\overset{\sigma_2}\to 2\overset{\sigma_3}\to 3\overset{\sigma_4}\to 3\overset{\sigma_5}\to 3\overset{\sigma_6}\to 3$

$4\overset{\sigma_1}\to 5\overset{\sigma_2}\to 5\overset{\sigma_3}\to 5\overset{\sigma_4}\to 5\overset{\sigma_5}\to 6\overset{\sigma_6}\to 4$

$5\overset{\sigma_1}\to 3\overset{\sigma_2}\to 4\overset{\sigma_3}\to 4\overset{\sigma_4}\to 4\overset{\sigma_5}\to 4\overset{\sigma_6}\to 5$

$6\overset{\sigma_1}\to 6\overset{\sigma_2}\to 6\overset{\sigma_3}\to 6\overset{\sigma_4}\to 7\overset{\sigma_5}\to 5\overset{\sigma_6}\to 6$

$故\sigma=(127)(3)(4)(5)(6)=(127)$

对换

定义：长为2的循环置换称为对换

定理：任一置换可表成若干个对换的乘积

证明：

$任一置换都可表成循环置换的乘积$

$下证结论对循环置换成立$

$设\sigma=(i_1i_2\cdots i_r)$

$当r=1时,\sigma=(i_1)=(1)=(12)(12)$

$当r\gt 1时$

$由置换乘法的定义$

$\sigma=(i_1i_2\cdots i_r)=(i_1i_r)(i_1i_{r-1})\cdots(i_1i_3)(i_1i_2)$

$故任一置换都可表成对换的乘积\qquad\mathcal{Q.E.D}$

偶(奇)置换

若置换 $\sigma$ 可表成偶数(奇数)个对换的乘积,则称 $\sigma$ 是偶(奇)置换

注： $\sigma$ 是偶(奇)置换 $\Leftrightarrow i_1i_2\cdots i_n$ 是偶(奇)排列

设 $\sigma=\begin{pmatrix}1&2&3&\cdots&s&\cdots&t&\cdots&n\\ i_1&i_2&i_3&\cdots&i_s&\cdots&i_t&\cdots&i_n\end{pmatrix}$ , $\tau=(i_si_t)$ 为对换

由映射的乘法

$(i_si_t)\sigma=(i_si_t)\begin{pmatrix}1&2&3&\cdots&s&\cdots&t&\cdots&n\\ i_1&i_2&i_3&\cdots&i_s&\cdots&i_t&\cdots&i_n\end{pmatrix}$

$=\begin{pmatrix}1&2&3&\cdots&s&\cdots&t&\cdots&n\\ i_1&i_2&i_3&\cdots&i_t&\cdots&i_s&\cdots&i_n\end{pmatrix}$

n次交错群

两个偶置换的乘积是偶置换,偶置换的逆变换仍是偶置换,故 $S_n$ 中所有偶置换作成 $S_n$ 的子群,称为n次交错群,记作 $A_n$

注： $|A_n|={n!\over 2}$

例：

1.三次交错群 $A_3=\{(1),(123),(132)\}$ 包含3个元

2.设 $\rho,\sigma\in S_n$ , $\sigma=(i_1i_2\cdots i_r)$ ,则 $\rho\sigma\rho^{-1}=(\rho(i_1)\rho(i_2)\cdots\rho(i_r))$

证：

$等式右边为一个置换$

$把\rho(i_1)变为\rho(i_2),把\rho(i_2)变为\rho(i_3),\cdots,把\rho(i_r)变为\rho(i_1)$

$并保持其他元不变$

$下证左端的置换也满足上述性质$

$(\rho\sigma\rho^{-1})(\rho(i_1))=(\rho\sigma)(\rho^{-1}\rho(i_1))$

$=(\rho\sigma)(i_1)=\rho(i_2)$

$(\rho\sigma\rho^{-1})(\rho(i_2))=(\rho\sigma)(\rho^{-1}\rho(i_2))$

$=(\rho\sigma)(i_2)=\rho(i_3)$

$\cdots$

$(\rho\sigma\rho^{-1})(\rho(i_r))=(\rho\sigma)(\rho^{-1}\rho(i_r))$

$=(\rho\sigma)(i_r)=\rho(i_1)$

$易证,当i\notin \{\rho(i_1),\rho(i_2),\cdots,\rho(i_r)\}时,$

$i=\rho^{-1}(\rho(i))\notin \{i_1,i_2,\cdots,i_r\}$

$\therefore \sigma(i)=i$

$\therefore \rho\sigma\rho^{-1}(i)=i\qquad\mathcal{Q.E.D}$

同态映射

定义：设 $(G,\cdot)$ , $(\overline{G},\overline{\cdot})$ 是两个群,若 $\exists f:G\to \overline{G}$ ,满足 $f(a\cdot b)=f(a)\overline{\cdot}f(b),\forall a,b\in G$ ,则称f为G到 $\overline{G}$ 的一个同态映射

注：

1.设f为群G到 $\overline{G}$ 的同态映射,则G在 $\overline{G}$ 中的像为同态像

2.若f为满射,则称G与 $\overline{G}$ 同态,记作 $G\sim\overline{G}$

3.若f为一一映射,则称f是从G到 $\overline{G}$ 的同构映射,称 $G$ 与 $\overline{G}$ 同构,记作 $G\cong \overline{G}$

4.群的结构由它的乘法完全确定,故同构的群本质上没有区别

5.同态映射是保持乘法的映射,即若 $f:G\to \overline{G}$ 是同态映射指 $\forall a,b\in G$ ,有 $f(ab)=f(a)f(b)$

例：

1.设 $G=(Z,+)$ , $\overline{G}=(Z/mZ,+)$ ,定义映射f： $f:Z\to Z/mZ\\\quad n\mapsto [n]$

$f(n_1+n_2)=[n_1+n_2]$

$=[n_1]+[n_2]=f(n_1)+f(n_2)$

显然f为满射,故f是从 $G$ 到 $\overline{G}$ 上的满同态,且不是单同态

2.设 $G=GL_n(R)$ ,乘法定义为矩阵的乘法, $\overline{G}=R^*$ 为全体非零实数的集合,乘法定义为实数的乘法,定义映射f： $f:GL_n(R)\to R\\\quad A\mapsto det(A)$

易证,f是满同态,且不是单同态

Cayley定理

定理：任一群与一个变换群同构

证明：

$设G是一个群$

$取集合X=G$

$\forall a\in G定义映射\tau_a:X\to X$

$\tau_a(x)=ax,\forall x\in X$

$由群的性质$

$\tau_a是集合X上的一一变换$

$即\tau_a\in S(X)$

$定义映射f如下：$

$f:G\to S(X)\\\quad a\mapsto \tau_a$

$若f(a)=f(b),即\tau_a=\tau_b$

$取e为G的单位元$

$则a=ae=\tau_a(e)$

$=\tau_b(e)=be=b$

$\therefore f为单射$

$\forall a,b\in G,\forall x\in X$

$\because (\tau_a\tau_b)(x)=\tau_a(\tau_b(x))$

$=\tau_a(bx)=a(bx)=(ab)x=\tau_{ab}(x)$

$\therefore \tau_a\tau_b=\tau_{ab}$

$即f(ab)=f(a)f(b)$

$\therefore f为一个单同态$

$\therefore G\cong f(G)\subseteq S(X)$

$易证f(G)作为群G的同态像也是一个群$

$\therefore f(G)为变换群\qquad\mathcal{Q.E.D}$

注：定理表明,一个群无论形式如何,总可看成一个变换群

推论：任一有限群与一置换群同构

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 205,132评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,802评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,566评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,858评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,867评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,695评论 1赞 282
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,064评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,705评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,915评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,677评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,796评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,432评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,041评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,992评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,223评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,185评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,535评论 2赞 343