陳健夫

(廣州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 廣州510006)

?

關(guān)于對(duì)換的幾個(gè)結(jié)論

陳健夫

(廣州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 廣州510006)

主要為了解決一個(gè)置換可以表示為至少多少個(gè)對(duì)換的乘積的問(wèn)題.通過(guò)使用初等方法包括數(shù)學(xué)歸納法和反證法證明了幾個(gè)引理,并用這幾個(gè)引理解決了問(wèn)題,同時(shí)給出一個(gè)應(yīng)用.

對(duì)換； 置換； 置換群

1 引 言

我們知道,一個(gè)置換總可以表成一些對(duì)換的乘積,并且這樣的表示可能不唯一.現(xiàn)在有一個(gè)問(wèn)題,一個(gè)確定的n元置換可以表示為至少多少個(gè)對(duì)換的乘積？由最小數(shù)原理知道,這個(gè)問(wèn)題是有意義的.本文沒(méi)有使用高級(jí)的數(shù)學(xué)工具,僅是綜合運(yùn)用基本的邏輯方法,包括數(shù)學(xué)歸納法和反證法證明了用于解決這個(gè)問(wèn)題的8個(gè)引理,并且這些引理本身也是很有益的,最后再給出這個(gè)結(jié)論在一個(gè)組合問(wèn)題上的應(yīng)用.

2 預(yù)備知識(shí)

定義1 一個(gè)有限集到自身的一一映射叫做一個(gè)置換.

定義2 有限集的一個(gè)把元素a1變到a2,a2變到a3，…，an-1變到an,an變到a1,并且其他元素不變的置換

叫做一個(gè)n-循環(huán)置換,并稱其階為n.

定義3 一個(gè)2-循環(huán)置換叫做一個(gè)對(duì)換.

定義4 如果兩個(gè)循環(huán)置換無(wú)公共元素,則稱這兩個(gè)循環(huán)置換不相連.

定義5 如果集合A有兩個(gè)置換σ1和σ2,規(guī)定這兩個(gè)置換的乘積為σ1σ2:x→σ2(σ1(x)),x∈A.換言之,乘積運(yùn)算是從左往右進(jìn)行的.

定理1 在不考慮順序的情況下,一個(gè)置換可以唯一地表成若干個(gè)不相連的循環(huán)置換的乘積.

定理2 置換的奇偶性不變.即一個(gè)置換表成對(duì)換的乘積時(shí),這些對(duì)換個(gè)數(shù)的奇偶性不變.

定義6 一個(gè)置換如果可以表成奇數(shù)個(gè)對(duì)換的乘積,則稱這個(gè)置換為奇置換.否則,稱為偶置換.

定理1,2的證明在一般的抽象代數(shù)學(xué)教材都會(huì)有.對(duì)于定理1,亦可以參看文獻(xiàn)[1]中的證明.對(duì)于定理2的證明,可以參看文獻(xiàn)[2]中的相關(guān)內(nèi)容,文獻(xiàn)[2]中證明該定理時(shí)使用了一個(gè)結(jié)論,即一個(gè)自然數(shù)排列施行一個(gè)對(duì)換,排列的奇偶性會(huì)改變,這個(gè)結(jié)論可以在文獻(xiàn)[3]中找到證明,但文獻(xiàn)[4]亦給出了比較新穎的證明方法,建議讀者參考.

3 8個(gè)引理及其證明

引理1 一個(gè)n-循環(huán)置換可以表成n-1個(gè)對(duì)換的乘積.

證 對(duì)于任意一個(gè)n-循環(huán)置換

可以發(fā)現(xiàn)

左邊的對(duì)換個(gè)數(shù)為n-1.

在下面的引理中,除非情況是自明的,否則提到一個(gè)n-循環(huán)置換或一個(gè)n元置換時(shí)均假定集合中只有n個(gè)元素.

引理2 一個(gè)n-循環(huán)置換

右乘以一個(gè)對(duì)換,可以得到一個(gè)置換,該置換可以表成兩個(gè)不相連循環(huán)置換的乘積,并且這兩個(gè)循環(huán)置換的階之和為n.

