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

陳健夫

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

?

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

陳健夫

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

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

對換； 置換； 置換群

1 引 言

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

2 預(yù)備知識

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

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

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

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

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

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

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

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

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

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

3 8個引理及其證明

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

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

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

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

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

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

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

證

右乘以任意對換

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

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

和

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

如果n≤4,只需逐個進行驗證,總共也只有幾種情況,這里不一一列出了.

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

和

的乘積,把π右乘以一個對換

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

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

后可以得到

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

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

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

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

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

可以表為至少n-1個對換的乘積.

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

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

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

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

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

添加一個元素b進去,得到

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

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

得到

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

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

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

可以表為至少m-1個對換的乘積,a1a2…an和b1b2…bm-1bm沒有共同元素,

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

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

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

對于k+1元置換

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

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

那么

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

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

下面往證

可以表為至少s+m-1個對換的乘積.

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

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

和

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

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

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

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

4 結(jié) 論

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

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

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

5 應(yīng) 用

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

排成

最少要對換多少次.這個問題實質(zhì)就是給出一個置換

問這個置換可以表成至少多少個對換的乘積.由定理3知道,只要找出其可以表成不相連循環(huán)置換的個數(shù)就可以了.因為

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

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

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

[3] 焦榮政.對換改變排列奇偶性的一個定量證明[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