半群K(n，r)的生成集

瞿云云，趙　平，游泰杰

(貴州師范大學數(shù)學科學學院，貴州 貴陽 550001)

半群K(n，r)的生成集

瞿云云，趙平，游泰杰

(貴州師范大學數(shù)學科學學院，貴州 貴陽 550001)

[摘要]設Tn是有限集xn上的全變換半群，對任意的1≤r≤n，令K(n，r)={α∈Tn|rank(α)≤r}，則其為Tn的一個子半群.研究了半群K(n，r)中秩為r的元素組成的集合的任意子集g構(gòu)成K(n，r)生成集的充分必要條件.

[關(guān)鍵詞]變換半群；生成集；圖

0引言

變換半群一直被人們研究并關(guān)注著.[1-10]類似于對稱群Sx，我們將一個有限或無限集合x上的全變換半群記為Tx，本文僅討論有限集x=xn={1，…，n} 的情形.引入以下記號：用Tn與Sn分別表示Txn與Sxn；TnSn是由xn上的奇異變換所構(gòu)成的半群，稱為奇異變換半群，記為Sinɡn；設α∈Tn，用im(α)與rank(α)分別表示變換α的像集及像集的元素個數(shù)；α的核定義為

ker(α)={(x，y)∈xn×xn|xα=yα}.

Tn中的格林關(guān)系刻畫如下：對于任意的α，β∈Tn，

(α，β)∈R?ker(α)=ker(β)；

(α，β)∈L?im(α)=im(β)；

(α，β)∈D?rank(α)=rank(β).

半群Tn有n個D-類:D1，D2，…，Dn，其中Dr={α∈Tn|rank(α)=r}.對任意的1≤r≤n，令

K(n，r)={α∈Tn|rank(α)≤r}，

則K(n，r)=D1∪…∪Dr，K(n，r)顯然是Tn的雙邊理想，且是Tn的正則子半群.

設S是一個半群且g是S的一個非空子集.S包含g的最小子半群稱為由g生成的子半群，記為〈g〉.設g是半群S的一個子集，如果〈g〉=S，則稱g是S的一個生成集.在半群研究中，一個自然的問題就是怎樣描述半群的(最小)生成集.Howie[11]證明了Singn是由秩為n-1的冪等元所生成的，并且與Gomes[6]共同證明了當n≥3時Singn的一個最小生成集包含n(n-1)/2個秩為n-1的元素；AyIk等[7]給出了秩為n-1的元素組成的集合構(gòu)成Singn的一個(最小)生成集的充分必要條件；Evseev等[8]證明了K(n，r)(1≤r≤n-1)是由秩為r的冪等元所生成的.本文給出了K(n，r)中秩為r的元組成的集合構(gòu)成K(n，r)的一個(最小)生成集的充分必要條件.

給定Tn的一個子集u，用E(u)表示子集u所有冪等元組成的集合.本文未定義的符號及術(shù)語請參見文獻[12-13].

1預備知識

設在圖Γ中，所有邊的集合為E(Γ)，所有頂點的集合為v(Γ).如果對任意的兩個頂點u，v∈v(Γ)，u≠v，滿足邊(u，v)∈E(Γ)或者邊(v，u)∈E(Γ)，則稱圖Γ是完全的；在圖Γ中，如果對于Γ中的頂點{v0，v1，…，vn}滿足(vi-1，vi)∈E(Γ)(1≤i≤n)，則稱之為v0到vn的一條路徑；對于圖Γ中的兩個頂點u，v∈v(Γ)，如果存在從u到v的一條路徑，則稱在Γ圖中u是連接到v的；如果對于任何的兩個頂點u，v∈v(Γ)，在圖Γ中u都是連接到v的，則稱圖Γ是強連接的.

S(n，1)=S(n，n)=1，S(n，r)=S(n-1，r-1)+rS(n-1，r).

設A∈Λr且α∈Dr.如果對任意的x，y∈A，xα≠yα，則稱A是α的一個橫截集，記為A#α.

定義ΓG(r)如下:

(1)ΓG(r)的頂點集是g，記為v=v(ΓG(r))；

引理1設α，β∈Dr.則αβ∈Dr，當且僅當im(α)#β.

引理2[12]對于半群S中的兩個元素A與b，ab∈RA∩Lb，當且僅當E(Rb∩LA)≠?.