證

右乘以任意對(duì)換

為了書(shū)寫(xiě)方便,不妨認(rèn)為n≥5,并且ai,aj都不等于a1,a2,和an,這時(shí)可以得到置換

不難發(fā)現(xiàn)，這個(gè)置換可以表成

和

的乘積,這兩個(gè)置換是不相連的循環(huán)置換,并且它們階數(shù)的和等于n.如果ai,aj可以是a2,a1和an中的某一個(gè),事實(shí)上,我們只需要重新對(duì)集合的元素命名,使得原來(lái)以i,j為下標(biāo)的元素改變其下標(biāo)變成不等于1,2和n即可.因?yàn)楸举|(zhì)上,集合的元素本身與用什么符號(hào)表示并沒(méi)有關(guān)系.

如果n≤4,只需逐個(gè)進(jìn)行驗(yàn)證,總共也只有幾種情況,這里不一一列出了.

引理3 如果一個(gè)置換π表成兩個(gè)不相連的循環(huán)置換

和

的乘積,把π右乘以一個(gè)對(duì)換

ai是第一個(gè)循環(huán)置換中的元素,bj是第二個(gè)循環(huán)置換中的元素,那么得到一個(gè)n+m-循環(huán)置換.

證 結(jié)論其實(shí)相當(dāng)顯然.為了書(shū)寫(xiě)方便,不妨認(rèn)為i≠1,2,n,j≠1,2,m,并且m,n≥5,那么π右乘以

后可以得到

這就是一個(gè)n+m-循環(huán)置換.對(duì)于i=1,2或n, j=1,2或m,道理跟引理2的證明是一樣的,可以對(duì)集合的元素重新命名,使之變?yōu)榉奖銜?shū)寫(xiě)的情況.對(duì)于m,n≤4的情況,只需逐個(gè)驗(yàn)證,證明本質(zhì)上是一樣的,這里不一一列出了.

引理4 如果一個(gè)置換π可以表為至少k個(gè)對(duì)換的乘積,那么對(duì)該置換還原最后一次對(duì)換,還原成π′,那么π′可以表為至少k-1個(gè)對(duì)換的乘積.

證 反證法.假設(shè)不然,π′可以表為至少k-3或k-5…或1或0個(gè)對(duì)換的乘積,由于對(duì)于k-5或以下的情況,可以對(duì)2個(gè)相同的元素一直施加對(duì)換,使得π′表成k-3個(gè)對(duì)換的乘積,馬上推出,π′可以表為k-3個(gè)對(duì)換的乘積(由定理2知道,一個(gè)置換可以表成的對(duì)換個(gè)數(shù)的奇偶性不變,所以一個(gè)置換可以表成的對(duì)換數(shù)相差一個(gè)偶數(shù)).下面幾個(gè)引理的證明都會(huì)用到這樣的反設(shè),下面不再做說(shuō)明.

那么,這時(shí)對(duì)π′重做剛才還原的對(duì)換,重新得到π,推出π可以表為k-2個(gè)對(duì)換的乘積,這與π可以表為至少k個(gè)對(duì)換的乘積矛盾.

引理5 一個(gè)n-循環(huán)置換

可以表為至少n-1個(gè)對(duì)換的乘積.

證 引理1已經(jīng)說(shuō)明了一個(gè)n-循環(huán)置換可以表為n-1個(gè)對(duì)換的乘積.下面證明這是最少需要對(duì)換的次數(shù),也就是說(shuō),不能通過(guò)施加少于n-1個(gè)對(duì)換得到一個(gè)n-循環(huán)置換.

反證法.假設(shè)不然,n-循環(huán)置換

