@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Mathematics, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Cherkassoff, Michael Boris"@en ; dcterms:issued "2009-06-19T23:32:19Z"@en, "1998"@en ; vivo:relatedDegree "Doctor of Philosophy - PhD"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description """In this thesis the question of generating PSLn(q) with three involutions, two of which commute is completely settled. When such a generation is possible we explicitly supply the generators as well as all computations that would enable one to write any particular matrix in terms of these generators. We also provide a complete classification (up to conjugacy) of embeddings of the Klein 4-group into PSLn(q) over finite fields of odd characteristic and explicitly list representatives of each embedding."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/9473?expand=metadata"@en ; dcterms:extent "3507602 bytes"@en ; dc:format "application/pdf"@en ; skos:note "G E N E R A T I O N O F C E R T A I N G R O U P S B Y T H R E E I N V O L U T I O N S , T W O O F W H I C H C O M M U T E . by MICHAEL BORIS CHERKASSOFF M.Sc. (Mathematics) Moscow State University, 1988 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES Department of Mathematics We accept this thesis as conforming tojjie required standard THE UNIVERSITY OF BRITISH COLUMBIA August 1998 © Michael Boris Cherkassoff, 1998 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for refer-ence and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Mathematics The University of British Columbia Vancouver, Canada A b s t r a c t In this thesis the question of generating P S L n ( q ) with three involutions, two of which commute is completely settled. When such a generation is possible we explicitly supply the generators as well as all computations that would enable one to write any particular matrix in terms of these generators. We also provide a complete classification (up to conjugacy) of embeddings of the Klein 4-group into P S L n ( q ) over finite fields of odd characteristic and explicitly list representatives of each embedding. Tab le o f Con ten t s Abstract ii Table of Contents iii List of Figures iv Acknowledgements v Chapter 1. Introduction. 1 Chapter 2. Preliminaries and Notation. 5 Chapter 3. Embeddings of Z 2 © Z 2 into PSLn{q) 10 3.1 Statement of the Results 10 3.2 Enumeration of Classes of Involutions 12 3.3 Two Commuting Involutions 14 Chapter 4. 3 by 3 matrices. 20 Chapter 5. Positive answer for n > 4. 23 5.1 Strategy 23 5.2 Case of 4 x 4 matrices 26 5.3 Case of 5 x 5 matrices 33 5.4 Case of (4k + 1) x (4k + 1) matrices 37 5.5 Case of (4k + 3) x (4k + 3) matrices 55 5.6 Case of 4k x 4k matrices 70 5.7 Case of (4k + 2) x (4k + 2) matrices 80 Bibliography 90 Appendix A . Maple V input for 4x4 case. 92 Appendix B . Maple V input for 5x5 case. 95 Appendix C . Maple V input for (4k + 1) X (4k + 1) case. 97 Appendix D . Maple V input for (4k + 3) X (4k + 3) case. 100 Appendix E . Maple V input for 4k X 4k case. 103 Appendix F . Maple V input for (4k + 2) X (4k + 2) case. 106 i i i L i s t o f F igu re s 5.1 First step of obtaining U4k-2,2{t), k > 2 , 77 5.2 First step of obtaining second column 78 5.3 Obtaining second column (whole block) 79 5.4 Obtaining transvections in (4k + 2) x (4k + 2) case 88 iv A c k n o w l e d g e m e n t s I would like to express my warmest gratitude to my supervisor Denis Sjerve for the all kinds of continued support he provided me throughout the years that it took to write this thesis. This piece of work would have not been possible if not for that support. It would have been impossible for me to do this research without the assistance of a great program - GAP[15]. Although I use Maple V in demonstrations of the proofs, the real research has been done with GAP, and the answers were obtained first using it. My thanks to all people in Aachen and Saint Andrews who developed (and continue developing) it, but especially to Alexander Hulpke who provided me with some code to incorporate into my programs. I would also like to thank Keith Orpen and Sandy Rutherford and many other people for assisting with v Chapter 1 I n t r o d u c t i o n The main task of this thesis is to completely answer, for the groups PSLn(q), the well known question first posed by V.D.Mazurov [10] (question 7.30): Which finite simple groups may be generated by three involutions, two of which commute? This question has generated considerable interest and has been partially answered in many cases. For example, it has been answered by Ya.Nuzhin [11] for Chevalley groups over finite fields of characteristic 2. For odd characteristic the paper by M.C.Tamburini and P.Zucca [17] gives the (positive) answer for PSLn(q), PSp2n{q), PSnn(q), PSUn(q2) provided the rank is sufficiently large. The paper by D.Sjerve and M.Cherkassoff [16] answers the question for PSL2(q), PGL2(q), alternating and symmetric groups (AN and 5n). Ya.Nuzhin [12] gave the same answer for AN independently, though it must be noted that his proof of impossibility of such generation for AQ given in [11] is incorrect. Also in [3] M.Conder gives the positive answer for alternating and symmetric groups with rank sufficiently (and rather) high using a completely different approach. After this thesis had been completed the AMS Math Reviews published a review of two papers by Ya.Nuzhin [13, 14] where this question is settled for all Chevalley groups. We formulate the complete answer to the problem of generating PSLn(q) by three involutions, two of which commute, as follows: Theorem 1.1. n = 1 - the problem is trivial. n = 2 - PSL2(q) can be so generated, iff q ^ 2,3,7,9 ([16]) 1 C h a p t e r 1. I n t r o d u c t i o n . n = 3 - P S L $ ( q ) c a n n o t be s o g e n e r a t e d ([11] f o r e v e n q, C h a p t e r 4 o f t h i s t h e s i s f o r o d d q). n = 4 - P S L 4 ( q ) c a n n o t be so g e n e r a t e d , if q i s e v e n ([11]) a n d c a n be if q i s o d d ( S e c t i o n 5.2 o f t h i s t h e s i s ) . n > 4 - P S L n ( q ) c a n be so g e n e r a t e d , ([11] f o r e v e n q, S e c t i o n s 5.3-5.7 o f t h i s t h e s i s f o r o d d q). As a semi-independent result we provide a complete classification of embeddings up to conjugacy of the Klein 4-group into P S L n ( q ) with odd q. A partial corollary of this classification, namely the fact that such an embedding into P S L ^ ( q ) is unique, is crucial in proving the impossibility of generation of P S L z ( q ) by three involutions two of which commute. The motivation for the study of the question of generation of groups by three involutions two of which commute comes from different areas: • It is known ([8]) that every finite simple non-abelian group other than P5(7s(3) is generated by three involutions. Therefore it is natural to restrict the conditions on the generators even further and ask for commutativity of two of the involutions. (We can't in fact ask for any further restrictions, since two involutions generate a dihedral group and if one of the three involutions commute with two others we get a direct product of the group of order 2 and a dihedral group). • There is a famous conjecture of Lovasz [7] that states that every vertex transitive graph, with just 4 exceptions, has a hamiltonian path. As D.Witte and J.A.Gallian [18] point out \"We are nowhere near a proof\" of this conjecture. However there is a considerable interest in proving it for certain classes of graphs. One obvious class of vertex transitive graphs is the class of Cayley graphs of presentations of groups. J.H.Conway, N.J.A.Sloane and A.R.Wilks [4] have shown that hamiltonian cycles exist in reflection groups. Their argument, in fact, applies to any group generated by involutions, such that its Dynkin diagram is a tree. Hence one of the corollaries of this thesis is the existence 2 C h a p t e r 1. I n t r o d u c t i o n . of a hamiltonian cycle in the Cayley graphs of P S L n ( q ) with odd q and n > 4. We also note that the case of only three involutions is the hardest in the graph-theoretical sense (since every vertex has minimal valiance - 3) as well as in the group theoretical sense (we have the minimal possible number of generating involutions). • The third source of interest comes from the study of regular polyhedra and algebraic curves over number fields. A.Grothendieck in his famous Esquisse d'un Programme [6] poses a question about finite quotients of the Cartographic group Ci, C2 = (ri,r2,r3\\r2 = r\\ = r\\ = (rir 2) 2 = 1). Therefore we show that P S L n ( q ) with n > 4, q- odd are examples of such quotients. The thesis is organized into the following chapters. This introduction is followed by a chapter where we collect necessary definitions, notation and other preliminary material. Chapter 3 gives the complete classification of embeddings of the Klein 4-group into P S L n (q). Chapter 4 answers negatively the main question of this thesis for the case of 3 x 3 matrices. The core of this thesis is Chapter 5. There we prove that for any n > 4 it is possible to generate P S L n ( q ) by three involutions, two of which commute. The strategy of the proof is described in detail in Section 5.1, but in brief it is quite simple. In the language of Chevalley groups, first we obtain one root element, then a root subgroup and then move it around to obtain more and more root subgroups until we exhaust the whole root system thus obtaining the whole group. We would like to point out that the methods used in the proofs are elementary. Also our proofs are completely constructive - not only do we explicitly give generators, we also in most cases give a precise sequence of computations that leads to obtaining every transvection (or root) and therefore (by Gauss elimination) any matrix (representative of an element of the group). In other words we present an algorithm for writing any particular element of the group as a 3 C h a p t e r 1. I n t r o d u c t i o n . word in the generators. We note that in Ya.Nuzhin's papers [11, 13, 14] such an algorithm is not given and in M.C.Tamburini-P.Zucca's paper [17] a considerable amount of effort is needed to deduce it. All matrix computations found in this thesis have been verified by the Maple V program. The verification Maple V input files for the values of n = 4... 10 are attached in Appendices. Also they are available in 4 different formats (plain text, Maple V worksheet, HTML and L#IpjX sources) at http://www.math.ubc.ca/~mikec/thesis.html. 4 Chapter 2 P r e l i m i n a r i e s and N o t a t i o n . In this chapter we introduce notation to be used throughout the thesis and state a few useful lemmas. By f2(n) we denote the highest power of 2 in n . For example 2^(144) = 4, 2^ (29) = 0. In the definition of the following two functions we follow J.Arkin [2]: {1 if m divides n , where m € Z>o,n € Z>o-0 otherwise, In particular A ( m , 0) = 1. p m ( n ) is the number of partitions of n into parts not exceeding m . The generating function for Pm(n) is 00 F m ( x ) = 1/(1 - x ) ( l - x 2 ) . . . (1 - x m ) = Y,Pm(n)xn 71=0 The most important fact for us is that by Theorem 1.4 in [1], p m ( n ) is equal to the number of partitions of n having at most m terms. 5 C h a p t e r 2. P r e l i m i n a r i e s a n d N o t a t i o n . Lemma 2.1. ( F o r m u l a s (10),(17), a n d (18) i n [2]) P2(n) = ^(n + l + A(2,n)) = n 2 1 + 1 p 3 ( n ) = — (2n2 + 12n + 13 + 3(-l)\" + 8A(3,n)) p A ( n ) = r^(2n 3 + 3 0 n 2 + !35n + 125 + 9(n + 3)(-l) n + Z o o 64A(3, n) + 32.4(3, n + 2) + 72A(4, n)). (2.1) (2.2) (2.3) For block-diagonal matrices we will use direct sum notation. So, for instance, the matrix A 0 0 0 B 0 0 0 c \\ will be denoted by A 0 B 0 C . For even n matrices of the special form: l 0 A 0 v Ax\" where all 4 blocks are of the size n/2 x n/2 will be denoted by Rn(X, x). The identity matrix will be denoted by I. The following matrices deserve special attention: Definition 2.2. A transvection is a matrix that has l's on the diagonal and only one non-zero off-diagonal entry. 6 C h a p t e r 2. P r e l i m i n a r i e s a n d N o t a t i o n . In other words a transvection is a matrix of the form I + tEij, where t is element of GF(q), Eij is an elementary matrix that has 1 in entry and 0 in any other entry. In the theory of Chevalley groups such elements are called root elements. We will denote transvections by Uij (t). Sometimes such a notation might lead to an ambiguity. In that cases we use comma to separate indices of the entry. Yet sometimes we use comma for completely different purpose - to indicate the dimension n of the group a transvection belongs to. If it might lead to an ambiguity we use parentheses such as for E/(2,2fc+i),ra- Ori the other hand it should be clear from the context whether comma separates dimension or two indices. We also need the following Definition 2.3. A \"double transvection\" is a matrix that has l's on the diagonal and two non-zero off-diagonal entries. We don't reserve any special notation for \"double transvections\", when necessary we will write them as I + aEij + (3Eiiji. Also it should be noted that all \"double transvections\" that we will use will have their non-zero off-diagonal entries either in the same row or in the same column. Throughout the thesis the following letters will be used solely with the following meaning: n dimension of the studied group (PSln(q)), the size of the underlying field (q is always assumed odd), d r g. c.d.(n,g - 1), q-1 d ' n s d c some (fixed) primitive root of unity in GF(q). The next lemma is obvious: Lemma 2.4. The nth roots of unity in GF(q) are (ir, i — 1> • • •, d 7 C h a p t e r 2. P r e l i m i n a r i e s a n d N o t a t i o n . We need the well-known criterion for conjugacy of matrices over a field (see, for example, [5] Theorem VI.5.7 or [9]): Theorem 2.5. T w o m a t r i c e s A a n d B i n G L n ( q ) a r e s i m i l a r if a n d o n l y if t h e y h a v e t h e s a m e i n v a r i a n t p o l y n o m i a l s or, w h a t i s t h e s a m e , t h e s a m e e l e m e n t a r y d i v i s o r s i n t h e field G F ( q ) The following criterion determines when two conjugate matrices in G h n ( q ) are conjugate by an element of SLn(g): Lemma 2.6. S u p p o s e A , B G G L n ( q ) a n d A i s c o n j u g a t e t o B i n G L n ( q ) by C G G L n ( q ) . T h e n A a n d B a r e c o n j u g a t e by a n e l e m e n t o f S L n ( q ) if a n d o n l y if t h e r e e x i s t s X G C e n t Q L n ^ ( A ) s u c h t h a t d e t X = detC. P r o o f . Let C ~ l A C = B , C G G L n ( q ) , and D ~ X A D = B , D E S L n ( q ) . Then D C ' 1 A C D ' 1 = A, so X = C D ' 1 G Cent G i n ( g )(A). Clearly detX = detC. Conversely, let X G C e n t G L n ^ ( A ) be such that detX = detC. Then X A X ~ X = A and C ~ 1 X A X ~ 1 C = B . Since det(X _ 1C) = 1, A and B are conjugate by an element of SLn(g). • The following lemma shows that preimages of involutions of PSL„(<7) always satisfy the criterion in lemma 2.6. Lemma 2.7. S u p p o s e A G G L n ( q ) , A 2 = X I , a n d B i s c o n j u g a t e t o A . T h e n t h e r e e x i s t s a n e l e m e n t C G S L n ( q ) , s u c h t h a t B = C ~ 1 A C . P r o o f . If A 2 = A7, then the minimal polynomial of A divides f(x) = x2 — A. If the minimal polynomial of A is linear, then A is scalar, lies in the center of GLn(g), so B = A and the statement is trivially true. If the minimal polynomial of A is quadratic, it coincides with f(x) and there are two cases to consider: f(x) is reducible and f(x) is irreducible, which correspond to A being square or non-square in G F ( q ) . Suppose A = x 2> then f(x) = (x — x)ix + x ) a n d the elementary divisors 8 C h a p t e r 2. P r e l i m i n a r i e s a n d N o t a t i o n . are (a; — x) a n d ix + x) • Hence A is similar to a diagonal matrix and its centralizer contains certain conjugates of all diagonal matrices and, in particular, of diag(l,..., 1,£) for any £. So the statement follows from lemma 2.6. If f ( x ) is irreducible, then n is necessarily even, say n = 2A; and the characteristic polynomial . Direct calculation shows that the matrices which lie in the centralizer of X have the following form: i i j \\^j io i i i c u u v / i u i u , uncii iij I D i i c b c o a a i I L J c v c u , o<-v — ^ri of A is {f{x))k and A must be similar to X = f j m=l V / Y f vx \\ v i X \\ v k X j where the V{ are row vectors in G F ( q ) n . We set v\\ = { x , y , 0,... ,0) and all other to have 1 in the (2i — l)st entry and 0 in all other entries; Then the determinant of Y equals to (x2 — X y 2 ) ( — X ) k ~ 1 . Since the Diophantine equation x 2 — Xy2 = s in any finite field has solutions in x , y for any non-zero A and s, we have matrices of any determinant in the centralizer of X . • 9 Chapter 3 E m b e d d i n g s o f Z 2 0 Z 2 in to P S L n ( q ) In this chapter we enumerate conjugacy classes of involutions in the groups PSLn(g) for odd q and determine up to conjugacy all possible embeddings of the Klein 4-group into PSLn(c7). We will give explicit descriptions of the classes and representatives using elementary methods of linear algebra. 3.1 Statement of the Results The conjugacy classes of one involution are described by the following Theorem 3.1. T h e n u m b e r o f c o n j u g a c y c l a s s e s o f i n v o l u t i o n s i n P S L n ( q ) i s : (0 (ii) (iii) (iv) (v) T h e t y p i c a l r e p r e s e n t a t i v e s o f e a c h c l a s s h a v e t h e f o l l o w i n g f o r m s ( c a s e s a r e a s a b o v e ) : —-—, if n i s o d d ; TI 2> i f 1 < u2(n) < v%(q- 1); TI - + i f u 2 ( n ) > u 2 ( q - l ) ; _ 2 — + 1, if vi{n) = v2(q - 1) = 1; TX - i f v 2 ( n ) = v 2 ( q - \\ ) > \\ . 10 Chapter 3. Embeddings of Z 2 © Z 2 into PSLn(q) (i) In-l © — ll, with even I, 2 < I < n Tl (ii) J n _ ; © —Ii, with even I, 2 < I < — and C,In-i © —C,Ii Tl with odd I, 1 < I < —. ' ~ ~ 2 Th (iii) and (iv) J n _f © with even I, 2 < I < — and X = eli| (! where k=^. Tl (v) In^i © —Ii, with even I, 2 < I < —. The embeddings of Z 2 © Z 2 into PSL n (g) are described by Theorem 3.2. . The number of embeddings ofZ2®Z2 into PSLn(q) up to conjugacy is: (i) pi (n) — pi (n), if n is odd; (ii) p4(n) -p2(n) + 2, i/ 1 < v2(n) < u2(q - 1); ( Tl\\ f TX \\ i Tl — 4 \\ Tl 2/ ~ P 2 V2 / + P i V^T\") + 2 + 4 , > l / 2 ^ ~ 1 ) ' M P4 Q) - P 2 Q) +P4 (^~) + ^ ' = G^? - 1) = 1/ M p4 (1) ~P2 (1) + P 4 (^ T )^ + 2' */^ (n) = ^ ( 9 - l ) >1-T/ie typical embeddings are given by: (a) Representatives are R\\ = Ii@—In-i, R2 = Imi®—Im2®Imz®—Im4, rn\\ < m2 < mz < m 4 , m\\ + m2 + 7713 + M4 = n > m 2 7^ 0, m i + m 2 = Z. A/so in cases fmj, (wj, and fuj all m's have to be of the same parity. These embeddings amount to p 4(n) —p2(n) in cases (i) and (ii) and to p\\ {^) — P2 (J^j +PA i^~2~) * n c a s e s (™)> ftv)> anc^ (v)-k fo l \\ n (b) R± = I\\ © —In-i, R2 = f © I r j , k = —, I is even. These classes exist only in cases 11 Chapter 3. Embeddings of Z 2 © Z 2 into PSLn(q) (iii) and (iv) and there are only — of them. (c) Ri = In/2 © -In/2, R2 = Rn(h l),Rn(l, C),-Rn(C, 1) orRn((r,() in case (iii) and R2 = i? n (l , l) or Rfi(l,Q in case (v). 3.2 Enumeration of Classes of Involutions. Let an element a be an involution in PSLn(g). This means that any preimage of a in SLn(q), say A, satisfies the equation x2 — A = 0, where A is an nth root of unity in GF(q). The minimal polynomial of A must therefore divide f(x) = x2 — A. If the minimal polynomial of A is linear, then A is scalar and hence lies in the center of SLn(q), so a is the identity in PSLn(c7). Therefore if a is an involution in PSL„(g), the minimal polynomial of A is x2 — A. We have two cases to consider - f(x) is reducible or f(x) is irreducible. If A = £ , r , the cases are: ir is even or odd. Suppose f(x) is reducible. Then ir is even and the minimal polynomial of A is f(x) = (x—x){x+ x), where x = C \" - / 2 . Therefore the elementary divisors are (x — x) and {x + x) a n d A is similar to a diagonal matrix. The characteristic polynomial of A is g(x) = {x — x)ll{x + x)l2ih+h = ra-in the case of an irreducible minimal polynomial, ir is odd, hence both i and r are odd. It follows that d is even and therefore n is also even. Let n = 2k. Then the characteristic polynomial of k A is g(x) = (x2 — X)k and A is similar to the matrix m=l By lemma 2.7 conjugacy classes of involutions stay the same, when we consider conjugation only by elements of SLn(q). Therefore we need to determine which conjugacy classes of involutions of SLn(o) fall into the same class after factorization. The next lemma gives a partial answer to this question. j Lemma 3.3. Let A = xhi © ~xh2 be an element of SLn(q). Then A represents in PSLn(q) the same element as 1^ © — Ii2, if l2 is even, and as C~^2Ii\\ © —C^Ih' tf h z s °dd- The latter can happen only if r is even. 12 Chapter 3. Embeddings of Z 2 © Z 2 into PSLn(q) Proof. We have x™( — I) ' 2 = 1- Hence if l2 is even then diag(x,... , x) G Z(SJn(g)) and we get the first part of the statement. Now suppose l2 is odd. If y = x 2 , then yn=l and by lemma 2.4 y = £ i r for some i. Note that ir is even and x = ± C \" ^ 2 - i n the case x = C\"\"/ 2 , x™( — I) ' 2 — 1 becomes x ^ ( - l ) ' 2 = ( - 1 ) ' 2 C ^ = {-l)hCs^ = ( - l ) ' 2 + i a = 1. Since l2 is odd, is is also odd. Therefore s is odd, i is odd and hence r is even. Now £™/ 2 = ^{q-i)/2 _ (_]_)* = _ i ; s o is in Sln(q). Also, since — 1 S a n integer, ~ = £( 2 ) r is an n throot of unity in GF(g), so diag(z,..., z) G Z(Sln(q)) and we have our statement for this case. In the case X = — £\"7 2 ; •^ \"'(--i)^ = 1 a n d we get (—l)'2+\"+n=i. If n is even, the same argument shows that with z = —((~)r, diag(,z,... ,2) G Z(SLn(q)) and again we have the statement. And if / ( l - t ) r \\ n n is odd, then both s and d are odd, hence r is even and i is also even. Now ( — £ 2 ) = ( - l ) n ( - l ) s ( - l )* s = 1. Therefore, again with z = - ^ - ^ , diag(z,... , *) G Z(SL n(g)) and the lemma is proven. • We are now ready to prove the reducible case of Theorem 3.1. Proposition 3.4. The number of conjugacy classes of involutions in PSLn(q) that have re-ducible minimal polynomial is I p2{n), if r is even; P2(|_2.P' if r i s odd-Proof. By lemma 3.3 the conjugacy class of the matrix is determined by a pair ( Z i , Z2), h+fo — n. However, the conjugacy class of a pair (h,l2) is the same as that of the pair (l2,h). To see this, denote by A\\ the representative described in lemma 3.3 corresponding to (h,l2), ami by A2 the one corresponding to {l2,h)-If n is odd, then one of Vs (say li) is even and the other is odd. Since ( £ r / 2 ) n ( — l ) ' 2 = 1, we have (—Cfl2)n = 1 since both n and l2 are odd. Therefore d iag (—£ r / 2 , . . . , —Qr^) belongs to Z(SLn(q)) and A\\ and A2 represent conjugate elements. If n is even, then since (—1)\" = 1, we have A\\ ~ — A2. 13 C h a p t e r 3. E m b e d d i n g s o f Z2 © Z2 i n t o P S L n ( q ) Therefore we have to count the number of pairs (l\\,l2), 1 < h < h , h + h = n, when r is even, and the pairs (li,I2), 1 < h < h , h + h = n , h = h = 0 mod 2, when r is odd. Clearly these are the numbers stated. • A similar proposition is true for the irreducible case of Theorem 3.1. Proposition 3.5. T h e n u m b e r o f c o n j u g a c y c l a s s e s o f i n v o l u t i o n s i n P S L n ( q ) t h a t h a v e i r r e -d u c i b l e m i n i m a l p o l y n o m i a l i s e q u a l t o 1 i n c a s e s (iii) a n d (iv) o f T h e o r e m 3.1 a n d 0 o t h e r w i s e . Proof. We already know that the conjugacy class of such an involution in SLn(g) is determined k fo l \\ k fo l \\ only by a scalar A. Two matrices A = I J and B = I J, where A = CriP = m=l V / m=l V / C j r , with r , i , j - odd, are conjugate in PSLn(g) if and only if A is conjugate to rjB in SLn(cy) for some 77, such that n n = 1. The elementary divisors of A are (x2 — A), and those of rjB are 1/2 (x2 — rfu). Therefore taking rj = y—j = ( 2 r we see that all such involutions fall into the i — 3 same conjugacy class (the condition on n is automatically satisfied since —-— is an integer.) When does this class exist? Recall that since A is not a square, i r is odd, so r is odd and we are in one of the last three cases of the theorem 3.1. We also have •j^ _ ^ y^k _ ^_-]^k^inr/2 _ ^_j^fc^irds/2 _ ( — \\^jk^is(q—1)/2 _ ^ ^k+is Since i is odd, k and 5 are of the same parity. When they are both even we have the case ( i i i ) of the theorem 3.1, when they both are odd we have case ( i v ) . • 3.3 Two Commuting Involutions In the section 3.2 we enumerated the conjugacy classes of a single involution in PSLn(q>). This section enumerates conjugacy classes of two commuting involutions! All considerations are quite similar to those in section 3.2 thanks to the following Lemma 3.6. F o r a n y e m b e d d i n g o f Z 2 © Z 2 i n t o P S L n ( q ) o n e o f t h e i n v o l u t i o n s i s c o n j u g a t e t o a d i a g o n a l i n v o l u t i o n . 14 C h a p t e r 3. E m b e d d i n g s o f Z 2 © Z 2 i n t o P S L n ( q ) Proof. An involution is conjugate to a diagonal involution if and only if it has minimal polyno-mial x 2 — A = 0, where A is a square in G F ( q ) . So A = ( k, where ( is a primitive root and k is an even integer. If two involutions are not conjugate to a diagonal matrix then their product is, since the sum of two odd integers is even • Hence, without loss of generality, we can assume that the first involution is diagonal corre-sponding to a pair (l\\, l 2 ) . Our strategy for determining conjugacy classes of Z 2 © Z 2 inside PSLn(g) relies on the more general Proposition 3.7. L e t V\\ = { e , u n , v \\ 2 , v \\ z } a n d V2 = { e , v 2 i , v 2 2 , v 2 ^ } be t w o s u b g r o u p s o f G i s o m o r p h i c t o Z2 © 7i2. T h e n V\\ is c o n j u g a t e t o V2 if a n d o n l y if t h e r e e x i s t s g G G, h G Centc(wn), 1 < h ^ «2 < 3, s u c h t h a t v n = g v ^ g \" 1 ,v\\2 = h g v 2 i 2 g ~ x h ~ x P r o o f . Suppose V\\ ~ V2. Then there exists a G G, such that v\\\\ = a v 2 i x a ~ x and v\\2 = a v 2 i 2 a ~ l for some i\\ ^ i2. Take any b G C e n t c i v u ) , then v\\\\ = b v \\ \\ b ~ l = b a v 2 i 1 a ~ 1 b ~ 1 . Now take g = ba, h = b ~ l to get the statement. For the converse note that D u = h v \\ \\ h ~ l — h g v 2 i x g ~ x h ~ ~ x and also «13 = v \\ i v X 2 = h g v 2 i 1 g ~ 1 h ~ l h g v 2 i 2 g ~ 1 h ~ 1 = h g v 2 i l v 2 i 2 g ~ l h ~ l = h g v 2 i 3 g ~ l h ~ l . Therefore Vi is conjugated to V2 by hg • Hence the strategy for determining conjugacy classes is to bring one involution to (some) stan-dard form and then, by conjugating by an element of the centralizer bring the second involution to (yet another) standard form. The next lemma is similar to lemma 3.3: Lemma 3.8. L e t A = £ I m i © — £ l m 2 © £ i m 3 © ~£7 m 4 be a n e l e m e n t o f S L n ( q ) . T h e n A r e p r e s e n t s i n P S L n ( q ) t h e s a m e e l e m e n t a s Imi © — Im2 © Im3 ffi —Im4, if m 2 + m 4 i s e v e n , a n d 15 C h a p t e r 3. E m b e d d i n g s o f Z 2 © Z 2 i n t o P S L n ( q ) a s ( r / 2 I m i © —C~l2Im2 © ( r ^ 2 I m 3 © —(r/2Im4! if m i + m4 ?s odd. TTie /airer can h a p p e n o n l y if r i s e v e n . P r o o f . The proof is a copy of the proof of lemma 3.3 with 1% substituted by m2 + m4 • By lemma 3.6 we can assume that the first involution has the form © —I\\2 or (1^ © —(Ii2. In the case l\\ ^ l2 matrices commuting with the first involution have the form ( ^ U ? \\ 0 A 2 2 J where An is a l\\ x l\\ matrix and A 2 2 is a l2 x l2 matrix. In the case l\\ = l2 the matrices in the centralizer of the first involution have the form f ^ U ^ | \\ 0 A 2 2 ) ( 0 A 1 2 \\ 0 1 \\ A 2 1 0 ) • We will call matrices of the form [ 1 1 ] matrices of the type I, and matrices of the form \\ 0 A22J ( A \\ 2 j t r j £ t n t y p e II. A2i 0 J y y Proposition 3.9. T h e n u m b e r o f c o n j u g a c y c l a s s e s o f p o s s i b l e e m b e d d i n g s o f Z 2 © Z 2 i n t o P S L n ( q ) s u c h t h a t t h e s e c o n d m a t r i x h a s t h e t y p e I a n d r e d u c i b l e m i n i m a l p o l y n o m i a l i s P i ( n ) — p 2 ( n ) , if r i s e v e n P i (1) ~ P 2 (I) + P A (~~2~~) ' tfris odd-P r o o f . If a matrix of the type I is an involution we have A \\ x — XI^, A 2 2 = XIi2 for some (but same) A. Also det An • det A 2 2 = 1. (Of course A\" = 1). Since A is a square, both An and A 2 2 have reducible minimal polynomial, so they are both similar to diagonal matrices inside G L ( l \\ , q ) and G L ( l 2 , q) correspondingly. According to lemma 2.6 these conjugations can be achieved by elements of S L ( l \\ , q ) and S L ( l 2 , q ) . Hence applying lemma 3.8 we see that the conjugacy class of the embedding of Z 2 © Z 2 into PSLn(g) is determined by a 4-tuple (mi, m 2 , 7773, m4) with mi + m2 + 777,3 + rn.4 = n. (It is 16 C h a p t e r 3. E m b e d d i n g s o f Z 2 © Z 2 into P S L n { q ) understood also that l\\ and l2 are found from the conditions l\\ — rn\\ + r«2 and l2 = + m\\.) The last step is to determine which 4-tuples yield the same conjugacy class. The claim is that for any permutation of (m\\,m2,7713, 7774) the conjugacy class of the embedding stays the same. n is odd) induces the permutation (7712,7711,7714,7713). Exchanging the first and second matrices gives (mi , 7713,7712, 7774) and exchanging the second and third gives (mi, 7712,7B4, m.3). Since these 3 permutations generate S4, the conjugacy class of an embedding is determined by an u n o r d e r e d 4-tuple (mi,777,2,7773,777.4). Also when r is odd, by lemmas 3.3 and 3.8 only 4-tuples having all elements of the same parity are allowed. Therefore the number of conjugacy classes of an embedding of Z2 © Z2 into PSL„(g) is deter-mined by the number of integer 4-tuples 0 < m i < • • • < 7774 with m i + 777,2 + 777,3 + r n 4 = n. To avoid degenerate case we also demand 777,2 7^ 0. In the case of even r we count all such 4-tuples, in case of odd r, only those of the same parity. Therefore the number of conjugacy classes is fn — 4\\ 774(77) —772(77) if r is even, and 774(77/2) — p 2 ( n / 2 ) + 774 I—-—j if r is odd • Proposition 3.10. T h e n u m b e r o f c o n j u g a c y c l a s s e s o f e m b e d d i n g s o f Z2 © Z2 i n t o P S L n ( q ) s u c h t h a t t h e s e c o n d m a t r i x h a s i r r e d u c i b l e m i n i m a l p o l y n o m i a l a n d t y p e I i s e q u a l t o Proof. First note that there are no such embeddings if 77 is odd (there are no involutions with irreducible minimal polynomial by proposition 3.5). If n is even, then the characteristic polynomials of both A n and A22 must be of even degrees since ( x 2 — X ) k does not have factors of odd degrees. Hence both l\\ and l2 are even. For each such pair the argument of the proof of the proposition 3.5 applies without change to show that there is only one class of such an embedding if the conditions of cases (iii) and (iv) of the Theorem 3.1 are satisfied and none otherwise • Indeed, multiplication of the second matrix by a scalar matrix {—I, if n is even, and -CI2T if 17 C h a p t e r 3. E m b e d d i n g s o f Z 2 © Z 2 into P S L n ( q ) The embeddings with the second involution of the type II are described by the following propo-sition for both reducible and irreducible minimal polynomials. Proposition 3.11. T h e n u m b e r o f c o n j u g a c y c l a s s e s o f e m b e d d i n g s o f Z2 © Z2 i n t o P S L n ( q ) s u c h t h a t s e c o n d i n v o l u t i o n i s o f t h e t y p e II i s 2 if I v2{q - 1); 0 o t h e r w i s e . Proof. This is the case when l\\ = l2 = k and the second (and therefore third) matrix has the ' 0 A \" X A \" 1 0 \\ / the condition on A: is + k is even. form R 2 = x x n , where A € G L k { q ) , (—l)fcAfc = 1, A = Cr• Hence, as usual, we have Note how a matrix of this form is changed by conjugation: fx ()\\ / 0 A \\ fx-1 0 \\ _ f 0 XAY'A \\0 Y j \\XA~l 0J\\0 Y-1) ~ yXYA^X'1 0 ) ' and fo x\\ f 0 A\\ f 0 y-A _ / 0 XXA^Y-1} [Y 0 ) yxA~l 0j \\x-1 0 j ~ \\YAX~1 0 ) ' We have d e t ( X ) • det(y) = 1 in the first case and det(X) • det(Y) = (—l)fc in the second. It follows that the parity of the power of £ in the determinant of A i 2 is invariant under such conjugation. Let d e t A = x - 1 . Then by conjugating R 2 by diag(l,... , © A we bring R 2 to the form R n ( X , x ) (see section 2 for notation). If x = C*, let y = (~[*/2l. Then conjugating the last matrix by diag(l,... , l , y , l , . . . , l , y _ 1 ) we obtain Rn(X,a) as a form for R 2 , where a is 1 or ( depending on parity of t. 18 C h a p t e r 3. E m b e d d i n g s o f Z 2 © Z 2 i n t o P S L n ( q ) Now we need to decide for which A and a, the corresponding Rn(X,a) fall into the same conjugacy class. A cannot be changed by conjugation, but, as in lemma 3.3, matrices with different A's fall into the same conjugacy class after factorization. More precisely: multiplication of a matrix by nl such that rf1 = 1 changes A to Xrj2. And, since n is also of the form rj — £ J' r, by a choice of an appropriate 77, A can be made 1 or £ r , depending on the parity of i in the original A(= £\"\")• We repeat the procedure of bringing multiplied matrix to the form Rn(X,a) and end up with at most 4 conjugacy classes of this type in PSL„(g) corresponding to the second matrices having the forms i^( l , 1), i^( l , (), Rn(C, 1) and i? n(( r, ()• The conjugacy classes of the embeddings corresponding to these 4 matrices are all distinct because of the difference of the elementary divisors or because of the difference in the parity of the power of ( in the determinant of A2\\. So we only need to check in which cases these matrices belong to SLn(q). We have det 7^(1,1) = det i? n(l,() = (—l)fc, det Rn{(r, 1) = det Rn((r,() = ( - l ) f c + s . Therefore, if k is odd, i? n(l, 1) and i^( l ,C) do not belong to SLn(q) and we have only two classes of embeddings of Z 2 © Z2. (Note that since is is odd, s is odd and hence Rn{Cr> 1) a n d Rn{(r, C) belong to SLn(q)). Finally, if k is even, then if s is even, we have all four classes, and if s is odd, Rn(C,l) and Rn((r,() are not in SL„(aJ and there are only two classes, corresponding to Rn(l,l)and Rn(l,() • Combining the results of the propositions in this section we obtain Theorem 3.2. 19 Chapter 4 3 b y 3 mat r ices . In this chapter we prove the following Theorem 4.1. P S L z ( q ) c a n n o t be g e n e r a t e d by t h r e e i n v o l u t i o n s t w o o f w h i c h c o m m u t e . Proof. According to Theorem 3.2 there is only one conjugacy classs of embeddings of Z2 © ZJ2 into P S L 3 ( q ) . Therefore the first two (commuting) involutions can be chosen as Ri = 1 0 0 0 - 1 0 0 0 - 1 and R2 = -1 0 0 0 1 0 0 0 - 1 We let R3 = R \\ R 2 and let Ro denote identity matrix I. We will show that no third involution X can be chosen so that P S L ^ ( q ) = (X, R i , R 2 ) or, equivalentlty, that S L z ( q ) can not be generated by X , R i , R 2 and scalar matrices. For matrices A, B € SL$(q) we use the notation A ~ B to indicate that A , B agree up to a scalar, that is A = XB for some A € G F ( q ) . Necessarily A3 = 1. Now, fix an involution X and let G — { X , R i , R 2 ) . By Theorem 3.1 there is only one conjugacy class of involutions in P S L z ( q ) . So there exists a matrix C G S L 3 ( q ) such that X ~ C R i C ~ l . Let C = Cu C12 C13 C21 C 2 2 C23 C31 C 3 2 C33 and C~Y = C l l C12 C13 C21 C 2 2 c 2 3 C31 C32 C33 20 C h a p t e r 4. 3 b y 3 m a t r i c e s . Since CC 1 = / , we have X ~ CRXC-1 ~ C 2 0 0 0 0 0 0 0 0 I I C - 1 ~ 2cc - J, where c = respectively. C21 V ; and c = ( cn ,C12,C13) are the first column and first row of C and C 1 If any one of c n , C 2 1 , C 3 1 , c . \\ \\ , c \\ 2 , C 1 3 is zero then each of X, Ri, R2 have both off-diagonal entries in some row or column equal to zero. For example, if C12 = 0 then X, Ri, R2 all have both (1,2) and (3,2) entries equal to 0. Since the matrices with such a property form a proper subgroup of PSL3 (q), all elements of G will have the form * 0 * * * * * 0 * and obviously G ^PSLz(q). Therefore, for X, R\\, R2 to generate PSLs(q) none of cn, C21, C31 , cn, c i 2 , C13 can be equal to zero. So from now on we assume this is the case. Now suppose we have chosen X such that X ~ 2cc — / . Consider the group D(X,Ri,R2)D~l where D =diag(di, d2, d^) for some d\\, d2, d3. Obviously this group has the same number of elements as G and will be all of PSL3 (q) if, and only if, G =PSLz (q). Since D commutes with all R^s we have D(X,Ri,R2)D~1 = (DXD~1,Ri,R2), and therefore without loss of generality we can change c to Dc and c to cD~l. Let D =diag(c 1 1 i,c 2 1 1,c 3 1 1). Then X ~ 2a 2/3 27 2ot 2(3 27 2a 2/3 27 21 C h a p t e r 4. 3 b y 3 m a t r i c e s . where a = q / c n , 0 = c^cn, and 7 = c3Xxc\\3. Now let F =diag(a, 0,7). Then FXF~l = XT. Suppose B is an element of {X, Ri,R2). Then B ~ RiXRjX ... XRkXRt. Therefore FBF~l ~ FRiF^FXF-1... FXF^FRiF'1 = RiXTRjXT ... XTRkXTRt = (RtXRkX ... XRjXRif ~ (R^X^R^X'1... X~l R~l X'1 R7l)T = (B^f This means if B is in G then conjugating it by a diagonal matrix we get a scalar multiple of {BT)~l. Then obviously 1 1 1 0 1 1 0 0 1 • This proves the negative part of Theorem 1.1. In the Introduction we have mentioned that one possible motivation for the question of which groups can be generated by three involutions, two of which commute, is the problem of finding a Hamiltonian cycle in a Cayley graph of a group. In the light of the negative answer to the question of such generation of PSL3 (q) the following question can be posed: can P S L s ( q ) be generated by s o m e number of involutions such that their Dynkin diagram is a tree? Unfortunately the answer to this, even more relaxed, question is still N O . This can be shown by considerations similar to those in this chapter. Again the key reason is that there is only one way to embed Z 2 © 7L2 into PSL3 (q). 22 Chapter 5 P o s i t i v e answer for n > 4. The purpose of this chapter is to prove Theorem 5.1. P S L n ( q ) , w i t h q o d d , c a n be g e n e r a t e d by t h r e e i n v o l u t i o n s , t w o o f w h i c h c o m -m u t e , if n> 4. 5.1 Strategy We are going to prove Theorem 5.1 by induction on the size of the matrices. Starting with the matrices of some size n x n we will show how to expand them to size (n + 4) x (n + 4) so that computations stay practically the same. For each n we will explicitly give three generators and demonstrate how to obtain all (off-diagonal) transvections, which are well-known to generate P S L n ( q ) . First we establish the result for n = 4 and n = 5 in sections 5.2 and 5.3. While the case n = 4 is completely distinct, the case n = 5 could have served as the base of the induction for the n — 4k + 1 case. However, although the generators are exactly the same (in terms of the Bar Operation introduced in definition 5.2) as in the general case, some computations in the proof are specific to the case n = 5 and cannot be extended for larger matrices. Hence we treat the case n = 5 in a separate section. Nevertheless we will point out the parts of the computation that are common to all of n = 4k + 1 and will use those when we prove the cases n = 9,13,17,.... Then in sections 5.4, 5.5, 5.6 and 5.7, we deal with the cases n — 4k + 1, n — 4k + 3, n = 4k 23 Chapter 5. Positive answer for n > 4. and n = 4k + 2 respectively. The method of proof in all cases is quite similar, consisting of the following Steps: Step 1. Obtain a transvection in G, thus getting a subgroup isomorphic to Z/pZ. Step 2. Obtain all transvections at some spot, thus getting a subgroup isomorphic to GF(g). Note that this step is redundant if q = p. Step 3. Obtain all off-diagonal transvections. As we already mentioned, the completion of Step 3 means the end of the proof. Since the precise sequence of computations necessary for completing each step varies from case to case, we will describe it in detail in the corresponding sections. All computations were verified by a Maple V program. The input files for the cases n = 4,..., 10 are provided in Appendices A - F and are also available at http://www.math.ubc.ca/~mikec/thesis.html Here is the description of the process for increasing the matrix size by 4. Let us call the matrix Bo = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 a block of type 0. Similarly B, = 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 a block of type 1, B2 = 1 0 0 0 1 0 -1 0 0 1 0 0 0 0 1 -1 24 Chapter 5. Positive answer for n > 4. a block of type 2, B3 = a block of type 3, a block of type 4 and Bu = B4 = a block of type 5. -1 1 0 0 \" 0 1 0 0 0 0 -1 1 0 0 0 1 _ 0 -1 0 0 \" 1 0 0 0 0 0 0 -1 0 0 1 0 _ 1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 Definition 5.2. If A is any matrix we denote by A[type, i] the matrix obtained by an insertion of the block Btyve after the i-th row and i-th column. We will call this the Bar Operation. Here are some examples of this notation: If A = a b c If s = d e f h 9 i a b c d then A[4,1] = then £[2,0] = a 0 0 0 0 b 0 0 -1 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 1 0 0 c 0 0 0 0 d 1 1 0 0 0 0 0 0 •1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 a b c 0 0 0 0 d e / 0 0 0 0 9 h i The next lemma is obvious. 25 Chapter 5. Positive answer for n > 4. Lemma 5.3. The Bar Operation has the following properties: 1. A[k,i] • B[k,i] == AB[0,i], if k = 0,1,2,3,5. 2. B[k,i] • A[0,i] • B[k,ifl = BAB-l[0,i], if k = 0,... ,5. 3. A[k,i] • B[0,i] • A{k,i)\"1 • 5[0,i]_ 1 = ABA~lB~l^),i], if k = 0,... ,5. In sections 5.4-5.7 we will give explicit generators for the base cases of the induction, that is n x n, where n = 9, 7, 8, 6. Then the generators for higher dimensions are described inductively in terms of the Bar Operation. Most computations also are expressed in terms of the Bar Operation and easily verified by lemma 5.3. 5.2 Case of 4 x 4 matrices. In this section we prove the following Proposition 5.4. For any odd q>3, SL^q) can be generated by the following three matrices: - 1 0 0 0 \" 0 1 1 I\" 0 0 - 1 - 1 0 0 0 1 x where x = —1, if q — 3, and if q > 5, then x & GF(q) is chosen so that z = is a primitive 8 — x root in GF(q) (this in particular implies x ^ 0,4, 8). Corollary 5.5. PSL^q) can be generated by three involutions two of which commute for any odd q > 3. Proof Simple computations show that R\\ = R\\ — R\\ = (R1R2)2 = I • We start with the following Ri = 1 X 0 - 1 0 0 0 x 0 0 0 0 -1 0 0 1 R2 = 0 0 0 1 0 0 1 0 0 1 0 0 -1 0 0 0 and i?3 = 26 Chapter 5. Positive answer for n > 4. Lemma 5.6. Suppose q > 5. Let T — A 0 B C the 2 x 2 matrices: A -suppose Am — I. Then x + - x be the 4 x 4 matrix, where A,B and C are . Let a; ^ 0,8 and ' 0 0 ' \" i C ' , B = X — X 0 1 L 2 J rpm. 1 0 0 0 0 1 0 0 mQz AmC,z 1 mC, 0 0 0 1 where z = 8-x Proof. By an easy induction Tk = Ak 0 Bk Ck , where Bk = BAk'x + CBAk~2 + ••• + CjBAk~l-i + ••• + Ck~2BA + C f c - 1 B . Our goal is to compute Bm = a B 7 5 Now ClB = 1 K' ' 0 0 ' \" *Cf Kx ' 0 l - X 2 x I 2 X and (a , (3) = ( | , x) • ( • ( A m ~ 2 + 2Am~3 + • • • + (m - 2)A + (m - 1)7) (7, 4. Then X = — Y, since X + Y = (m - l ) ( A m - 1 + A m ~ 2 + • • • + A +1) = (m - 1) • 0 = 0. A 0 To compute Y, first assume A is diagonal, say Ad = Let 0 A\" f(x) = (m - l)*\"1\"1 + (m - 2)xm~2 + • • • + x2 + x. , A m = 1. Then Y d = Write /(A) 0 0 /(A\" 1) /(x) = x((m- l)xm-2 + (m - 2)xm~3 + • • • + x + l) = xg(x). Then xm - 1 x = x\"*-1 + x ^ - 2 + . . . + x + C = + C, x - 1. and therefore mxm-1(x-l)-xm + l (x - l ) 2 : i m - l So g(\\) = and /(A) = m A - 1 Thus A - 1 Y/ = m A - 1 A \" 1 - ! Now if E is such that A = EAdE 1 , then 1\" = EYdE 1 . The characteristic polynomial of A is /(t) = « 2-(f-2)t + l, so since x ^ 0, 8, A is diagonalizable. We can take E to be the matrix having eigenvectors of A as columns. A choice of eigenvectors (from the second row of A) is A + l \\ / A ^ + l e\\ = | _1 J , and eA-i = I _1 2 / V 2 28 Chapter 5. Positive answer for n > 4. and so E = A + l A _ 1 + l 1 1 ~2 ~2 and E~l = A - 1 - A A + l Therefore (using A + A 1 = ^ — 2) we have x Y = 2m 4-x/2 x 2 -1 1 z/2-2 4 , and X = 4m -1 x \"2 1 s - 4 4 4 Note that the entries of A^, Y^ and E might not lie in GF(q), but they are elements of GF(q2). Nevertheless Y is an element of SL±(q). Finally t R\\ (X \\ and the lemma is proved. - - f 4 4 = m«C • (1 , 4), • The analogue of this lemma for the case q = 3 is the following Lemma 5.7. Let 0 -1 0 0 1 0 0 0 1 -1 0 0 Q 0 1 0 0 . Then T = 0 0 1 1 1 1 1 0 1 -1 0 1 0 0 0 1 Proof. Computation • Now we are ready to prove proposition 5.4. Proof. Let G = (R\\,R2,#3). We will go through the Steps described in section 5.1. For this particular case we will use lemmas 5.6 and 5.7 to get a transvection at the position (3,1). Step 2 is redundant for q = 3. We will repeatedly use lemma 5.6 to obtain all transvections at position (3,1) for q > 5. Then in Step 3 we will easily obtain all transvections at the positions (3,4), (2,4), (2,1) and (2,4), and then after a few computations we will obtain the rest. 29 Chapter 5. Positive answer for n > 4. See Appendix A for the Maple V input file to verify all computations. By computation: (R2R3)4 = 1 0 0 0 - 2 1 4 2 0 0 1 0 0 0 0 1 Therefore for any integer s (R2R3)4s = 1 0 0 0 -2s 1 4s 2s 0 0 1 0 0 0 0 1 and ^3(^2^3) 4s - 1 0 0 0 -2s 1 4s + 1 2s + ^ 0 0 - 1 0 0 0 -1 1 P - 1 —-—, ifp=lmod4, 1 Let so = { (In other words so = —7)- Then we put 3P - 1 -F _ o A A 4 —-—, il p — 3 mod 4. Ri = R3(R2R3)4so = - 1 0 0 0 \\ 1 0 0 0 0 - 1 - 1 0 0 0 1 and T = R ^ = x -1 X 0 0 1 -1 0 0 ~2 0 0 1 1 X X 0 1 TrU=Tm = (5.1) Now T satisfies the conditions of lemma 5.6 with £ = 1, if q > 5, or lemma 5.7, if q = 3. Hence 1 0 0 0 0 1 0 0 mz 4mz 1 m ^ 0 0 0 1 if q > 5, or \" 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 if q = 3. Note that in the first case z / 0, since x ^ 0, and m^0, since m is a divisor of q — 1. Put 1 0 0 0 0 1 0 0 mz — m 0 1 m — mz 0 0 0 1 Tm = T3 = S = Tmi?2TTOi?2 = (5.2) 30 Chapter 5. Positive answer for n > 4. if q > 5, or S — TmR2TmR2 1 0 0 0 0 1 0 0 1 0 1 -1 0 0 0 1 if q = 3, and then U31(2m(z - 1)) = (TmR4S)2 = if q > 5, or tf3i(l) = (rm JR 4S) 2 = 1 0 0 0 0 1 0 0 2mz-2m 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 - 1 0 1 0 0 0 0 1 (5.3) if q = 3. Note that U3\\(2m(z — 1)) ^ I since z ^ 1, or equivalently x ^ 4. At this point we have completed Step 1 for q > 5. If g = 3, we have in fact completed Step 1 and Step 2. Now we complete Step 2 of the proof for q > 5. U~3i(2m (z — 1)) generates a subgroup which contains all transvections at the (3,1) position with non-zero off-diagonal elements being multiples of z — 1, we denote them Uz\\{k (z — 1)). Putting U34{-m{z-l)) = U31{-m(z-l))S we obtain a similar subgroup at the (3,4) spot. Consequently x 0 0 - 1 0 0 0 1 z x 0 1 (5.4) Tz = TUu(z - 1) 1 ~2 0 x 2 (5.5) 31 Chapter 5. Positive answer for n > 4. satisfies conditions of the lemma 5.6 with C, — z. So by the lemma -im z 1 0 0 1 m z2 4 m z4 0 0 .2 0 0 0 1 m z 0 0 1 (5.6) So repeating the computations 5.1-5.6 using Tz instead of T we get Sz = T™R2T™R2 and U31(2m(z2-z)) = (Tf R4SZ)2 and Un(2 m {z2 - 1)) = U3l{2m (z2 - z))U31(2m (z - 1)). Note now that U3i(2m(z2 — 1)) generates the same subgroup as U3\\(z2 — 1). As before we obtain U3i{z2 — 1) and set Tzi = T L ^ z 2 — 1). Now we repeat the computations 5.1-5.6 with Tz2 and inductively with all Tzi,l € N. Doing this we will run through all the elements of the form zk — 1, thus, if z is a primitive root, through all the elements of GF(g) except —1. Hence we obtain all the transvections U3i (t) and Step 2 is completed. For Step 3 we do not distinguish cases q = 3 and q > 5, since we only use the Step 2 result which is the same for both cases. Multiplying U3i(t) by the corresponding S we obtain all transvections U34(t). Now (R3U34{t))2 = U2i{t) and R2U2i{-t)R2 = U21{-t). Also (i?iC/3i(^)2 = U32{-tx). So at this point we have obtained all transvections at spots (3,1), (3,2), (3,4), (2,1), and (2,4). Now put Then we have U23(t) = R^U^i^R*,. Hence we have all transvections at the spot (2,3). Since we also have all transvections at the spot (3,2), our group contains the subgroup isomorphic to SL2(q) at the entries (2,2), (2,3), (3,2), and (3,3). In particular, the matrix R5 = U32(l)R3Uu(-l)U2i(l/2)U32(l) = 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 i?6 = 1 0 0 -1 0 0 0 0 0 0 0 0 1 0 0 1 32 Chapter 5. Positive answer for n > 4. Now we need a few more computations to finish the proof. Put Q = R ^ R ^ U ^ l ) 1 x 2x 0 0 1 1 0 0 0 1 0 0 x 0 1 and P = U32(t)U23(-l)R6Q 1 x 2x 0 0 - 1 0 0 0 -t -1 0 0 x 0 1 Then P2U32(2t) = Ui2(—2xt), and we obtain all transvections at the spot (1,2). Finally • Ul3{t) = Ul2{-t)U23{-l)Ul2{t)U23{l) • Uu{t) = Ul3(-t)U34(-l)U13(t)Uu(l) . U43(t) = R2U13(-t)R2 • UA1(t) = R2Uu(t)R2 • UA2(t) = R2Ul2{t)R2 We have obtained all transvections, thus completing Step 3 and the proof of the proposition. 5.3 C a s e o f 5 X 5 m a t r i c e s . In this section we go through Steps 1, 2 and 3 in the case of 5 by 5 matrices. Step 1 will be very easy and we'll obtain U23{1). To complete Step 2 we will first obtain U2i(l) and then all U24(t),t EGF(q). Step 3 will consist of three following substeps: a) Obtain all U2i(t) b) Obtain all Uj2(t) c) Obtain all Uij(t) • 33 Chapter 5. Positive answer for n > 4. See Appendix B for the input Maple V file to verify computations. We will enumerate some of the computations that we will use in the next section to prove inductively the case of n = 4k + 1. As in the previous section the main result is the Proposition 5.8. For any odd q > 3 SLs(q) can be generated by the following three matrices: ' 1 x 0 0 0 \" ' 0 0 0 0 1\" \" 1 0 0 0 0 0 - 1 0 0 0 0 -1 0 0 0 0 1 1 0 0 Ri = 0 0 0 1 0 R2 = 0 0 1 0 0 and i?3 = 0 0 -1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 . 0 -x 0 0 1 . _ 1 0 0 0 0 . . 0 0 0 0 -1 where x is a primitive root in GF(q). There is an immediate Corollary 5.9. PSLs(q) can be generated by three involutions two of which commute for any odd q > 3. Proof. As in the case of 4 x 4 matrices simple computations show that R\\ = R\\ — R\\ = (RxR2f = I • Proof of the proposition 5.8. We start with U23(4) = (R2R3)4 = 1 0 0 0 0 0 1 4 0 0 0 0 1 0 . 0 0 0 0 1 0 0 0 0 0 1 (5.7) Thus completing Step 1. At this point we have obtained all transvections U2$(l), where / is an integer. Our next goal is to complete Step 2. We will do it by obtaining all transvections U2^(t), where t is an arbitrary element of GF(g). Computations to obtain U24(l) are unique to the case q = 5. 34 Chapter 5. Positive answer for n > 4. Let Ri = RZUK{-1) = 1 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 0 1 1 0 0 0 0 -1 and W = (RiR4)4 = 1 0 0 0 0 0 1 0 0 0 0 -2x 1 0 0 0 -2x 0 1 0 0 4x 0 0 1 Also let 1 -4x 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 Ax 0 0 1 S = WR2WR2 = Thus we have obtained all matrices with ones on the diagonal and having as the only off-diagonal entries the opposite integer multiples of x at the spots (1,2) and (5,2). In particular we have obtained the matrix Now if T = 1 X 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 —x 0 0 1 RQ = R\\T 1 = 1 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 then [724(1) = R6U23(-1)R6 = 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 To finish Step 2 we need to produce all U24{t) from t/24(1). We proceed as follows: assume that we have obtained some 1724(a), then we can also obtain P = (RxRzR^iia))2 = 1 0 0 0 0 0 1 0 0 0 0 0 1 x a 0 0 0 0 1 0 0 0 0 —2xa 1 (5.8) 35 Chapter 5. Positive answer for n > 4. and U2A(xa) =P- 1C/ 2 3(1)P*7 2 3(-1) = 1 0 0 0 0 0 1 0 xa 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 (5.9) This means that starting with ?724(1) we can successively obtain U24(xl) for all integers I hence all U24{t),t &GF(q) since x is a primitive root. This completes Step 2. Now Unit) = R%U2i{t)Rs. U25(t) = R3U24(t)R3U24(-t). U21(t) = R2U25(-t)R2. (5.10) (5.11) (5.12) We have just obtained all transvections with off-diagonal element in the second row thus com-pleting substep a). The next series of computations obtains all transvections with off-diagonal element in the second column. Q = R1U21 [ -) RiU2l (--. x 1 \\ x 0 X 0 0 0 1 0 0 0 0 X 0 0 1 0 0 0 0 0 1 0 1 —x 0 0 1 (5.13) QU21 x' 2 Q) = 1 t 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 -t 0 0 1 (5.14) F2 = (U23(l)R3Fi)2 = 1 2t 0 0 0 0 1 0 0 0 0 0 1 0 0 0 -t 0 1 0 0 0 0 0 1 (5.15) 36 Chapter 5. Positive answer for n > 4. F3 — RQF2RQ = 1 -2t 0 0 0 0 1 0 0 0 0 t 1 0 0 0 0 0 1 0 0 0 0 0 1 (5.16) So now . U12(-At) = (U23(l)R3F3)2, • U32(t) = U12(2t)F3, • UA2{t) = U12(2t)F2~1 and • U52(t) = Ul2{t)F{\\ (5.17) (5.18) (5.19) (5.20) We have obtained all transvections with off-diagonal entry in the second column thus completing substep b). (5.21) • Now to finish Step 3 and the proof we observe that for i,j,2 all distinct Uij{t) = Ui2(l)U2j(t)Ui2(-l)U2j(-t) 5.4 Case of (4k + 1) X (4k + 1) matrices. In this section we deal with the case n — Ak + 1, k > 2. We will use the Bar Operation(see Definition 5.2) to increase the size of the matrices inductively and we will use lemma 5.3 to verify that the same computations yield the same results for all sizes. Precisely we want to prove the following Proposition 5.10. Let R\\, R2 and R3 be the 5x5 matrices defined in proposition 5.8. Define inductively: Ri,5 = R\\) 7?2,5 = 7^ 2) #3,5 = R3 and Ri,n = i?i,n-4[l,2], R2,n = fl2)n-4[0,2], R3,n = R3,n-i[2,3], for n = Ak + 1, k > 2. 37 Chapter 5. Positive answer for n > 4. Then SLn(q) = (Riyn,R2,n,R3,n) As in the cases of 4 x 4 and 5 x 5 matrices we have an immediate Corollary 5.11. PSL4k+\\{q), k>2 can be generated by three involutions two of which com-mute. Proof. This follows immediately from the previous proposition, computations of corollary 5.9 and lemma 5.3 • In essence the proof of proposition 5.10 follows from the following (trivial) key observation and lemma 5.3, Lemma 5.12. a) Rl,n = R\\,n--4[l,2j], 1 < j < 2fc - 2, b) R2,n = R2,n--4[0,j], 2 4. Lemma 5.13. For any 1 < j < 4k + 1 a) R\\>nE\\j = Eij b) R\\,nE2j = xEij — E2j — xEik+i,j c) Ri,nE2i+i,j = E2i+2,j, forln = —Ei2 c) Eij2l+1R1>n = Eifii+2, forl 4. Lemma 5.16. For any 1 < i < 4k + 1 a) EnR2,n = Ei^k+i b) Ei2R-2,n = — Ei2 c) EijR2,n = Eij, forZnE2i+ij = E2ij - E21+1J, for 1 < I < 2k And right multiplication by the third generator is described by the following Lemma 5.18. For any 1 < i < 4k + 1 a) EnRz^n = En b) Eit2iR3!n = Eit2i + Eij2i+i, forl 4. Step 3 will consist of three following substeps: a) Obtain all U2j(t) b) Obtain all Ui2(t) c) Obtain all Uij(t) For Step 1 we only need to note that i? 2 i„ = -R2,n-4[0, 3] by lemma 5.12, hence by lemma 5.3 and computation 5.7 we have •tf23,n(4) = tf23,n-4(4)[0,3] = (i2 2,„_ 4[0, 3] • i? 3,n- 4[0, 3])4 Therefore we have just obtained all transvections £/23,n(0> where I is an integer. We now proceed with Step 2. First we obtain C/24,n(0 and (725,n(0 with I an integer. For the base of the induction (n = 9) we make the following computations: 1 0 0 x 0 0 0 0 0 -Pl,9 = RlflU2Z${1)R\\$ = 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 -x 0 0 0 0 1 (5.22) 7^ 2,9 = -^3,9^1,9 #3,9 = 1 0 0 X X 0 0 0 0 0 1 0 -1 -1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 —x —x 0 0 1 0 0 0 0 X X 0 0 0 1 (5.23) 41 Chapter 5. Positive answer for n > 4. ^3,9 = ^2,9^2,9^2,9^2,9 = and finally 1 0 0 0 0 0 0 0 0 0 1 0 2 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 (5.24) 1/24,9(2) = #3,9^3,9^3,9 ^25,9(2) = ^ ( 2 ) P 3 , 9 and (5.25) (5.26) We now will repeat computations 5.22-5.26 starting with 1/25(1) instead of J723(l) to obtain 1^ 26 (2) and ^ 27(2). In fact the same computations will work successively in the n x n case and we will obtain all transvections in the second row but the last two. In other words in the n x n case we can obtain all (7 (^1) for 3 < j < 4k — 1 thanks to the following Claim 5.19. Let 1 < I < 2k - 2. Set P i = Rl,nU2i2l+l(ORl,n, P2 = Rz,nPlRz,n, P 3 = # 2 , ^ 2 #2,^2\" 1 • T h ™ a) t/2,2(+2(2£) = R3,nP3Rs,n b) r/ 2 ) 2 / + 3(20 = u-^mp* Proof. Since f7 2, 2/+i(£) = I + ££2,21+1 w e n a v e by lemmas 5.13 and 5.14 Pi = I + Rl,n£E2,2l+lRl,n = I + £(xEi^l+l — #2,2/+l ~ xE^k+\\,2l+l)R\\,n — I + £xEij2l+2 - £E2,2l+2 ~ £xEik+it2l+2 42 Chapter 5. Positive answer for n > 4. Now by lemmas 5.17 and 5.18 we have -f*2 = Rz,nP\\Rz,n = -R3,n(7 + ^ - ^ l , 2 / + 2 ~ {-^ 2,2^+2 ~ &Eik+l,2l+2)R3,n = I + (xEit2l+2R3,n — t,E2t2l+2R3,n ~ (x(E4k,2l+2 ~ E4k+l,2l+2)R3,n = I + £,xEit2l+2 + &Eit2l+3 - C-^2,2(+2 ~ ^2,24+3 ~ (,xE4k,2l+2 - ixEAk,2l+3 + £,xE4k+l,2l+2 + £xE4k+l,2l+3 Now write P2 = I + Q. Then since 21 + 2 > 2 and 21 + 3 < 2(2k - 2) + 3 = 4k - 1 < 4 k , Q2 = 0 as every product of elementary matrices involved is equal to 0. Hence P2~l = I — Q. Also by lemmas 5.15 and 5.16 we have R2,nP2R2,n = 7?2,n(7 + £xEi,2i+2 + £xEij2l+3 ~ ^2,21+2 ~ £ # 2 , 2 / 4 - 3 - (,xE4k<2l+2 - (,xE4kj2l+3 + f £ # 4 * 4 - 1 , 2 1 4 - 2 + ££#4*4 -1 ,2*4 -3 )^2 , 71 = I + £(x#4fc4-l,2/4-2 + xEth+1,21+3 + #2,2/4-2 + #2,2/4-3 - xE4k,2l+2 - xE4kt2l+3 + £ # 1 , 2 / 4 - 2 + xEij2l+3)R2^n = I + £ (£#4fc+l ,2 /4-2 + £#4fc4-l ,2/4-3 + #2,2/4-2 + E2t2l+3 - £ # 4 f c , 2 / 4 - 2 - X#4A:,2/4-3 + £ # 1 , 2 / 4 - 2 + £ # 1 , 2 / 4 - 3 ) = 1 + 0' Again all the products of elementary matrices in the product of Q and Q' are 0. Hence P3 = R2,nP2R2,nP2~l = (I + Q')(I - Q) = I + Q' - Q = I + 2 £ # 2 > 2 / 4 - 2 + 2^2/4-3 Finally by lemmas 5.17 and 5.18 R3,nP3R3,n = R3,n(I + 2£#2,2/4-2 + 2 £ # 2 , 2 / 4 - 3 ) # 3 , n = I + £(2#2,2/4-2 + 2E2}2l+3)R3,n = I + 2^E2j2i+2 + 2£E2,2i+3 — 2(E2t2i+3 — U2t2i+2 (2£) and U2-2\\+2(20P3 = (7 - 2^ ,21+2) ( / + 2£#2,2/4-2 + 2^2,2/4-3) = I + 2£E2t2i+2 + 2£E2>2i+3 - 2^E2>2i+2 = {72i2/+3(2^) and the claim is proved • 43 Chapter 5. Positive answer for n > 4. Therefore, using the claim with £ = 1 we successively obtain U2j{l), where / is an integer and 3 < j < 4k - 1. To finish Step 2 we need to produce C/24(*) for all t eGF(g). The computations are exactly the same as in the 5x5 case (5.8-5.9) but we need to split them into smaller steps to show that they still hold in higher sizes. More precisely : Claim 5.20. Let Pi = Rl,nU2A{£)Rl,n P2 = #3,71-^ 1 #3,71, #3 = Rl,np2Rl,n-Then U2A(X0 = Pf^tk-iMPsfytk-ii-l)-Proof. We compute these matrices in the case n = 9 and then use lemma 5.3 to prove the claim for all n = 4k + 1. Pi,9 = Rl,9U2i,9(ORl,9 = 1 0 x£ 0 0 0 0 0 0 0 1 -e 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 (5.27) P2,9 = -R3,9-Pl,9-R3,9 = 1 0 0 0 0 0 0 0 0 1 £ 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 x£ 0 0 0 0 1 0 0 0 0 0 0 0 0 1 (5.28) 44 Chapter 5. Positive answer for n > 4. ^3,9 = -Rl,9-P2,9-Rl,9 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -( 0 1 0 0 x£ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 -2x£ 0 0 0 0 (5.29) Finally, UuM*0 = Pf9U27,<>{l)P3,9U27,9(-l). For the bigger sizes we notice that ?7 24 ] 7 l(£) = ^24,n-4[0,4]. Therefore by lemmas 5.3 and 5.12 we have Pl,n = Pl,n-4[0,4] = i2i,„-4^24,n-4(O^l,n-4[0,4] = -Rl,„-4[1, 4] • t/24,n-4(£)[0, 4] • i2lin_4[l,4] (5.30) Observe that Pi>n can also be regarded as Pi)Tl_4[0,5]. Hence by lemmas 5.3 and 5.12 P2,n = P2,n-4[0, 5] = i*3,n-4Pl,n-4i*3,n-4[0, 5] = i23,„_4[2, 5] • Pl,„_4[0, 5] • i? 3 ,„- 4 [ 2 , 5] (5.31) Regarding P 2 ) T l as P2]n_4[0,4] we have [0,4] = i?1)„_4P2j„_4i?i,n-4[0,4] = i?i,n_ 4[l,4] • P2,„_4[0,4] • i?i i n_ 4[l, 4] (5.32) Finally we regard U(2,4k-i),n(l) a s ^(2,4fc-5),n-4(l)[0,4] and we obtain U24,n{x£) = C/24)n-4(a;£)[0,4] = P3i7l_4t/(2)4fc-5),n-4(l)P3,n-4^(2,4fc-5),n-4(-l)[0, 4] = ^-4[0,4]-t/ ( 2 ,4fc—5),n—4 (l)[0,4]-P 3,„_ 4[0,4]-C/ ( 2 ,4k—5),n—4 (-1)[0,4] And the claim is proved. (5.33) • Therefore starting with U2A(1) we can successively obtain all t/24(x() for any integer I. Hence if x is a primitive root in GF(g) we obtain all £/24(r;) for any t eGF(g), thus completing Step 2. 45 Chapter 5. Positive answer for n > 4. For substep a) of Step 3 we first obtain U2^{t): U25,9 (*) = R3,9 U2i,9(t)R3,9 ^24,9 (-*) and (5.34) U25,n(t) = LT 2 5 i„_ 4(t)[0,5] = JR 3,n-4C/24,n- 4(i) JR3 >n-4^24 !n- 4(-i)[0,5] = i?3,n_4[2,5] • J724,n-4(t)[0,5] • i*3,„_4[2,5] • U24,n-4(-t)[0,5] Now use claim 5.19 with £ = t to obtain successively all U2j(t) with 5 < j < Ak — 1. We have to work a little harder to obtain the last two transvections in the second row. This is achieved by the following computations (first we do them for n = 9): -Pi,9 = Ri$U25${t)Ri$ = P2,9 = #3,9-Pi ,9 #3,9 = 1 0 0 0 0 X t 0 0 0 0 1 0 0 0 -t 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 --xt 0 0 1 1 0 0 0 0 X t xt 0 0 0 1 0 0 0 -t -t 0 0 0 0 1 0 0 0 .0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 o. 0 0 1 0 0 0 0 0 0 0 —xt --x t 1 0 0 0 0 0 0 xt X t 0 1 46 Chapter 5. Positive answer for n > 4. -P3,9 = Rl,9p2,9Rl,9 = 1 0 0 0 0 0 0 0 0 0 1 0 0 t 0 0 t 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 —xt 0 1 —x t 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2xt 0 0 2x t 1 Pi,9 = U27,9(l)Ps!9U27,9(-l)P^ = 1 0 0 0 0 0 0 0 0 0 1 0 0 —tx 0 0 —tx 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 Finally U28,9{-tx) = U25j9{tx)P4:,9 and U29,9(-tx) = #3,9^28,9 i~t x)R3t9U28,9(t x) As t runs through all elements of GF(g) so does — tx, hence we have just obtained all U2%{t) and U29(t) with t €GF(q) for n = 9. By lemmas 5.3 and 5.12 we have P\\,n = Pl,n-4-[0,4] = i2i,n-4^(2,4fc-7),n-4(*)-Rl,n-4[0,4] = i ? i , „ _ 4 [ l , 4 ] • tf(2,4*-7),n-4(t)[0,4] • i?l ,n-4[ l ,4] , P2,n = P2,n-i[Q, 3] = .R3,„_4-Pl,n-4-R3,n-4[0, 3] = i ? 3 > n _ 4 [ 2 , 3] • P i , n -4 [0 , 3] • #3^-4[2, 3], P3,n = P3,n-4[0,4] = i E 1 > n _ 4 P 2 ) n - 4 i 2 l , n - 4 [ 0 , 4] = i ? i , n _ 4 [ l , 4 ] • P 2 , „ - 4 [ 0 , 4 ] • i 2 i , n _ 4 [ l , 4 ] , 47 Chapter 5. Positive answer for n > 4. Pi,n = P4)n-4[0,4] = C/ ( 2 i4 f c_ 5 ) ) n_4(l)P3,n-4t/(2,4fc-5),n-4(-l)P 3,n-4[ 0> 4] ,4k—5),n—4 (1)[0,4] • P3)n-4[0,4] • tf(2)4*-5),n-4(-l)[0,4] • P - ^ M Hence (^2,4lfe),nW = ^(2,4fc-4),n-4(*)[0,4] = Cf(2,4fc_7))n_4(-r-)P4,9[0, 4] %4fc-7),n-4(-*)[0,4]-P4,9[0,4] and (^2,4*4-1) ,n(*) = U{2 ,4k—3),n—4 (i)[0, 5] = JR3,n-4^(2,4fe),n-4W-R3,n-4^(2>4fc),n-4(-*)[0,5] ,4k),n—4 ( i ) [0 ,5]- i? 3 ,„_ 4 [2 ,5]-C/ ( 2 ,4k),n—4 (-t)[0,5] To finish substep a) of Step 3 we only need to obtain J72i(i) and U23(t). The former is achieved by an easy computation using lemmas 5.15 and 5.16: R2,nU2,4k+l(—t)R2,n = R2,n{I ~ *#2,4fc+l)-R2,n = I + tE2i4k+iR2ln = I + i-#21 = U2l(t) and the latter by the following series of computations: Pl,9 = Rl,9U24,9{t)Rl,9 -1 0 xt 0 0 0 0 0 0 0 1 -t 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 —x t 0 0 0 0 0 1 P2,9 = -^3^1,9-^3,9 — 1 0 —xt 0 0 0 0 0 0 0 1 t 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 xt 0 0 0 0 1 0 0 0 — X t 0 0 0 0 0 1 48 Chapter 5. Positive answer for n > 4. P3,9 = #2,9^1,9 = 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 xt 0 0 0 0 1 0 -2xt 0 0 0 0 0 1 P4,9 = 7?2,9P3,9-R2,9-P3,9 = -2xt 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2xt 0 0 -2xt 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 Finally ^23,9 (~2t) = P^l For the n x n case these computations expand as follows: [0,4] = i2i,„_4l724,n-4(«)^l>n-4[0,4] = J?i,„-4[1,4] • tf24,n-4(*)[<), 4] • i?i,„-4[l,4] P2,n = P2,n-4[0,5] = R3 ,n—4:Pl,n— 4jR3,n-4[0, 5] = P3,n-4[2, 5] • Pi,„_4[0, 5] • i?3,„_4[2, 5] P3,n = P3,n-4[0, 5] = P 2, n_ 4Pi, n_ 4[0, 5] = P2,„_4[0,5] • Pi,n_4[0, 5] P4,n = P4,n-4[0,5] = -R2,n_4P3,n_4-R2,n-4P3,n-4[0, 5] = R2,n-i[0, 5] • P 3,„-4[0, 5] • R2,n-4[0, 5] • P3,„-4[0, 5] Finally U23,n(-2t) = t/23,n-4[0,5] = PA,n-4P^_4[0,5] = P4,„_4[0,5] • P2,n-4[0,5] -2 49 Chapter 5. Positive answer for n > 4. This finishes substep a) of Step 3. For substep b) we first obtain the \"double transvection\" Y = I + tEyi — tEn2, then through other \"double transvections\" we will obtain the transvection U\\2{t) and then all transvections ui2(t). • The first part is achieved by the following computations: Pi,9 = #1,9^21,9 ( — ) Rl,9 = 2 x 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 X 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 -1 —X 0 0 0 0 0 0 1 P 2 , 9 = Pl.9U, 1,9^21,9 0 X 0 0 0 0 0 0 0 1 X 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 —x 0 0 0 0 0 0 1 -^3,9 = ^3,9^21,9 t 2x2 -1 - 2 ' 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -P3,9 — 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 2 1 2< 0 0 0 0 0 0 1 50 Chapter 5. Positive answer for n > 4. Then P4,9 = I + tE\\2 — tE$2 = P$#-We easily expand these computations to the n x n case: P\\,n = -Pl,n-4[0, 2] = i?i ) T i-4^21,n-4 i^j ^l,n-4[0, 2] = J2i,n_4[l,2] • U2i,n-4 [0,2] • i2 l i n_ 4[l,2] P2,n = P2)n-4[0,2] = P i , n - 4 l72l 1 „-4 (~^) [0,2] = Pi,„_4[0,2] • U2l,n-4 (~^J [0,2] Pz,n = P3,n-4[0,2] = P2,n-4^21,n-4 ( ~ ^ ) ^2,n-4[0,2] = P2,„_4[0,2] • U2i,n-i ( - ) [0,2] • P2,„-4[0,2] Then P 4 , „ = I + tEl2 - tEn2 = P4,n_4[0,2] = P32)n_4[0,2] = P3>n-4[0,2] . In the subsequent computations we will refer to this P 4 i „ as Tn We now obtain another involution using t = x in Tn: Ri,n = TnR\\,n-To describe how it acts on the elementary matrices we state the following two lemmas which are analogues of lemmas 5.13-5.18. The proof again is trivial. For left multiplication by -R4,„ we have Lemma 5.21. For any 1 < j < 4k + 1 a>) Ri,nE\\j = Eij b) Ri;nE2j = — E2j c) Ri>nE2i+i,j = E2i+2,j, for 1 < I < 2k - 1 51 Chapter 5. Positive answer for n > 4. d) RijnE2i+2,j = E21+IJ forln = En b) Ei2Rl,n = —Ei2 c) Ei}2i+iRi,n = Eit2i+2, forl 4. -^ 2,9 = -^4,9^1,9-^4,9 = (5.36) 1 -2t 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 t 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 Now we repeat computations 5.35-5.36 again starting with instead of T 9 , thus obtaining \"double transvections\" with non-zero entries at the spots (1,2) and (6,2) and also (1,2) and (5,2). In fact in general case we can repeat these computations to obtain \"double transvections\" all the way up to the spots (1,2) and (3,2) thanks to the following Claim 5.23. Let T = I + aE12 + BE2l+l>2 with 2 < I < 2k. Then (U23{l)R3T)2 = I + 2ctEl2 + pE2l>2 and R4(I-2aEx2 + 0E2lt2)R4 = I-2aEl2-/3E2t^2 Proof. Using lemmas 5.18 and 5.17 first compute {I + E23)R3{I + aE12 + 3E2i+1>2) = {R3 - #23) (7 + aE12 + 3E2l+ly2) — i?3 — E23 + ctE12 + 8E2ij2 - 3E2i+i%2 (5.37) 53 Chapter 5. Positive answer for n > 4. Now square it: (R3 - # 2 3 + « # i 2 + PE2i,2 - B E 2 W ) • (R3 - E23 + ctE12 + (3E2li2 - BE2l+h2) = I — E23 + OLE\\2 4- /3#2/,2 — /3(#2/,2 — #21+1,2) + #23 + a ( # i 2 + # 1 3 ) - aEn (5.38) + /?(#21,2 + #2/,3) — /3#21,3 — /3(#2Z+1,2 + #21+1,3) + /3#21+1,3 = I + 2aE12 + BE2K2 Also by lemmas 5.21 and 5.22 RA{I + 2aEl2 + 0E2li2)R4 = 1 + 2aE12RA + pE2l^2R4 = I - 2aE12 - BE2l_lj2 (5.39) • From this claim it follows that starting with the previously obtained Tn = I + tE\\2 — tE4k+i,2 we obtain after 2k — 1 repetitions of the computations 5.35-5.36 a \"double transvection\" I + 22k~1tEi2 + tE32 along with all intermediate \"double transvections\". We are finally ready to obtain all transvections Ui2(t). For n = 9: \" 1 -16* 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 Ul2(-m) = {U23(1)R3(I + 8i#i2 + i# 2 3)) 2 = (5.40) 54 Chapter 5. Positive answer for n> 4. And we extend computation 5.40 to an arbitrary n by UnA-2^) = C/i2,n_4(-22fci)[0,3] = ( * 7 2 3,n - 4(l)i* 3 ( / + W-HEl2,n-4 + tE23,n-4))2{0, 3] 2 (5-41) = (U23,n-4(l)R3(I + 2 2 f c-liE 1 2 , N - 4 + tE23,n-4))[0, 3] = (u23,n-i(l)[0,S\\-R3,n-iM • {I + 22k-HE12,n^ + tE23,n^)[0,3]y Now to complete substep b) of Step 3 we note that we can obtain all transvections in the sec-ond row by just multiplying the \"double transvections\" previously obtained by an appropriate transvection Ui2(—2lt). Finally to finish Step 3 and thus the proof of the proposition we refer to computation 5.21. • 5.5 Case of (4k + 3) X (4k + 3) matrices. In this section we deal with the case n = 4fc + 3, k > 1. This case is almost an exact copy of the previous case (n = 4k + 1, k > 2). In fact all computations stay the same with the results differing by plus or minus sign here and there, which will not affect the argument. We will use the Bar Operation (see Definition 5.2) to increase the size of the matrices inductively and we will use lemma 5.3 to verify that the same computations yield the same results for all sizes. Precisely we want to prove the following Proposition 5.24. Let -1 X 0 0 0 1 1 0 0 Ri = 0 1 0 R2 = 0 -1 0 , and R3 0 -1 1 0 -x -1 1 0 0 0 0 1 where x is such that —x is a primitive root in GF(q). Define inductively: Ri,3 = Ri, R2,3 = R2, R3,3 = R3 and R1>n = iJi, n_ 4[l,2], R2,n = ^2^-4[0,2], R3n_4[3,3], for n = 4k + 3, k > 1. 55 Chapter 5. Positive answer for n > 4. Then SLn(q) = {Rl,n, R2,n, R-3,n)• As in all previous cases we have an immediate Corollary 5.25. PSL^+siq), k>2 can be generated by three involutions two of which com-mute. Proof. This follows immediately from the previous proposition, easy computations to check that i?i, R2, i?3 and R1R2 are indeed involutions and lemma 5.3 • In essence the proof of proposition 5.24 follows from the following (trivial) key observation and lemma 5.3, Lemma 5.26. a) Rl,n = i?i,n-4[l,2j], l < j < 2 * - l , b) R2,n =R2,n-A[0J], 2 < j < 4 / c - 2 , C) i?3,n = -R3,n-4[3,2j + l], 0 < j < 2k - 1. The comments to lemma 5.12 also apply here. See Appendix D for the Maple V input file to verify computations. The following three lemmas describe how the generators R\\,n, R2,n, Rz,n act on elementary ma-trices Eij. (These lemmas can also be regarded as an alternate definition for Jf?i)7l, R2,n, Rz,n)-The proofs are elementary. Left multiplication by the first generator is described by the following Lemma 5.27. For any 1 < j < 4k + 3 a) R\\tnE\\j = —E\\j b) Ri,nE2j = xEij + E2j - xEAk+3,j 56 Chapter 5. Positive answer for n > 4. c) RltTlE2l+id = E2i+2,j, forln = Eij2l+2, for 1 n — —Ei2 57 Chapter 5. Positive answer for n> 4. c ) E i j R 2 , n = E^, f o r 3 < i < 4 k + 2 d) ^ , 4 ^ + 3 / ^ 2 , 7 1 = E n Finally left multiplication by the third generator is described by the following Lemma 5.31. For any 1 < j < 4k + 3 a) R3,nE\\j = — E i j b) R3,nE2i,j = - E 2 l J , f o r l < l < 2 k + l c ) R 3 i n E 2 i + i j = E21J + E 2 l + i j , f o r l < l < 2 k + l And right multiplication by the third generator is described by the following Lemma 5.32. For any 1 < i < 4k + 3 a) E n R 3 j n = E n b) E i j 2 l R 3 , n = - E i t 2 i + E h 2 l + i , f o r l < l < 2 k + l c ) Eit2l+iR3tn = E i t 2 i + i , f o r l < l < 2 k + l Now we are ready to prove proposition 5.24. P r o o f o f p r o p o s i t i o n 5.24- The steps in this case are exactly the same as in case n = 4 k + 1. Step 1 will be very easy and we'll obtain U23(l). To complete Step 2 we will first obtain U24(l) and then all U2i{t),t Q . G ¥ { q ) . We will do it by first obtaining U 2 j ( l ) for 4 < j < 4k + 1, then having obtained C/2,4A;+i(l) w e w d l use it to finish Step 2 by obtaining all U24(t) with t €GF(g). Step 3 will consist of three following substeps: a) Obtain all U2j(t) 58 Chapter 5. Positive answer for n > 4. b) Obtain all Ui2{t) c) Obtain all Uij(t) For Step 1 we compute: t/23,7(-4) = (i?2,7i?3,7)4 = 1 0 0 0 0 0 0 0 1 -4 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 (5.42) and note that R2>N = 7?2,n-4[0,3] by lemma 5.26, hence by lemma 5.3 and computation 5.42 we have U23A-4) = tf23,n-4(-4)[0,3] = (i?2,n_4[0,3] .i?3in_4[3,3]r Note that we are not able to start the computation from n = 3 since i?2,7 7^ 7?2,3[0, 3]. But for all higher sizes we have just obtained all transvections U23>n(l), where I is an integer. We now proceed with Step 2. First we obtain U24,n(l) and U25>n(l) with I an integer. For the base of the induction (n = 7) we make the following computations: P\\j = RIJU23J{1)RIJ 1 0 0 X 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 — X 0 0 1 P 2 ,7 = R. ZJPIJRZJ — 1 0 0 X — X 0 0 0 1 0 1 -1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 X —x 1 0 0 0 0 X —x 0 1 (5.43) (5.44) 59 Chapter 5. Positive answer for n > 4. #3,7 — #2,7#2,7#2,7#;; >-l 2,7 1 0 0 0 0 0 0 0 1 0 -2 2 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 (5.45) and finally U2ij{—2) = #3,7#3,7#3,7 and (5.46) 025,7(2) = U24J(2)P3J (5.47) In sizes higher than 7 we will repeat computations 5.43-5.47 starting with 1/25(1) instead of £%(1) to obtain U2Q(2) and U2j(2). In fact the same computations will work successively in the n x n case and we will obtain all transvections in the second row but the last two. (In the 7x7 case we've already done so). In other words in the n x n case we can obtain all U2j(l) for 3 < 3 < 4.k + 1 thanks to the following Claim 5.33. Letl2i+2 + £ # 2 , 2 i + 2 - ££#4fc+3,2;+2 Now by lemmas 5.31 and 5.32 we have #2 = #3,n#l#3,n = #3,n(7 + (,xEit2[+2 + £ # 2 , 2 / + 2 ~ £z#4fc+3,2/+2)#3,n = I — £ a ; £ i ) 2 / + 2 # 3 , n — £ # 2 , 2 / + 2 # 3 , n — ££(#4fc+2,2 /+2 + #4fc+3,2i+2)#3,n = I + £xi?i,2i+2 - £x#l,2/+3 + £#2,2J+2 — £ # 2 , 2 / + 3 + ££-#4fc+2,2/+2 — £x#4fc+2,2i+3 + ££#4fe+3,2i+2 — ££#4fc+3,2Z+3 60 Chapter 5. Positive answer for n> 4. Now write P2 = I + Q. Then since 21 + 2 > 2 and 21 + 3 < 2(2A; - 1) + 3 = 4k + 1 < 4k + 2, Q2 = 0 as every product of elementary matrices involved is equal to 0. Hence P 2 ~* = I — Q-Also by lemmas 5.29 and 5.30 we have -R2,nP2-R2,n = R2,n{I + £xEit2l+2 ~ £xEifll+3 + £E2l2l+2 ~ £E2>2l+3 + (xE4k+2t2l+2 - £xE4h+2,2l+3 + ££-E4fc+3,2/+2 ~~ £xEik+zfil+3)R2,n = I + i(xE4k+3j2l+2 - xEik+3,2l+3 ~ E2>2l+2 + E2,2l+3 + xEik+2,2l+2 - xEik+2,2l+3 + xEipi+2 ~ xEifil+3)-#2,71 = I + £{xEik+32l+2 — xEik+z:2l+3 - E2,2l+2 + E2>2l+3 + xEik+2,2l+2 - xEik+2t2l+3 + xE\\fll+2 ~ xE\\pi+3) = I + Q' Again all the products of elementary matrices in the product of Q and Q' are 0. Hence P 3 = - R 2 , n P 2i? 2 , n P 2 - 1 = (I + Q')(I - Q) = I + Q' - Q = I - 2ZE2,2l+2 + 2£E2W Finally by lemmas 5.31 and 5.32 -R3,n-P3-R3,n = R3,n(I ~ 2£-E 2,2(+2 + 2£i?2l Z+3)-R3,n = I + £(2£?2,2/+2 — 2J^2,2;+3)-R3,n = / - 2£E2>2l+2 + 2£^2,2i+3 - 2£/32l Z+3 = ^2,2H-2(—2 £) and ^2,21+2(2 £ ) P 3 = {I + 2££?2,2i+2)(-f - 2£E2,2l+2 + 2£i?2,2i+3) = I - 2£E2,2l+2 + 2£-E2,2/+3 + 2£E2,2l+2 = ^ 2,2/+3(2£) and the claim is proved. • Therefore, using the claim with £ = 1 we successively obtain V~2j(l), where I is an integer and 3 < j < 4k + 1. To finish Step 2 we need to produce U2i(t) for all t €GF(q). The computations are exactly the same as in the (4k + 1) x (4k + 1) case (5.20-5.29). More precisely : 61 Chapter 5. Positive answer for n > 4. Claim 5.34. Let Pi — #1,71^24 (0#l,n #2 — #3,n#l#3,7i, #3 = #l,n#2#l,n-Proof. We compute these matrices in the case n = 7 and then use lemma 5.3 to prove the claim for all n = 4k + 3. ~ 1 0 xt, 0 0 0 0 ~ 0 1 £ 0 0 0 0 Finally, #1,7 = #1,7^24,7 (0#1,7 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 #2,7 = #3,7#1,7#3,7 = 0 0 - x f 0 0 0 1 1 0 -x£ 0 0 0 0 0 1 - f 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 - x f 0 0 1 0 0 0 - x f 0 0 0 1 #3,7 = #1,7#2,7#1,7 = 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -£ 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 x £ 0 0 [/24,7(-x0 = #3:7^5,7(l)#3,7C/2 5 ,7(-l). (5.48) (5.49) (5.50) For the bigger sizes we notice that E/24,n(0 = ^24,71-4 [0,4]. Therefore by lemmas 5.3 and 5.26 we have #l,n — #l,n—4 [0,4] = # i , n - 4 £ / 2 4 , n - 4 (O # l , « - 4 [ 0 , 4 ] = #1,„- 4[1,4] • L/24,n-4(0[0,4] • #l,n- 4[l,4] (5.51) 62 Chapter 5. Positive answer for n > 4. Observe that P\\,n can also be regarded as Pi ] n _ 4 [0, 5]. Hence by lemmas 5.3 and 5.26 P2,n = P2,n-4[0, 5] = JR 3 )n-4Pl,n-4#3,r l-4[0, 5] = i?3,n-4[3, 5] • Pi,„_ 4[0, 5] • P 3,n- 4[3, 5] (5.52) Regarding P2 ] T l as P2>n_4[0,4] we have P3,n = p3,n-4[0, 4] = i 2 i , n _ 4 P 2 , n _ 4 i i i i n _ 4 [ 0 , 4] = i?l,„- 4[l, 4] • P 2, n_ 4[0, 4] • i J i > n _ 4 [ l , 4] (5.53) Finally we regard t/(2,4fc+i),n(1) as L 7( 2,4fc-3),7i-4(l)[0, 4] and we obtain U24,n(-X0 = tf24,n-4(-z£)[M] = ^3>n-4^(2)4*-3),n-4(l)-P3,n-4^(2)4*-3),n-4(-l)[0, 4] = P3;n1_4[0,4] • C/(2,4fc-3),n-4(l)[0,4] • P 3 l „- 4 [0,4] • C/ ( 2 i 4 f c_ 3),„_ 4(-l)[0,4] And the claim is proved. (5.54) • Therefore starting with f724(l) we can successively obtain all U~24{{—x)1) for any integer Hence if —x is a primitive root in GF(g) we obtain all U2i{t) for any t E G F ( q ) , thus completing Step 2. For substep a) of Step 3 we first obtain U25{—t): U25j(-t) = R3,7U24,7(t)R3,7U24,7(-t) (5.55) and ^25,71 (-*) = t/25,n-4(-*)[0,5] = i?3,n-4^24,n-4(*)-R3,n-4#24,n-4(-*)[0, 5] = #3,n-4[3, 5] • t/24,n-4(*)[0, 5] • i?3, n_ 4[3, 5] • tf24)„_4(-t)[0, 5] . Now use claim 5.33 with £ = t to obtain successively all U2j{t) with 5 < j < 4k + 1. We have previously obtained U2z{C) but not U~2z{t). We now do just that using the matrix P 2 from Claim 5.34 (see computation 5.49): \" 1 0 0 0 0 0 0 0 1 2£ 0 0 0 0 1 0 0 0 0 t/ 2 3 , 7 (2£) = P 2 j 7 P 2 , 7 P 2 , 7 P 2 ( 7 1 ) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 (5.56) 63 Chapter 5. Positive answer for n > 4. Hence setting £ = t we have all U2zj(t). Now we expand computation 5.56 using the Bar Operation: C/23,n(2£) = C/ 2 3 >„-4(2£)[0,4] = P 2, 7P 2, 7i? 2, 7P 2 (- 1 }[0,4] = P2,7[0,4] • P2)7[0,4] • P2,7[0,4] • P2(,7X)[0,4] To obtain £ / 2 ] 4fc + 2 ( / j ) and t/2,4jfc+3(£) we make the following computations (first we do them for n = 7): P i > 7 = Ri,7U2z,7{t)Ri,7 = P 2 ) 7 = RZJPIJPZJ Pz,7 = -Rl,7P 2 ,7Pl,7 = 1 0 0 X t 0 0 0 0 1 0 t 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 _ 0 0 0 -xt 0 0 1 _ \" 1 0 0 xt -x t 0 0 \" 0 1 0 t -t 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 X t -X t 1 0 . 0 0 0 X t -X t 0 1 1 0 0 0 0 0 0 \" 0 1 t 0 0 -t 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 X t 0 1 --x t 0 0 0 0 0 0 1 0 0 0 -2xt 0 0 2xt 1 P4,7 = U2bj{-l)P3,7U2bJ{l)P^ = 1 0 0 0 0 0 0 0 1 —X t 0 0 xt 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 64 Chapter 5. Positive answer for n > 4. Finally U26,7{tx) = U23,7(tx)P4,7 and U27j(-tx) = R-ijU2Qj(-tx)RZjU2Qj{tx) As t runs through all elements of GF(g) so does — tx, hence we have just obtained all U2e(t) and U27(t) with t eGF(q) for n = 7. By lemmas 5.3 and 5.26 we have #l,n = #l,7i-4[0, 2] = i2l,n-4O(2,4fc-5),n-4(*)#l,n-4[0, 2] = J?i ) T i-4[l ,2] • ?7(2,4fc-5),n-4(*)[0)2] • # i , n _4[ l , 2], P2,n = #2,n-4[0, 3] = 7?3 ) T l_4Pi ! n_4i?3 ] n_4[0, 3] = R3tn-4[3, 3] • PI J 7 J_4[0, 3] • i?3 i 7 l_4[3, 3], #3,71 = #3,n-4[0,2] = iH ,7 i -4#2 ,n -4# l ,7 i -4[0 , 2] = # l i n _ 4 [ l , 2 ] • P2]n_4[0, 2] • Ri^4[l, 2], #4,n = #4,n-4[0,2] = J7(2,4*;-3),7i-4(l)#3,7i-4C7(2,4fc-3),7i-4(-l)#37n-4[0'2] = O(2,4*-3),n-4(l)[0,2] • P 3 , „ - 4 [ 0 , 2 ] • t/(2,4*-3),n-4(-l)[0,2] • Hence U(2,Ak+2),n(tx) = ^(2,4A:-2),7i-4( i a ;)[0, 2] = [7(2 ,4fc—5),n—4 (tx)P4,7[0,2] = ^(2,4fc-5),7i-4(^)[0,2]-P 4, 7[0,2] and U(2,4k+3),n(t) = L7(2,4fc-l),n-4(*)[0, 3] = #3,n-4f7(2,4fc+2),7i-4(*)#3,7i-4^(2,4A:+2),n-4(-*)[0, 3] = #3,7i-4[2, 3] • C7(2)4fe+2),7i-4(*)[0, 3] • #3,n_4[2, 3] • J7(2)4fc+2))n-4(-*)[0, 3] To finish substep a) of Step 3 we only need to obtain U2i(t). This is achieved by an easy computation using lemmas 5.29 and 5.30: #2,nC/2,4fc+3(-*)#2,7i = #2,7i(7 - *#2,4fc+3)#2,7i = I + *#2,4fe+3#2,n = I + tE2i = U2i(t). 65 Chapter 5. Positive answer for n > 4. This finishes substep a) of Step 3. For substep b) we first obtain the \"double transvection\" Y = I + tE\\2 — tEn2, then through other \"double transvections\" we will obtain the transvection U\\2{t) and then all transvections ui2(t). The first part is achieved by the following computations: Pl,7 = #1,7^21,7 - Rl,7 = Pl,7 — #1,7^21,7 ( — 2 -x 0 0 0 0 0 1 X 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 -1 X 0 0 0 0 1 —X 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 x 0 0 0 0 1 #3,7 = #2,7^21,7 '2x2 ) Plj = Then -1 1 \" a ' 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 2 1 2* 0 0 0 0 1 P4,7 = / + tE12 - tE72 = P|> 7. 66 Chapter 5. Positive answer for n > 4. We easily expand these computations to the n x n case: Pl,n = Pl,n-4[0,2] = Ri,n-iU2l,n-A (^j #i,„_4[0,2] = i2i > n_ 4[l,2] • r/2i,n-4 (J^j [0, 2] • fli,n_4[l,2] P2,n = P2,n-4[0,2] = Pl,„-4^21,n-4 (^j [0,2] = Pi>n_4[0,2] • U21,n-A (^j [0,2] P*,n = P3,n-4[0,2] = P2,n-AU2l,n-4 P2,n-4[0,2] = P2l„-4[0,2] • U2l,n-4 (\"2^2) [°> 2] • 2^,n-4[0,2] Then 7 + tE12 - tEn2 = P4,n_4[0,2] = P32)7l_4[0,2] = P3,„-4[0,2] . We will call this matrix Tn. We now obtain another involution using t = —x in Tn: Ri,n — TnR\\n. To describe how it acts on the elementary matrices we state the following two lemmas which are analogues of lemmas 5.27-5.32. The proof again is trivial. For left multiplication by i ? 4 ) n we have Lemma 5.35. For any 1 < j < 4k + 3 a) R^nE\\j = —E\\j b) R^nE2j = E2j c) R4tnE2i+l!J = E2i+2>j, forl 4. And right multiplication by R^n is described by the following Lemma 5.36. For any 1 < i < 4k + 3 a) EnR4,n = —En b) EiiR^n = Ei2 c) Eit2i+iR4,n = Eit2i+2, for I 2i+2R4,n = #1,21+1, forl7 instead of T7, thus obtain-ing \"double transvections\" with non-zero entries at the spots (1,2) and (4,2) as well as (1,2) and (3,2). In fact, in the general case we can repeat these computations to obtain \"double transvections\" all the way up to the spots (1,2) and (3,2) thanks to the following 68 Chapter 5. Positive answer for n > 4. Claim 5.37. Let T = I + aE12 + (3E2l+h2 with 22)RA = / - 2 a £ 1 2 - / 3 £ 2 / - i , 2 Proof. Using lemmas 5.32 and 5.31 first compute (I - E23)R3(I + aEl2 + pE2l+1>2) = (R3 - E2Z)(I + aE12 + (3E2l+1>2) = Rz — E2z (5.59) — aE\\2 + 0E2i>2 + (3E2i+i<2 Now square it: (Rz — E2z — aE\\2 + (3E2it2 + (3E2i+it2) • (Rz - E2z — a.E\\2 + (3E2i}2 + /3E 2; +i ) 2) = I + £ 2 3 + OLE\\2 — j3E2i,2 + j3(E2i2 + £ 2 / 4 - 1 , 2 ) — E2z - a(-El2 + Eiz) + aExz (5-60) + P(—E2i,2 + E2itz) — PE2ii3 + P(—E2i+it2 + E2i+itz) — @E2i+itz = 1 + 2aEl2 - pEhia Also by lemmas 5.35 and 5.36 R4 (I + 2 a £ 1 2 - /3E2lj2)R4 = 1- 2aE12R4 - PE2l^2R4 = 1- 2aE12 - PE2l_1>2 (5.61) • From this claim it follows that starting with the previously obtained Tn = I+tE\\2 — tE4k+3,2 we obtain after 2k repetitions of the computations 5.57-5.58 a \"double transvection\" I + 22ktE\\2 — tEz2 along with all intermediate \"double transvections\". We are finally ready to obtain all 69 Chapter 5. Positive answer for n > 4. transvections U\\2(t). For n = 7: f/ 1 2( 8i) = (U2z(-l)R3(I + 4tE12 + tE23))2 = 1 8* 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1^00 0 0 0 0 0 1 0 0 0 0 0 0 0 1 And we extend computation 5.62 to an arbitrary n by U12,n(22k+1t) = r/12>n_4(22*+it)[0,3] = (U23,n-4(-l)R3(I + 22ktE12,n_4 - i£23,n-4))2[0, 3] (5.62) (5.63) = (t/23,n-4(-l)#3(7 + 22ktEl2,n_4 - tE23,n-4))[0, 3] = (t/23,n-4(-l)[0,3] • i?3)n-4[3,3] • (I + 2*ktE12>n_4 - tE23>n^)[0,3])2 Now to complete substep b) of Step 3 we note that we can obtain all transvections in the second column by just multiplying \"double transvections\" previously obtained by an appropriate transvection U\\2(—2lt). Finally to finish Step 3 and thus the proof of the proposition we refer to computation 5.21. • 5.6 C a s e o f 4k x 4k m a t r i c e s . In this section we prove the possibility of generation of PSl4k(q) with k > 2. Precisely we prove Proposition 5.38. Let 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 z O O O O O O - l #1 = R?. 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 and 70 Chapter 5. Positive answer for n > 4. #3 = 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 where x is a primitive root in GF(q). Define inductively: 0 0 0 0 0 0 1 -1 #1,8 = #1) #2,8 = #2, #3,8 = #3 and # l , n = # i , „ - 4 [ 0 , 2 ] , i? 2 ,n = # l ,r l -4[ l , l ] , # l , n = # l , n - 4 [ l , 0], for n = Ak, k > 3. Then SLn(q) = ( # i , n , #2,n, #3,n)-An immediate corollary of this proposition is Corollary 5.39. PSL4k{q),k > 2 can be generated by three involutions two of which commute. The proof is a routine check that the matrices are indeed involutions and that the first two commute (this is done exactly the same way as in corollaries 5.11 and 5.25) Before starting the proof of Proposition 5.38 we, as in earlier cases, observe the following trivial facts: Lemma 5.40. a) # i , n = # i i n _ 4 [ 0 , j ] , b) # 2 , n = #2,n- 4 [ l ,2j + l], c) # 3 , n = #3,n- 4[l,2i], 0 < j < Ak - 7, 0 < j < 2k - A, 0 4. much simpler permutation computations. We also provide diagrams to help with some of the computations. In Appendix E though we provide the full Maple V input files including even those simple but crucial computations. Proof of Proposition 5.38. We are going to complete the same Steps described in Section 5.1. Step 1 is relatively easy (especially when characteristic p does not divide 4k — 2). In fact this is the only step in the proof that involves heavy matrix computations similar to those in Sections 5.2-5.5. We obtain U^h-ifi^) during this step. Step 2 is also quite simple and we obtain U4k-2,2(t) and (as can be easily seen) U4k-i,2(t) together with U23(t) for all t eGF(q). And in Step 3 we first aim for getting transvections in the second column but in fact we obtain all transvections in the upper-left (4k — 2) x (4k — 2) block. After that the proof is easy to finish. We first compute (R2R3)ik~2. (Here we include the computation for k = 2). (#2#3) 6 = -1 0 0 -1 0 0 0 0 0 0 0 - 1 0 0 0 - 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -10 0 0 1 6 0 0 1 Note that in the general case the matrix (i? 2 # 3 ) 4 f e _ 2 has (4k — 2) x (4A; — 2) block equal to —I and 2x2 block-transvection I + (4k — 2)E\\2. This follows from the fact that both R2 and R3 are block-diagonal matrices with blocks of the sizes (4k — 2) x (4k — 2) and 2x2. The first block is a sign-permutation matrix with a single —1 at the end in R2 and a permutation matrix in R3. The product of these two permutations is a (4k — 2)-cycle. The product of 2 x 2 matrices is the negative of the simple transvection I + E\\2. 72 Chapter 5. Positive answer for n > 4. Now the following sequence of computations will produce a transvection Let Pl,8 = -1 0 0 0 0 0 0 0 P 2 , 8 = (P 3 PlPl ,8#3) 4 = 3,8 0 0 0 0 0 0 \" 0 0 0 0 0 0 --1 0 0 0 0 0 0 --1 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 a 0 0 0 0 0 1 _ 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -2ax 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 - 2 ( -2 +a) X 0 0 0 0 1 0 0 —4x 0 0 0 0 0 1 \" 1 0 0 0 0 0 0 0 \" 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 —8ax 0 0 0 0 1 0 0 0 0 0 0 0 0 1 (5.64) (5.65) (5.66) This gives transvections {/^ (mx) with m an integer if characteristic p does not divide 4k — 2. The computations 5.64-5.66 are easily expanded by the Bar Operation to obtain U^k-i^rnx) with m an integer for this case: P2 [0,2] = (P3,n-4#1 ,71 — 4pL,7!.— 4 i? 3 ,„- 4 ) 4 [0 ,2] = (i? 3,n- 4[l,2] • J?i,„-4[0,2] • Pi,n_4[5,2] • i? 3,n-4[l,2]) 4 (5.67) (5.68) PS,n = P3,n-4[0,2] = P 1 2 > n_ 4P 2 > n_ 4P 172_ 4P 2 ) n_ 4[0,2] = Pi,n- 4[5,2] • P2,n-4[0,2] • P{;n2_4[5,2] • P2,n_4[0,2] (5.69) (5.70) 73 C h a p t e r 5. P o s i t i v e answer for n > 4. In case the characteristic p divides Ak — 2 we obtain transvections (/^^(ma;) w i t h m an integer using the following computations: #1,8 = -1 0 0 - 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 1 0 0 0 1 0 0 0 1 #2,8 = (#1,8#1,8) 4 = 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 -Ax 0 0 0 0 0 0 1 A n d expand this by #2,n - #2,n- 4 [0,2] = ( P 1 ) r l _ 4 # l , n - 4 ) 4 [ 0 , 2] = ( P 1 > n _ 4 [ 5 , 2 ] • # i , n _ 4 [ 0 , 2]) 4 (5.71) T h i s completes Step 1 of the proof. We make a couple more computations to obtain L / ^ - i ^ m a ; ) i n case the characteristic p divides Ak — 2 to uniformize the consequent considerations. 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 -Ax 0 0 0 0 1 0 0 Ax 0 0 0 0 0 1 #3,8 = #3,8#2,8#3,8 = 74 Chapter 5. Positive answer for n > 4. #4,8 = #1,8#3,8#1,8 = 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 -Ax 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 -Ax 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 . 0 0 0 0 0 0 0 \" 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 8x 0 0 0 0 1 0 0 0 0 0 0 0 1. Each of these computations is easily expanded by the Bar Operation at the spot (2,2) in exactly the same manner as it has been done in expansions 5.67-5.71. For Step 2 we first note that UAk-2,2(x) = RiU4k-\\,2(x)Ri- From now till the end of Step 2 we will use only R2 and # 3 to obtain new transvections. Since both are just sign-permutation matrices in the block (Ak — 2) x (Ak — 2) we will obtain only transvections (in that block) by conjugating transvections from that block. Also it is obvious that from a transvection Uij(a) we can obtain only transvections C^y (±a) . Since Uij(a) is just the inverse of Uij(-a) we can without loss of generality assume that non-diagonal entry stays the same under any conjugation by these two generators. Therefore we only need to follow the position of the non-diagonal entry. #5,8 = #4,8#1,8#4;8#1,8 = 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 -8x #6,8 = #3 8#5.8 = 3,8^5,8 1 0 0 0 0 0 0 0 75 Chapter 5. Positive answer for n > 4. The permutation corresponding to R2 is p2 = (2,3) (4,5)... (4k — 4,4k — 3). The permutation corresponding to #3 is p3 = (1,2)(3,4)... (4& - 3,4k - 2). Therefore any index of the non-diagonal entry is changed by ± 1 depending on parity and the generator that is used for conjugation (except when the index is 1 or 4k — 2 and the conjugator is R2, in which case the index does not change). Hence starting with U4k-2,2{x) and conjugating alternately by R3 and R2 we successively obtain starting with R3 positions: {4k - 3,1), {4k - 4,1), (4k - 5, 2), (4k - 6, 3),... , (2k, 2k - 3), (2k -1, 2k — 2) and starting with R2 we successively obtain positions: (4k — 2, 3), (4k — 3,4),... , (2k + Z,2k-2),(2k + 2,2k-l). Thus if n — 8 (k — 2) we can obtain U23(x). Now, the commutator of UQ2(X) and U23(x) is U§3(x2). We then obtain U$2(x2) by conjugating by R2 and again bring the non-diagonal entry (this time x2) to the position (2,3). The commutator of Ue2(x) and U23(x2) is UQ3(X3). Repeating this process we obtain all powers of x as non-diagonal entry at the position (6,2). Thus if a; is a primitive root in GF(g)we obtain all transvections at this position. This completes Step 2 in the case n — 8. For the general case we need a little extra work. Having obtained U2k+2,2k-i(x) and U2k-\\,2k-2(x) we obtain U2h+2,2k-2(x2) by taking their commutator. By conjugating successively by R3 and R2 starting with R3 we move this entry from position (2A; + 2,2k - 2) through (2k + 1,2k - 3),... , (5,1), (4,1), (3,2) to position (2,3). See figure 5.1 to for the details of trajectories of the non-diagonal entry under conjugation. Now the commutator of U4k-2,2(x) and U23(x2) is Uik-2,z(xz)- Hence by repeating the process we can obtain all odd powers of x at the position (4k — 2,2). But since every element of GF(g) can be written as a sum of (two) odd powers of a primitive root, taking x to be primitive root gives us all transvections at the position (4k — 2,2) thus completing Step 2. For Step 3 we assume that we have obtained all transvections Uik-x,2(t) and U23(t), t GGF(g). 76 Chapter 5. Positive answer for n > 4. 1 (4k-2,2) (4k-2,3) Figure 5.1: First step of obtaining U4k-2,2(t), k > 2. (Curved arrows denote commutators.) (They can be obtained from U4k-2,2{t) by conjugation by R\\ or a sequence of conjugations by i?3 and R2.) We will now concentrate on obtaining transvections in the second column. First from U 4. At this moment we have obtained all transvections C/j2 (t) with i = 4j — 1 and i = Aj + 2 for 1 < j < k — l.(See figure 5.2). <4k-2J) Figure 5.2: First step of obtaining second column. (Curved arrows denote commutators.) Now succesively conjugating U^k-i^it) by R3 we obtain C/^ —1,1 (*), then conjugating by Ri we get C/4fe_2,i(<), then using R3 again we get C4fc-3,2(*)-Now we again repeatedly do the following starting with j = Ak — 3: Take a commutator of Uj2(t) and (723(1) to get Uj3(t). Conjugate Uj3(t) by R2, to get r/,-_1)2(t). Conjugate Uj-ifi(t) by # 3 , i?2 and R3 to obtain i7 7_4 )2(i). 78 Chapter 5. Positive answer for n > 4. This way we get all the transvections Ui2(t) with i — 4j — 3 and i = 4j with 1 < j < k —1. R3 Figure 5.3: Obtaining second column (whole block). (Curved arrows denote commutators.) In fact we have obtained much more than that. Once we have all transvections in the second column of the block (4k — 2) x (4k — 2) we in fact have all transvections in this block which we obtain only by conjugating by a series of i?3's and i?2's. (See figure 5.3 - the last fact outlined by dotted lines). Finally we note that since we have C^-x^i) we can (taking appropriate commutators) obtain the whole 4k — 1st row except the last entry. Also since £ /2 ,4A : - iM = -Ri^2,4fc-2(*)-Ri w e a l s o obtain all 4k — 1st column without the last entry. 79 Chapter 5. Positive answer for n > 4. Two of the last necessary transvections are obtained as follows: U1Ak{t) = i?3^2,4fe-i(t)#3^i,4fc-i(-t), and Uik>2(t) = RiUn{t/x)R1U12{-t/x). We now can obtain the rest of transvections using appropriate commutators. • 5.7 Case of (4k + 2) X (4k + 2) matrices. This is the last section. We prove here the case of (4k + 2) x (4k + 2) matrices. This section's main result is the following two propositions: Proposition 5.41. Let Ri 1 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 X 0 0 0 0 -1 0 0 0 0 0 -1 and #3 = -1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0 0 -1 0 where x is a primitive root in GF(q). Then SL^(q) = (Ri,R2,R3). Proposition 5.42. Let Ri = 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 X 0 0 0 0 -1 #2 = 1 0 0 0 0 0 0 0 1 0 0 0 0 1 .0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 80 Chapter 5. Positive answer for n> 4. and 0 0 0 \" 0 0 0 1 0 0 0 0 0 ' 0 0 - 1 0 1 0 where the choice of x is discussed on page 87. Define inductively Rl,6 = Ri, #2 ,6 = R2, #3 ,6 = # 3 and R h n = # l , „ - 4 [ 0 , l ] , R2,n = #2,n-4[l,2], # 3,n = #3,n-4[4,2], for n = 4k + 2, k > 2. Then SLn(q) = ( # i , „ , #2 ,n , #3 ,n)-The immediate corollary is Corollary 5.43. PSL^+iiq)) k>2 can be generated by three involutions, two of which com-mute. Remark 1. Note the difference of this case from all previous. # 3 is not an involution in SLn(q) but its image in PSLn(q) is. The difference between n = 6 and n = 4k + 2 with > 2 is very small (and is notable only in Step 1), so we will use the same computations almost everywhere in both cases. Thus we combine the proofs into one proof. As in previous section we note how the Bar Operation works on our generartors: Lemma 5.44. a) #l,n = #l,n- 4[0,j], 1 < J < 4A - 1, b) R2,n = # 2 , « - 4 [ l , 2 j + 1], 0 4. Proof of propositions 5.41 and 5.42. Step 1 is the most difficult step in this proof. We obtain a transvection at the spot (6,2) if n = 6 and at the spot (4k — 2,1) if n > 10. Step 2 is relatively simple and Step 3 looks very much like Step 3 in Section 5.6 We first make computations for n — 6: l 0 0 0 0 0 0 1 0 0 0 0 = (RiRz)A = -x 0 0 -x -1 0 0 -1 0 0 0 0 0 —x 0 0 -1 0 X 0 0 0 0 -1 ' 1 0 0 0 0 0 \" X -1 0 0 0 0 — R2P1R2 = 0 0 1 0 0 0 0 0 —x --1 0 0 0 0 —x 0 1 0 X 0 0 0 0 -•1 1 0 0 0 0 0 \" 0 1 0 0 0 0 #3 = (P2P1)2 = 0 2x2 0 1 0 0 0 1 0 0 0 0 2x2 0 0 0 1 0 0 0 0 0 0 1 (5.72) (5.73) (5.74) PA = -R3-P3-R3 = and finally 1 0 0 0 0 0 0 1 -2x2 0 0 2x2 U62(4x2) = PAR1Pr1Ri = 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 4x2 0 0 0 1 (5.75) (5.76) 82 Chapter 5. Positive answer for n > 4. In the higher dimensions cases the first computations are the same but unfortunately they only lead to a \"double transvection\", not a transvection so we have to continue. The analogue of computations 5.72-5.76 for the case n = 10 is the following: P i = CRitfs)4 = P 2 — P 2 P l # 2 = P 3 = ( P 2 P l ) 2 = 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 — X 0 0 0 0 0 -1 0 0 0 0 —x 0 0 0 0 0 -1 0 0 0 —x 0 0 0 0 0 0 -1 0 X 0 0 0 0 0 0 0 0 1 _ 1 0 0 0 0 0 0 0 0 0 \" 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 —x 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 --x 0 0 0 0 -1 0 0 0 0 --x 0 0 0 0 0 -1 0 X 0 0 0 0 0 0 0 0 — 1 ' 1 0 0 0 0 0 0 0 0 0 \" 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2x -2x 0 0 0 0 1 0 0 0 2x -2x 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 (5.77) (5.78) (5.79) 83 Chapter 5. Positive answer for n > 4. and P 4 = R3P3R3 = P5 — P4R1P4 1R\\ 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2x 0 0 2x 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 2x 0 0 -2x 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 4x 0 0 Ax 0 0 0 0 0 1 (5.80) (5.81) The computations 5.77-5.81 expand using the Bar Operation and Lemma 5.44 as follows: Pi, n = Pi,n-4[0,2] = (P 1 ) n_ 4P 3 > n-4) 4[0,2] = (i2i,n_4[0,2] • il3,„-4[4,2]) 4, (5.82) P 2,n = P2,n-4[0,3] = P 2,n-4Pl,n-4P 2,n- 4[0,3] = P2,n-4[1,3] • Pi,„_4[0,3] • #2,n-4[l,3], ' (5.83) P 3,n = P3,n-4[0, 3] = (P 2,n_ 4P 1,n- 4) 2[0, 3] = (P2>„_4[0, 3] • Pl,„_4[0, 2])4, (5.84) P 4 > n = P4,n-4[0, 4] = P 3 ,n- 4P3,n- 4#3,n- 4[0, 4] = # 3 , n - 4 [ 4 , 4] • P3,n-4[0, 4] • P 3 > n- 4[ 4, 4] (5.85) and P 5 )n = P5,n-4[0,4] = P4,n-4i2l,n-4P 4\\„_4 ~ l)Pl,n-4[0, 4] P4,n_4[0,4] • JR1,n_4[0,4] • P4,n_4[0,4] • -Ri,n-4[0,4] (5.86) (5.87) 84 Chapter 5. Positive answer for n > 4. Now R2 is a permutation matrix and R% is a sign permutation matrix. The permutations corresponding to them are p2 = (2, 3)(4, 5)... (Ak,Ak + l) andrj3 = (1, 2)(3,4)... (Ak + l,Ak + 2). We now conjugate P^,^ successively by R2 and R3 to bring the (4& + 2,4) entry to the (5,4A; + 2) position. The (Ak + 2,1) entry will go to the (5,4A; — 2) position at the same time. (In other words we conjugate P^^ by (R2Rs)^2k~l\\ When we do this the sign of the (Ak + 2,4) entry might change, but it does not matter since we can take an inverse of the \"double transvection\" we obtain in the end. We call this \"double transvection\" Pg,n- Now #6 = 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 a 0 0 0 b 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 (5.88) where a and b are equal to ±Ax. Pi = RiPeRiP^ 1 = 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 bx 0 0 0 1 0 0 0 0 -2b 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 (5.89) Now consider R4 = (R2Rz)^2k+1\\ Prom the permutation multiplication it follows that R4 is the matrix that has only entries equal to ±1 along the big non-main diagonal and zeroes everywhere 85 Chapter 5. Positive answer for n > 4. else. In particular conjugation by it swaps first and last row as well as first and last column with possible multiplication by —1 So to finish Step 1 we need to make following computations. P s = RAPJRA = 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 ei26 0 0 0 0 1 0 0 0 62 b 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 and finally Uu-2,1 = (RiPs)2 = 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 + e2 b x2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 (5.90) (5.91) where ei, e2 = ± 1 . The only possible source of trouble, i.e. not obtaining a transvection, can arise if x2 ± 4 = 0. We will address this issue at the end of Step 2 ,when we discuss the choice of x. The computations 5.89-5.91 are easily expanded by the Bar Operation at the position (5,5) by identity blocks. This completes Step 1. For Step 2 we again divide the cases of n = 6 and n > 10 although the computations are the 86 Chapter 5. Positive answer for n > 4. same. We proceed very similarly to Step 2 in the proofs of previous sections. Let n = 6. Sup-pose we have a transvection U%2(a). Then [/51(a) = R3UQ2(a)R3 and U2§(a) = #40/51 (a)_R4. Now U2\\(ax) = (RiU2§(a))2. In the same way U^(—ax) = RAXJ2\\{ax)Ri and U^{ax) = R2U^{—ax)R2. Finally U*,\\(ax2) = RiU4§(ax)RiU 10. We start with U4k-2,i(a). U5Ak+2(±a) = R4U4k„2,i(a) #4. U5ti{±ax) = {RiU5t4k+2(a))2. In the same way Uik-2,4k+2(±ax) = i? 4[/ 5 )i(ax)R 4 and Uik-2ti{±ax2) = (RiU4k-2,4k+2(±ax))2. So similarly to case n = 6 we obtain all U4k-2^{t), t €GF(g). It should be noted here that Step 2 is redundant if q — p and thus we don't need x to be primitive root to obtain all transvections. This means that if q = p we choose x such that x2 + 4 0 or x2 — 4 / 0 depending on the dimension (the sign depends on R4 = (R2R3)(2k+V). If q = 9 then any primitive root satisfies x2 ± 4 / 0 and we choose it for x. And if a > 25 then there are plenty (more than 4) primitive roots to choose from and we always can satisfy this condition. Appendix F provides the input in case n = 10 and note that it trivially expands at the spot (2k + 1,2k + 1) by the Bar Operation using the identity block. This completes Step 2. Now for Step 3 we are going to use only R2 and R3 in a way similar to the Ak x Ak case. First we note that each transvection spot we obtain yields immediately 2n new spots that are 87 Chapter 5. Positive answer for n > 4. obtained by conjugation by R2 and i? 3. We get two transvections in each row this way (also two transvections in each column). If we have a transvection U in the first row (but not in columns 4k and 4k + 1) or a transvection in the last column (but not in rows 4k and 4k + 1), then computing (RxU)2 will yield yet another transvection in the last row and the same column or the first column and the same row. We will call it flipping. The 2n new transvections then will have positions symmetrical to 2n positions of the original transvection. See figure 5.4 for the details. Symmetry axis Figure 5.4: Obtaining transvections in (4k + 2) x (4k + 2) case. The rest of the proof is easy. We start with the (4k — 1,1) position and obtain the (4k + 1,3) position by #3 and R2. We also obtain the (2,4k) position by applying R2R3 to the (4k + 1,3) 88 Chapter 5. Positive answer for n > 4. position. Now we flip the (2,4k) position to the symmetric position which is (2,3). After that we proceed exactly as in the first half of obtaining second column in the proof of Proposition 5.38. (compare Figures 5.2 and 5.4). After obtaining half of the transvections we just use i?i to flip to symmetric positions. This gives us all the transvections except those on the big non-main diagonal. They are easily obtained as commutators. • 89 B i b l i o g r a p h y George Andrews. The theory of partitions. Addison-Wesley, 1976. Joseph Arkin. Researches on partitions. Duke Math. Journal, 38:403-409, 1970. Marston Conder. More on generators for alternating and symmetric groups. Quarterly J. of Math., 32:137-163, 1981. J.H. Conway, N.J.A. Sloane, and Allan R.Wilks. Grey codes for reflection groups. Graphs and Combinatorics, 5(4):315-325, 1989. F.R. Gantmacher. The Theory of Matrices, volume 1. Chelsea Publishing Company, New York, 1959. A. Grothendieck. Esquisse d'un programme. In L.Schneps and P.Lochak, editors, Geomet-ric Galois Actions, pages 5-48. Cambridge University Press, 1997. Laszlo Lovasz. Problem 11. In Richard Guy, Haim Hanani, Norbert Sauer, and Jo-hanan Schonheim, editors, Combinatorial structures and their applications. Gordon and Breach,New York, 1970. Gunter Malle, Jan Saxl, and Thomas Weigel. Generation of classical groups. Geometriae Dedicata, 49:85-116, 1994. Morris Newman. Integral Matrices. Academic Press, New York and London, 1972. The Kourovka Notebook. Unsolved problems in group theory. Novosibirsk, 13 edition, 1995. Ya.N. Nuzhin. Generating triples of involutions of Chevalley groups over a finite field of characteristic 2. Algebra and Logic, 29(3):134-143, 1990. Ya.N. Nuzhin. Generating triples of involutions of alternating groups. Mat.Zametki (Rus-sian), 51(4):91-95, 1992. Ya.N. Nuzhin. Generating triples of involutions for lie-type groups over a finite field of odd characteristic i. Algebra and Logic, 36(1):46—59, 1997. Ya.N. Nuzhin. Generating triples of involutions for lie-type groups over a finite field of odd characteristic ii. Algebra and Logic, 36(4):245-256, 1997. Martin Schonert et al. GAP - Groups, Algorithms, and Programming. Lehrstuhl D fur Mathematik, Rheinisch Westfalische Technische Hochschule, Aachen, Germany, third edi-tion, 1993. D. Sjerve and M. Cherkassoff. On groups generated by three involutions,two of which com-mute. In G. Mislin, editor, The Hilton Symposium. CRM Proc. Lecture Notes, volume 6, pages 169-185. Montreal(PQ), 1994. 90 Bibliography [17] M.C. Tamburini and P. Zucca. Generation of certain matrix groups by three involutions, two of which commute. Journal of Algebra, 195(2):650-661, 1997. [18] D. Witte and J.A Gallian. A survey - hamiltonian cycles in cayley graphs. Discrete Math., 51:293-304, 1984. 91 Appendix A M a p l e V inpu t for 4 x 4 case. > with(linalg): > em:= mat -> map(simplify,evalm(mat)): > tr:= proc( i , j ,val) > local res; > res := matrix(4,4,0); > res[ i , j ] := val; > evalm(res+l); > end: > c:= proc(a,b) > em(a&*b&*a~(-l)&*b~(-l)) ; > end: > co:= proc(a,b) > em(a~(-l)&*b&*a); > end: > rl:=array(l . .4 ,1. .4,[[ l ,x ,0,0] ,[0,-1,0,0] ,[0,0,-1,0] ,[0,x,0, l ]]); > r2:=array(l . .4,1. .4, [[0,0,0,1],[0,1,0,0],[0,0,-1,0] ,[1,0,0,0]]); > r3:=array(l..4,1..4,[[-1,0,0,0],[0,1,1,1/2],[0,0,-1,-1],[0,0,0,1]]); > em(rl~2); > em(r2~2); > em(r3\"2); > em((rl&*r2)~2) ; > det(rl); > det(r2); 92 Appendix A. Maple V input for 4x4 case. > det(r3) ; > t3:=array(l. ..4,1. .4, [[0,-1,0,0] , [1,-1,0,0] , [0,0,1,1] , [1 ,-1,0,1] ] ) ; > em(t3~3); > em((r2&*r3)\"4); > r3xr2r3_4s:=em(r3&*(tr(2,l,-2*s)&*tr(2,3,4*s)&*tr(2,4,2*s))); > r4:=subs(s=-l/4,em(r3xr2r3_4s)); > T:=em(rl&*r4); > t33:=array(l..4,1..4,[[1,0,0,0],[0,1,0,0],[1,1,1,0],[0,0,0,1]]); > s3:=em(t3&*r2&*t3&*r2); > u3_31:=em((t3&*r4&*s3)~2); > tm:=array(l..4,1..4, [[1,0,0,0], [0,1,0,0],[m*z,4*m*z,1,m],[0,0,0,1]]); > s:=em(tm&*r2&*tm&*r2); > u31:=em((tm&*r4&*s)~2); > u31m:=tr(3,l,-m*(z-l)); > u34:=em(u31m&*s); > u34z:=tr(3,4,z-l); > tz:=em(T&*u34z); > tmz:=array(l..4,1..4,[[1,0,0,0],[0,1,0,0],[m*z~2,4*m*z\"2,l,mz],[0,0,0,1]]); > sz:=em(tmz&*r2&*tmz&*r2); > u31z:=em((tmz&*r4&*sz)\"2); > u34t:=tr(3,4,t); > u31t:=tr(3,l,t); > u24t:=em((r3&*u34t)\"2); > u21t:=em(r2&*u24t&*r2); > u32:=em((rl&*u31t)~2); > r5:=em(tr(3,2,l)&*r3&*tr(3,4,-l)&*tr(2,4,l/2)&*tr(3,2,-l)); > u32t:=tr(3,2,t); > u23t:=evalm(r5&*u32t&*r5); > r6:=array(l. .4,1..4, [[1,0,0,0],[0,-1,0,0],[0,0,-1,0] ,[0,0,0,1]] ); > q:=em(r5&*rl&*r5&*rl&*tr(2,3,l)); > p:=em(u32t&*tr(2,3,-l)&*r6&*q); > ul2:=em(p~2&*tr(3,2,-2*t)) ; 93 Appendix A. Maple V input for 4 x 4 case. > u l 3 t : = e m ( t r ( l , 2 , - t ) & * t r ( 2 , 3 , - l ) & * t r ( l , 2 , t ) & * t r ( 2 , 3 , l ) ) ; > ul4t:=em(ul3t~(-l)&*tr(3,4,-l)&*ul3t&*tr(3,4,l)); > u43t:=em(r2&*ul3t&*r2); > u41t:=em(r2&*ul4t&*r2); > u42:=em(r2&*tr(l,2,t)&*r2); 94 Appendix B M a p l e V inpu t for 5 x 5 case. > w i t h ( l i n a l g ) : > em:=mat -> map(simplify,evalm(mat)): > tr:= p r o c ( i , j , v a l ) > l o c a l res; > res := matrix(5,5,0); r e s [ i , j ] : = v a l ; evalm(res+l); > end: > rl:= a r r a y ( l . . 5 , 1 . . 5 , [[l,x,0,0,0],[0,-1,0,0,0],[0,0,0,1,0] , [0,0,1,0,0],[0,-x,0,0,1]]); > r2:=array(l..5,1..5, [[0,0,0,0,1],[0,-1,0,0,0] ,[0,0,1,0,0] , [0,0,0,1,0],[1,0,0,0,0]]); > r3:=array(l..5,1..5, [[1,0,0,0,0],[0,1,1,0,0],[0,0,-1,0,0] , [0,0,0,1,1], [0,0,0,0,-1]]); > em(rl&*rl),em(r2&*r2),evalm(rl&*r2&*rl&*r2),evalm(r3*r3); > d e t ( r l ) , d e t ( r 2 ) , d e t ( r 3 ) ; > r2r3_4:=em((r2&*r3)~4); > u23:=tr(2,3,l); > r4:=em(r3&*u23~(-l)) ; > w:=evalm((rl&*r4)\"4) ; > s:=evalm(w&*r2&*w&*r2); > T:=em(tr(l,2,x)&*tr(5,2,-x)); > r6:=evalm(rl&*T\"(-l)); > u24:=evalm(r6&*t23~(-l)&*r6); > u24a:=tr(2,4,a); 95 Appendix B. Maple V input for 5 x 5 case. > p:=em((rl&*r3&*rl&*u24a)~2) ; > u24xa:=em(p~(-l)&*u23&*p&*t23~(-D); > u24t:=tr(2,4,t); > u25t:=em(r3&*u24t&*r3&*u24t~(-l)); > u21t:=em(r2&*u25t\"(-l)&*r2); > q:=em(rl&*tr(2,l,l/x)&*rl&*tr(2,l,-2/x)) ; > fl:=em((q&*tr(2,l,-t/(2*x~2))&*q)~2); > f2:=em((u23&*r3&*f1)~2); > f3:=em(r6&*f2&*r6); > ul2:=em((u23&*r3&*f3)*2); > u32:=em(tr(l,2,2*t)&*f3); > u42:=em(tr(l,2,2*t)&*f2~(-l)); > u52:=em(tr(l,2,t)&*f1~(-1)); 96 Appendix C M a p l e V inpu t for (4k + 1) X (4fc + 1) case > with(linalg) : > em:= mat -> map(simplify,evalm(mat)): > tr:= proc( i , j ,val) > local res; > res := matrix(9,9,0); > res[ i , j ] := val; > evalm(res+l); > end: > rl:=matrix([[l,x,0,0,0,0,0,0,0],[0,-1,0,0,0,0,0,0,0] ,[0,0,0,1,0,0,0,0, 0],[0,0,1,0,0,0,0,0,0], [0,0,0,0,0,1,0,0,0],[0,0,0,0,1,0,0,0,0],[0,0,0, 0. 0.0.0.1.01,[0,0,0,0,0,0,1,0,0],[0,-x,0,0,0,0,0,0,1]]); > em(rl&*rl); > r2:=matrix([[0,0,0,0,0,0,0,0,1], [0,-1,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0, 01, [0,0,0,1,0,0,0,0,0], [0,0,0,0,1,0,0,0,0],[0,0,0,0,0,1,0,0,0] ,[0,0,0, 0. 0.0.1.0.01, [0,0,0,0,0,0,0,1,0], [1,0,0,0,0,0,0,0,0]]); > evalm(rl&*r2&*rl&*r2); > evalm(r2&*r2); > r3:=matrix([[1,0,0,0,0,0,0,0,0],[0,1,1,0,0,0,0,0,0],[0,0,-1,0,0,0,0,0, 01, [0,0,0,1,1,0,0,0,0], [0,0,0,0,-1,0,0,0,0],[0,0,0,0,0,1,1,0,0] ,[0,0,0 ,0,0,0,-1,0,0],[0,0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,0,-1]]); > em(r3*r3); > det(rl),det(r2),det(r3); > r2r3_4:=em((r2&*r3)~4); 97 Appendix C. Maple V input for (4k + 1) x (4k + 1) case. > u23:=tr(2,3,l) ; > pi : = e m(rl&*u23&*rl); > p2 :=em(r3&*pl&*r3); > p3:=em(r2&*p2&*r2&*p2~(-1)); > u24_2:=em(r3&*p3&*r3); > em(u24_2~(-l)&*p3); > p l l : = e m ( r l & * t r ( 2 , 5 , l ) & * r l ) ; > p21 : =em(r3&*pll&*r3); > p31:=em(r2&*p21&*r2&*p21~(-l)); > u26_2:=em(r3&*p31&*r3); > em(u26_2~(-l)&*p31); > u23:=tr(2,3,l): > u24:=tr(2,4,l): > u25:=tr(2,5,l): > u26:=tr(2,6,l): > u27:=tr(2,7,l): > u24a:=tr(2,4,a): > pl9 : = e m(rl&*u24a&*rl); > p29 :=em(r3&*pl9&*r3); > p39 : = e m(rl&*p29&*rl); > U24ax:=em(p39~(-l)&*u27&*p39&*u27~(-l)) ; > u25t:=tr(2,5,t): > p l 9 _ l : = e m ( r l & * u 2 5 t & * r l ) ; > p29_l :=em(r3&*pl9_l&*r3); > p39_l : = e m(rl&*p29_l&*rl); > p49_l :=em(u27&*p39_l&*u27\"(-l)&*p39_l~(-D); > u28tx :=em(tr(2,5,t*x)&*p49_l) ; > u29tx :=em(r3&*u28tx&*r3&*u28tx~(-l)); > u21t : = e m(r2&*tr(2,9,-t)&*r2); > p l _ l : = e m ( r l & * t r ( 2 , 4 , t ) & * r l ) ; > p2_l : = e m(r3&*pl_l&*r3); >. p3_l :=em(p2_l&*pl_l) ; 98 Appendix C. Maple V input for (4k + 1) x (4k + 1) case. > p4_l:=em(r2&*p3_l&*r2&*p3_l); > u23t:=em(p4_l&*p2_l-(-2)); > pl_2:=em(rl&*tr(2,l,l/x)&*rl) ; > p2_2:= em(pl_2&*tr(2,l,-2/x)); > p3_2:=em(p2_2&*tr(2,l,-t/(2*x*x))&*p2J2) ; > tn:=em(p3_2~2); > r4:=subs(t=x,em(tn&*rl)); > pl_3:=em((u23&*r3&*tn)~2); > p2_3:=em(r4&*pl_3&*r4); > pl_4:=em((u23&*r3&*p2J)\"2); > p2_4:=em(r4&*pl_4&*r4); > pl_5:=em((u23&*r3&*p2_4)\"2); > p2_5:=em(r4&*pl_5&*r4); > ul2t:=em((u23&*r3&*(tr(1,2,-8*t)&*tr(3,2,t)))\"2) > 99 Appendix D M a p l e V inpu t for (4k + 3) X (4k + 3) case > with(linalg): > em:= mat -> map(simplify,evalm(mat)): > tr:= proc( i , j ,val) > local res; > res := matrix(7,7,0); > res[ i , j ] := val; > evalm(res+l); > end: > rl:=matrix([[-l ,x,0,0,0,0,0], [0,1,0,0,0,0,0],[0,0,0,1,0,0,0], [0,0,1,0,0,0,0], [0,0,0,0,0,1,0],[0,0,0,0,1,0,0],[0,-x,0,0,0,0,-1]]); > em(rl&*rl); > det(rl); > r2:=matrix([[0,0,0,0,0,0,1],[0,-1,0,0,0,0,0] ,[0,0,1,0,0,0,0] , [0,0,0,1,0,0,0], [0,0,0,0,1,0,0],[0,0,0,0,0,1,0] ,[1,0,0,0,0,0,0]]); > det(r2); > evalm(rl&*r2&*rl&*r2); > evalm(r2&*r2); > r3:=matrix([[-1,0,0,0,0,0,0],[0,-1,1,0,0,0,0] ,[0,0,1,0,0,0,0] , [0,0,0,-1,1,0,0], [0,0,0,0,1,0,0],[0,0,0,0,0,-1,1],[0,0,0,0,0,0,1]]); > em(r3*r3); > det(r3); > u23_4:=em((r2&*r3)~4); > u23:=tr(2,3,l); 100 Appendix D. Maple V input for (4k + 3) x (4k + 3) case. > pl:=em(rl&*u23&*rl); > p2:=em(r3&*pl&*r3); > p3:=em(r2&*p2&*r2&*p2~(-1)); > u24_2:=em(r3&*p3&*r3); > u252:=em(u24_2~(-l)&*p3); > u24:=tr(2,4,l) : > u25:=tr(2,5,l): > u24a:=tr(2,4,a): > pl7:=em(rl&*u24a&*rl); > p27:=em(r3&*pl7&*r3); > em(r2&*p27&*r2&*p27~(-l)); > p37:=em(rl&*p27&*rl); > u24ax:=em(p37~(-l)&*u25&*p37&*u25~(-l)); > u24t:=tr(2,4,t): > u25t:=em(r3&*u24t&*r3&*u24t~(-l)); > u23t:=tr(2,3,t); > p_l:=em(rl&*u23t&*rl); > p_2:=em(r3&*p_l&*r3); > p_3:=em(rl&* p_2 &*rl); > p_4:=em(u25\"(-l)&*pJ3&*u25&*p_3\"(-l)); > u26tx:=em(tr(2,3,t*x)&*p_4) ; > u27tx:=em(r3&*u26tx~(-l)&*r3&*u26tx); > u27t:=tr(2,7,t); > u21t:=em(r2&*u27t~(-l)&*r2); > pll:=em(rl&*tr(2,l ,-l /x)&*rl); > p21:= em(pll&*tr(2,l,2/x)) ; > p31:=em(p21&*tr(2Jl,-t/(2*x\"2))&*p21); > p41:=em(p31~2); > r4:=subs(t=-xJem(p41&*rl)); > pl_l:=em((u23~(-l)&*r3&*p41)\"2); > p2_l:=em(r4&*pl_l&*r4); > pl_2:=em((u23~(-l)&*r3&*p2_l)\"2) ; 101 Appendix D. Maple V input for (Ak + 3) x (Ak + 3) case. > p2_2:=em(r4&*pl_2&*r4); > ul2t:=em((u23\"(-l)&*r3&*p2J2)~2); 102 Appendix E M a p l e V inpu t for 4k X 4k case > with(linalg): > em:= mat -> map(simplify,evalm(mat)): > tr:= proc( i , j ,val) > local res; > res := matrix(8,8,0); > res[ i , j ] := val; > evalm(res+l); > end: > c:= proc(a,b) > em(a&*b&*a~(-l)&*b~(-l)) ; > end: > mp:= proc(a,b) > mulperms(a,b); > end: > co:= proc(a,b) > em(a~(-l)&*b&*a); > end: > rl:=matrix([[1,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0],[0,0,1,0,0,0,0,0], [0,0,0,1,0,0,0,0], [0,0,0,0,1,0,0,0],[0,0,0,0,0,0,1,0] ,[0,0,0,0,0,1,0,0], [x,0,0,0,0,0,0,-1]]); > em(rl&*rl); > det(rl); > r2:=matrix([[l,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0],[0,1,0,0,0,0,0,0], 103 Appendix E. Maple V input for Ak x Ak case. [ 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , - 1 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , - 1 , 0 ] , [0,0,0,0,0,0,0,1]]); > det(r2); > c (r l , r2) ; > evalm(r2&*r2); > r3:=matrix([[0,l,0,0,0,0,0,0],[1,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0], [0,0,1,0,0,0,0,0], [0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0] ,[0,0,0,0,0,0,1,1] , [0,0,0,0,0,0,0,-1]]); > em(r3*r3); > det(r3); > tl:=em((r2fc*r3)~6); > pi:=em(tl&*tr(7,8,a-6)); > p2:=em((r3&*rl&*ta&*r3)~4); > p3:=c(ta~2,ta2); > pl8:=em(tl&*tr(7,8,-6)); > p28:=em((pl8&*rl)~4); > p38:=co(r3,p28); > p48:=co(rl,p38); > p58:=em(p48&*pl8&*p48\"(-l)&*pl8) ; > p68:=em(p38~2&*p58); > u72:=tr(7,2,a) ; > u62:=co(rl,u72) ; > u51:=co(r3,u62); > u41:=co(r2,u51); > u32:=co(r3,u41); > u23:=co(r2,u32); > u73:=c(u72,u23); > u72a2:=co(r2,u73); > c(u72a2,u23); > u26:=tr(2,6,a) ; > u27:=co(rl,u26); > em(r3&*u27&*r3&*tr(l,7,-a)) ; 104 Appendix E. Maple V input for 4k x 4k case. > em(rl&*tr(l,2,a/x)&*rl&*tr(l,2,-a/x > Appendix F M a p l e V inpu t for (4k + 2) X (4k + 2) case. The 6 x 6 input file: > with(linalg) : > em:= mat -> map(simplify,evalm(mat)): r > tr:= proc( i , j ,val) > local res; > res := matrix(6,6,0); > res[ i , j ] := val; > evalm(res+l) ; > end: > c:= proc(a,b) > em(a&*bfc*a~(-l)&*b~(-1)); > end: > co:= proc(a,b) > em(a~(-l)&*b&*a); > end: > rl:=matrix([[l,0,0,0,0,0], [0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,0,1,0], [0,0,0,1,0,0],[x,0,0,0,0,-l]]); > em(rl&*rl); > det(rl); > r2:=matrix([[-1,0,0,0,0,0], [0,0,1,0,0,0],[0,1,0,0,0,0] ,[0,0,0,0,1,0], [0,0,0,1,0,0],[0,0,0,0,0,-1]]); > det(r2); > c (r l , r2) ; 106 Appendix F. Maple V input for (4k + 2) x (4k + 2) case. > evalm(r2&*r2); > r3:=matrix([[0,-1,0,0,0,0], [1,0,0,0,0,0],[0,0,0,-1,0,0],[0,0,1,0,0,0], [0,0,6,0,0,-1],[0,0,0,0,1,0]]); > em(r3*r3); > det(r3); > r4:=em((r2&*r3)\"3); > pl:=em((rl&*r3)~4) ; > p2:=co(r2,pl); > p3:=em((p2&*pl)~2) ; > p4:=co(r3,p3); > c(p4,rl); > u62:=tr(6,2,a) ; > u51:=co(r3,u62); > u26:=co(r4,u51); > u21x:=em((rl&*u26)~2); > u56x:=co(r4,u21x); > u46x:=co(r2,u56x); > em(rl&*u46x&*rl&*u56x~(-l)); > The 10 x 10 input file. > with(linalg): > em:= mat -> map(simplify,evalm(mat)): > tr:= proc( i , j ,val) > local res; > res := matrix(10,10,0); > res[ i , j ] := val; > evalm(res+l); > end: > c:= proc(a,b) > em(a&*b&*a~(-l)&*b~(-l)) ; > end: > co:= proc(a,b) 107 Appendix F. Maple V input for (4k + 2) x (4k + 2) case. > em(a~(-l)&*b&*a); > end: > rl:=matrix([[l,0,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0] , [0,0,1,0,0,0,0,0,0,0], [0,0,0,1,0,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,1,0], [0,0,0,0,0,0,0,1,0,0], [x,0,0,0,0,0,0,0,0,-1]]); > em(rl&*rl); > det(rl); > r2:=matrix( [[1,0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0], [0,1,0,0,0,0,0,0,0,0], [0,0,0,0,1,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,0], [0,0,0,0,0,0,1,0,0,0], [0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,1,0], [0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,0,0,1]]); > det(r2); > c (r l , r2) ; > evalm(r2&*r2); > r3:=matrix( [[0,-1,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0], [0,0,0,-1,0,0,0,0,0,0], [0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,-1,0,0,0,0], [0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,-1,0,0],[0,0,0,0,0,0,1,0,0,0], [0,0,0,0,0,0,0,0,0,-1], [0,0,0,0,0,0,0,0,1,0]]);• > em(r3*r3); > det(r3); > r4:=em((r2&*r3)~5); > pl:=em((rl&*r3)\"4); > p2:=co(r2,pl); > p3:=em((p2&*pl)~2); > p4:=co(r3,p3); > p5:=em(p4&*rl&*p4~(-l)&*rl); > p6:=co(em((r2&*r3)~3),p5); > p6ab:=em(tr(5,6,a)&*tr(5,10,b)); > p7b:=c(rl,p6ab); > p7pm:=em(tr(6,l,epsl*b*x)&*tr(6,10,eps2*2*b)); > p8:=co(r4,p7pm); 108 Appendix F. Maple V input for (4k + 2) x (4k + 2) case. > p82pm:=em((rl&*p8)\"2); > t61:=tr(6,l,a); > t510:=co(fl,t61); > t51x:=em((rl&*t510)~2) ; > t610x:=co(fl,t51x); > t61x2:=em((rl&*t610x)~2) ; > 109 Chapter 5. Positive answer for n > 4. Now R2 is a permutation matrix and R3 is a sign permutation matrix. The permutations corresponding to them are p2 = (2,3)(4, 5)... (4k,4k+l) andp3 = (1,2)(3,4)... (4k+l,4k + 2). We now conjugate P^^ successively by R2 and R3 to bring the (4A; + 2,4) entry to the (5,4/c + 2) position. The (4k + 2,1) entry will go to the (5,4k — 2) position at the same time. (In other words we conjugate Psin by (R2R3)(2h~l\\ When we do this the sign of the (4k + 2,4) entry might change, but it does not matter since we can take an inverse of the \"double transvection\" we obtain in the end. We call this \"double transvection\" Pe,n. Now 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 a 0 0 0 b 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 (5.88) where a and b are equal to ±4x. Pi = RiPeRiPa 1 = 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 bx 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 -2b 0 0 0 0 1 (5.89) Now consider R4 = (R2R3)(2k+l\\ From the permutation multiplication it follows that R4 is the matrix that has only entries equal to ± 1 along the big non-main diagonal and zeroes everywhere 85 "@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "1998-11"@en ; edm:isShownAt "10.14288/1.0080085"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Mathematics"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Generation of certain groups by three involutions, two of which commute"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/9473"@en .