2主要結(jié)果

定理1設g是Dr的一個子集.則g是K(n，r)的一個生成集，當且僅當對于每個ε∈E(Dr)，存在α，β∈g，使得：

(ⅰ)αRεLβ；

(ⅱ)在圖ΓG(r)中，α是連接到β的.

證明必要性.設g是K(n，r)的一個生成集，則對于每個ε∈E(Dr)，存在α1，α2，…，αs∈g使得

ε=α1α2…αs.

由α1，α2，…，αs，ε∈Dr，α1RεLαs且αkαk+1∈Dr(1≤k≤s-1).由引理1可知im(αk)#αk+1，故在圖ΓG(r)中存在一條路徑從α1連接到αs，令α1=α，αs=β，則必要性得證.

充分性.因為K(n，r)中的每一個元素都可寫成Dr冪等元的乘積，故只需證明E(Dr)?〈g〉.設ε∈E(Dr)，由結(jié)論(ⅰ)可知存在α，β∈g使得αRεLβ；從結(jié)論(ⅱ)可知存在一條路徑連接α到β，為

α=α1→α2→…→αs-1→αs=β，

則im(αk)#αk+1(1≤k≤s-1)，從而im(α1…αk+1)=im(αk+1)(1≤k≤s-1)，im(α1…αs-1)#αs.由引理1可知α1α2…αs∈Dr且α1Rα1α2…αsLαs，由于α=α1，β=αs，αRεLβ，因此α1α2…αsHε.因hε為具有單位元ε的有限群，存在一個正整數(shù)m使得ε=(α1α2…αs)m∈〈g〉，由此可得E(Dr)?〈g〉，充分性得證.

因為rank(K(n，r))=S(n，r)[14]，K(n，r)具有S(n，r)個元素的生成集是K(n，r)的最小生成集，因此有如下結(jié)論.

推論1設g是Dr的具有S(n，r)個元素的子集.則g是K(n，r)的一個最小生成集，當且僅當對于每個ε∈E(Dr)，存在α，β∈g，使得：

(1)αRεLβ；

(2)在圖ΓG(r)中，α是連接到β的.

對A，b∈Λr，因Tn是正則的，存在ε∈E(Dr)使得ε∈LA，設α∈Rε∩Lb，則εα=α.由K(n，r)=〈g〉，存在α1，α2，…，αp，β1，β2，…，βq∈g，使得α=α1α2…αp且ε=β1β2…βq.又g?Dr，則αLαp，εLβq，從而A=im(ε)=im(βq)，b=im(α)=im(αp).因為αi，βj∈g?Dr(1≤i≤p，1≤j≤q)且

β1β2…βqα1α2…αp=εα=α∈Dr，

所以βqα1，αiαi+1∈Dr，其中i=1，2，…，p-1，由引理1得im(βq)#α1，im(αi)#αi+1(1≤i≤p-1)，故存在一條從A到b的路徑：

(A，im(α1))，(im(α1)，im(α2))，…，(im(αp-1)，b).

(A0，A1)，(A1，A2)，…，(Am-2，Am-1)，(Am-1，Am)，

其中A0=im(α)，Am=im(ε)，且存在α1，α2，…，αm∈g使得Ai=im(αi)(1≤i≤m)且Ai#αi+1(0≤i≤m-1)，因此im(αα1…αk)=im(αk)(1≤k≤m)，且im(αα1…αk)#αk+1(1≤k≤m-1)，再根據(jù)引理1可知ɡ=αα1…αm∈Dr，αRɡLαm.由于ker(α)=ker(ε)=π且im(αm)=im(ε)=Am?αRεLαm，則有ɡHε.注意到hε是一個帶單位元ε的有限群，存在一個正整數(shù)m使得ε=ɡm(xù)∈〈g〉，從而E(Dr)?〈g〉.

同樣地，由于rank(K(n，r))=S(n，r)，K(n，r)具有S(n，r)個元素的生成集是K(n，r)的最小生成集，因此有如下推論.

設g是E(Dn-1)的一個非空集合.與文獻[7]類似，定義圖ΓG如下：

(1)ΓG的頂點集是g，記為v(ΓG)；

