離散數(shù)學(xué)ii(李占山)6.3置換群_第1頁(yè)
離散數(shù)學(xué)ii(李占山)6.3置換群_第2頁(yè)
離散數(shù)學(xué)ii(李占山)6.3置換群_第3頁(yè)
離散數(shù)學(xué)ii(李占山)6.3置換群_第4頁(yè)
離散數(shù)學(xué)ii(李占山)6.3置換群_第5頁(yè)
已閱讀5頁(yè),還剩34頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

§6.3置

6.3.1置換的定義

6.3.2置換的輪換表法

6.3.3置換的順向圈表示

6.3.4置換的奇偶性

1精選課件ppt6.3.1置換的定義

定義.設(shè)M是一個(gè)非空的有限集合,M的一個(gè)一對(duì)一變換稱為一個(gè)置換。設(shè)M={a1,a2,…,an},則M的置換σ可簡(jiǎn)記為

σ=,bi=σ(ai),i=1,2,…,n

結(jié)論:M的置換共有n!個(gè)。

M上的置換稱為n元置換。特別地,若σ(ai)=ai,i=1,2,…,n,則σ為n元恒等置換。

Sn:n!個(gè)置換作成的集合。2精選課件ppt置換的例設(shè)M={1,2,3},則有3!=6個(gè)3元置換,所有元素不動(dòng):σ1=一個(gè)元素不動(dòng):σ2=σ3=σ4=0個(gè)元素不動(dòng):σ5=σ6=故,S3={σ1,σ2,σ3,σ4,σ5,σ6}3精選課件ppt置換的乘法對(duì)M中任意元素a及M的任意兩個(gè)置換σ,τ,規(guī)定στ(a)=σ(τ(a))。例.設(shè)σ=,τ=則στ=,

τσ=≠

στ4精選課件ppt滿足結(jié)合律:(στ)ρ=σ(τρ),σ,τ,ρ∈

Sn。Sn中有單位元:n元恒等置換,設(shè)為σ0,有:σ0τ=τσ0,τ∈Sn每個(gè)n元置換在Sn

中都有逆元素:=置換的乘法的性質(zhì)5精選課件pptn次對(duì)稱群n元置換的全體作成的集合Sn對(duì)置換的乘法作成一個(gè)群,稱為n次對(duì)稱群。

n=1,M={a},S1={}—在置換的乘法作成1次對(duì)稱群,為Abel群。

n=2,M={a,b},S2={,}.在置換的乘法作成2次對(duì)稱群,為Abel群。

當(dāng)n≥3時(shí),Sn不是交換群。

6精選課件ppt輪換.設(shè)σ是M的置換,若可取到M的元素a1,…,ar使σ(a1)=a2,σ(a2)=a3,…,σ(ar-1)=ar,σ(ar)=a1,而σ不變M的其余的元素(自己變換到本身),則σ稱為一個(gè)輪換,記為(a1a2…ar)6.3.2置換的輪換表法

輪換的定義7精選課件ppt

例σ=

=(134)=(341)=(413)8精選課件pptM的兩個(gè)輪換

σ=(a1…ar)和τ=(b1…bs)說(shuō)是不相雜或不相交,如果

a1,…,ar和b1,…,bs

都不相同(即{a1,…

,ar}∩{b1,…,bs}=)不相雜輪換9精選課件ppt不相雜輪換結(jié)論:若σ和τ是M的兩個(gè)不相雜的輪換,則στ=τσ.證明:設(shè)σ=(a1…ar),τ=(b1…bs),σ和τ不相雜。命χ為M的任意元若χ∈{a1,…,ar},設(shè)χ=ai,則

στ(χ)=στ(ai)=σ(ai)=ai+1,τσ(χ)=τσ(ai)=τ(ai+1)=ai+1。

i=r時(shí),ai+1應(yīng)改為a1。

故,στ(χ)=τσ(χ)。10精選課件ppt不相雜輪換同理可證,若χ∈{b1,…,bs},,也有στ(χ)=τσ(χ)。設(shè)χ{a1,…,ar,b1,…,bs},于是,