可以表為至少n-3個(gè)對(duì)換的乘積.此時(shí),對(duì)π還原最后一次的對(duì)換,得到π1,由引理2知道,π1可以表為兩個(gè)不相連循環(huán)置換的乘積,并且由引理4推出,π1可以表為至少n-4個(gè)對(duì)換的乘積.再對(duì)π1進(jìn)行一次還原,得到π2,這次還原的對(duì)象不可能是兩個(gè)不相連循環(huán)置換中各自取出的元素,否則根據(jù)引理3,會(huì)得到一個(gè)n-循環(huán)置換,而這個(gè)n-循環(huán)置換可以表為至少n-5個(gè)對(duì)換的乘積,這與我們的假設(shè)矛盾.所以,第二次還原的對(duì)象必須是其中一個(gè)循環(huán)置換的2個(gè)元素 ,那么π2就“分裂”成三個(gè)不相連循環(huán)置換的乘積.這樣的操作一直進(jìn)行下去,最后會(huì)經(jīng)過(guò)n-3次還原得到恒等變換

但是根據(jù)上面的過(guò)程,我們實(shí)際上只“分裂”出n-2個(gè)循環(huán)置換,這意味著n元恒等變換表為n-2個(gè)不相連循環(huán)置換的乘積,但事實(shí)上n元恒等變換唯一地表為n個(gè)1-循環(huán)的乘積,于是得出矛盾.

引理6 一個(gè)n-循環(huán)置換

添加一個(gè)元素b進(jìn)去,得到

是一個(gè)新的n+1元集合的置換,那么π可以表為至少n-1個(gè)對(duì)換的乘積.

證 反證法.假設(shè)不然,那么π可以表為n-3個(gè)對(duì)換的乘積.這時(shí)對(duì)π右乘以一個(gè)對(duì)換

得到

這是一個(gè)n+1-循環(huán)置換,可以由n-2個(gè)對(duì)換相乘得到,但由引理5知道,π′可以表為至少n個(gè)對(duì)換的乘積,矛盾.

引理7 設(shè)任意n元置換

可以表為至少s個(gè)對(duì)換的乘積,對(duì)于任意一個(gè)m-循環(huán)置換

可以表為至少m-1個(gè)對(duì)換的乘積,a1a2…an和b1b2…bm-1bm沒(méi)有共同元素,

是新的n+m元集合中的置換,那么π=可以表為至少s+m-1個(gè)對(duì)換的乘積.

證 第二數(shù)學(xué)歸納法.①當(dāng)n=1時(shí),由引理6知道命題成立.

②設(shè)當(dāng)n≤k時(shí)命題成立,考察n=k+1的情況.

對(duì)于k+1元置換

設(shè)其可以表為至少s個(gè)對(duì)換的乘積,由定理1知道,π可以表為若干個(gè)不相連循環(huán)置換的乘積,不妨從中抽出一個(gè)q-循環(huán)置換

其他循環(huán)置換并起來(lái)得到

那么

由歸納假設(shè)可以知道

可以表為至少s-q+1個(gè)對(duì)換的乘積(要注意,這是在僅有d1d2…dk+1-q這些元素的集合的意義下討論的).

下面往證

可以表為至少s+m-1個(gè)對(duì)換的乘積.

反證法.假設(shè)不然,π′可以表為s+m-3個(gè)對(duì)換的乘積,那么現(xiàn)在對(duì)π′右乘以一個(gè)置換

得到π*,由引理3知,π*可以表為q+m-循環(huán)置換

和

的乘積,這兩個(gè)置換沒(méi)有公共元素,并且這可以由s+m-2個(gè)對(duì)換相乘得到.但由歸納假設(shè)立得π*可以表為至少q+m-1+s-q+1=s+m個(gè)對(duì)換的乘積,推出矛盾,反證結(jié)束.于是證得對(duì)于n=k+1的情況命題成立.

引理8 如果置換π′表為n個(gè)不相連的循環(huán)置換π1π2…πn的乘積,而π1π2…πn分別可以表為至少a1a2…an個(gè)對(duì)換的乘積,那么π′可以表為至少a1+a2+…+an個(gè)對(duì)換的乘積.

證 數(shù)學(xué)歸納法：①當(dāng)n=1時(shí),由引理4知道命題成立.