對α，β∈Dn-1，容易得到Def(α)?Ker(β)?im(α)#β，從而圖ΓG和圖ΓG(n-1)是相同的.設ε∈E(Dn-1)，存在i，j∈xn(i≠j)使得ε=ξi，j，容易證明αRε(=ξi，j)Lβ?ker(α)=ker(ξi，j)，im(β)=im(ξi，j)?Ker(α)={i，j}且Def(β)={i}.因此在定理1中取r=n-1，則有如下推論.

推論3設g是Dn-1的一個子集.則g是Singn的一個生成集，當且僅當對于每一ξi，j∈E(Dn-1)，存在α，β∈g使得：

(1)Ker(α)={i，j}；

(2)Def(β)={i}；

(3)在圖ΓG中，α是連接到β的.

經(jīng)比較發(fā)現(xiàn)，文獻[7]中的主要結(jié)果與推論3完全相同，因此定理1推廣了文獻[7]的主要結(jié)論.

[參考文獻]

[1]HOWIE J M.The subsemigroup generated by the idempotents of a full transformation semigroup[J].J London Math Soc，1966，1(1):707-716.

[2]KEARNES K A，SZENDREI，WOOD J.Generating singular transformations[J].Semigroup Forum，2001，63(3):441-448.

[3]ANDRé J M.Semigroups that contain all singular transformations[J].Semigroup Forum，2004，68(2):304-307.

[4]AYIK G，AYIK H，HOWIE J M.On factorisations and generators in transformation semigroup[J].Semigroup Forum，2005，70(2):225-237.

[5]AYIK G，AYIK H，HOWIE J M，et al.Rank properties of the semigroup of singular transformations on a finite set[J].Commun Algebra，2008，36(7):2581-587.

[6]GOMES G M S，HOWIE J M.On the ranks of certain finite semigroups of transformations[J].Math Proc Cambridge Phil Soc，1987，101(3):395-403.

[7]AYIK G，AYIK H，BUGAY L，et al.Generating sets of finite singular transformation semigroups[J].Semigroup Forum，2012，86(1):59-66.

[8]EVSEEV A E，PODRAN N E.Semigroups of transformations generated by idempotents of given defect[J].Izv Vysebn Saved Mat，1972，117(2):44-50.

[9]趙頤，游泰杰，趙平.半群PORn理想的極大正則子半群[J].東北師大學報(自然科學版)，2015，47(3):44-48.

[10]吳江燕，游泰杰.保序部分變換半群POn的平方冪等元 [J].東北師大學報(自然科學版)，2015，47(1):6-11.

[11]HOWIE J M.Idempotent generators in finite full transformation semigroups[J].Proc Roy Soc Edinburgh Sect A，1978，81(3/4):317-323.

[12]CLIFFORD H，PRESTON G B.The algebraic theory of semigroups[M].Providence：American Math Soc，1961：-.

[13]HOWIE J M.Fundamentals of semigroup theory[M].Oxford：The Clarendon Press，1995:341-343.

[14]HOWIE J M，MCFADDEN R B.Idempotent rank in finite full trasformation semigroup[J].Proc Roy Soc Edinburgh Sect A，1990，114:161-167.

(責任編輯：李亞軍)

Generating sets of the semigroup K(n，r)

QU Yun-yun，ZHAO Ping，YOU Tai-jie

(School of Mathematics Science，Guizhou Normal University，Guiyang 550001，China)

Abstract:Let Tn be the full transformation semigroup on a finite set Xn.For 1≤r≤n，let K(n，r)={α∈Tn|rank(α)≤r}，which is an subsemigroup of Tn.Necessary and sufficient conditions are founded to keep the set constructed by the transformations of rank r to be a(minimal)generating set for the semigroup K(n，r).

Keywords:tramformation semigroup; generating set; digraph

[文章編號]1000-1832(2016)02-0023-04

[收稿日期]2014-02-24

[基金項目]國家自然科學基金資助項目(11461014)；貴州省科學技術(shù)基金資助項目(黔科合J字[2013]2225).

[作者簡介]瞿云云(1983—)，男，碩士，副教授，主要從事代數(shù)與密碼學研究；通訊作者：趙平(1973—)，男，碩士，教授，主要從事半群代數(shù)理論研究.

[中圖分類號]O 157.1[學科代碼]110·21

[文獻標志碼]A

[DOI]10.16163/j.cnki.22-1123/n.2016.02.006