στ(χ)=σ(χ)=χ,τσ(χ)=τ(χ)=χ。

綜上,στ(χ)=τσ(χ),故

στ=τσ。

11精選課件ppt定理6.3.2

任意置換σ恰有一法寫成不相雜的輪換乘積。即,任意置換σ可以寫成不相雜的輪換的乘積(可表性),如果不考慮乘積的順序,則寫法是唯一的(唯一性)。不相雜輪換12精選課件ppt證明:

(1)可表性。設(shè)σ是M上置換,任取a1∈M。若σ(a1)=a1,則有輪換(a1)。設(shè)σ(a1)=a2,σ(a2)=a3,…。由于M有限,故到某一個(gè)元素ar,σ(ar)必然不能再是新的元素,即σ(ar)∈{a1,…,ar}。由于σ是一對(duì)一的,已有σ(ai)=ai+1,i=1,2,…,r-1,所以σ(ar)只能是a1。于是得到一個(gè)輪換(a1…ar)。13精選課件ppt若M已經(jīng)沒(méi)有另外的元素,則σ就等于這個(gè)輪換,否則設(shè)b1不在a1,…,ar之內(nèi),則同樣作法又可得到一個(gè)輪換(b1…bs)。因?yàn)閍1,…,ar各自已有變到它的元素,所以b1,…,bs中不會(huì)有a1,…,ar出現(xiàn),即這兩個(gè)輪換不相雜。若M的元素已盡,則σ就等于這兩個(gè)輪換的乘積,否則如上又可得到一個(gè)輪換。如此類推,由于M有限,最后必得σ=(a1…ar)(b1…bs)…(c1…ct)(1)即σ表成了不相雜的輪換的乘積。

證明14精選課件ppt(2)唯一性.設(shè)σ又可表為不相雜的輪換的乘積如下:σ=(a’1…a’r’)(b’1…b’s’)…(c’1…c’t’)(2)考慮(1)式中任意輪換(a1…ar)。

不妨設(shè)

a1∈{a’1…a’r’},且a1=a’1。于是,a2=σ(a1)=σ(a’1)=a’2,,a3=σ(a2)=σ(a’2)=a’3,…,證明15精選課件ppt證明

可見(jiàn),(a1…ar)必和(a’1…a’r’)完全相同。這就是說(shuō),(1)中的任意輪換必出現(xiàn)在(2)中,同樣(2)中的任意輪換必出現(xiàn)在(1)中,因之,(1)和(2)一樣,最多排列的方法不同,但不相雜的輪換相乘適合交換律,所以排列的次序本來(lái)是可以任意顛倒的。16精選課件ppt例.

設(shè)M={1,2,3,4},M的24個(gè)置換可寫成:I;(12),(13),(14),(23),(24),(34);(123),(132),(124),(142),(134),(143),(234),(243);(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23)。17精選課件ppt輪換的長(zhǎng)度

其中所含的元素個(gè)數(shù)。(a1a2…ar)長(zhǎng)度為r。對(duì)換

