FACULTY OF MATHEMATICS AND PHYSICS UNIVERSITY OF LJUBLJANA Gregor Cigler GROUPS OF MATRICES WITH PRESCRIBED SPECTRUM Doctoral dissertation Ljubljana, 2005 FAKULTETA ZA MATEMATIKO IN FIZIKO UNIVERZA V LJUBLJANI Gregor Cigler GRUPE MATRIK S PREDPISANIM SPEKTROM Doktorska disertacija Ljubljana, 2005 Contents Abstract 7 Povzetek 9 1 SOME TRIANGULARIZABILITY RESULTS 17 1.1 About the algebra Fn×n. . . . . . . . . . . . . . . . . . . . . . . . . 17 1.2 Permutable trace and triangularization . . . . . . . . . . . . . . . . . 22 2 MATRIX GROUPS WITH FINITE SPECTRA 27 2.1 Algebraic groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 Some results from the theory of algebraic groups . . . . . . . . . . . . 28 2.3 An extension of Kolchin’s theorem . . . . . . . . . . . . . . . . . . . . 29 2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA 37 3.1 Systems of imprimitivity and Clifford’s theorem . . . . . . . . . . . . 37 3.2 Matrices with p-property . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 On monomial groups with p-property . . . . . . . . . . . . . . . . . . 44 3.4 Main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4 PERMUTATION-LIKE MATRIX GROUPS 55 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3 Sylow subgroups in a permutation-like group . . . . . . . . . . . . . . 63 4.4 Permutation-like groups with maximal cycles . . . . . . . . . . . . . . 65 4.5 Cases n= 2,3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.6 Cases n= 4,5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 References 99 Zahvala Zahvaljujem se profesorjema Matjaˇ zu Omladiˇ cu in Romanu D rnovˇ sku za njuno pomoˇ c in sugestije pri nastajanju tega dela. Rad bi se zahva lil tudi profesorju Heydarju Radjaviju za skrben pregled in jezikovne nasvete t er profesorju Thomasu J. Laffeyu za zelo koristne predloge. Gregor Cigler Abstract The general form of the problem that we discuss in this work is the following. Let G be a (semi)group of n×nmatrices over the field Fsuch that each matrix from Gis (individually) similar to a matrix with a given property P. Is then the (semi)group Gsimultaneously similar to a (semi)group of matrices all hav ing the property P, i.e., can we find an invertible matrix S∈Fn×nsuch that for all X∈ Gthe matrix SXS−1has the property P? When the answer is negative in general, we search for additional assumptions under which the (semi)group Gis simultaneously similar to a desired (semi)group. In Chapters 2 and 3 we consider triangularizability of matri x (semi)groups. In this case a matrix has the property P, if it is upper triangular and its spectrum satisfy some additional conditions. IfGis a matrix semigroup which is triangularized, diagonal ent ries on a fixed position form a subsemigroup of the multiplicative group F\ {0}. In Chapter 2 we study the triangularizability under the assumption that th e union of the spectra of all matrices from Gforms a group Γ. When Γ = {1}is the trivial group, the well-known Kolchin’s theorem gives the affirmative answer to our problem: Every semigroup of unipotent matrices is triangularizable. We investigate the case where Γ is a finite group and we show tha t Kolchin’s theorem extends only to the case where Γ = {1,−1}. We give counterexamples for groups Γ not contained in the group {1,−1}. In the search for further extensions of Kolchin’s theorem in Chapter 3 we intro- ducep-property, which is some kind of independency condition of t he eigenvalues. We investigate more closely groups of monomial matrices wit h this property. The main theorem of this chapter is a generalization of Kolchin’ s theorem to the groups with 2-property. Chapter 4 is dedicated to the permutation-like groups, i.e. , the finite groups G ⊂ Cn×nsuch that any matrix X∈ Gis similar to a permutation matrix. In this case a matrix has the property P, if it is a permutation matrix. Since a matrix similar to a permutation matrix is determined by its spectru m, we could describe this 7 property in terms of the spectrum, but the previous descript ion is more transparent. We deal with the question when a permutation-like group is si multaneously similar to a group of permutation matrices. Various examples in this chapter show that in general a permutation-like group does not have to be simulta neously similar to a group of permutation matrices. In fact, there are counterex amples for every n≥6. The low-dimensional cases n= 2,3,4,5 are investigated in detail. Math. Subj. Class. : 15A18, 20G05, 20C30 Keywords : Matrix group, spectrum, similarity, triangularization, permutation ma- trix 8 Povzetek Sploˇ sni problem, ki ga obravnava to delo, lahko opiˇ semo ta kole: Naj bo Fpolje inM ⊂ Fn×nmnoˇ zica kvadratnih matrik, med katerimi je vsaka podobna m atriki z izbrano lastnostjo P. Vpraˇ sanje je tedaj sledeˇ ce: Ali je Msimultano podobna kaki mnoˇ zici matrik, ki imajo lastnost P, tj. ali obstaja taka obrnljiva matrika S∈Fn×n, da ima za vsako matriko X∈ M matrikaSXS−1lastnost P? Ponavadi privzamemo, da mnoˇ zica Mima kako algebrsko strukturo za matriˇ cno mnoˇ zenje (in seˇ stevanje), npr. strukturo (pol)grupe ali algebre. V primerih, ko je odgovor na opisano vpraˇ sanje v sploˇ snem negativen, iˇ sˇ c emo dodatne zadostne po- goje, pri katerih je mnoˇ zica Msimultano podobna kaki mnoˇ zici matrik s predpisano lastnostjo P. V okviru tega sploˇ snega problema je posebej zanimiv primer , ko predpiˇ semo zgornjetrikotno obliko matrik. ˇCe je Falgebraiˇ cno zaprto polje, je vsaka matrika podobna neki zgornjetrikotni matriki, zato sploˇ sni probl emtrikotljivosti (oz.tri- angularizabilnosti ) mnoˇ zice matrik ustreza iskanju dodatnih pogojev, ki jim m ora mnoˇ zica zadoˇ sˇ cati, da je simultano podobna kaki mnoˇ zic i zgornjetrikotnih matrik. Lastnost trikotljivosti lahko izrazimo z obstojem verige i nvariantnih podprosto- rov, ki je maksimalna kot veriga linearnih prostorov nad pol jemF. Definicija 0.1 Mnoˇ zica matrik M ⊂ Fn×njetrikotljiva , ˇ ce obstaja taka veriga za Minvariantnih podprostorov {0}=V0⊂V1⊂V2⊂ · · · ⊂Vn=Fn, (chn) da je dimVi=i, tj. veriga (chn) je maksimalna veriga linearnih podprosto rov. Mnoˇ zici matrik M ⊂ Fn×n, ki nima nobenega invariantnega prostora, pravimo nerazcepna (oz.ireducibilna ) mnoˇ zica. ⋄ ˇCe ima mnoˇ zica Mkako algebrsko strukturo za matriˇ cno mnoˇ zenje (in seˇ ste vanje), dobimo znane zanimive rezultate, ki so povzeti v prvem pogla vju. Izrek 0.2 (Burnside) ˇCe je Falgebraiˇ cno zaprto polje, je Fn×nedina nerazcepna podalgebra algebre Fn×n. 9 Iz Bursideovega izreka takoj sledi, da je polgrupa matrik ne razcepna natanko tedaj, ko razpenja celotni prostor matrik Fn×n. V drugem delu prvega poglavja obravnavamo permutabilne fun kcije na mnoˇ zicah matrik. Definicija 0.3 Za funkcijo Φ : Fn×n→ Epravimo, da je permutabilna na mnoˇ zici matrik M ⊂ Fn×n, ˇ ce za poljuben nabor matrik X1,X2,...,X n∈ M in poljubno permutacijo π∈Snvelja Φ(X1X2· · ·Xn) = Φ(Xπ(1)Xπ(2)· · ·Xπ(n)). ⋄ Izkaˇ ze se, da je pojem permutabilnosti tesno povezan z razc epnostjo mnoˇ zic matrik. Lep primer tega je zadnji izrek prvega poglavja. Izrek 0.4 (Radjavi) ˇCe je Falgebraiˇ cno zaprto polje s karakteristiko 0, je mnoˇ zica matrik M ⊂ Fn×ntrikotljiva natanko tedaj, ko je sled permutabilna na M. Direktna posledica zadnjega izreka je znani Kolˇ cinov izre k. Izrek 0.5 (Kolˇ cin) Vsaka polgrupa S ⊂Fn×nunipotentnih matrik je trikotljiva. Iz zgornjetrikotne oblike matrik takoj razberemo njihove l astne vrednosti. ˇCe jeG (pol)grupa zgornjetrikotnih matrik, diagonalni elementi na izbranem mestu diago- nale tvorijo pod(pol)grupo multiplikativne grupe F\ {0}. Ali lahko ta sklep na nek naˇ cin obrnemo? Eno od moˇ znih vpraˇ sanj se glasi: Denimo, d a unija spektrov vseh matrik iz Gtvori neko grupo Γ. Ali je tedaj (pol)grupa Gtrikotljiva? V primeru trivialne grupe Γ = {1}nam Kolˇ cinov izrek da pritrdilen odgovor. Drug zanimiv primer najdemo v [25]: ˇCe je G ⊂Cn×ndeljiva grupa matrik in Γ = (0,∞), je grupa Gtrikotljiva. V drugem poglavju obravnavamo primer, ko je Γ konˇ cna grupa. Dokaˇ zemo, da lahko pri takem privzetku Kolˇ cinov izrek razˇ sirimo le na p rimer, ko je Γ = {1,−1}. Izrek 0.6 Naj bo Fpolje s karakteristiko 0. Vsaka polgrupa S ⊂ Fn×nmatrik s spektrom vsebovanim v mnoˇ zici {1,−1}je trikotljiva. 10 Za konˇ cne grupe Γ, ki niso vsebovane v {1,−1}, konstruiramo primere netriko- tljivih polgrup matrik s spektri v Γ. V dokazu izreka 0.6 si pomagamo z algebraiˇ cnimi podgrupami grupe Fn×n, tj. grupami matrik, ki jih lahko predstavimo kot mnoˇ zice skupn ih niˇ cel nekega nabora polinomov s koeficienti iz F. Algebraiˇ cne grupe so topoloˇ ske grupe v topologiji Zari- skega. Mnoˇ zica je v tej topologiji zaprta, ˇ ce sovpada z mno ˇ zico skupnih niˇ cel kakega nabora polinomov s koeficienti iz F. Jasno je, da zaprtje mnoˇ zice zgornjetrikotnih matrik ˇ se vedno sestavljajo le zgornjetrikotne matrike. S pomoˇ cjo te opazke se lahko omejimo na algebraiˇ cne grupe. Topologija Zariskega ima separacijsko lastnost T1, kar pomeni, da so konˇ cne mnoˇ zice zaprte. Ker so spektri matrik iz polgrupe Svsebovani v konˇ cni mnoˇ zici, se ni teˇ zko prepriˇ cati, da so tudi spektri matrik iz algebr aiˇ cnega zaprtja polgrupe vsebovani v predpisani konˇ cni mnoˇ zici. Po eni od trditev t eorije algebraiˇ cnih mnoˇ zic je zaprtje polgrupe matrik algebraiˇ cna grupa, s ˇ cimer naˇ s prvotni problem v celoti prevedemo na ekvivalentni problem v okviru algebraiˇ cnih g rup. Definicija 0.7 Zaprta podmnoˇ zica Salgebraiˇ cne grupe Gjeireducibilna , ˇ ce je ni moˇ zno zapisati kot netrivialno unijo zaprtih mnoˇ zic; tj. za vsaki zaprti mnoˇ zici A,B⊂S, ki zadoˇ sˇ cata pogoju S=A∪B velja bodisi A=S, bodisiB=S. ⋄ Vsako algebraiˇ cno grupo lahko razbijemo na disjunktno uni jo ireducibilnih mnoˇ zic G=G1∪G2∪ · · · ∪Gk, pri ˇ cemer je G1najveˇ cja ireducibilna mnoˇ zica, ki vsebuje enoto grupe G. Izkaˇ ze se, da jeG1algebraiˇ cna podgrupa edinka, ireducibilne mnoˇ zice G1,G2,...,G kpa ravno odseki kvocientne grupe G/G 1. V algebraiˇ cni grupi Gobstaja taka algebraiˇ cna unipotentna podgrupa edinka Gu, ki vsebuje vse unipotentne podgrupe edinke grupe G. ˇCe je Fpolje s karakteristiko 0, veljata naslednja izreka. 11 Izrek 0.8 Za algebraiˇ cno grupo Gobstaja taka algebraiˇ cna podgrupa P, da jeG poldirektni produkt G=Gu⋊P, tj. vsako matriko X∈Glahko na en sam naˇ cin zapiˇ semo kot produkt X=UT, kjer jeU∈GuinT∈P. SlediP≈G/G u. Izrek 0.9 Vsaka unipotentna podgrupa Talgebraiˇ cne grupe Gje ireducibilna. Od tod sledi, da je Guireducibilna grupa. V dokazu izreka 0.6 najprej dokaˇ zemo, da pri danih pogojih velja Gu=G1in na ta naˇ cin dokaz prevedemo na primer konˇ cne grupe. V tretjem poglavju iˇ sˇ cemo nadaljne posploˇ sitve Kolˇ cin ovega izreka in vpeljemo p-lastnost. Privzamemo, da je Falgebraiˇ cno zaprto polje s karakteristiko 0. Tedaj lahko v polje Fvloˇ zimo polje racionalnih ˇ stevil Q. Definicija 0.10 Naj bopneko naravno ˇ stevilo in A∈Fn×nkvadratna matrika s spektrom λ1,...,λ r,µ1,...,µ s(v tem naboru vsako veˇ ckratno lastno vrednost ponovimo z njeno veˇ ckratnostjo). ˇCe sta zai/\e}atio\slash=j(multiplikativna) reda elementov λiinλjkonˇ cni ˇ stevili, katerih skupna mera deli ˇ stevilo p, elementiµ1,...,µ spa so algebraiˇ cno neodvisni nad Q, pravimo, da ima matrika A p-lastnost . Mnoˇ zica M matrik ima p-lastnost, ˇ ce ima p-lastnost vsaka njena matrika. ⋄ Razloˇ zimo najprej, od kod definicija p-lastnosti. Naj bo Amatrika s spektrom λ1,...,λ r,µ1,...,µ s, kjer sta za i/\e}atio\slash=jredaλiinλjtuji konˇ cni ˇ stevili, elementi µ1,...,µ spa so algebraiˇ cno neodvisni nad Q. Potem velja det( A) = 1 natanko tedaj, ko je Aunipotentna matrika, tj. σ(A) ={1}. Privzetek za matriko Aje seveda ekvivalenten 1-lastnosti, zato je za matriˇ cno grup oGz 1-lastnostjo preslikava det :G →F\ {0} homomorfizem grup z jedrom K, ki ga tvorijo unipotentne matrike. Podgrupa edinka Kje po Kolˇ cinovem izreku trikotljiva. V dokazu glavnega izr eka 3.19 tretjega po- glavja lahko vidimo, da trikotljivost grupe Kporodi trikotljivost grupe G(uporabimo komutativnost nerazcepnih komponent grupe K). Vpeljavo p-lastnosti tako motivira 12 primerp= 2. Jedro homomorfizma (det)2:G → F\ {0}je podgrupa iz matrik s spektrom, vsebovanim v mnoˇ zici {1,−1}, ki je trikotljiva po izreku 2.8. Pri sploˇ snem pgrupa Gni nujno trikotljiva, v kar nas prepriˇ cajo primeri 2.4 na ko ncu drugega poglavja. Glavni izrek tretjega poglavja se glasi: Izrek 0.11 Naj bo G ⊂ Fn×ngrupa matrik nad algebraiˇ cno zaprtim poljem Fs karakteristiko 0.ˇCe ima grupa G2-lastnost, je trikotljiva. Del tretjega poglavja je posveˇ cen monomialnim grupam s p-lastnostjo, pri ˇ cemer jeppraˇ stevilo. Med drugim izpeljemo naslednjo zanimivo trdi tev: Trditev 0.12 Vsaka nerazcepna grupa G ⊂GL9(F)eksponenta 3je konjugirana tenzorskemu produktu H ⊗ K , kjer sta H,Kpodgrupi grupe P3=  DCk|k= 0,1,2, D= a0 0 0b0 0 0c , abc= 1, a3=b3=c3= 1   za C= 0 0 1 1 0 0 0 1 0 . V zadnjem poglavju obravnavamo lokalno permutacijske grupe matrik G ⊂Cn×n. Definicija 0.13 Konˇ cno grupo matrik G ⊂Cn×nimenujemo lokalno permutacijska grupa, ˇ ce je vsaka matrika X∈ Gpodobna neki permutacijski matriki. ⋄ Spraˇ sujemo se, kdaj je lokalno permutacijska grupa simult ano podobna kaki grupi permutacijskih matrik. Razni primeri nas prepriˇ caj o o tem, da to v sploˇ snem ni res. Primer 0.14 Obstaja lokalno permutacijska grupa G ⊂C4×4, ki vsebuje cikel dolˇ zine 3in ni simultano podobna nobeni grupi permutacijskih matrik . Dokaz. Naj boω∈Cprimitivni tretji koren enote. Oznaˇ cimo B=/bracketleftbigg ω ω−1/bracketrightbigg inT0=/bracketleftbigg 0 1 1 0/bracketrightbigg 13 ter definirajmo bloˇ cno zapisani matriki C=/bracketleftbigg I B/bracketrightbigg inT=/bracketleftbigg T0 T0/bracketrightbigg , kjer jeIidentiˇ cna matrika velikosti 2 ×2. Matrika Ctedaj ustreza ciklu dolˇ zine 3, matrika Tpa produktu dveh tujih transpozicij. Ker velja TC=C−1T, je vsak element grupe G, generirane z matrikama TinC, bodisi oblike TCkbodisi oblike Ck. Ni se teˇ zko prepriˇ cati, da matrika oblike TCkustreza produktu dveh tujih transpozicij, matrika oblike Ckpa neki potenci cikla dolˇ zine 3. Grupa Gje tako res lokalno permutacijska grupa. Denimo, da je grupa Gsimultano podobna kaki grupi permutacijskih matrik, kjer matrika Tustreza permutaciji σin matrika TCpermutaciji σ′. Vsaka izmed permutacij σinσ′ustreza produktu dveh tujih transpozicij. Produkt T·(TC) =C, ki ustreza produktu σσ′, ustreza po drugi strani nekemu ciklu γdolˇ zine 3, in ima zato kot permutacija natanko eno negibno toˇ cko. Naj bo anegibna toˇ cka cikla γ. Ker sta permutaciji σinσ′brez negibnih toˇ ck, permutacija σ′vsebuje neko transpozicijo oblike (ab). Ker je anegibna toˇ cka produkta σσ′, slediσ(b) =a. Tedaj tudi permutacija σvsebuje transpozicijo ( ba), od koder sledi, da je bdodatna negibna toˇ cka permutacije σσ′. Priˇ sli smo do protislovja, zato grupa Gres ni simultano podobna nobeni grupi permutacijskih matrik. /square Primer 0.14 lahko razˇ sirimo v vse sode dimenzije n≥4 (glej primer 4.3), poleg tega pa obstajajo protiprimeri za poljubne dimenzije n≥6. Vsem protiprimerom je skupno, da lokalno permutacijska grupa Gne vsebuje maksimalnega cikla , tj. matrikeC, podobne matriki oblike  0· · · · · · 0 1 1... 0 0........................ 0· · · 0 1 0 . Konstruirani protiprimeri nas navedejo na naslednjo domne vo: Domneva: Vsaka lokalno permutacijska grupa, ki vsebuje maksimalni c ikel, je simultano podobna grupi permutacijskih matrik. 14 Naslednje trditve, ki jih dokaˇ zemo v ˇ cetrtem poglavju, po trjujejo domnevo za n≤5 in v primeru komutativne grupe. Trditev 0.15 Vsaka komutativna lokalno permutacijska grupa G, ki vsebuje maksi- malni cikel C, je oblike G=. Izrek 0.16 Vsaka lokalno permutacijska grupa G ⊂Cn×nzan= 2,3,5je simultano podobna neki grupi permutacijskih matrik. Izrek 0.17 Vsaka lokalno permutacijska grupa G ⊂ C4×4, ki vsebuje maksimalni cikel, je simultano podobna neki grupi permutacijskih matr ik. 15 17 1 SOME TRIANGULARIZABILITY RESULTS 1.1 About the algebra Fn×n In this section we recall some well-known results related to triangularizability. For the sake of completeness we include their proofs. We mainly f ollow the monograph [20] of H. Radjavi and P. Rosenthal. Definition 1.1 LetFbe a field and M ⊂ Fn×na set of matrices. The set Mis irreducible if the only M-invariant subspaces are {0}andFn. We say that Mis triangularizable if there exists a chain of M-invariant subspaces {0}=V0⊂V1⊂V2⊂ · · · ⊂Vn=Fn(chn) such that dim Vi=i, i.e., the chain (chn) is a maximal chain of linear spaces. ⋄ Lemma 1.2 LetA ⊂ Fn×nbe an irreducible algebra. If Acontains a matrix T0 with rank 1, then A=Fn×n. Proof. Let (Fn)∗be the space of all functionals on Fnand pick a vector y0/\e}atio\slash= 0 in the range of T0. Then we can find a linear functional Φ 0∈(Fn)∗such that T0x= Φ 0(x)y0for allx∈Fn. Since every linear operator is a sum of operators of rank 1, it suffices to show that Acontains every Tof the form Tx= Φ(x)y (rg1), where Φ ∈(Fn)∗andy∈Fn. For eachA∈ Awe haveT0A∈ A. ButT0Ax= Φ 0(Ax)y0, so Φ from (rg1) ranges over all Φ 0◦A, withA∈ A. If we denote F={Φ0◦A|A∈ A}, then F is a subspace of ( Fn)∗. IfFis a proper subspace, then there is x0/\e}atio\slash= 0 such that Φ(x0) = 0 for all Φ ∈ F, i.e., Φ 0(Ax0) = Φ 0(Fn) = 0. This is a contradiction, since Φ0/\e}atio\slash= 0. Therefore Acontains all Tof the form Tx= Φ(x)y0. AsAis irreducible, for arbitrary y∈Fnthere isA∈ Asuch thatAy0=y. Then forTx= Φ(x)y0we getAT(x) = Φ(x)y, which completes the proof. /square The following result is the well-known Burnside theorem. 18 1 SOME TRIANGULARIZABILITY RESULTS Theorem 1.3 IfFis an algebraically closed field, then Fn×nis the only irreducible subalgebra of Fn×n. Proof. LetA ⊂Fn×nbe an irreducible algebra of matrices and T0∈ Aa transfor- mation with minimal nonzero rank in A. We show that T0has rank 1. Assume otherwise. Then we find vectors x1,x2∈Fnsuch thatT0x1,T0x2are linearly independent vectors. Since Ais irreducible we get {AT0x1|A∈A}=Fn and we can find A0∈ Asuch thatA0T0x1=x2. ThenT0A0T0x1andT0x1are linearly independent. We can find a scalar λ∈Fsuch that the restriction of ( T0A0−λI) toT0Fnis not invertible. As T0A0T0x1−λT0x1/\e}atio\slash= 0 the operator ( T0A0−λI)T0is nonzero. Since the rank of the operator ( T0A0−λI)T0is strictly smaller then the rank ofT0, this is a contradiction. We conclude that T0has rank 1. We use Lemma 1.2 to complete the proof. /square Theorem 1.4 The only two-sided ideals of the algebra Fn×nare{0}andFn×n. Proof. For a nonzero A∈ Iwe can find B∈Fn×nsuch thatT0=AB∈ Ihas rank 1. By Lemma 1.2 we get I=Fn×n. /square We will need the next result in establishing a ’block triangu larization theorem’. Theorem 1.5 For an algebraically closed field Fall the automorphisms of the al- gebra Fn×nare inner, i.e., for an automorphism Φ :Fn×n→Fn×nthere exists an invertible matrix S∈Fn×nsuch that Φ(X) =SXS−1 for allX∈Fn×n. Proof. Let Φ : Fn×n→Fn×nbe an automorphism. First we note that Φ ta- kes idempotents into idempotents. Let A0be an idempotent of rank 1. Then {A0BA0|B∈Fn×n}is one-dimensional subspace. Its image {Φ(A0)CΦ(A0)|C∈ Fn×n}is therefore also one-dimensional subspace. Thus Φ( A0) is rank-one idempo- tent whenever A0is. 1.1 About the algebra Fn×n19 Fix any rank-one idempotent A0. Clearly any two rank-one idempotents are similar, so Φ( A0) is similar to A0. If we compose this similarity with Φ we can assume that Φ( A0) =A0. Letx0be a nonzero vector in the range of A0, i.e., A0x0=x0. Now we define a transformation that implements Φ. For each B∈Fn×nwe define S(Bx0) = Φ(B)x0. We first check that Sis a well-defined mapping. If B1x0=B2x0, then (B1−B2)A0x0= 0 and therefore ( B1−B2)A0= 0, sinceA0has rank 1. It follows that (Φ(B1)−Φ(B2))Φ(A0) = (Φ(B1)−Φ(B2))A0= 0, and (Φ(B1)−Φ(B2))x0= 0. ThusSis well-defined. It is clear that Sis linear. If S(Bx0) = 0, then Φ( B)x0= 0. This implies Φ(B)Φ(A0) = Φ(BA0) = 0, soBA0= 0 and thus Bx0= 0. This shows that Sis injective. Since Sis an endomorphism of finite-dimensional space, it is also surjective, and hence invertible. Now fixA∈Fn×n. Then for each B∈Fn×nwe get S(AB)x0= Φ(AB)x0= Φ(A)Φ(B)x0 and SBx 0= Φ(B)x0, so SABx 0= Φ(A)SBx 0. Eachx∈Fnis of the form x=Bx0for a suitable B∈Fn×n, therefore we get SAx= Φ(A)Sx, i.e., Φ(A) =SAS−1. /square Theorem 1.6 LetFbe an algebraically closed field. For any subalgebra AofFn×n, there is a decomposition Fn=N1⊕ N 2⊕ · · · ⊕ N k, 20 1 SOME TRIANGULARIZABILITY RESULTS with respect to which every matrix A∈ Ahas the block upper diagonal form A= A11A12· · ·A1k 0A22· · ·A2k 0 0A33... ............ 0· · · 0Akk  where the set {1,2,...,k }is a disjoint union of subsets J1,J2,...,J lsuch that (1){Aii|A∈ A} = End F(Ni)fori= 1,2,...,k ; (2) ifi,j∈Jsthen Aii=Ajj for allA∈ A; (3) ifJs/\e}atio\slash=Jtandi∈Js,j∈Jtthen {(Aii,Ajj)|A∈ A} = End F(Ni)×End F(Nj); (4) fori∈Jsthere is an A∈ Asuch thatAii=IandAjj= 0for allj /∈Js. Proof. IfAis irreducible, then Burnside’s theorem (Theorem 1.3) give s us the desired result, with k= 1 and N1=Fn. Assume that Ais reducible and let M0={0} ⊂ M 1⊂ · · · ⊂ M m−1⊂ M m=Fn be a maximal chain of distinct A-invariant subspaces. For each i= 1,...,m , choose a complementary space NiofMi−1inMi, so that Mi=Mi−1⊕ N i. Then the space Fnis a direct sum, namely Fn=N1⊕ · · · ⊕ N m. Since Mi’s are invariant spaces, all the transformations in Aare clearly block upper triangular with respect to this decomposition. For each i, letPi:Fn→ N idenote the projection onto Ni along the sum/summationtext j/negationslash=iNj. Then we have P1+P2+· · ·+Pm=I. For eachi, letAi={PiA|Ni|A∈ A} be the ’compression’ of the algebra A onNi. Then Aiis an irreducible algebra, since there is no A-invariant subspace ’strictly’ between Mi−1andMi. By Burnside’s Theorem, we get Ai= End F(Ni) for eachi. 1.1 About the algebra Fn×n21 We now show that the algebras Aiare either pairwise independent or linked in the following sense. Fix distinct iandj. If there is an A∈ Asuch thatPiA|Ni=I andPjA|Nj= 0, then we say that AiandAjare independent. This relation is symmetric, for Pi(I−A)|Ni= 0 andPj(I−A)|Nj=I. IfAiandAjare not independent, we say that they are linked. We justify t his terminology by the following. Suppose that for some A∈ Awe havePiA|Ni/\e}atio\slash= 0 andPjA|Nj= 0. Then the set {PiA|Ni|A∈ A, PjA|Nj= 0}is a nonzero two-sided ideal in Ai. Since Ai= End F(Ni), it follows from Theorem 1.4 that the identity is in this ideal. Thus if AiandAjare linked, then for A∈ Awe have PiA|Ni= 0⇔PjA|Nj= 0 (link) . LetAiandAjbe linked. Then we can define a mapping Φ : Ai→ A jby Φ(PiA|Ni) =PjA|Nj. It is easy to verify that Φ is indeed a well-defined homomorphi sm of algebras. By the property (link) Φ is injective. By the definition of the al gebra Ajthe map Φ is surjective and therefore it is an isomorphism of algebras. It follows that NiandNjhave the same dimension. As Ai= End F(Ni) and Aj= End F(Nj), we can identify them which gives us an automorphism of the algebra End F(Ni). By Theorem 1.5 we get an invertible linear transformation S: Ni→ N jthat implements Φ, i.e., PiA|Ni=S−1PjA|NjS for allA∈ A. This justifies the terminology ’linked’. The proof of the theorem can now be completed by simply identi fying linked Aiwith each other. Fix iand define J(i) ={j| AiandAjare linked }. For each j∈J(i) we choose Sj:Ni→ N jso that PiA|Ni=S−1 jPjA|NjSj for allA∈ A. Then we define T(i) :Fn→Fnwith respect to the decomposition Fn=N1⊕ N 2⊕ · · · ⊕ N m 22 1 SOME TRIANGULARIZABILITY RESULTS by the block diagonal matrix having T(i)kk=Ifork /∈JandT(i)jj=Sjfor j∈J(i). Then every element of T(i)−1AT(i) has the same entries in the positions (j,j) for allj∈J(i). We defineJ1=J(1) and proceed inductively. Having defined Jk=J(ik) we takeik+1to be the smallest element of the set {1,2,...,m } \(J1∪ · · · ∪Jk) if this set is not empty (otherwise we are done). We define Jk+1=J(ik+1). Once we have {1,2,...,m }=J1∪ · · · ∪Jl, we finally define R=T(i1)T(i2)· · ·T(il). Then the algebraR−1ARhas the required properties. /square 1.2 Permutable trace and triangularization Although we will use the following results for groups of matr ices, we formulate them in more general context of semigroups. Definition 1.7 A set S ⊂Fn×nis called a matrix semigroup if it is closed under the matrix multiplication. ⋄ The algebra generated by a matrix semigroup Sis just the linear span of S. If Fis an algebraically closed field, then by Theorem 1.3 a semigr oup is irreducible if and only if it contains a basis for the space Fn×n. Definition 1.8 Let Φ be a function from Fn×ninto a set E. We say Φ is permutable on a collection M ⊂ Fn×nif for arbitrary X1,X2,...,X nand all permutations π∈Sn, we have Φ(X1X2· · ·Xn) = Φ(Xπ(1)Xπ(2)· · ·Xπ(n)). ⋄ Lemma 1.9 LetFbe an algebraically closed field and let M ⊂ Fn×nbe any col- lection where n≥2. If there is a nonzero linear functional fonFn×nwhich is permutable on M, then Mis reducible. Proof. LetSandAbe the semigroup and the algebra generated by M, respec- tively. Permutability of fonSfollows directly from the hypothesis. However, one can easily verify that fis actually permutable on A. 1.2 Permutable trace and triangularization 23 Suppose that Mis irreducible. Then by Theorem 1.3 we get A=Fn×n. Pick any pairA,B∈Fn×nsuch thatC=AB−BA/\e}atio\slash= 0. Then permutability of f implies that f(XCY ) = 0 for all X,Y∈Fn×n. It follows that fis zero on a nonzero two-sided ideal I={XCY |X,Y∈Fn×n}. By Theorem 1.4 we get I=Fn×nand f= 0. This contradiction shows that Mis reducible. /square Corollary 1.10 LetFbe an algebraically closed field and let S ⊂Fn×nbe a matrix semigroup where n≥2. If there is a nonzero linear functional fonFn×nwhich is constant on S, then Sis reducible. LetPbe a property of collections of square matrices over F. Since we consider the simultaneous similarity of sets of matrices, we assume t hat the property P is preserved by the similarities of matrices. This means tha t the property Pis in fact well defined on collections of linear endomorphisms, since we can choose an arbitrary basis and consider the given property on the corre sponding set of matrices. LetM ⊂ Fn×nbe a collection of matrices and U⊂V⊂Fna pair of invariant subspaces. Then we have a decomposition Fn=U⊕U′⊕V′, whereV=U⊕U′. If we choose a basis of Fnaccording to this decomposition, the matrices from Mhave the form X= XU∗ ∗ 0XV/U ∗ 0 0 XV′ . We denote MV/U={XV/U|X∈ M}. Definition 1.11 LetPbe a property of collections of square matrices over F. We say that the property Pisinherited by quotients , if for any M ⊂ Fn×nhaving property Pand any M-invariant subspaces U⊂V⊂Fnthe set MV/Ustill has the property P. ⋄ The next lemma is often used when triangularizability is con sidered. Lemma 1.12 (Triangularization Lemma) LetPbe a property of subsets of Fn×n which is inherited by quotients. If the property Pon a collection M ⊂ Fn×nimplies reducibility of Mforn≥2, then it implies the triangularizability of any collection . 24 1 SOME TRIANGULARIZABILITY RESULTS Proof. Suppose that {0}=V0⊂V1⊂V2⊂ · · · ⊂Vm=Fnis a maximal chain ofM-invariant subspaces. Then for all ithe set MVi/Vi−ihas the property P. By the hypothesis the set consists of 1 ×1 matrices, which implies triangularizability of M. /square Lemma 1.13 LetPbe a property of subsets of Fn×nwhich is inherited by the quotients, and assume that any M ⊂ Fn×nwith the property Pis triangularizable over the algebraic closure K=Fof the field F. If the spectrum σ(X)is contained inFfor everyX∈ M, then we can triangularize Mover the field F. Proof. We prove the lemma by the induction. Forn= 1 there is nothing to prove, so we proceed with n >1. In a suitable basis ofKnall matrices X∈ M transform in the form Φ(X) =/bracketleftbigg f1(X)∗ 0X′/bracketrightbigg , withf1(X)∈F. If we write the (possibly infinite) system of linear equatio ns defining the intersection of all the kernels Ker ( X−f1(X)I), it has a nontrivial solution in K. By a rank argument it is clear that we can find a solution in F, so we can assume that Φ(X)∈Fn×nfor allX∈ M. Since the collection M′={X′|X∈ M} still satisfies the assumptions from lemma, we use the inductive hy pothesis to finish the proof. /square Theorem 1.14 (Kolchin’s theorem) LetS ⊂Fn×nbe a semigroup of unipotent matrices. Then Sis triangularizable. Proof. By Lemma 1.13 it is enough to consider the case of algebraical ly closed fields. The spectrum of every matrix X∈ Sis{1}, therefore trace has constant valuenonS. By Corollary 1.10 the semigroup is reducible for n >1. Since the unipotency is inherited by the quotiens, we complete the pro of using Lemma 1.12. /square If a collection of matrices M ⊂ Fn×nis triangularizable, it is clear that the trace is a permutable function on M. The following theorem shows that the converse holds provided Fis an algebraically closed field. 1.2 Permutable trace and triangularization 25 Theorem 1.15 (Radjavi) LetFbe an algebraically closed field with characteristic zero and M ⊂ Fn×na collection of matrices. Then Mis triangularizable if and only if trace is permutable on M. Proof. Assume that trace is permutable on Mand let Adenote the algebra generated by M. Clearly permutability of trace extends to the algebra A. Let {Aij}be the block triangularization of Aobtained in Theorem 1.6. We must show that all the subspaces Niare one-dimensional. Assume otherwise. Then one of the subsetsJk=Jcorresponds to equal diagonal blocks {Aii|i∈J}acting on spaces of dimension at least 2. Let mbe the number of elements of J. Then by (1) and (4) of Theorem 1.6 the function f, defined by f(A) =m·tr(A) is permutable on End F(Ni). Sincem/\e}atio\slash= 0 it follows that trace is permutable on End F(Ni) which is a contradiction. /square The next example shows that in general the field Fhas to be algebraically closed to satisfy the previous theorem. Example 1.16 LetG ⊂R2×2be the group of all matrices of the form X=/bracketleftbigg a−b b a/bracketrightbigg , a,b∈R. Then trace is permutable on G, butGis not triangularizable over R. Proof. SinceG=R{I,J}, where J=/bracketleftbigg 0−1 1 0/bracketrightbigg , the group Gis commutative and therefore trace is permutable. The matri xJhas no real eigenvalues, so the group Gis irreducible over R. /square 27 2 MATRIX GROUPS WITH FINITE SPECTRA 2.1 Algebraic groups We start with the notion of the algebraic set and the algebrai c group. Let Fdenote a field with characteristic zero. Definition 2.1 An ordered pair consisting of a set Sand a finitely generated alge- braP(S)j. Next, we have (x(1 det))(y) =1 det(yx)=1 det(y)1 det(x)=1 det(y), since det(x) = 1. From the above relations we get xαij=αij+n/summationdisplay km . We must now show that c=m. It is clear that we can disregard αifori>m and assume that n=m. An easy calculation shows that Tn+1=TnS1−Tn−1S2+· · ·+ (−1)n−1T1Sn. Denotingsk=Sk(α1,...,α n) and using the hypothesis Tk(α1,...,α n) = 0 fork= 1,...,n + 1, yields 1 =s1−s2+· · ·+ (−1)n−1sn. 2.3 An extension of Kolchin’s theorem 33 By the relation (rec), for k=n, we also get c(s1−s2+· · ·+ (−1)n−1sn−1) + (−1)nnsn= 0. Sincesn/\e}atio\slash= 0, the last two equations imply c=n. By (1) we get βi= 1 for all i, proving that αi= 1. /square Lemma 2.7 (Kaplansky) IfS ⊂Fn×nis a matrix semigroup of invertible matrices andtr :S → Fis constant, then every matrix X∈ Shas only 1in its spectrum (i.e.,Sis unipotent). Proof. It follows directly from (3) of Lemma 2.6. /square Let us now recall Radjavi’s trace condition (see Theorem 1.1 5). For an alge- braically closed field Fa semigroup S ⊂Fn×nis triangularizable if and only if for arbitraryA,B,C ∈Swe have tr (ABC) = tr(CBA), i.e., trace is permutable on the semigroup S. We will use this fact to prove the following theorem. Theorem 2.8 LetSbe a semigroup of matrices having their eigenvalues in the se t {1,−1}. ThenSis triangularizable. Proof. According to Lemma 1.13 we may assume that Fis algebraically closed. We can clearly assume that Sis a submonoid of GL n(F). By [14, Prop. 4.1, p.12] the algebraic closure GofSis in fact an algebraic subgroup of GL n(F). Forλ /∈ {1,−1} we definefλ:G → Fbyfλ(X) = det(X−λI). It is clear that fλis a polynomial function in the coordinate functionals αij. As the canonical upper diagonal form of any matrix in Shas diagonal entries 1 or −1, it follows that fλ(S)⊂ {(1−λ)r(−1−λ)s|r+s=n}, which implies that fλ(S) is a finite set not containing 0. Since Zariski topology has the property T1, the setfλ(S) is closed. For fλis a continuous map we get fλ(G) =fλ(S)⊂fλ(S) =fλ(S). 34 2 MATRIX GROUPS WITH FINITE SPECTRA It follows that the set fλ(G) does not contain 0, and the spectra of the matrices from Gare also contained in {1,−1}. We can now replace the semigroup Sby the group G. Consider the polynomial function tr : G → F. It is clear that it takes only finitely many distinct values. If G1is the irreducible component of the unit, the set tr( G1) is an irreducible subset of the finite set tr( G). It follows that tr ( G1) is a singleton, which means that the map tr is constant on G1. By Lemma 2.7, G1is a unipotent group of matrices and by Lemma 2.5 also is an unipotent algebraic subgroup of G. Since G1is a normal subgroup of G, we have G1⊂ Gu. (6) ForGuis irreducible (see Theorem 2.3) and contains the unit of the group G, we have Gu⊂ G1. (7) From (6) and (7) it follows that Gu=G1. (8) Therefore, by Theorem 2.4 we get G=G1⋊P. (9) SinceG1has a finite index and by (9) P≈ G/G1, it follows that Pis a finite subgroup. AsPis finite and Fhas characteristic zero, the Jordan from of a matrix X∈P must be diagonal. It follows that for all X∈Pwe have X=X−1 and therefore Pis commutative. Now we pick A,B,C ∈ G. By (9) we can write A=A′X,B=B′YandC=C′Zfor someA′,B′,C′∈ G1andX,Y,Z ∈P. Since tr takes only finitely many values and elements of the factor g roupG/G1are exactly the irreducible components of Git follows that tr is constant on every coset G1Tfor T∈ G. AsPis commutative, we get tr (ABC)∈tr(G1ABC) = tr ( G1XYZ) = = tr (G1ZYX) = tr( G1CBA)∋tr(CBA), 2.4 Examples 35 and thus tr (ABC) = tr(CBA). Radjavi’s trace condition then implies triangularizabili ty of the group G, and there- fore also triangularizability of the semigroup S ⊂ G . This completes the proof. /square 2.4 Examples The following examples shows us that Theorem 2.8 is the best p ossible extension of Kolchin’s theorem under the assumption that the spectra of m atrices of a matrix semigroup lies under some finite subgroup of the multiplicat ive group of the field F. Let Γ be a finite subgroup of the multiplicative group F\ {0}having more than two elements (i.e., Γ /\e}atio\slash⊂ {1,−1}). We now construct a finite group Pof matri- ces such that the union of the spectra of its matrices is exact ly Γ, but Pis not triangularizable. First we make the next remark. Assume that a finite matrix group Pis triagularizable and that all of its matrices are upper triangular. Then for any pair A,B∈ Pthe matrixABA−1B−1is an upper triangular matrix having all the diagonal entries equal to 1 , i.e., is unipotent. Since Pis a finite group the only possible unipotent matrix in Pis the identity matrix and therefore Phas to be a commutative group. By the above it is enough to construct a noncommutative finite group Pwith the desired spectra. First we define P2=/braceleftbigg/bracketleftbigg a0 0b/bracketrightbigg |a,b∈ {1,−1}/bracerightbigg ∪/braceleftbigg/bracketleftbigg 0a b0/bracketrightbigg |a,b∈ {1,−1}/bracerightbigg . It is easy to verify, that the union of the spectra of the matri ces from P2is the group {1,−1,i,−i}and that P2is a noncommutative group with eight elements. For an odd prime pwe denote by Ppthe matrix group generated with the matrices D= 1 0 · · · 0 0λ...............0 0· · · 0λp−1  36 2 MATRIX GROUPS WITH FINITE SPECTRA and C= 0· · · · · · 0 1 1... 0 0........................ 0· · · 0 1 0  forλ/\e}atio\slash= 1,λp= 1. One can verify that the group Ppconsists of p3matrices and the union of the spectra of its matrices is the group {µ|µp= 1}. For the required group Pwe can take P=/braceleftbigg/bracketleftbigg ν0 0X/bracketrightbigg |ν∈Γ, X∈ Pl/bracerightbigg , withl= 2 if the order of Γ is a power of 2 and l=pifpis some prime factor dividing the order of Γ. 37 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA 3.1 Systems of imprimitivity and Clifford’s theorem In this introduction we consider imprimitivity of the matri x groups and its extreme case, i.e., monomiality. The following facts can be found in [27]. Definition 3.1 LetG ⊂Fn×nbe a matrix group and W ⊂ Fn. IfWis aG-invariant space with respect to the left action of GonFn, we call WaG-module . ⋄ Definition 3.2 A matrix group G ⊂Fn×nis called imprimitive if the space Fncan be represented as a direct sum of ksubspaces ( k >1) that are permuted among each other by the elements of G, i.e., Fn×n=Q1⊕Q2⊕ · · · ⊕Qk and forX∈ G,i≤kwe findj≤ksuch that X(Qi) =Qj. The subspaces Q1,Q2,...,Q kare called systems of imprimitivity ofG. If such a decomposition does not exist, then Gisprimitive . ⋄ LetG ⊂Fn×nbe an irreducible imprimitive matrix group and Fn×n=Q1⊕Q2⊕ · · · ⊕Qk a direct sum of systems of imprimitivity. Since Gis irreducible, it is clear that the elements of Gpermute the spaces Q1,Q2,...,Q ktransitively. Let Hibe the set of all elements of Gthat interchange vectors of QiwithinQi. It is easy to verify that Hiis in fact a subgroup of Gand forX∈ Gsuch thatX(Qi) =Qjwe have XHiX−1=Hj. Let us pick X1,X2,...,X k∈ Gsuch that for all i≤kwe haveXi(Q1) =Qi. Then forX∈ Gwe findjsuch thatX(Q1) =Qj. SinceX−1 jXQ1=Q1it follows that XH1=XjH1and therefore X1,X2,...,X k∈ Gform a complete system of left representatives of H1inG. 38 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA Lemma 3.3 LetGbe an irreducible group. The subgroup Hiinduces an irreducible subgroup GionQi. Proof. By symmetry it is sufficient to consider the case i= 1. LetR1⊂Q1ba a nontrivial invariant subspace of Q1andX1,X2,...,X k∈ Ga complete system of left representatives of H1inG. We define R=X1(R1)⊕X2(R1)⊕ · · · ⊕Xk(R1). SinceH1(R1) =R1, it is easy to verify that for X∈ Gwe haveX(R) =R.AsR/\e}atio\slash= 0 andGis an irreducible group we get R=Fn. Sincen= dim(R) =k·dim(R1), we have dim(R1) =n k= dim(Q1) and therefore Q1=R1. This completes the proof. /square Proposition 3.4 For an irreducible group Gthere exists a decomposition of Fninto a direct sum of systems of imprimitivity Q1,Q2,...,Q ksuch that the groups Gi(see Lemma 3.3) are primitive. Proof. LetH1induce an imprimitive group G1on the space Q1(see Lemma 3.3), and let Q1=Q11⊕Q12⊕ · · · ⊕Q1l be a decomposition into systems of imprimitivity. Then Fncan be represented as the direct sum of klsystems of imprimitivity, namely Qij=Xi(Q1j), whereX1,X2,...,X k∈ Gis a complete system of left representatives of H1inG. In a finite number of steps we reach the situation described in the proposition. /square The decomposition in Proposition 3.4 is called a complete decomposition into systems of imprimitivity . 3.1 Systems of imprimitivity and Clifford’s theorem 39 Theorem 3.5 (Clifford’s theorem) LetG ⊂Fn×nbe an irreducible matrix group andH⊳Ga normal subgroup of G. Then (1) There is a decomposition of Fn, Fn=L1⊕L2⊕ · · · ⊕Ls, whereLiare irreducible H-modules all having the same dimension. (2) LetQibe the sum of all spaces Ljwhich are isomorphic to LiasH-modules. Then all the different spaces Qiare systems of imprimitivity of the group G. In particular, if Gis a primitive group, then all the spaces Liare isomorphic H-modules. Proof. (1) LetL1be an irreducible H-submodule of Fn. Since His a normal subgroup, for B2∈ Gwe have HB2(L1) =B2H(L1) =B2(L1). Therefore the space L1+B2(L1) either coincides with L1or is the direct of two irreducible H-modules. Suppose that for some B2,...,B s∈ G L=L1⊕B2(L1)⊕ · · · ⊕Bs(L1) is a direct sum such that for every G∈ Gthe sumL+G(L1) is no longer direct. ThenG(L1)⊂Land therefore G(L) =L. Since Gis an irreducible group, we get L=L1⊕L2⊕ · · · ⊕Ls=Fn(hdec) forLj=Bj(L1). This proves the first part of the theorem. (2) Now let Q1be the sum of all spaces Ljwhich are isomorphic to L1asH-modules. IfRis aH-submodule of Fnisomorphic to L1thenR⊂Q1since the decomposition (hdec) is unique up to some permutation of the sumands. For a p air of isomorphic H-modulesR1,R2⊂FnandG∈ Git is easy to verify that G(R1) andG(R2) are also isomorphic H-modules, since the His a normal subgroup. We now examine G(Q1), whereG∈ G. ClearlyG(Q1) contains G(L1) as a direct summand, and all the other summands are isomorphic to G(L1). In the decomposition (hdec) we find an H-moduleLiisomorphic to G(L1). Therefore G(Q1) is contained in a direct sum Q2of allLjisomorphic to Li. However, the H- modulesG−1(Li) andL1are isomorphic, which implies that G−1(Q2)⊂Q1. Hence G(Q1) =Q2and the proof is complete. /square 40 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA Corollary 3.6 IfHis a normal subgroup of an irreducible primitive matrix grou p, then the linear span FHis a simple algebra over F. Proof. All the H-modulesLiin the decomposition provided by Theorem 3.5 are isomorphic. Therefore we can find a similarity such that all Li’s are actually the same. By Theorem 1.4, L1is a simple algebra, and thus FHalso is a simple algebra over. /square Lemma 3.7 LetG ⊂ Fn×nbe an irreducible primitive matrix group and Han abelian normal subgroup of G. Then His a subgroup of the multiplicative group of a certain field Kcontained in the algebra Fn×n. Proof. We consider the linear span FHofH. Since His a normal subgroup of a primitive irreducible group, Corollary 3.6 is applicab le. Thus FHis a simple commutative subalgebra of Fn×n. Therefore K=FHis a field. /square Corollary 3.8 IfGis an irreducible primitive matrix group over an algebraica lly closed field FandHan abelian normal subgroup of G, then His contained in the centerZ(G)⊂F{I}. Proof. We apply Lemma 3.7 to conclude that K=FHis a finite extension of the fieldF. AsFis an algebraically closed field, we get K=Fand therefore H ⊂F{I}. /square The extreme case of imprimitivity is the monomiality defined as follows. Definition 3.9 A matrixAis called monomial if it has the form A=DP, whereD is a diagonal matrix and Pa permutation matrix. A group consisting of monomial matrices is called a monomial group . ⋄ Theorem 3.10 (Taketa) LetFbe an algebraically closed field and G ⊂Fn×nan irreducible nilpotent matrix group. Then Gis similar to a monomial group. Proof. By Proposition 3.4 the space Fnis a direct sum of complete systems of imprimitivity Q1,Q2,...,Q r. Then the groups Gi(see Lemma 3.3) are primitive. 3.2 Matrices with p-property 41 We show that an irreducible nilpotent matrix group Kof degreem >1 is im- primitive. Let {I}=Z0⊂ Z 1⊂ · · · ⊂ Z l=Kbe the central series of Kand G∈ Z2\Z1. Then the group generated by {G}∪ Z 1is an abelian normal subgroup ofKnot contained in the center Z1=Z(K). By Corollary 3.8, the group Kis imprimitive. Since Giare irreducible nilpotent primitive groups, the subspaces Qiare one- dimensional and Gis similar to a monomial group. /square 3.2 Matrices with p-property LetFbe a field of characteristic zero. Then the field of rationals Qis contained in F. We first show where the definition of the p-property comes from. If every matrix Aof an irreducible matrix group Gis similar to a triangular matrix with diagonal entriesλ1,...,λ r,µ1,...,µ swhere fori/\e}atio\slash=jthe orders of λiandλjare finite numbers without a common divisor and µ1,...,µ sare transcendently independent over Q, then det :G →F\ {0} is a homomorphism of groups with the kernel Kconsisting of unipotent matrices. The normal subgroup Kis then triangularizable by the celebrated Kolchin theorem (Theorem 1.14). In the proof of the main theorem (Theorem 3.1 9) one can see how the triangularizability of Kaffects the triangularizability of G(we use commutativity of the irreducible parts of the group K). The ”invention” of the p-property then does not look so odd, because in the case of p= 2 we want the kernel of det2to be a subgroup consisting of the matrices with eigenvalues 1 a nd−1 (see Theorem 2.8). Clearly in the case of a general pgroup Gwould not be triangularizable (see Examples 2.4). Definition 3.11 Letpbe a prime number and let matrix Abe similar to a tri- angular matrix with diagonal entries λ1,...,λ r,µ1,...,µ s. If fori/\e}atio\slash=jthe orders ofλiandλjare finite with greatest common divisor dividing pandµ1,...,µ sare transcendently independent over Qwe say that the matrix Ahasp-property . We will use this term for a single matrix or a set of matrices all h aving this property. ⋄ 42 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA Let us now introduce the following notation. For an element λ∈Fwith finite multiplicative order, we will denote its order by |λ|, i.e., |λ|= min {t∈N|λt= 1}. Lemma 3.12 Letq∈Nandλ,µ∈F. If the greatest common divisor d(|λ|,|µ|) dividesq, thend(|λq|,|µq|) = 1. Proof. Let us denote |λ|=t,|µ|=u,|λq|=rand|µq|=s. First we determine the numbers rands. It is easy to verify that r=t d(t,q), and similarly s=u d(u,q). Sinced(u,t) dividesq, the numbers sandrare co-prime. This completes the proof. /square For a monomial group there is an epimorphism φ:G →PG, wherePGis the group of all permutation matrices P(see Definition 3.9) associated with the matrices from G. We will often use the notation PA=φ(A). Let us denote Zp={λ∈F|λp= 1}. Lemma 3.13 (1) If detp(A) = 1for a matrix Awithp-property, then σ(A)⊂ Z p. (2) If a monomial matrix A, wherePAis a permutation matrix, given by permutation π, hasp-property, then the permutation πconsists only of transpositions and p- cycles. Ifp= 2then every transposition in πgives us a block with eigenvalues 1 and−1in the matrix A. Ifp >2, then every p-cycle inπgives us a block with eigenvaluesp√ 1in the matrix A, andπhas at most one transposition. Proof. (1) LetAbe a matrix with p-property and detp(A) = 1. Then λp 1· · ·λp rµp 1· · ·µp s= 1 3.2 Matrices with p-property 43 Foro=|λ1| · · ·|λr|we get µo·p 1· · ·µo·p s= 1. Asµ1,...,µ sare transcendently independent, it follows that s= 0. Since by Lemma 3.12 orders |λp 1|,...,|λp r|are co-prime, it is easy to see, using the equation λp 1· · ·λp r= 1, that in fact λp 1=· · ·=λp r= 1 andσ(A)⊂ Z p. (2) Suppose that πcontains a cycle of length n. By permuting the basis we can rearrangeπto include the cycle (123 ...n) and thusAhas the form A=/bracketleftbigg B0 0C/bracketrightbigg , where B= 0· · · · · · 0d1 d2... 0 0d3...... ............... 0· · · 0dn0 . Letλ1,...,λ nbe the eigenvalues of Band denote d=d1· · ·dn. Then we get λn i=d for alli= 1,2,...,n . Ifdis transcendental over Q, thenλiare transcendental and therefore have infinite orders. But on the other hand, λiare algebraically dependent (λn i=λn j) andAdoesn’t have p-property. We can therefore assume that the orders of λiare finite. It follows that d|λi|=λn|λi| i= 1, so that |d|=mdivides |λi|for alli= 1,2,...,n and therefore m∈ {1,p}. Letν be a primitive solution of the equation xmn= 1. Then νnis a primitive solution of the equation xm= 1 and we can write d= (νn)k. Since the order |d|ism, kandmmust be co-prime. Let λbe a solution of the equation xn=d. Then λmn=dm= 1,soλ=νs. Sinceνsn=λn=d=νkn,mdividess−kand therefore s=k+lm,wherelranges over a complete remainder system modulo n. Letr=|λ|. As 1 =λr=ν(k+lm)r,mnhas to divide ( k+lm)r. Askandmare co-prime, m dividesr,r=tmandndivides (k+lm)t. 44 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA Letncontain a prime factor q. Thenq|(k+lm)tfor alll. Ifn>2, there are l1/\e}atio\slash=l2, 0≤l1,l2< nsuch thatqdoes not divide ( k+lim), since otherwise we could find l1,l2such thatqdivides (k+lim) andqdoes not divide ( l2−l1). From this we would getq|(l2−l1)mwhich implies q|mandq|k. This is a contradiction, since k andmare co-prime. From the above we conclude that n= 2 orAhas two eigenvalues with orders containing the prime factor q. This implies q=pthenn=pj. Forj >1 we see from the above that p2dividestwhich is again a contradiction. Thus we have proved that n= 2 orn=p. For the second part of (2) let us first deal with the case p= 2. Ifp= 2, thenn= 2. We have already seen that d2= 1. We have to exclude the possibility d=−1. It is obvious since λ1,2=±√−1 have order 4. Now letp >2 andn=p. Then every solution of the equation λp=dhas order dividingp2. Ifd/\e}atio\slash= 1 then the order of λis neither 1 nor p(asλp=d/\e}atio\slash= 1) so that all the solutions have orders p2which is a contradiction. For the last statement of (2) one can easily verify that every transposition gives an eigenvalue with an even order and therefore only one transpo sition is permitted. /square 3.3 On monomial groups with p-property We restrict our attention now to monomial matrix groups. We s tate some remarks on the previous results connected to this subject. The letter Gwill denote a monomial matrix group with p-property. For a matrix Awe will often make no distinction betweenPAand its associated permutation π. Remark 1. Ifp/\e}atio\slash= 2 and Gcontains a matrix Awith a transposition in its PA, thenPApis a permutation matrix of the transposition and −1∈σ(A). We got the equivalence: PGcontains no transposition ⇔ −1/∈σ(G) Remark 2. By the discussion given below one could see that transpositi ons are possible only in the cases n= 2 orn= 3 withp= 3. In both cases we have examples: 3.3 On monomial groups with p-property 45 Casen= 2: G2=/braceleftbigg/bracketleftbigg a0 0b/bracketrightbigg |(ab)p= 1/bracerightbigg ∪/braceleftbigg/bracketleftbigg 0a b0/bracketrightbigg |(ab)p= 1/bracerightbigg Casen= 3,p= 3: G3=  DP|P∈S3, D= a0 0 0b0 0 0c , abc= 1, a,b,c ∈ Z3   LetG ⊂GLn(F) be irreducible with n >2 andp >2. Assume that PGcontains a transposition. After a conjugation with a suitable permut ation the matrix PG contains the transposition τ= (12). Irreducibility of the group Gimplies transitivity of the permutation group PGand we can find such a matrix Y∈ GthatPY(1)/∈ {1,2}an thus (12)/\e}atio\slash=PYτP−1 Y∈PG. We have found another transposition τ′/\e}atio\slash=τinPG. Ifτandτ′are disjoint we get a matrix with two transpositions in PGwhich is a contradiction. The remaining possibility is that the product ττ′is a 3-cycle which means p= 3. Let us now analyze the case p= 3 andn>3. We can assume that PGcontains the transposition τ= (12) and a permutation πwith 3-cycle (otherwise we would need another disjoint transposition for irreducibility). Afte r a conjugation with a suitable permutation from PGwe can assume that πis of the form (1 bc).... If 2/∈ {b,c}by conjugation with a permutation πwe either get τ′= (b2)∈PG(ifπfixes 2) and (12)(b2) = (12b)∈PGor withτdisjoint transposition τ′which is a contradiction. Thus we can assume that the 3-cycle (123) is contained in PG. SincePGis transitive, we find such a permutation ρ∈PGthatρ(1) = 4. Otherwise the conjugation with ρ would give us a transposition disjoint with τ′and we have ρ(2)∈ {1,2}. Ifρ(2) = 1 thenρ= (142)..., (12)ρ= (14)...and thus (14) ∈PG. We get (14)π= (1234...)... which is a contradiction by Lemma 3.13. As the assumption (14 )∈PGyields a contradiction, in the case ρ(2) = 2 we get ρ= (14j)..., wherej/\e}atio\slash= 1,2. It follows that (12)ρ= (14j2...)... 46 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA which again is a contradiction by Lemma 3.13. We now give a criterion for irreducibility of monomial group s by which one can get irreducibility of the above groups G2andG3. Let us first state a lemma. Lemma 3.14 LetG ⊂Fn×nbe a monomial group with transitive group PGand let V≤Fnbe aG-module. Then there exists a vector v= (v1,...,v n)∈Vwithvi/\e}atio\slash= 0 for alli. Proof. Assume that v= (v1,...,v k−1,0,vk+1,...,v n)∈V. SincePGis transitive there is a vector w∈Vwithwk/\e}atio\slash= 0. Forn∈Nlarge enough the vector nv+w has at least one more nonzero component as the vector v, so we reach the desired vector inductively. /square For a monomial group Gwe denote by DGthe subgroup of all diagonal matrices. Proposition 3.15 LetG ⊂Fn×nbe a monomial group with transitive PG. If the linear span of DGisn-dimensional, then Gis irreducible. Proof. IfD1,...,D n∈DGare linearly independent and v∈Fna vector with nonzero components (provided by Lemma 3.14), then it is easy to check that D1v,...,D nvspan Fn. /square By the Proposition 3.15 the groups G2andG3from Remark 2 are irreducible. Lemma 3.16 LetFbe an algebraically closed field, G ⊂Fn×nan irreducible group andK⊳Gan abelian subgroup such that the quotient G/Kis an abelian group. If n>1, then the group Gis imprimitive. Proof. LetZbe the center of the group G. Since Gis an irreducible group and Fis algebraically closed, we have Z=G ∩F{I}. IfK ⊂ Z , then Gis nilpotent and by Theorem 3.10 monomial. IfK /\e}atio\slash⊂F{I}then by Corollary 3.8 Gis imprimitive. /square LetGbe a matrix group with p-property. Then detp:G →Fis a homomorphism of groups. Let Kdenote the kernel of this homomorphism. By Lemma 3.13 K={A∈ G|σ(A)⊂ Z p}. 3.3 On monomial groups with p-property 47 Proposition 3.17 LetGbe an irreducible monomial matrix group with p-property. Forp>2we assume in addition that matrices in PGare without transpositions (the latter assumption is necessary in the cases described in Rem ark 2.). Then G=K orGis one-dimensional. Proof. IfGis a diagonal matrix group, it is one-dimensional. Thus we as sume thatGcontains some nondiagonal matrices. Then PGis a nontrivial group. Since all elements of PGhave order p, the group PGis ap-group and has nontrivial center Z. IfZcontains a matrix of the form U=/bracketleftbigg I0 0B/bracketrightbigg whereIis the identity matrix and Bis the permutation matrix of the product of disjointp-cycles, it is easy to see that the subspace associated with t he blockIis invariant under G. Though we can find (if we suitably rearrange the basis) a matr ix U∈Zof the form U= C C... C  whereCis the permutation matrix of the p-cycle. One can easily show that every other matrix X∈PGhas the block-form X= X11· · ·X1n...... Xn1· · ·Xnn  withXij=εijCkij,kij≥0 where [εij]i,jis a permutation matrix. Recall the natural homomorphism φ:G →PGand pick a matrix ˜U∈φ−1(U). Since ˜Uconsists of ( p×p)-blocks associated with p-cycles inU, by Lemma 3.13 ˜Ulies in K. IfA∈ Gis a diagonal matrix, A˜Ualso consists of ( p×p)-blocks so A˜U∈ K andA∈ K. AsApis a diagonal matrix for every A∈ G,Ap∈ Kandσ(A)p={1}. IfA /∈ Kwe can find λ1∈σ(A) with |λ1|=p2. Since every p×p-block inAgives us only eigenvalues in Zp, eigenvalue λ1must be on the diagonal part of the matrix A. According to the block-structure of PGwe can assume the following structures 48 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA of matrices A,˜UandA˜U: A= λ1 λ2... λp ... , ˜U= 0· · ·0d1 d2... 0 ...... dp0 ... , A˜U= 0· · · 0d1λ1 d2λ2... 0 ...... dpλp0 ... . By Lemma 3.13 we get λ1d1· · ·λpdp= 1. Asd1· · ·dp= 1, we get λ1· · ·λp= 1 and λp 1· · ·λp p= 1. Since the matrix Ahasp-property, the orders |λ2|,...,|λp|cannot be p2. Thus they are all equal to pand we get λp 1= 1, which is a contradiction. This completes the proof. /square Remark 3. Let us now assume that Gis not necessarily irreducible, where Gis not diagonal. If the center ZofPG, which is again nontrivial, contains a matrix U= C C... C  we proceed as in the proof of Proposition 3.17 to get G=K. Otherwise, we find a matrix U=/bracketleftbigg I0 0B/bracketrightbigg ∈ Z such thatBis a product of disjoint p-cycles. We decompose a matrix M∈PG according to the above block decomposition of U, M=/bracketleftbigg X Y Z W/bracketrightbigg . 3.3 On monomial groups with p-property 49 SinceMandUcommute, we get the condition (B−I)Z= 0. IfZ/\e}atio\slash= 0, we can find a vector efrom the basis such that Be=e which is a contradiction, since Bhas no fixed points in our basis. Similarly we get Y= 0, so the group Gis of the form G=/braceleftbigg/bracketleftbigg X10 0X2/bracketrightbigg |X1∈ G1, X2∈ G2/bracerightbigg , where G1andG2are monomial groups of smaller dimension than G. Now we can see inductively that a monomial group Gwithp-property can be put in the form G=/bracketleftbigg D0 0K/bracketrightbigg , whereDis a diagonal group and σ(K)⊂ Z p. According to the conclusions of Proposition 3.17 we now cons ider the case of an irreducible matrix group G ⊂Fn×nwith prime exponent p. In this case Gis a nil- potent group and is therefore automatically monomial (see T heorem 3.10). Since G is irreducible its degree is a power of p,n=pk. Ifp= 2, then Gis one-dimensional (since it is commutative). What can be said about general p? In Examples 2.4 one can find an example of p-dimensional G. Using tensor product we can construct groups with exponent pand arbitrary degree pk. The following proposition shows that in the case p= 3 andk= 2 this is the only possibility. Proposition 3.18 LetG ⊂GL9(F)be an irreducible matrix group with exponent 3. Then Gis conjugate to a tensor product H ⊗ K , where H,Kare subgroups of the group P3=  DCk|k= 0,1,2, D= a0 0 0b0 0 0c , abc= 1, a3=b3=c3= 1   50 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA and C= 0 0 1 1 0 0 0 1 0 . Proof. The group Gis a monomial group with 3-property. Since PGis a homo- morphic image of the group G, it has exponent 3. From the proof of Proposition 3.17 one can get Pd=C⊗I∈Z(PG) and all the matrices of PGare of the form [εijCkij]i,jwhere [εij]i,jis a permutation matrix whose order divides 3. We conclude that every matrix P∈PGtakes the form P= Ck1 Ck2 Ck3 (I⊗Cl). (1) SincePGis transitive we find a matrix  I Cm Cn ∈PG. After the conjugation with the matrix  I C2m I  we getPc=I⊗C∈PG. AsPd∈PGwe find a matrix X∈ Gof the form X= d1 1 d1 2 d1 3 d2 1 d2 2 d2 3 d3 1 d3 2 d3 3 Pd. 3.3 On monomial groups with p-property 51 FromX3=Iwe getd1d2d3= 1 and thus after the conjugation with the diagonal matrix D= 1 d1 2 d1 2d1 3 1 d2 2 d2 2d2 3 1 d3 2 d3 2d3 3  we assume that Pd∈ G. (Note that a conjugation with a diagonal matrix doesn’t change the associated group PG.) Using (1) we can write every X∈ Gas X= D1Ck1 D2Ck2 D3Ck3 (I⊗Cl) (2) for some diagonal matrices Di. Assume first that l= 1 and denote Ai=DiCki. ThenA3A2A1=I. SinceXPs d∈ G, we see that D3Ck1+sD2Ck2+sD3Ck3+s=I (3) fors= 0,1,2. Let us define an action of the matrix Con the set of diagonal matrices byDC(=CDC−1). Then the condition (3) is equivalent to D3DCm+s 2DCn+2s 3=I (4) wherem=k3andn=k2+k3. If we replace sbys+1 in the equation (4) and then multiply the resulting equation by the inverse of the equati on (4), we get (DC 2D−1 2)Cm+s(DC2 1D−1 1)Cn+2s=I. (5) This implies (DC 2D−1 2)C2s(DC2 1D−1 1)Cn−m=I. (6) HenceDC 2D−1 2is a scalar matrix (1 /ω)Iand thus D2=βD(ω) 52 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA where D(ω) = 1 ω ω2 . From the equation (5) we get D1=αD(ω) and finally from (4) D3=γD(ω). It follows that the associated diagonal matrix DXfor a matrix Xis of the form DX=D(ω)⊗ α β γ . Hence X= (D(ω)⊗ α β γ ) Ck1 Ck2 Ck3 (I⊗C) (7) . Ifl/\e}atio\slash= 1 in the form (2) we multiply the matrix Xwith a matrix of the form (7) and apply our conclusions. It follows that every X∈ Gcan be written as X= (D(ω)⊗ α β γ ) I Cm Cn (Ck⊗Cl) (8) . It is now sufficient to show that 3 divides mandn. Assume otherwise. Since Pd,Pc∈PG, we can take k= 0 andl= 0 and choose A= αD(ω) βD(ω) γD(ω)  I Cm Cn ∈ G wherem,n∈ {1,2}. We can also find a matrix F∈ Gof the form F= δD(ϑ) εD(ϑ) ϕD(ϑ)  I I I . FromF3=Iwe get δεϕ= 1. (9) By Burnside’s theorem (Theorem 1.3) a matrix group G ⊂Fn×nis irreducible if and only if its linear span is Fn×n. The only matrices in Gwhose linear combinations have nonzero entries at places 11 ,22,33 are those of the form X= λD(ψ) µD(ψ) νD(ψ)  I Ck Cl . (10) 3.4 Main theorem 53 As (FA)3=I, we have αβγ(ωϑ)m= 1. (11) Similarly (FA2)3=Iimplies α2β2γ2(ω2ϑ)2m= 1. (12) From equations (12) and (11) then follows ωm= 1,and hence ω= 1. If we take a matrix of the form (10), where m=n= 0, then the matrix AXhas the property established for the matrix Aand thusψ= 1.Since all entries at places 11,22,33 are equal for all matrices in the group G, it is not irreducible which is a contradiction. This completes the proof. /square Remark 4. It is easy to see that in the case of an arbitrary prime number pevery irreducible group G ⊂GLp(F) with exponent pis a subgroup of the group Gp=  DP|D= λ1 λ2... λp , λp i= 1,λ1· · ·λp= 1, P=Cl   whereCis the permutation matrix associated with the cycle (12 ...p). 3.4 Main theorem Theorem 3.19 LetG ⊂Fn×nbe a group of matrices over an algebraically closed fieldFwith characteristic zero. If Ghas2-property, then it is triangularizable. Proof. We can assume that Gis irreducible. We now show that Gis one- dimensional. Let us first show that Gis a monomial group. We have already seen that the natural homomorphism of groups det2:G →F∗ has the kernel K= Ker det2consisting of matrices with eigenvalues 1 ,−1. By Clifford’s theorem (Theorem 3.5) we have a decomposition Fn=L1⊕· · ·⊕Lt, where 54 3 MATRIX GROUPS WITH INDEPENDENT SPECTRA eachLiis an irreducible K-module. Since a group of matrices with eigenvalues 1 ,−1 is triangularizable (see Theorem 2.8), we get dim Li= 1, so Kis diagonalizable and therefore commutative. By Proposition 3.4 there exist syst ems of imprimitivity Fn=Q1⊕ · · · ⊕Qt where the stabilizers GiofQiare primitive irreducible groups. Since Gisatisfy the conditions of the theorem, by the above we can find normal abel ian groups Ki⊳Gi such that Gi/Kiare abelian. Lemma 3.16 implies that dim Qi= 1 and Gis indeed a monomial group. By Proposition 3.17 we know that G=KorGis one-dimensional. In both cases G is commutative and therefore one-dimensional. This comple tes the proof. /square Proposition 3.20 LetGfrom Theorem 3.19 be without Q-transcendent eigenvalues and assume that Ghas already been triangularized. For X∈ Gwe denote by di(X) theithdiagonal entry of the matrix XandDi=di(G). Then for i/\e}atio\slash=jan arbitrary pairλ∈ D iandµ∈ D jsatisfies the condition d(λ,µ)≤2, i.e., the condition on orders holds ”all over” the group G, not just matrix-wise which was the original assumption. Proof. Let us choose X,Y∈ Gwithdi(X) =λ,dj(X) =ν,di(Y) =ϑ,dj(Y) =µ, |λ|=p,|ν|=q,|ϑ|=rand|µ|=s. We already know that for every matrix W∈ Gthe eigenvalues of W2have pairwise prime orders. As Z= (XqYr)2, we getdi(Z) = (λ2)qanddj(Z) = (µ2)r. Since |(λ2)q|=|λ2|,|(µ2)r|=|µ2|, d(di(Z),dj(Z)) = 1, the orders |λ2|and|µ2|are prime, and therefore d(|λ|,|µ|)≤2. /square 55 4 PERMUTATION-LIKE MATRIX GROUPS 4.1 Introduction In previous chapters we discussed various questions of the t ype: Let Gbe a matrix (semi)group and assume that each matrix has a property which reveals the best in some canonical form of this matrix (in our cases we considere d the upper triangular form). Can all matrices of Gbe simultaneously put in this form, i.e., can we find an invertible matrix S∈Cn×nsuch that for all X∈ Gthe matrix SXS−1is in this canonical form? In this chapter we discuss this question for permutation mat rices. Definition 4.1 LetG ≤ Cn×nbe a finite group of matrices. If every X∈ Gis similar to a permutation matrix, then Gis called a permutation-like group . ⋄ The central question: Is a permutation-like group equivalent to a group of per- mutation matrices, i.e., can we find an invertible matrix S∈Cn×nsuch that for all X∈ Gthe matrix SXS−1is a permutation matrix? In Section 4.2 we familiarize ourselves with the topic by giv ing various exam- ples of permutation-like groups. These examples shows us th at the answer to this question is not always affirmative. The counterexamples that we construct lead us to the additio nal assumption that the group Gcontains a maximal cycle , i.e., a matrix Ccorresponding to the cycleγ= (123...n)∈Sn. We can choose a basis B={f0,f1,...,f n−1}, in which Ctakes the form C= 1 0 0 · · · 0 0λ... 0 0...λ2...............0 0 0 · · · 0λn−1 , whereλis a primitive n-th root of the unity. Under this assumption the only possibl e commutative permutation-like group is the cyclic group G= which is clearly equivalent to a group of permutation matric es. This is shown in Proposition 4.11. 56 4 PERMUTATION-LIKE MATRIX GROUPS In Section 4.3 we prove that Sylow p-subgroups of a permutation-like group G ⊂ Cn×nforp >n 2are cyclic which coincides with the property of such Sylow subgroups of the symmetric group Sn(consider the order of Sn). A useful object that we investigate in Section 4.4 is the normalizer N( ). If nis a prime number, the subgroup N( ) is equivalent to a group of permutation matrices, by Theorem 4.15. The complete analysis of the cases n= 2,3 is given in Section 4.5. In Section 4.6 we consider the cases n= 4,5. In the case n= 4 the answer to the main question is affirmative provided that the group Gcontains a maximal cycle. The first example of Section 4.2 shows the opposite if a maxima l cycle is absent. At the end we show that every permutation-like group G ⊂C5×5is equivalent to a group of permutation matrices. Forn≥6 examples from Section 4.2 show that for an affirmative answer we have to add some assumptions. One of possible conjectures wo uld be: Conjecture: A permutation-like group G ⊂ Cn×ncontaining a maximal cycle is equivalent to a group of permutation matrices. This problem turns out to be more difficult as it seemed, so that with the pre- sent tools we managed to give the complete answer only for n≤5. In the sequel we will use the next notation. Let α1≥α2≥ · · · ≥αk>1 and α1+α2+· · ·+αk≤n. Then the multiindex α= (α1,α2,· · ·,αk) determines the cyclic structure of a permutation from the symmetric group Sn. According to this we denote by Cα⊂ Gthe subset of all matrices in Gthat are similar to the permu- tation matrix associated with α. Additionally, we define C0={I},C0 α=Cα∪ C0, and bymαwe denote the cardinality of Cα. It is the well-known fact that every finite group is equivalen t to a group of unitary matrices, so we can assume in the sequel that our group consis ts of unitary matrices. 4.2 Examples 57 In [1] we find the next proposition which turns out to be very us eful for our problem. Proposition 4.2 If the sum of all the matrices from some finite matrix group G ⊂ Cn×nis nonzero, then all the matrices from Ghave a common fixed point, i.e., there exists a non-zero vector e∈Cnsuch that Xe=e for allX∈ G. Proof. Let S=/summationdisplay X∈GX/\e}atio\slash= 0 be the sum of all the matrices in G. Then we find a vector fsuch thate=Sf/\e}atio\slash= 0. SinceGis a group, for X∈Gwe haveXS=Sand therefore Xe=XSf=Sf=e. /square 4.2 Examples We first show that the answer to the central question is negati ve in general. Example 4.3 Letm≥l >1. There is a permutation-like group G ⊂F2m×2msuch that it contains a cycle of length 2l−1(C2l−1/\e}atio\slash=∅) and is not equivalent to a group of permutation matrices. Proof. Letn= 2mandN= 2lbe even numbers with m,l> 1 andωa primitive root of degree N−1. Fori∈Zwe define Bi=/bracketleftbigg ωi ω−i/bracketrightbigg and T0=/bracketleftbigg 0 1 1 0/bracketrightbigg . 58 4 PERMUTATION-LIKE MATRIX GROUPS We construct matrices C,T∈Cn×n C= I B0... Bl−1  and T= T0... T0 , whereIis the (n−N)×(n−N) identity matrix. Then the matrix Ccorresponds to an (N−1)-cycle and the matrix Tto a product of mdisjoint transpositions. Since TC=C−1T, every element of group G, generated by the matrices TandC, is either of the form TCkorCk. It is easy to see that the matrices of the form TCkcorrespond to a product of mdisjoint transpositions, while the matrices Ckare similar to powers of a cycle of length ( N−1). Therefore Gis indeed a permutation-like group. Suppose that Gis equivalent to a group of permutation matrices, where Tcor- responds to the permutation σandTCto the permutation σ′. We have already mentioned that each of σandσ′is a product of mdisjoint transpositions. The productT·(TC) =Cthen corresponds to the product σσ′and is on the other hand clearly similar to a ( N−1)-cycleγwhich has an odd number of fixed points. Let a be a fixed point of the cycle γ. Since the permutations σandσ′have no fixed points, σ′must contain a transposition ( ab). Sinceais a fixed point of the product σσ′, it follows that σ(b) =a. This yields that σcontains the transposition ( ba) which forcesbto be another fixed point of the product σσ′. Therefore fixed points of the productσσ′appears in pairs and thus the number of them is even. Since γhas odd number of fixed points, this is a contradiction and Gis not equivalent to a group of permutation matrices. /square Permutation-like groups of exponent 2: LetGbe a permutation-like group of involutions, i.e., X2=Ifor every matrix X∈ G. This assumption implies that Gis a commutative group and each of its matrices is similar to a product of disjoint transpositions . 4.2 Examples 59 Consider first a pair of commuting permutations τ,σ∈Snunder the assumption that both of them are products of disjoint transpositions. W e assume that τconta- ins the transposition (12). If 1 and 2 are fixed points of σ, orσalso contains (12), we can restrict ourselves to the set {3,4,...,n }. In the remaining case let σcontain a transposition (1 a) witha/\e}atio\slash= 1,2. We get (τσ)(a) = 2. The transposition (2 a) is therefore contained in τσ=στ. From τ(a) =b/\e}atio\slash= 2 we get σ(b) =σ(τ(a)) = 2 which yields that σcontains the transposi- tion (2b). Therefore for some a/\e}atio\slash=bwe have τ= (12)(ab)· · · and σ= (1a)(b2)· · ·. We conclude that the transpositions from τandσthat intersect, but are not equal, appear in pairs which will be called the conjugated pairs . We notice that the conju- gated pairs commute and their product is the third remaining conjugated pair. We have proved the following lemma. Lemma 4.4 Letσandτbe permutations of order 2, where the disjoint transpositi- onsP1,P2,...formσand the disjoint transpositions Q1,Q2,...formτ. We interpret a transposition T= (ab)also as set {a,b}. Permutations σandτcommute if and only if for each Piwith property ∅ /\e}atio\slash=Pi∩Qj/\e}atio\slash=Pi, for somej, there exist transpositions PkandQlsatisfying the condition Pi∪Pk=Qj∪Ql. Example 4.5 Forn≥8there exists four generator group G ⊂Fn×nof exponent 2, which is not equivalent to a group of permutation matrices. Proof. LetA0,B0,C0,D0∈ G ⊂ C8×8be the diagonal matrices with the diagonals d(A0) = (−1,−1,−1,−1,1,1,1,1), 60 4 PERMUTATION-LIKE MATRIX GROUPS d(B0) = ( 1,−1,−1,−1,−1,1,1,1), d(C0) = ( 1,1,−1,−1,1,1,1,1) and d(D0) = ( 1,1,1,−1,−1,1,1,1). We define the diagonal matrices A,B,C,D ∈ G ⊂ Cn×n, A=A0⊕I1⊕(−I2), B=B0⊕I1⊕(−I2), C=C0⊕I1⊕(−I2) and D=D0⊕I1⊕(−I2), whereI2is the identity matrix of degree m= [(n−8)/2] andI1is the identity matrix of degree n−8−m. It is easy to verify that Gis a permutation-like group of exponent 2. Suppose that Gis equivalent to a group of permutation matrices, where matricesA,B,C,D correspond to the commuting permutations α,β,γ,δ , respecti- vely. Clearly the number of′−1′on the diagonal of each of the matrices is equal to the number of the disjoint transpositions that form the corr esponding permutation. The permutations αandβare therefore products of 4 + mdisjoint transpositions, while the permutations γandδconsist ofm+ 2 disjoint transpositions. We assume that α= (1,2)(3,4)(5,6)(7,8)(9,10)· · ·(8 + 2m−1,8 + 2m). Sinceα,β,γ andδcommute, Lemma 4.4 implies that in the case n= 8 + 2m+ 1 the pointnis fixed also by β,γandδ. Therefore we restrict ourselves to the case of even degree n= 8 + 2m. For the product ABcorresponds to a product of two disjoint transpositions, permutation βcontainsm+2 transpositions from αand one conjugate pair of the transpositions from α. By symmetry we can assume that β= (1,2)(3,4)(5,7)(6,8)(9,10)· · ·(8 + 2m−1,8 + 2m). The permutation γis a product of m+ 2 disjoint transpositions and each of the permutations αγandβγis a product of two disjoint transpositions. If γcontains 4.2 Examples 61 some conjugate pair form α, the product γαhas at least four disjoint transpositions. Therefore the set of the transpositions forming γis contained in the set of the transpositions forming α. In the same fashion we conclude that the set of the transpositions forming γis contained in the set of the transpositions forming β. It follows that γ= (1,2)(3,4)(9,10)· · ·(8 + 2m−1,8 + 2m). Since the matrix BDcorresponds to a product of two disjoint transpositions, pe r- mutationδcontains exactly m+ 2 transpositions from β. Therefore we get δby ’erasing’ two transpositions, say T1inT2, fromβ. Let us denote Γ ={(1,2),(3,4),(9,10),...,(8 + 2m−1,8 + 2m)}. We show that we cannot choose δsatisfying the above conditions. 1. Suppose that T1= (5,7) (orT1= (6,8)). Since αandδcommute we get T2= (6,8) (orT2= (5,7)). Thenαδ= (5,6)(7,8) which is a contradiction, as ADcorresponds to a product of four disjoint transpositions. 2. In the remaining case we have T1,T2∈Γ. This yields δ= (5,7)(6,8)P1P2· · ·Pm, wherePiare from set Γ, i.e.,the set of the transpositions forming pe rmutation γ. Then the product δγcontains four disjoint transpositions which again is a contradiction since CDcorresponds to a product of two disjoint transpositions. /square Proposition 4.6 Every permutation-like group isomorphic to Klein quadrupl e is equivalent to a group of permutation matrices. Proof. In this case Gis the group of exponent 2, generated by two matrices. Let us write the block decomposition of the two generators of G A=−I1⊕ −I2⊕I3⊕I4andB=−I1⊕I2⊕ −I3⊕I4, (blk) 62 4 PERMUTATION-LIKE MATRIX GROUPS whereI1,I2,I3andI4are the identity matrices of dimensions k,k′,landl′=n− k−k′−l, respectively. Suppose that the matrix Ahas the smallest trace in the group Gand that the number of ’ −1’ on the diagonal of Aisd. Thenk+l≤dand l≤d/2, since otherwise ABwould have smaller trace than A. We now describe the construction of the permutations α,β∈Sncorresponding to the matrices AandB. Decompose the standard basis of Cninto the sets N1,P1, N2,P2corresponding to the block decomposition (blk). Then N2has the smallest cardinality among the given sets. For 1 ≤i≤lwe form the quadruple Qiconsisting ofi-th vector from N1,i-th vector from P1,i-th vector from N2andi-th vector from P2. It is easy to see that the restriction of Aonto the span CQican be represented by a pair of disjoint transpositions and Bwith the conjugated pair. Therefore for everyiwe attach a pair of disjoint transpositions into αand the conjugated pair intoβ. Finally we join the remaining vectors of the basis into such pairsDjthatA acts on the span CDjas transposition while Brestricted onto CDjeither coincides withAor acts as the identity. It the first case we add the same transp osition to both permutations αandβwhile in the later case we add a new transposition only to the permutation α. This way we get a desired pair of commuting permutations, so t hatGis equivalent to a group of permutation matrices. /square Example 4.7 (T. J. Laffey) Forn≥6there is a permutation-like group iso- morphic to the quaternion group, which is not equivalent to a group of permutation matrices. Proof. LetIbe the identity matrix of dimension n−6. The following representa- tion of the quaternion group Q={±1,±i,±j,±k}consists of matrices individually similar to some permutation matrices. M(i) = −1 0 0 1 −i0 0i 1 0 0 1 I  4.3 Sylow subgroups in a permutation-like group 63 M(j) = −1 0 0 1 0 1 −1 0 0 1 1 0 I  M(k) = 1 0 0 1 0−i −i0 0 1 1 0 I  The group G ⊂Cn×ngenerated by the matrices M(i),M(j) andM(k) is a permutation- like group isomorphic to the group Q. Suppose that Gis equivalent to a group of permutation matrices. Then from the spectra of the matrices we conclude that M(i) corresponds to a 4-cycle, say γ1= (1234),M(j) corresponds to a disjoint product of a 4-cycle, say γ2, and a transposition, say τ2, whileM(k) corresponds to a 4-cycle, sayγ3. Sincei2=j2the cyclesγ1andγ2act on the same set {1,2,3,4}. It follows that the product γ1γ2τ2, corresponding to ij=k, contains a transposition τ2, which is not possible since the matrix M(k) corresponds to a 4-cycle. /square 4.3 Sylow subgroups in a permutation-like group In this section we show that for p >n 2the Sylowp-groups of a permutation-like group are cyclic, which is also the case in the symmetric grou pSn. We use the well-known facts which can be found in [23, p. 78-80]. Lemma 4.8 LetG ⊂Cn×nbe a permutation-like group, p≤na prime number and H ⊂ C0 pa nontrivial subgroup of G. Then His a cyclic group. Proof. SinceHis a nontrivial group, we can choose a basis for Cnsuch that H contains a matrix of the form A= I ω ω2 ... ωp−1 , 64 4 PERMUTATION-LIKE MATRIX GROUPS whereω∈Cis a primitive p-th root of the unity and Ithe identity matrix of order n−p+ 1. Let us write an arbitrary matrix X∈H\ in the form X= Y∗ ∗ ∗ ∗x1∗ ∗ ∗ ∗...∗ ∗ ∗ ∗ xp−1 . We first show that x1=· · ·=xp−1= 0. (zeros) Let us denote y= tr(Y). Fork= 0,1,...,p −1 we haveAkX∈ Cpwhich gives us the system of linear equations tr (AkY) =y+ωkx1+ω2kx2+· · ·+ω(p−1)kxp−1=n−p, having the unique solution, namely y=n−pandx1=· · ·=xm−1= 0. SinceHis ap-group and has nontrivial center, we may assume that the matr ixA commutes with all the matrices from H. Pick a matrix X /∈ and decompose the matrices AandXin the fashion A=/bracketleftbigg I D/bracketrightbigg andX=/bracketleftbigg X1X2 X3X4/bracketrightbigg , where D= ω ω2 ... ωm−1 . Since the matrices AandXcommute, we get X2=X2D,DX3=X3andDX4= X4D. As 1 is not an eigenvalue for D, it follows that X2= 0 andX3= 0. AsDis a diagonal matrix with pairwise different diagonal entries, X4is a diagonal matrix. By (zeros) the diagonal entries of X4are zero, therefore X4= 0. The matrix Xis then singular which is a contradiction. Therefore H= is indeed a cyclic group. /square 4.4 Permutation-like groups with maximal cycles 65 Corollary 4.9 LetG ⊂Cn×nbe a permutation-like group, p >n 2a prime number andS ≤ G a Sylowp-subgroup of G. Then: (a) The group Sis a cyclic group of order pgenerated by some A∈ Cp. (b) The group Ghas order |G|=p·l, wherepdoes not divide l. Proof. (a) Sincep>n 2, we haveS⊂ C0 pand so we can use (b) from Lemma 4.8. (b) This is a basic fact following from Sylow’s theorems (see [1]). /square 4.4 Permutation-like groups with maximal cycles In this section we consider permutation-like groups G ⊂Cn×ncontaining a maximal cycle, i.e., a matrix C∈ Cn. IfGis a permutation-like group, the sum of its matrices cannot be zero since the traces of all the matrices are nonneg ative and the identity matrixI∈ Ghas positive trace. Therefore by Proposition 4.2 we can writ e G= 1⊕ G′. We can choose a basis B={f0,f1,...,f n−1}in whichCtakes the form C= 1 0 0 · · · 0 0λ... 0 0...λ2...............0 0 0 · · · 0λn−1 , (dia) whereλis a primitive n-th root of the unity. In the same basis we have G= 1⊕ G′, since the elements of the basis Bare unique up to the scalar factors. Lemma 4.10 Let{f0,f1,...,f n−1}be a basis in which a maximal-cycle matrix C takes the form (dia) and let e=n−1/summationdisplay i=0βifi. Then the set B={Cke|k= 0,1,...n−1} is a basis of the space Cnif and only if βi/\e}atio\slash= 0for alli. 66 4 PERMUTATION-LIKE MATRIX GROUPS Proof. It is clear that the set Bis linearly dependent if some βiis zero. We assume that all the coefficients βiare nonzero. From n−1/summationdisplay j=0γjCje= 0 we get n−1/summationdisplay i,j=0βiγjCjfi=n−1/summationdisplay i,j=0βiγjλijfi= 0. Since the coefficients at fivanish for all i, we conclude that n−1/summationdisplay j=0λijγj= 0. This is possible if and only if all γjare zero coefficients. /square Remark: The matrix Ctakes its ’classical’ permutation form in a basis B C= 0· · · · · · 0 1 1... 0 0........................ 0· · · 0 1 0 (cyc) if and only if the basis Bis given asB={Cke|k= 0,1,...n−1}for somee∈Cn. We now show that every commutative permutation-like group c ontaining a maxi- mal cycle is equivalent to a group of permutation matrices. Proposition 4.11 LetGbe a commutative permutation-like group containing a maximal cycle C. Then G=. Proof. Letλ∈Cbe a primitive n-th root of unity and pick any X∈ G. AsC has no multiple eigenvalues and Xcommutes with C,Xis a circulant, i.e., X=p(C), for some polynomial p(x) =a0+a1x+· · ·+an−1xn−1. Since each matrix from Gis similar to a permutation matrix, for every k≤n−1 we have nak= tr (C−kX) =mk, 4.4 Permutation-like groups with maximal cycles 67 wheremk≤nare nonnegative integers. It follows that ak=mk n≥0. AsXis a unitary matrix, we get a0+a1+...+an−1=|p(1)|= 1 = |p(λ)|=|a0+a1λ+...+an−1λn−1|. It is easy to see that this is only possible in the case where al= 1 for some l, while fork/\e}atio\slash=lwe haveak= 0. Therefore G={I,C,C2,...,Cn−1}, and it is clearly equivalent to a group of permutation matric es. /square Recall that the multiplicative group Zn={λk|k∈Z}is isomorphic to the cyclic groupZn={0,1,...,n −1}. This group affords the structure of a commutative ring which is a field if nis a prime number. LetCbe a maximal cycle in a permutation-like group GandX∈ G\< C > a matrix with property XC=CkX,or equivalently XCX−1=Ck. ThereforeCandCkare similar matrices which means that Ckalso represents a maximal cycle. This is possible if and only if kis a unit of the ring Zn. Lemma 4.12 LetX∈ Gbe a matrix satisfying XC=CkX, for some unit k/\e}atio\slash= 1of the ring Znand letl=k−1be its inverse. Then π(i) =il defines a permutation on the set Zn. Let π=γ0·γ1· · ·γr be a disjoint cycle decomposition for πand choose a basis in which Ctakes the form (dia). Then Xis a monomial matrix of the form X=D0P0⊕D1P1⊕ · · · ⊕DrPr, whereDiare diagonal matrices and Pithe permutation matrices corresponding to the cyclesγi. The multiplicative order of lcoincides with the order of the permutation π. 68 4 PERMUTATION-LIKE MATRIX GROUPS Proof. Letf0,f1,...,f n−1be a basis such that Chas the form (dia). From (λk)l=λit follows that CkXfi=XCf i=λiXfi= (λil)kXfi, therefore we find a scalar αsuch that Xfi=αfil, (mon) since the eigenvalues 1 ,λk,λ2k,...,λ(n−1)kof the matrix Ckare distinct. The multi- plication by ldefines a permutation πon the setZn={0,1,...,n −1}which fixes 0. Letobe the multiplicative order of element l. The group {1,l,l2,...,lo−1}acts on the setZn, while the ’ordered’ orbits of this action are exactly the di sjoint cycles of π. Since the length of each orbit divides the degree of the acti ng group, we have π=γ0·γ1· · ·γr, whereγiare the cycles of lengths dividing o. It follows that πo=id. The cycle corresponding to the orbit containing 1 has clearl y lengthowhich implies thatois exactly the order of the permutation π. LetPibe the permutation matrix associated with the cycle γi. Then the permutation matrix Pcorresponding to the permutation πhas the form P=P0⊕P1⊕ · · · ⊕Pr. By (mon) matrix Xis monomial and we can write it as X=D0P0⊕D1P1⊕ · · · ⊕DrPr. /square Lemma 4.13 Let X= 0· · · · · · 0a1 a2... 0 0a3...... ............... 0· · · 0an0 ∈Cn×n 4.4 Permutation-like groups with maximal cycles 69 be a matrix similar to a permutation matrix P. Then we can choose a basis such thatPis equal toCin the form (cyc). If we define Q= µ1 µ2 ... µn , with µi=1 a1a2· · ·ai, it holds QXQ−1=C. Proof. We can write X=DC, whereDis a diagonal matrix with the diagonal entries (a1,a2,...,a n). Writea=a1a2· · ·an. Then the matrix Xhas the spectrum σ(X) ={z∈C|zn=a}. SinceXis similar to a permutation matrix, its spectrum contains 1, and soa= 1. It follows that the matrix Xis indeed similar to C. Fora= 1 we get µn= 1 and thereforeQXQ−1=C. /square Corollary 4.14 Letnbe a prime number, G ⊂ Cn×na permutation-like group containing a maximal cycle C, and letX∈ G\ be a matrix satisfying XC=CkX for somek∈N. Then there exist a basis Bdiaand a basis Bcycin whichXtakes the permutation form, while Chas the form (dia) in the basis Bdiaand the form (cyc) in the basisBcyc. In the basis BdiaXcorresponds to the permutation on Zngiven by the multiplication with k−1, while in the basis Bcycit corresponds to the multiplication byk. The order oof the element kis equal to the order of the permutation matrix Xwhich is a product of, say p, disjoint cycles of length oand p·o=n−1. We can express the basis Bcycin the form Bcyc={e,Ce,C2e,...,Cn−1e}for some e∈Cn. 70 4 PERMUTATION-LIKE MATRIX GROUPS Proof. SinceC/\e}atio\slash=Iwe havek/\e}atio\slash= 0. Ifk= 1 the group is commutative; therefore by Proposition 4.11 it follows that X∈ which is a contradiction. Asnis a prime number, each k/\e}atio\slash= 0 is a unit of the field Znand the group of units Z∗ nis a cyclic group. Let us write l=k−1and denote by othe order of lwhich is clearly equal to the order of k. By Lemma 4.12 it follows that the multiplication bylis a permutation π=γ0·γ1· · ·γron the setZnhaving the fixed point 0. We can assume that γ0= (0). Since Z∗ nis a group, it is easy to see that all the cycles γ1,...,γ rhave length o. Choose a basis Bin whichCtakes the form (dia) and G= 1⊕ G′. By Lemma 4.12 we can write Xas X= 1⊕D1P1⊕ · · · ⊕DrPr. SincePicorresponds to the cycle γi, it holds (Pi)o=I, and therefore (Xo)′= (detD1)I⊕(detD2)I⊕ · · · ⊕ (detDr)I, whereIis the identity matrix of dimension o×o. AsXois a diagonal matrix, it commutes with Cand therefore by Proposition 4.11 we have Xo=Cs. From the block (detD1)Iof the matrix ( Xo)′we see that det D1=λs=λlsand therefore s=lswhich yields s= 0. We have proved that Xo=I, or detDi= 1 for all i. By Lemma 4.13 we can transform the matrix DiPiintoPi using a diagonal similarity. Therefore there exists a diago nal similarity of the matrix Xand the matrix P=P0⊕P1⊕· · ·⊕Pr. Since a diagonal similarity doesn’t change diagonal matrix C, the new basis satisfies the conditions for Bdia. Let us write Bdia={f0,f1,...,f n−1}. Then for e=f0+f1+· · ·+fn−1we have Xe=e, while the set B={Cie|i= 0,1,...n−1}is a basis by Lemma 4.10. Since X(Cie) =CkiXe=Ckie, Xis a permutation matrix, therefore the basis Bcan be taken as Bcyc. /square Theorem 4.15 (Normalizer theorem )Letnbe a prime number, G ⊂ Cn×na permutation-like group containing a maximal cycle C, and N=N(< C > )the 4.4 Permutation-like groups with maximal cycles 71 normalizer of the group . Then in a suitable basis Nconsists of permutation matrices. If N /\e}atio\slash=< C > the group Nis generated by Cand some matrix X0∈ N\ , therefore all the elements X∈ Nare of the form X=CrXs 0. The matrix X0corresponds to a product of disjoint cycles of length o, whereodivides n−1. Proof. For arbitrary X∈ N there is a uniquely determined k∈Z∗ nwith the propertyXCX−1=Ckwhich is equivalent to the already mentioned relation XC= CkX. PickX1,X2∈ N. Then fori= 1,2 we getXiCX−1 i=Ckifrom what follows X1X2C=Ck1k2X1X2,soZ∗ nis in fact a homomorphic image of the group N. Let X0∈ N\ be an element with the maximal order oand X0C=CkX0. Let forX∈ N\ beXC=ClX. We write ofor the order of kandrfor the order ofl. By the choice of X0we haver≤o. SinceZ∗ nis a cyclic group with the orderm=n−1, we getk=ap, wherel=aq. Then o=m d(p,m) and r=m d(q,m). We investigate the condition l=kt(1), which is equivalent to the condition aq=apt(1′). The equation (1′) is satisfied if and only if q−ptis divisible by m. Sinceo≥r, we getd=d(p,m)≤d(q,m) and therefore we can write m=m′d,p=p′dandq=q′d. Now (1′) holds if and only if q′−p′tis divisible by m′. Asm′andp′have no common divisor, we can find numbers tandusuch thatq′=p′t+m′uwhat confirms our 72 4 PERMUTATION-LIKE MATRIX GROUPS hypothesis. We denote by P(σ) the permutation matrix associated with a permutation σ. Letπ be the permutation on the set Zncorresponding to the multiplication by k−1. Pick a basisBdiasuch thatChas the form (dia) and X0=P(π). Then we have X=DP(σ), whereσis the multiplication by l−1=k−tandDa diagonal matrix. By (1) we get σ=πt. It follows that P(σ) =P(π)t=Xt 0, and therefore D=XX−t 0∈ N. In the basis Bdiaall the diagonal matrices of Nare contained in < C > , and so X∈ NX0⊂ Nwhat implies N ⊂. If we choose a basis Bcyc, where matrices CandX0are both permutation matrices, then the group Nconsists of permutation matrices. By Corollary 4.14 we get t he last claim of our theorem. /square 4.5 Cases n= 2,3 Recall that Cαdenotes the set of matrices from a permuation-like group cor respon- ding to the permutation with cyclic structure given by multi indexα. Case n=2: We assume that Gis not a trivial group. It this case each nonidentity matrix corresponds to a transposition. For all X∈ Gwe haveX2=I. Therefore G is an abelian group and by Proposition 4.11 it is equivalent t o a group of permuta- tion matrices. Case n=3: Proposition 4.16 LetG ⊂C3×3be a permutation-like group. Then Gis equivalent to a group of permutation matrices. 4.6 Cases n= 4,5 73 Proof. The group Gis the union of the sets C3,C2andC0. Suppose that C3/\e}atio\slash=∅. Since 3>3 2, the order of Gcan be written in the form |G|= 3·2l by Corollary 4.9. If C2=∅, we get |G|= 3 and G=. IfC2=∅, it follows from Corolary 4.9 that |G|= 6.LetS= be a Sylow 3-subgroup for some C∈ C3. Since the number 1 + 3 kof Sylow 3-subgroups divides the order |G|, we getk= 0. It follows that Sylow subgroup is a normal subgroup of G. Therefore G=N( ) is equivalent to a group of permutation matrices by Theorem 4 .15. In the case C3=∅the group G=C0 2is either trivial or G= for someT∈ C2. /square 4.6 Cases n= 4,5 Some tools for the case Cn/\e}atio\slash=∅ LetG ⊂ Cn×nbe a permutation-like group and let C∈ Cnbe a maximal cycle. Choose a basis in which Chas the form (cyc). Since all the matrices from Ghave a common fixed point and each fixed point of the matrix Chas to be a scalar multiple of the vector e0= [1,...,1]T for each matrix X∈ G, we haveXe0=e0. Therefore for arbitrary iwe get n/summationdisplay k=1xik= 1. (row) For an integer kwe define sk(X) = tr (CkX). Then n−1/summationdisplay k=0sk(X) =n/summationdisplay i,j=1xij, 74 4 PERMUTATION-LIKE MATRIX GROUPS and the property (row) implies n−1/summationdisplay k=0sk(X) =n. (sum) Since in permutation-like groups each matrix Yis similar to its inverse Y−1, it follows that s−k(X−1) = tr (C−kX−1) = tr (XCk) = tr (CkX) =sk(X) IfX∈ C2,2,...,2, i.e.,Xis a matrix satisfying X2=IorX−1=X, we get sk(X) =s−k(X). (sym) Let the cyclic group act on Gby the left multiplication, and write O(X) for the orbit of X∈ G. Then O(X) ={X,CX,C2X,...Cn−1X}. If we choose a fixed point of the group Gas the first vector of our basis, each subgroup H ≤ G decomposes as H= 1⊕ H′. According to this we write the matrix X∈ GasX= 1⊕X′and for an integer k we define reduced traces by s′ k(X) = tr((CkX)′) =sk(X)−1. Since the fixed point of Cis determined up to a scalar multiple, the group G′is without fixed points, which gives us /summationdisplay X∈Gs′ 0(X) = 0, (sumg) by Proposition 4.2. Let GSbe the subgroup of the ’even’ (meant as similar to a permutation matrix associated with an even permutation) ma trices in G, andGLbe the subset of the ’odd’ matrices. If nis an odd number, the matrix Ccorresponds to 4.6 Cases n= 4,5 75 an ’even’ permutation and therefore the group G′ Shas no fixed point. By Proposition 4.2 it follows that/summationdisplay X∈GSs′ 0(X) = 0 (evn) and consequently/summationdisplay X∈GLs′ 0(X) = 0. (odd) ForX∈ Gwe denote the unordered list of its traces by Tr(X) = [s0(X),s1(X),...,s n−1(X)] and the ordered list of its traces by Tr(X) = (s0(X),s1(X),...,s n−1(X)). The properties (sum) and (sym) will in some cases help us to re duce the possibilities for the lists Tr(X) and Tr(X). Case n=4: LetG ⊂C4×4be a permutation-like group containing a maximal cycle C∈ C4. The set of the ’even’ matrices is then the union of sets C3,C2,2andC0, while the set of the ’odd’ matrices splits into the sets C4andC2. Let us write the table of the traces in the group G TYPE C2C2,2C3C4 s0 2010 s′ 0 1-10-1 Table 1 Property (sumg) in this case implies 3 +m2−m2,2−m4= 0, (sum′) wheremαdenotes the cardinality of the set Cα. Let us denote C′ 2,2=C2,2\< C > andC′ 4=C4\< C > and consider the lists Tr(X) and Tr(X) for a chosen matrix Xknowing that the matrices XandCXhave different parity. 76 4 PERMUTATION-LIKE MATRIX GROUPS 1)X∈ C2: We have s0(X) = 2 and by (sym) s1(X) =s3(X). If the list Tr(X) contains 1, then Tr(X) = (2,1,0,1), (T1) otherwise Tr(X) = (2,0,2,0). (T2) We join the matrices of the type (T1) into the set C(1) 2and the matrices of the type (T2) into the set C(0) 2. 2)X∈ C′ 2,2: In view of (sym), the only possibility in this case is Tr(X) = (0,2,0,2). 3)X∈ C3: Sinces0(X) = 1 andCXis an odd matrix, we can exclude the possibility that Tr(X) = (1,1,1,1). Therefore our list contains 2 and the orbit of Xcoincides with the orbit of an element from C2. This gives us Tr(X)∈ {(1,2,1,0),(1,0,1,2)}. 4)X∈ C′ 4: Ass0(X) = 0 the list Tr(X) contains 2. Since CX,C3X∈ GS, we get s1(X),s3(X)≤1 and Tr(X) = (0,1,2,1). We construct the table of the orbits in the following fashion. The column under a chosen type (given in the first row) shows the numbers of elem ents of the given type (in the first column) contained in the orbit. For instanc e, the orbit of a matrix X∈ C3(5thcolumn) contains 1 element from C2, 2 elements from C3and 1 element fromC4. TYPE C(0) 2C(1) 2C′ 2,2C3C′ 4 C2 2 1 211 C2,2 2 2 C3 2 22 C4 1 11 Table 2 4.6 Cases n= 4,5 77 Lemma 4.17 LetG ⊂C4×4be a permutation-like group containing a maximal cycle C. LetS⊂ GSbe a Sylow 2-subgroup in the ’even’ part GSofG, andX1∈S. Then one of the following cases occurs: (1) The group Shas order 2and G=. (2) The group Scan be written as SC={X1,X2,X3=X1X2,I}, whereX2∈ C2,2is a matrix commuting with X1=C2. The set SG={C,C3,CX 2,CX 3,X1,X2,X3,I} is a Sylow 2-subgroup in G, and we have C2,2={X1,X2,X3}. (3c22) Proof. The Sylow 2-subgroup Sof the group GSis contained in C0 2,2, and therefore for allX∈Swe getX2=Iwhich implies that Sis a commutative group. (1) Assume that |S|= 2 and C3/\e}atio\slash=∅. By Corollary 4.9 the Sylow 3-subgroups have order 3 and we have |GS|= 6. The number 1 + 3 kof Sylow 3-subgroups divides |GS|from what follows that k= 0 andm3= 2. As 6 = |GS|=m3+m2,2+ 1, we havem2,2= 3 and by applying (sum’) we get m2=m4. The group GSis a normal subgroup with index 2 in G, therefore |G|= 12 and the number of the ’odd’ matrices ism2+m4= 6. This gives us m4= 3 and C4={C,C3,Z}for someZ∈ C4\ . ThenZ/\e}atio\slash=Z3∈ C4and therefore Z3∈< C > , from what follows Z∈< C > . This is a contradiction which means that C3=∅, |GS|= 2 and |G|= 4 = | |. It follows that G=. 78 4 PERMUTATION-LIKE MATRIX GROUPS (2) Let |S| ≥4 and pick a matrix X1∈S,X1/\e}atio\slash=I. SinceSis a commutative group of matrices, it can be transformed by a common similarity int o a diagonal group of matrices with X1=/bracketleftbigg I0 0−I/bracketrightbigg , (∗) whereIis the identity matrix of dimension 2 ×2. Each nonidentity matrix in Sis a diagonal matrix whose diagonal is the unordered quadruple [ 1,1,−1,−1]. It is easy to see that the only possibility is then S={X1,X2,X1X2,I}, with X2= 1 −1 −1 1 . Therefore |S|= 4. 1. IfC3=∅thenGS=C0 2,2and therefore |GS|= 4. It follows that m2,2= 3. 2. Assume now that C3/\e}atio\slash=∅. Then |GS|= 12. The number of Sylow 3-subgroups inGSis 1 + 3kand it divides 12. This gives us k= 0,1. If there is only one Sylow 3-subgroup in G, we get C3={A,A2}. Table 2 shows us that the orbit O(A) coincides with an orbit O(Z) for a suitable Z∈ C′ 4and contains both 3- cyclesA,A2. Therefore C4={C,C3,Z}. ThenZ/\e}atio\slash=Z3∈ C4which means that Z3∈< C > andZ∈< C > . This contradiction shows that we have 4 Sylow 3-subgroups. Since a pair of Sylow 3-subgroups have trivial intersection, we getm3= 4·2 = 8. As 12 = |GS|=m3+m2,2+ 1, we conclude that m2,2= 3. In both cases we have got m2,2= 3 which means that C2,2={X1,X2,X3}. SinceCX2C−1∈ C2,2and by Proposition 4.11 the matrix X2does not commute withC, we haveCX2=X3C. In the same way we get CX3=X2Ctherefore the setSGis closed under multiplication and it is indeed a group. Sinc e the order of a Sylow 2-subgroup in GSis 4, a Sylow 2-subgroup in Ghas order 8. Therefore SGis a Sylow 2-subgroup of G. /square 4.6 Cases n= 4,5 79 Theorem 4.18 LetG ⊂C4×4be a noncommutative permutation-like group conta- ining a maximal cycle, S4⊂C4×4the group of all permutation matrices, and SGthe Sylow 2-subgroup from Lemma 4.17. Then: (1) For C3=∅we have G=SG andGis equivalent to the group of permutation matrices isomorph ic to the group of symmetries of a square. (2) For C3/\e}atio\slash=∅the group Gis equivalent to the group S4. Proof. We pick a maximal cycle C∈ C4and fix a basis such that C= 1 i −1 −i . Then X1=C2= 1 −1 1 −1 . By the property (3c22) from Lemma 4.17 we can find a matrix X2∈ C2,2which does not commute with C. This gives us X2CX−1 2∈ C4\ {C}. Assume first that G=SG. Then C4={C,C3}. AsX2CX−1 2/\e}atio\slash=Cit follows that X2C=C3X2. By Lemma 4.12 we get X2= 1 a b c . Table 2 shows us that T=CX2∈ C2. From the spectrum of Twe conclude that [√ac,−√ac,−b] = [1,1,−1] which means that b=−1 andac= 1. By Lemma 4.13 we can find a diagonal similarity which gives us a=c= 1. It is easy to see that Gis then equivalent to a group of permutation matrices, where th e cycleCcorresponds to cycle (1234) and X2corresponds to the permutation (12)(34). The group Gis then isomorphic to the group of symmetries of a square. 80 4 PERMUTATION-LIKE MATRIX GROUPS Assume now that Gis a general permutation-like group satisfying the conditi ons of the theorem. Since Gis noncommutative, its Sylow 2-subgroups has order 8 by Lemma 4.17. 1.Suppose that C3=∅. Then Gis a 2-group and therefore G=SG. 2.Assume that C3/\e}atio\slash=∅and pickA∈ C3. By Corollary 4.9 Sylow 3 groups have order 3. Therefore |G|= 3·8 = 24. We can choose a basis Bsuch that G= 1⊕ G′, A= 1⊕A′andX1,X2,X3=X1X2fromSGare diagonal matrices, where X′ 1= −1 1 −1 , X′ 2= −1 −1 1 andX′ 3= 1 −1 −1 . ThenS={X1,X2,X3,I}is a Sylow subgroup in GS. SinceA /∈Sfor alli= 1,2,3, we getAXi∈ GS\S=C3yieldings′ 0(AXi) = 0 and A′= 0a b c0d e f 0 . We also have AX1A−1∈ {X2,X3}. Assume first that AX1A−1=X2. It follows thatAX2A−1=A2X1A−2=X3. It means that X2A=AX1andX3A=AX2. This gives us 0−a−b −c0−d e f 0 = (X2A)′= (AX1)′= 0a−b −c0−d −e f 0  and  0a b −c0−d −e−f0 = (X3A)′= (AX2)′= 0−a b −c0d −e−f0 . The above relations imply a=d=e= 0. Therefore A′is of the form A′= 0 0b c0 0 0f0 . (c3m) IfAX1A−1=X3thenA2X1A−2=X2and the matrix ( A2)′is of the form (c3m). As shown before we can find a basis B={e1,e2,e3,e4}such thatSGis a group of per- mutation matrices and Cthe permutation matrix corresponding to the cycle (1243). 4.6 Cases n= 4,5 81 ThenX1=C2,X2andX3correspond to the permutations (14)(23), (12)(34) and (13)(24), respectively. Conjugation by the orthogonal mat rix Q=1 2 1 1 1 1 1−1 1 −1 1−1−1 1 1 1 −1−1  transforms our group into G= 1⊕ G′, whereX1,X2andX3have the previously prescribed diagonal form and Cis of the form C= 1 −1 0 1 −1 0 . Then a cycle A∈ C3satisfies (c3m) and we have (CA)′= 0 0 −b 0f0 −c 0 . The ordered list of traces Tr( A) shows us that CA∈ C4∪ C2, so that we consider two cases: 1. IfCA∈ C4thens′ 0(CA) =f=−1 andbc=−1 orc=−1 b. Let us denote P= 1 1 b −1 1 . Then PAP−1= 1 0 0 1 1 0 0 0 1 0 (c3p) andPCP−1=C3. The group PGP−1then contains a matrix Ain the form (c3p) and matrix C3. Conjugation by the matrix Q−1=QTpreserves the matrix Ain the form (c3p) and transforms C3into the permutation matrix corresponding to the cycle (1342). After these conjugations Gcontains permutation matrices associated with (234) and (1342). Since C3/\e}atio\slash=∅, the group of permutation matrices GP, generated with these two matrices, has 24 elements. It follows that G=GP,which completes 82 4 PERMUTATION-LIKE MATRIX GROUPS the proof of this case. 2. IfCA∈ C2thens′ 0(CA) =f= 1 andbc= 1, i.e., 2c=1 b. Then for P= 1 1 b 1 1  we get PAP−1= 1 0 0 1 1 0 0 0 1 0  andPCP−1=C. The group PGP−1contains a matrix Aof the form (c3p) and matrixC. The conjugation by Q−1=QTpreservesAand changes Cinto the per- mutation matrix associated with the permutation (1243). On ce these conjugations are applied the group Gcontains permutation matrices corresponding to the per- mutations (234) and (1243). Since C3/\e}atio\slash=∅, the group GPgenerated by these two matrices has 24 elements, and therefore G=GP which means that Gconsists of permutation matrices. /square Case n=5: Ifn= 5, the set of ’even’ matrices is the union of the sets C5,C3,C2,2 andC0while the set of the ’odd’ matrices is the union of the sets C4,C3,2andC2. The table of traces is the following TYPE C2C2,2C3C3,2C4C5 s0 312010 s′ 0 201-10-1 Table 3 Consider an orbit for X∈ Cα. AsCis an even matrix, the product CkXhas the same parity as X. Table 3 shows that the trace separates the elements in GSand also in GL. Therefore we can reconstruct the structure of the orbit O(X) knowing 4.6 Cases n= 4,5 83 just the (unordered) list Tr(X). 1)X∈ C2: Sinces0(X) = 3, the only possible list is Tr(X) = [3,1,1,0,0]. From (sym) we conclude that s3(X) =s−2(X) =s2(X) ands4(X) =s−1(X) = s1(X), and so Tr(X) = (3,1,0,0,1),(3,0,1,1,0). 2)X∈ C2,2: This case gives us the possibilities Tr(X) = [1,1,1,1,1],[1,1,1,2,0],[1,2,2,0,0], where we can eliminate the second one using the property (sym ). Let us decompose the set C2,2as union of the sets C(fix) 2,2={X∈ C2,2|O(X)⊂ C2,2} and C(var) 2,2={X∈ C2,2|O(X)/\e}atio\slash⊂ C2,2}. ForX∈ C(var) 2,2we have Tr(X) = (1,2,0,0,2),(1,0,2,2,0). 3)X∈ C3: Ass0(X) = 2 is an even number, the list Tr(X) must contain the number 1 and therefore the orbit O(X) coincides with the orbit of an element Y∈ C(var) 2,2. It follows that Tr(X) = (2,1,2,0,0),(2,0,1,0,2). 4)X∈ C3,2: Sinces0(X) = 0 and O(X)⊂ G Lthe list Tr(X) contains 3. The orbitO(X) then coincides with the orbit of an element Y∈ C2which gives the possibilities Tr(X) = (0,3,0,1,1),(0,1,3,1,0). 84 4 PERMUTATION-LIKE MATRIX GROUPS 5)X∈ C4: We get two cases. If the list Tr(X) contains 3, the orbit O(X) coincides with the orbit of an element Y∈ C2and therefore Tr(X) = [1,1,3,0,0], while in the second case we have Tr(X) = [1,1,1,1,1] which means that O(X)⊂ C4. We decompose the set C4into the sets C(fix) 4={X∈ C4|O(X)⊂ C4} and C(var) 4={X∈ C4|O(X)/\e}atio\slash⊂ C4}. 6)X∈ C5: Let us assume that X /∈ . Ass0(X) = 0, the list Tr(X) contains 1 with ’odd multiplicity. Then the orbit O(X) coincides with the orbit of an element Y∈ C2,2and therefore Tr(X) = (0,1,0,2,2),(0,2,1,2,0). We denote C′ 5=C2,2\ and resume the structure of the orbits for the matrices X /∈ . TYPE C2C(fix) 2,2C(var) 2,2C3C3,2C(fix) 4 C(var) 4 C′ 5 C2 1 1 1 C2,2 5 1 1 1 C3 2 2 2 C3,22 2 2 C4 2 2 5 2 C5 2 2 2 Table 4 Proposition 4.19 LetC∈ C5be a maximal cycle and C3=∅. Then the group G coincides with N( )and is equivalent to a group of permutation matrices. 4.6 Cases n= 4,5 85 Proof. IfC3=∅, table 4 shows that C2,2=C(fix) 2,2, since the orbits of the elements of C(var) 2,2intersect C3. As the orbit of an element of C(var) 4contains a matrix Y∈ C3,2, andY2∈ C3, we get C(var) 4=∅. Since the orbit of an arbitrary element from C2intersects C3, we have C2=∅. This gives us G=C5∪ C(fix) 4∪ C(fix) 2,2∪ C0. Since the orbit of a matrix X∈ C′ 5intersects C3, we get C0 5=. ForX∈ Gwe haveX X−1⊂ C0 5= . It follows that G=N( ) andGis by Theorem 4.15 equivalent to a group of permutation matri ces. /square Remark: IfG=N( )/\e}atio\slash= Theorem 4.15 implies C3=∅. It follows that G /\e}atio\slash=N( ) holds if and only if C3/\e}atio\slash=∅. Lemma 4.20 LetG ⊂C5×5be a permutation-like group. Then: (1) If C3/\e}atio\slash=∅, then Sylow 3-subgroups of Gare cyclic. (2) If C2,2/\e}atio\slash=∅, then Sylow 2-subgroups of the group GS≤ Ghave orders 2or4. We assume now that C5,C3/\e}atio\slash=∅andC∈ C5is a maximal cycle. (3) We have m5= 24 andm3= 20 and Sylow 2-subgroups of Ghave orders 4or8. (4) The order of the group Gis60or120. If|G|= 60thenG=GS. (5) The set C(fix) 2,2is contained in N( )and has 5elements. Proof. (1) This follows from Corollary 4.9. (2) LetSbe a Sylow 2-subgroup of the group GS= 1⊕ G′ S. Assume that G=GS. 86 4 PERMUTATION-LIKE MATRIX GROUPS ThenS⊂ C0 2,2and therefore for X∈Swe getX2=I. It follows that Sis a commutative group. Let us pick a matrix X1∈S,X1/\e}atio\slash=I. SinceSis a commutative group, it is equivalent to a group of diagonal matrices and we can write X1= 1⊕/bracketleftbigg I0 0−I/bracketrightbigg , whereIis the identity matrix of order 2 ×2. Each matrix from Sis a diagonal matrix with diagonal equal to (unordered) five-tuple [1 ,1,1,−1,−1]. It is easy to verify that in this situation S⊂ {X1,X2,X1X2,I}, with X2= 1⊕ 1 −1 −1 1 . We conclude that |S| ≤4. (3) First we assume that G=GS. By Corollary 4.9 Sylow 5-sugroups of Gare cyclic. According to (1) and (2) we get |G| ≤ 60. Since G /\e}atio\slash=N( ), the Sylow subgroup is not a normal subgroup. The number 1 + 5 kof Sylow 5-subgroups is then at least 6. As the intersection of two Sylow 5-subgroups is tr ivial, the number of elements of the set C5is m5= 4(1 + 4k)≥24. By the property (evn) we get −m5+m3+ 4 = 0, i.e., m5=m3+ 4. It follows that m3≥20 and |G| ≥ 24 + 20>30. Since |S|= 2 would imply that |G|= 30, we actually have |S|= 4 andS={X1,X2,X1X2,I}.Fork >1 the numbersm5andm3are too big, therefore we have m5= 24 andm3= 20. We now assume that Gis a general permutation-like group. Then an arbitrary subgroupH≤ Gsplits into the ’even part’ HS, which is a normal subgroup of H, 4.6 Cases n= 4,5 87 and the ’odd part’ HLwhich is either empty set or it has the same cardinality as HS. For a Sylow 2-subgroup Sits ’even part’ has order 4 which gives us the last claim of (3). (4) From Corollary 4.9 it follows that the Sylow 5-subgroups have order 5. By (1) and (3) it follows that the order of Gis either 5 ·3·4 = 60 or 5 ·3·8 = 120, |G|= 60,120 (or5) . (5) The orbit of a matrix X∈ C3contains exactly one matrix Y∈ C(var) 2,2. Since the orbit O(Y) contains exactly two elements from C3, the cardinality of C(var) 2,2is m(var) 2,2=m3 2= 10. Then we get 60 =|GS|=m5+m3+m(var) 2,2+m(fix) 2,2+m0= 55 +m(fix) 2,2, which gives us m(fix) 2,2= 5. Pick a matrix X∈ C(fix) 2,2. ThenCX∈ C2,2and (CX)2=Iwhich implies XCX−1=XCX =C−1, and therefore X∈N( ). /square Lemma 4.21 LetG= 1⊕ G′be a permutation-like group and X1= 1⊕T, where T= 1 1 1 1 . Suppose that X2∈ Gcommutes with X1and denote X3=X1X2. (1) Then X2= 1⊕ α β γ δ β′α′δ′γ′ γ′δ′α′β′ δ γ β α . (c22) IfX2∈ C2,2\ {X1,I}we additionally get α′=−αinδ′=−δ. (2) There exists a basis Bcycsuch thatChas the form (cyc), X1= 1⊕Tand X2= 1⊕X′ 2. We haveX1∈ C(fix) 2,2and forX2∈ C2,2\{X1,I}we getX2,X3∈ C(var) 2,2. 88 4 PERMUTATION-LIKE MATRIX GROUPS (3) IfBcycis a basis such that Chas the form (cyc), X1= 1⊕TandX2= 1⊕X′ 2, then  1 0 1 1 0 0 1 1 0 ∈ {X2,X3}. Proof. (1) By comparing the second and third rows in the products X1X2and X2X1we get the desired results. SinceX2∈ C2,2, we have tr X2= 1 and therefore α′=−α. AsX2 3= (X1X2)2=I andX1X2/\e}atio\slash=I, we conclude that X3∈ C2,2and getδ′=−δ. (2) We first check that X2/∈ C(fix) 2,2. By (5) of Lemma 4.20 it follows that C(fix) 2,2= O(X1). Suppose that X2=CpX1. Since 4 = −1 is the only element of the multiplicative group Z∗ 5with order 2, we get X1C=C−1X1 by Corollary 4.14 and therefore X1X2=X1CpX1=C−p/\e}atio\slash=Cp=X2X1. It follows that X2∈ C(var) 2,2. ForX3also commutes with X1, we getX3∈ C(var) 2,2. From the list Tr( X2) we see that {CX2,C2X2} ∩ C 3/\e}atio\slash=∅. Assume that CX2,CX 3∈ C3. Then I= (CX3)3=X1C−1X2CX2C−1X2. By the left multiplication with C2X1we get C2X1= (CX2)2C−1X2= (CX2)−1C−1X2=X2C−2X2 and C2X3=X2C−2. Therefore C2X3C2=X2. 4.6 Cases n= 4,5 89 ThenCX2=C3X3C2=C−2X3C2∈ C2,2which contradicts the fact that X2∈ C(var) 2,2. It follows that exactly one of the matrices CX2andCX3is contained in C3. We can assume that CX2∈ C3andCX3∈ C5. By (1) we can write X2= 1⊕ α β γ δ β′−α−δ γ′ γ′−δ−α β′ δ γ β α . SinceCX2∈ C3, we get s′ 0(CX2) =α(λ−λ2−λ3+λ4) = 1. It follows that α=1 λ−λ2−λ3+λ4. ForC2X3∈ C3we can use the same argument to show that δ=1 λ2−λ4−λ6+λ8=−α. This gives us α+δ= 0. (∗) LetBdia={f0,f1,f2,f3,f4}be a basis such that Chas the form (dia) and X1= 1⊕T. We define g1=f1+f4,g2=f2+f3,V1=L{g1,g2}inV−1=V⊥ 1. Then X1|V1=IandX1|V−1=−Iwhich implies that V1andV−1are invariant subspaces forX2. IfX2|V1=−Iwe getX′ 2=−X′ 1which means that −1 is an eigenvalue for X3with multiplicity 4. This is clearly impossible in our group . We can therefore find a vector g∈V1such that X2(g) =g. Let us write g=µ1g1+µ2g2. Ifµ1= 0, we have X2g2=g2from what follows that −α−δ= 1. Ifµ2= 0, we have X2g1=g1which gives us α+δ= 1 and by (*) µ2/\e}atio\slash= 0. Since both cases contradict (*), we have µ1,µ2/\e}atio\slash= 0. For e=f0+g, 90 4 PERMUTATION-LIKE MATRIX GROUPS we get X1e=eandX2e=e, By Lemma 4.10 Bcyc={e,Ce,C2e,C3e,C4e}is a basis such that the matrices C, X1inX2have the prescribed forms. (3) LetBcycbe a basis satisfying the assumptions. By (1) we can write X2as X2= 1⊕ α β γ δ β′−α−δ γ′ γ′−δ−α β′ δ γ β α . If necessary we interchange the matrices X2andX3and assume that CX2∈ C3. Then (CX2)2= 0δ γ β α 1 0 0 0 0 0α β γ δ 0β′−α−δ γ′ 0γ′−δ−α β′ 2 = ∗ ∗ ∗ ∗ ∗ 0δ γ β α ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ . It follows that  ∗ ∗ ∗ ∗ ∗ 0δ γ β α ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ = (CX2)2= (CX2)−1=X2C−1= ∗ ∗ ∗ ∗ ∗ δ0α β γ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗  and therefore δ= 0. AsCX2∈ C3, we get 2 =s1(X2) =β+β′. SinceX2is a unitary matrix, we have |β|=|β′|= 1 and therefore β=β′= 1. We have shown that the matrix X2has the prescribed permutation form. /square Corollary 4.22 LetG ⊂C5×5be a permutation-like group such that C5/\e}atio\slash=∅. Then its subgroup GSof ’even’ matrices is equivalent to a group of permutation ma trices. Proof. IfC3=∅, we use Proposition 4.19. Otherwise pick a matrix C∈ C5. By (5) of Lemma 4.20 we can find a matrix X1∈ C(fix) 2,2. By Lemma 4.21 we can find a 4.6 Cases n= 4,5 91 matrixX2∈ C(var) 2,2and a basis Bsuch thatC,X1andX2are permutation matrices. The group Hgenerated by these three matrices therefore consists of per mutation matrices. By Lemma 4.20 the group Hhas 60 elements and same holds for the group GS. Since GScontains group H, the two groups actually coincide and GSitself is a group of permutation matrices. /square Lemma 4.23 LetG ⊂C5×5be a permutation-like group such that C3,C4,C5/\e}atio\slash=∅. Then there exists a matrix Z∈N( )∩ C4. Proof. We pick a matrix Y∈ C4. ThenS=Y < C > Y−1is a Sylow 5- subgroup contained in GS. Therefore Sis conjugated to the Sylow subgroup within the group GS. This means that we can find a matrix A∈ G Ssuch that Y Y−1=A−1A, i.e., (AY) (AY)−1=. ThenZ=AY∈N(< C > ) is an ’odd’ matrix and we can find a number ksuch that ZC=CkZ. By Corollary 4.14 we know that Z /∈ C2, thusZ∈ C4andZis a required matrix fromC4. /square Theorem 4.24 LetG ⊂C5×5be a permutation-like group such that C5/\e}atio\slash=∅. Then Gis equivalent to a group of permutation matrices. Proof. IfG=GS, our claim follows from 4.22. We assume that GL/\e}atio\slash=∅. Then C4/\e}atio\slash=∅and we can pick a matrix Z∈N( ) by Lemma 4.23. Then ZC=CkZ, wherek= 2,3, since 2 and 3 are the only elements of order 4 in the multipli cative groupZ∗ 5. If necessary we change matrix ZwithZ3and assume that ZC=C2Z. 92 4 PERMUTATION-LIKE MATRIX GROUPS By Corollary 4.14 we can find a basis Bmon={f0,f1,f2,f3,f4}such thatChas the form (dia) and Z= 1 1 1 1 1 . It follows that Z2=X1= 1 1 1 1 1 . LetS={Z,Z3,X1,X2,X3,T1,T2,I}be a Sylow 2-subgroup containing the matrix Z. We denote g1=f1+f4√ 2,g2=f2+f3√ 2,h1=f1−f4√ 2andh2=f2−f3√ 2. ThenB= {f0,g1,g2,h1,h2}is an orthonormal basis such that Z= 1 0 1 1 0 0 1 −1 0 , X1= 1⊕I⊕(−I) and therefore X2= 1 a b b−a c d d−c , whereaandcare real numbers. It follows that T=ZX2= 1 b−a a b d−c −c d . SinceT∈Sis an ’odd matrix’ and T/\e}atio\slash=Z,Z3, we haveT∈ C2. We getT=T−1= T∗,a= 0 and |b|= 1. The matrix Thas real diagonal entries, thus bis a real number which means that b=±1. As −1 is a simple eigenvalue of T, we conclude 4.6 Cases n= 4,5 93 thatb= 1 which implies that X2(g1+g2) =g1+g2. If we define e=f0+g1+g2=f0+f1+f2+f3+f4, we getZe=X1e=X2e=e. The setBper={e,Ce,C2e,C3e,C4}is by Lemma 4.10 a basis such that Chas the form (cyc), X1= 1 1 1 1 1  andX2= 1⊕X′ 2. By (3) of Lemma 4.21 the group H={X1,X2,X3,I}is a permutation group. Since CandZare permutation matrices it follows that the group G0generated by H,CandZconsists of permutation matrices and intersects setsC5,C4andC3. As such it has the order 120. Since the group Ghas the same order we get G=G0, andGitself is a permutation group. /square LetG ⊂C5×5be a permutation-like group. Since Theorem 4.24 gives the affi r- mative answer in the case C5/\e}atio\slash=∅, we consider now the case C5=∅. Lemma 4.25 We pick a matrix A∈ C3and write A=/bracketleftbigg I D/bracketrightbigg , (c3d) where D=/bracketleftbigg α α2/bracketrightbigg . Assume that the matrix X=/bracketleftbigg B1B2 B3B4/bracketrightbigg satisfies the condition XA=AkX. ThenB2= 0andB3= 0. There exists a unitary matrix U=V⊕Isuch thatUAU−1=AandVB1V−1is a diagonal matrix. Additionally we have: 94 4 PERMUTATION-LIKE MATRIX GROUPS (1) Fork= 1the matrixB4is diagonal. (2) Fork= 2the matrixB4is of the form B4=/bracketleftbigg 0a a0/bracketrightbigg . Proof. Since the spectrum of Ddoes not contain 1, the matrix D−Iis invertible. It follows that B2= 0 andB3= 0. We also get DB4=DkB4which yields the desired form forB4. It is clear that the conjugation by Udoes not change A, while for a suitableVblockB1changes into a diagonal matrix. /square Theorem 4.26 LetG ⊂C5×5be a permutation-like group such that C5=∅. Then Gis equivalent to a group of permutation matrices. Proof. 1.C3/\e}atio\slash=∅: First we explore the case G=GS. Then the order of Gis 3, 6 or 12, since its Sylows 2-subgroups again contain at most 4 elements. • |G|= 3: In this case we have G= for a matrix A∈ C3andGis clearly equivalent to a group of permutation matrices. • |G|= 6: Then the number of Sylow 3-subgroups is equal to 1 + 3 kand divides 6. It follows that k= 0 and is a normal Sylow subgroup for arbitrary A∈ C3. This yields m3= 2,m2,2= 6−m3−1 = 3 and therefore C2,2={X1,X2,X3}. Fori/\e}atio\slash=jwe getXiXj/∈ C0 2,2, since otherwise we would have XiXj=XjXiand {I,X i,Xj,XiXj}would be a subgroup of order 4. The group Gcan be realized by permutations X1= (12)(34), X2= (12)(35) and X3= (12)(45), whereA=X1X2= (345). 4.6 Cases n= 4,5 95 • |G|= 12: The number of Sylow 3-subgroups is 1 + 3 kand divides 12 therefore we getk= 0,1. The Sylow 2-subgroups are of the form {I,X,Y,XY },for some X,Y∈ C2,2. Ifk= 0 there is only one Sylow 3-subgroup, and therefore m3= 2. Since it follows that m2,2= 9 we have at least 3 Sylow 2-subgroups. As the number of Sylow 2-subgroups is 1 + 2 land it divides 12, we actually have 3 Sylow 2-subgroups with pairwise trivial intersections. Let S={I,X,Y,XY }andS′={I,X′,Y′,X′Y′} be two Sylow subgroups. Then XX′/∈ C0 2,2, since otherwise we would get a Sylow subgroup {I,X,X′,XX′}having nontrivial intersection with S. Similarly we show thatXY′,XX′Y′/∈ C0 2,2thereforeXX′,XY′,XX′Y′∈ C3={A,A2}. It follows that the list [ XX′,XY′,XX′Y′] has at least two equal element which is clearly a contradiction. In the remaining case we get k= 1 therefore there are 4 Sylow 3-subgroups and m3= 8. It follows that m2,2= 3 and S=C0 2,2={I=X0,X1,X2,X1X2=X3} is the unique Sylow 2-subgroup. The matrices XiandXjcommute for arbitrary iandj. Let us pick a matrix X∈ C2,2and a matrix A∈ C3. SinceA /∈S, we getXA∈ C3. By lemma 4.25 the condition XA=AXimplies that in a suitable basis we get B2= 0 andB3= 0, while B1is a diagonal matrix. If B4=−I, then the spectrum of matrix XAcontains −αwhich is impossible therefore −1 is in the spectra ofB1andXA. Since the spectra of the matrices from C3do not contain −1, matrices XandAdo not commute. We pick a matrix A∈ C3and a matrix X1∈ C2,2and defineX2=A−1X1A,X3=A−1X2A. Then G={AkXi|k= 0,1,2, i= 0,1,2,3}. It follows that the group Gcan be realized by setting A= (123) and X1= (12)(34). LetGbe a general permutation-like group without a maximal cycle . • |G S|= 3: In this case we get GS= andC2,2=∅therefore C4=∅. The order of Gis then 6 which implies the existence of a matrix T∈ C2. We must treat two cases: 96 4 PERMUTATION-LIKE MATRIX GROUPS (a) IfAT=TAthe matrix B=AT∈ C3,2is an element of order 6 and G=. (b) IfAT=A2Tthe group Gcan be realized by A= (123) and T= (12). • |G S|= 6: Let< A > be the unique Sylow 3-subgroup, where Ahas the form (c3d). We write C2,2={X,X 2,X3}and assume that X= 1 −1 1 0 1 1 0 , (p22) whereX2=AXandX3=A2X. Let{I,X1,T,T′}be a Sylow 2-subgroup. Suppose thatAT=TA. Then by Lemma 4.25 we can find a basis such that Xhas the form (p22),Ahas the form (c3d) and Tis a diagonal matrix. We get T22=−1, since otherwise the spectrum of the product ATwould either contain −αor−α2, or−1 would be a triple eigenvalue for the product XT. It follows that T′=XTis of the form T′= 1 1 1 0 1 1 0 , which give us T′A=A2T′. By changing the roles of TandT′we cover the remaining case. We have found out that the matrices A,XandTgenerate a group which can be represented by the following permutations A= (345),X= (12)(34) and T= (12). • |G S|= 12: In this case we have the unique Sylow 2-subgroup {I,X1,X2,X3} inGStherefore all the Sylow 2-subgroups in Ghave the form S={I,X1,X2,X3,T1,T2,Z1,Z2}. We writeS= 1⊕S′. It is easy to verify that at least one of matrices T1,T2,Z1,Z2 lies in the set C4. Casen= 4 shows that S′is equivalent to a group of permutation matrices, where Z1corresponds to cycle (1234), X1to permutation (13)(24), and 4.6 Cases n= 4,5 97 T1,T2respectively to transpositions (12) and (24). Therefore ea ch matrixT∈ C2 commutes with exactly one of the matrices X1,X2,X3. Suppose that we can find a matrix B∈ C3,2. Then matrices T=B3∈ C2andA= B2∈ C3commute. From the structure of ’even part’ GSwe see that Tcommutes, say, with the matrix X1. SinceX2=A−1X1AandX3=A−2X1A2, matrixTalso commute with matrices X2andX3. For this is impossible we conclude that C3,2=∅. We can therefore write G= 1⊕ G′, where G′satisfies the assumptions of Theorem 4.18. It follows that G′andGare equivalent to some groups of permutation matrices. 2.C3=∅: In this case we clearly get C3,2=∅andGS=C0 2,2. • C4/\e}atio\slash=∅: If we write G= 1⊕ G′thenG′satisfies the assumptions of Theorem 4.18. As before this completes the proof. • C4=∅: Under this assumption, Gis a commutative group. If GShas order 4, the order of group Gis 8 and G={I,X1,X2,X3,T1,T2,T3,T4}whereXi∈ C2,2and Tj∈ C2. The diagonal form of Gshows us that this is impossible, since otherwise −1 is a triple eigenvalue of at least one of the products X1Tj. In the remaining case we have GS={I,X}, whereX∈ C2,2andG={I,X,T 1,T2}. We can realize the group Gby settingX= (12)(34), T1= (12) inT2= (34). As we have checked all the cases, the proof is complete. /square Combining the last two theorems we get the following main res ult of this section. Theorem 4.27 Every permutation-like group G ⊂C5×5is equivalent to a group of permutation matrices. References [1] J. Bernik, R. Drnovˇ sek, T. Koˇ sir, M. Omladiˇ c, H. Radja vi,Irreducible semigro- ups of matrices with eigenvalue one , Semigroup forum 67(2003), 271–287. [2] A. Borel, Linear algebraic groups, Springer-Verlag, New York 1991. [3] J. V. Brawley, Scalar polynomial functions on the nonsingular matrices ov er a finite field , Linear Algebra and Applications 174(1992), 1–12. [4] G. Birkhoff, S. MacLane, A survey of modern algebra , Macmillan, New York, 1965. [5] M. Burrow, Representation theory of finite groups , Academic press, New York, 1971. [6] G. Cigler, On matrix groups with finite spectrum , Linear Algebra and Applica- tions286(1999), 287–295. [7] G. Cigler, Matrix groups with independent spectra , Linear Algebra and Appli- cations 327(2001), 27–40. [8] G. Cigler, Permutation-like matrix groups , in preparation. [9] D. ˇZ. Djokoviˇ c, Exponential map and automorphism group of a connected Lie group, American Journal of Mathematics 99(1977), 973–984. [10] L. Dornhoff, Group Representation Theory (part A) , Marcel Dekker, New York, 1971. [11] W. Feit, Characters of Finite Groups , W. A. Benjamin, New York, 1967. [12] W. Feit, The Representation Theory of Finite Groups , North-Holland Publi- shing Company, Amsterdam-New York-Oxford, 1982. 99 [13] M. Fried, Irredicibility results for separated equations , Journal of Pure and Applied Algebra 48(1987), 1–23. [14] G. P. Hochschild, Basic theory of algebraic groups and Lie algebras , Springer- Verlag, New York 1981. [15] S.-T. Hu, Elements of modern algebra , Holden-Day, San Francisco, 1965. [16] I. Kaplansky, Lie algebras and locally compact groups, The University of Chi- cago press, 1971. [17] S. Lang, Algebra, Addison-Wesley, 1965. [18] M. Omladiˇ c, H. Radjavi, Irreducible semigroups with multiplicative spectral ra- dius, Linear Algebra and Applications 251(1997), 59–72. [19] B. Peterson, E. Taft, Hopf algebra of linearly recursive sequences , Aequationes Mathematicae 20(1980), 1–17. [20] H. Radjavi, P. Rosenthal, Simultaneous triangularization , Springer-Verlag, New York, 2000. [21] H. Radjavi, P. Rosenthal, Invariant Subspaces , Springer-Verlag, New York 1973. [22] R. W. Richardson, P. J. Slodowy, Minimum vectors for real reductive algebraic groups , J. London Math. Soc. 42(1990), 409–429. [23] J. J. Rotman, The Introduction to the Theory of Groups , Springer-Verlag, New York, 1991. [24] J. P. Serre, Algebraic groups and class fields , Springer-Verlag, New York 1988. [25] A. Simoniˇ c, Matrix Groups With Positive Spectra , Linear Algebra and Appli- cations 173(1992), 57–76. [26] D. A. Suprunenko, Matrix Groups , AMS Providence, Rhode Island, 1976. [27] D. A. Suprunenko, Solvable and Nilpotent Linear Groups , AMS Providence, Rhode Island, 1963. 100 [28] M. E. Sweedler, Hopf Algebras , Benjamin, New York 1969. [29] W. C. Waterhouse, Introduction to affine group schemes, Springer-Verlag, New York 1979. 101 Izjava Izjavljam, da je to delo rezultat lastnega raziskovalnega d ela. Gregor Cigler