②設(shè)當(dāng)n=k時(shí)命題成立,考察n=k+1的情況.因?yàn)橛杉僭O(shè)知道π=π1π2…πk可以表為至少a1+a2+…+ak個(gè)對(duì)換的乘積,由引理7立即可以得到π′=π1π2…πkπk+1可以表為至少a1+a2+…+ak+ak+1個(gè)對(duì)換的乘積.

4 結(jié) 論

現(xiàn)在重新回到我們一開(kāi)始想要解決的問(wèn)題：一個(gè)n元置換可以表示為至少多少個(gè)對(duì)換的乘積?由引理8就可以容易得到答案,因?yàn)橐粋€(gè)n元置換可以唯一地表成若干個(gè)不相連的循環(huán)置換的乘積,如果這些不相連的循環(huán)置換有k個(gè),那么這個(gè)n元置換可以表成的對(duì)換乘積的最小個(gè)數(shù)等于這些循環(huán)置換各自可以表成對(duì)換乘積的最小個(gè)數(shù)之和,由引理5馬上就可以知道,這個(gè)數(shù)就是n-k,于是我們有定理3.

定理3 如果一個(gè)n元置換唯一地表成k個(gè)不相連的循環(huán)置換的乘積,那么這個(gè)置換可以表成至少n-k個(gè)對(duì)換的乘積.

所以我們最初的問(wèn)題便解決了,并且引理1就給出了對(duì)換的辦法.下面給出該結(jié)論的一些應(yīng)用.

5 應(yīng) 用

有這樣一類智力題,給出一列亂序的數(shù)碼,要把它排成順序數(shù)碼,每次只能對(duì)其中兩個(gè)數(shù)碼進(jìn)行對(duì)換,問(wèn)最少要對(duì)換多少次,應(yīng)該怎樣對(duì)換.比如把序列

排成

最少要對(duì)換多少次.這個(gè)問(wèn)題實(shí)質(zhì)就是給出一個(gè)置換

問(wèn)這個(gè)置換可以表成至少多少個(gè)對(duì)換的乘積.由定理3知道,只要找出其可以表成不相連循環(huán)置換的個(gè)數(shù)就可以了.因?yàn)?/p>

不相連的循環(huán)置換有2個(gè),所以答案就是可以表示成至少6-2=4個(gè)對(duì)換的乘積,并且按照引理1的做法,即先把4和1對(duì)換,再把4和6對(duì)換,再把4和3對(duì)換,最后再把5和2對(duì)換.雖然這是只有6個(gè)數(shù)的序列,恐怕單純通過(guò)窮舉就不容易解出了.定理3就保證能夠很容易知道最少需要對(duì)換多少次,并且用引理1就可以給出對(duì)換的方法.如果對(duì)于特別長(zhǎng)的序列需要排序,設(shè)計(jì)算法使用計(jì)算機(jī)去找出這些不相連的循環(huán)置換就可以了.

[1] 陳健夫.循環(huán)置換分解定理的一個(gè)證明及其應(yīng)用[J].大學(xué)數(shù)學(xué),2015,31(4)：95-98.

[2] 楊子胥.近世代數(shù)[M].北京：高等教育出版社,2000.

[3] 焦榮政.對(duì)換改變排列奇偶性的一個(gè)定量證明[J].大學(xué)數(shù)學(xué),2009,25(6)：174-176.

[4] 張禾瑞,郝炳新.高等代數(shù)[M].北京：高等教育出版社,2007.

Some Conclusions about Transposition

CHENJian-Fu

(School of Mathematics and Information Science, GuangZhou University, Guangzhou 510006, China)

This article solves a problem that how many transpositions are needed to denote a permutation at least. I give and prove several lemmas used to solve this problem by fundamental methods including mathematical induction and reduction to absurdity. At the meantime, I give an application related to combinatorics.

transposition; permutation; permutation group

2016-03-18； [修改日期]2016-06-01

陳健夫(1995-),男,本科生,數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè).Email:jmchenjianfu@126.com

O152

C

1672-1454(2016)05-0121-06