長(zhǎng)度為2的輪換。結(jié)論.任意輪換可以寫成對(duì)換的乘積。(a1a2…ar)=(a1ar)(a1ar-1)…(a1a3)(a1a2)(3)證明:對(duì)r進(jìn)行歸納,當(dāng)r=2時(shí)命題顯然成立,假設(shè)r=t時(shí)結(jié)論為真,考慮σ=(a1a2…arat+1)的情況。令σ1=(a1at+1),σ2=(a1a2…at),下面證明σ=σ1σ2。對(duì)換18精選課件ppt任取lS,若l{a1,a2,…,at-1},不妨設(shè)l=am,則σ(l)=σ(am)=am+1,σ1σ2(l)=σ1(am+1)=am+1;若l=at,則σ(l)=at+1=σ1(a1)=σ1(σ2(at))=σ1σ2(at)=σ1σ2(l);若l=at+1,則σ(l)=σ(at+1)=a1=σ1(at+1)=σ1(σ2(at+1))=σ1σ2(l);若l{a1,a2,…,at+1},則σ(l)=l=σ1(l)=σ1(σ2(l))=σ1σ2(l),即σ=σ1σ2=(a1at+1)σ2。由歸納假設(shè),σ2=(a1a2…at),可表為(a1at)(a1at-1)…(a1a2),所以σ=(a1at+1)(a1at)(a1at-1)…(a1a2),歸納法完成。19精選課件ppt有興趣的同學(xué)可以采用直接證明的方法進(jìn)行證明。推論.對(duì)任意置換,有一法(未必只有一法)可將其寫成一些對(duì)換的乘積。(12)=(12)(13)(13)=(23)(13)(23)。20精選課件ppt先把置換表成不相雜輪換之乘積,然后用一組順向圈來(lái)表示每個(gè)順向圈的長(zhǎng)度,即圈上所含的元素個(gè)數(shù),就是該圈所表示的輪換的長(zhǎng)度。

一個(gè)n元置換對(duì)應(yīng)一組順向圈,這組圈的長(zhǎng)度之總和為n;反之,一組順向圈表示一置換,置換的元素個(gè)數(shù)就是組中各圖長(zhǎng)度之總和。

6.3.3置換的順向圈表示

21精選課件ppt132422精選課件ppt

n元置換σ對(duì)應(yīng)圖形表達(dá)式

(圖型)Gσ==α1z1+α2z2+…+αrzrzi表示長(zhǎng)度為i的圈,而zi的系數(shù)αi表示如此的zi的個(gè)數(shù);諸α為非負(fù)整數(shù),0≤α1≤n,αn=0或1;

α1+2α2+…+rαr=n6.3.3置換的順向圈表示23精選課件ppt設(shè)σ表為k個(gè)不相雜的輪換的乘積(包括長(zhǎng)度為1的輪換在內(nèi)),長(zhǎng)度分別為r1,r2,…,rk。若=n-k為奇數(shù)(偶數(shù)),則稱σ為奇置換(偶置換)。例如

σ==(134)是偶置換是奇置換6.3.4置換的奇偶性24精選課件ppt因每個(gè)長(zhǎng)度為r的輪換可寫成r-1個(gè)對(duì)換的乘積:(a1a2…ar)=(a1ar)(a1ar-1)…(a1a3)(a1a2)于是σ可寫成=n-k個(gè)對(duì)換的乘積。

結(jié)論:奇置換可表為奇數(shù)個(gè)對(duì)換之積,偶置換可表為偶數(shù)個(gè)對(duì)換之積。

25精選課件ppt定理6.3.3

每個(gè)置換都能分解為對(duì)換的乘積,但偶置換只能分解為偶數(shù)個(gè)對(duì)換的乘積,奇置換只能分解為奇數(shù)個(gè)對(duì)換的乘積。證明.只需證明“只能分解”。任取σ∈Sn,設(shè)σ等于k個(gè)輪換之積,這些輪換分別含r1,r2,…,rk個(gè)元素,于是σ可以寫成

個(gè)對(duì)換之積,定義置換σ的符號(hào)sgnσ如下:sgnσ=26精選課件ppt顯然,偶置換的符號(hào)為1,奇置換的符號(hào)為-1。首先證明sgnστ=sgnσsgnτ(4)設(shè)σ等于k個(gè)不相雜輪換之積,τ等于h個(gè)不相雜輪換之積,且σ寫成對(duì)換乘積時(shí)最后一個(gè)對(duì)換為(ab)。以(ab)乘τ而看其變化。27精選課件ppt(1)若a和b在τ的兩個(gè)不同的輪換之內(nèi):

τ=(aa1…as)(bb1…bi)

…則

(ab)τ=(aa1…asbb1…bi)

…若τ為h個(gè)不相雜輪換之積,則(ab)τ為(h-1)個(gè)不相雜輪換之積,故,sgn(ab)τ=(-1)n-(h-1)=-(-1)n-h=-sgnτ(2)若a和b在τ的同一個(gè)輪換之內(nèi):τ=(aa1…asbb1…bi)…則(ab)τ=(aa1…as)(bb1…bi)…故,

sgn(ab)τ=(-1)n-(h+1)=-(-1)n-h=-sgnτ28精選課件ppt補(bǔ)充證明(ab)=(ab)(aa1…as)(bb1…bi)…=29精選課件ppt總之,以一個(gè)對(duì)換乘τ則將sgnτ變號(hào),今σ等于(n-k)個(gè)對(duì)換之積,故以σ乘τ將sgnτ變號(hào)(n-k)次,即sgnστ=(-1)n-ksgnτ=sgnσsgnτ因此,σ和τ的奇偶性與其乘積στ的奇偶性之關(guān)系如下:

偶×偶=偶,

奇×奇=偶,奇×偶=奇,偶×奇=奇。

因?yàn)閷?duì)換是奇置換,所以只有奇數(shù)個(gè)對(duì)換之積是奇置換,偶數(shù)個(gè)對(duì)換之積是偶置換。

30精選課件ppt定理6.3.4

設(shè)M的元數(shù)為n,若n>1,則奇置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等,都等于

。證明:命τ1,τ2,…,τm(5)為M的所有偶置換,由于n>1,故可取到一個(gè)對(duì)換ρ,而作下列乘積:ρτ1,ρτ2,…,ρτm(6)顯然ρτi是奇置換,而且諸ρτi互不相同,即(6)中無(wú)重復(fù)元素。反證,若ρτi=ρτj,則以ρ-1左乘得τi=τj,矛盾,這說(shuō)明M的奇置換不少于偶置換。31精選課件ppt

反之,若σ為M的任意奇置換,則ρ-1σ為偶置換,故必等于某一個(gè)τi,ρ-1σ=τi,因而σ=ρτi,這說(shuō)明M的任意奇置換必在(6)中,(6)就是M的所有奇置換,M的奇置換不多于偶置換。于是奇置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等,各占置換總數(shù)n!的一半。

32精選課件ppt定義σ之奇偶性的整數(shù)=n-k稱為σ的定性數(shù)。定理6.3.5設(shè)n元置換σ有圖型Gσ=則σ之定性數(shù)等于?σ=證明.n=α1+2α2+…+rαr+…+nαnk=α1+α2+…+αr+…+αnn-k=α2+…+(r-1)αr+…+(n-1)αn

=置換的定性數(shù)33精選課件ppt例子圖1是一個(gè)22的方格圖形,它可以圍繞中心旋轉(zhuǎn),也可以圍繞對(duì)稱軸翻轉(zhuǎn),但要求經(jīng)過(guò)這樣的變動(dòng)以后的圖形要與原來(lái)的圖形重合(方格中的數(shù)字可以改變)。例如,當(dāng)它繞中心逆時(shí)針旋轉(zhuǎn)900以后,原來(lái)的數(shù)字1,2,3,4分別變?yōu)?,3,4和1,可以把這個(gè)變化看作是{1,2,3,4}上的圖1一個(gè)置換(4321)。下面給出所有可能的置換:σ1=(1)繞中心順時(shí)針轉(zhuǎn)00;σ2=(1234)繞中心順時(shí)針轉(zhuǎn)900;σ3=(13)(24)繞中心順時(shí)針轉(zhuǎn)1800;124334精選課件pptσ4=(1432)繞中心順時(shí)針轉(zhuǎn)2700;σ5=(12)(34)繞垂直軸翻轉(zhuǎn)1800;σ6=(14)(23)繞水平軸翻轉(zhuǎn)1800;σ7=(24)繞西北---東南軸翻轉(zhuǎn)1800;σ8=(13)繞西南---東北軸翻轉(zhuǎn)1800。表1給出它們的運(yùn)算表。令D4={σ1,σ2,…,σ8},易見(jiàn)D4關(guān)于置換的乘法是封閉的。σ1=(1)是單位元。且σ1-1

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論