UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The permanent of a certain matrix Horn, Peter J. 1966-12-31

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
831-UBC_1966_A8 H64.pdf [ 2.55MB ]
Metadata
JSON: 831-1.0080613.json
JSON-LD: 831-1.0080613-ld.json
RDF/XML (Pretty): 831-1.0080613-rdf.xml
RDF/JSON: 831-1.0080613-rdf.json
Turtle: 831-1.0080613-turtle.txt
N-Triples: 831-1.0080613-rdf-ntriples.txt
Original Record: 831-1.0080613-source.json
Full Text
831-1.0080613-fulltext.txt
Citation
831-1.0080613.ris

Full Text

THE  PERMANENT OF A CERTAIN MATRIX  BY  PETER J . HORN  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE  REQUIREMENTS FOR THE DEGREE OF MASTER OF ARTS in  t h e Department of Mathematics  We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e s t a n d a r d r e q u i r e d from candidates f o r t h e degree o f MASTER OF ARTS.  THE  UNIVERSITY OF B R I T I S H COLUMBIA April,  1966  In p r e s e n t i n g t h i s t h e s i s requirements Columbia, for  in p a r t i a l  f u l f i l m e n t of  f o r an advanced degree at the U n i v e r s i t y of  I agree t h a t the L i b r a r y  r e f e r e n c e and s t u d y .  t e n s i v e copying of t h i s  s h a l l make i t  freely  the  British available  I f u r t h e r agree that p e r m i s s i o n f o r thesis for  ex-  s c h o l a r l y purposes may be gran  by the Head of my Department o r by h i s  representatives.  understood t h a t copying o r p u b l i c a t i o n o f t h i s  thesis for  It  is finan-  c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n .  Depa rtment The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8 , Canada Date  #ft  A] A V  6£  ABSTRACT  The purpose o f t h i s t h e s i s i s t o a t t e m p t t o e v a l u a t e t h e permanent f u n c t i o n o f a nxn complex m a t r i x with entries  a.  ±  = 9  , 9 being a p r i m i t i v e n  root of  unity. I f t h i s m a t r i x i s denoted by A t h e n i t s permanent n f u n c t i o n i s g i v e n by p e r  A  n lfK<r<i> =  T£S„  ^  (r<tS„  In t h i s t h e s i s the f o l l o w i n g r e s u l t s are proved. Per A  n  i s always an i n t e g e r ; w i t h p e r  = 0 mod n.  I f n i s even p e r A =0. n P o r n odd however, t h e problem i s i n g e n e r a l n o t r e s o l v e d . 2 I t i s shown t h a t i f n=p  w i t h p a prime, t h a t per A  n  = 0 mod  and t h a t f o r any prime n, p e r A^ c a n be narrowed down t o be one o f a r e s t r i c t e d c l a s s o f numbers.  TABLE OF CONTENTS  PAGE I II III IV V VI  Introduction  1  P r e l i m i n a r y Theorems  10  Some G e n e r a l R e s u l t s on P e r A Per A  n  Q  i f n i s a Prime  18 21  p  The Case o f n=p , Where p i s a Prime . . . .  33  Computer R e s u l t s  *H  Bibliography  . . . . .  kk  ACKNOWLEDGMENTS  I wish t o express f o r a l l the help thesis,  he h a s g i v e n me i n t h e p r e p a r a t i o n o f t h i s  a n d t o whom many o f t h e t h e o r e m s a n d p r o o f s  I am a l s o i n d e b t e d helpful  my s i n c e r e t h a n k s t o D r . B.N. M o y l s  suggestions  f o r programming  t o D r . W . McWorter  a r e due.  for his  and encouragement, and t o Ted P o w e l l  assistance.  I  The  INTRODUCTION  purpose o f t h i s t h e s i s i s t o attempt to evaluate  the permanent f u n c t i o n of an nxn complex m a t r i x w i t h e n t r i e s a^j = 6  , 6 being a p r i m i t i v e n  root of u n i t y .  (a) Permanents. F o r a m a t r i x A of order n w i t h e n t r i e s i n some f i e l d , the permanent f u n c t i o n of A Is d e f i n e d by perA =  gtt  l 0 U )  .  where S i s the symmetric group of order n. n  This s c a l a r  f u n c t i o n of the m a t r i x A appears f r e q u e n t l y i n c o m b i n a t o r i a l problems c o n c e r n i n g enumerations [ l ] , and has the f o l l o w i n g formal p r o p e r t i e s .  The per(A) remains i n v a r i a n t under a r b i t r a r y  permutations of the rows and columns of A and i s a l s o T under t r a n s p o s i t i o n ;  i . e . , per(A) « per(A ).  s c a l a r from the u n d e r l y i n g  I f oc i s a  f i e l d o f A, then the m u l t i p l i c a t i o n  of a row o r column of A by cx r e p l a c e s per(A) by The  Invariant  o<'Per(A).  s i m i l a r i t y o f the above d e f i n i t i o n to t h a t of a  determinant f u n c t i o n of a matrix suggests the p o s s i b i l i t y o f a computational procedure f o r per(A) analogous t o the w e l l known theory  f o r det(A).  C e r t a i n determinantal  laws such as  2 the"Laplace for  E x p a n s i o n Theorem", and  example have a n a l o g i e s  f o r the  t h e most u s e f u l p r o p e r t y ,  ( o r c o l u m n ) , has  invalidated plicative fact  the  relation,  r o o t s A.  can  of A  be  This  (det A)(det  i'l  the  i s these p r o p e r t i e s  permanent f u n c t i o n  matrices  t o be  inhibits  the  easily  the  and  not  have n o t  the  character-  by  d e t e r m i n a n t s o f most the  lack  of  them g r e a t l y  i n f a c t , make i t  Many m a t r i c e s  undetermined  have  an  easily  permanents.  t o overcome t h i s  t h a t no  more t r a c t a b l e  inherit  been o v e r l y s u c c e s s f u l .  b e e n shown f o r d e t e r m i n a n t s ,  as  possessed  to r e l a t e permanents to o t h e r  scalar functions,  difficulty, has  problem.  d e t e r m i n a n t s and Efforts  matrix  the  c o m p u t a t i o n o f p e r ( A ) and,  extremely d i f f i c u l t evaluated  evaluated,  well  multi-  x  that are  that allow  as  basic  =  1  It  B)  another  unfortunately  the  i n terms o f  (namely d e t ( A )  invariant  alone  permanent o f  expressed  but  ( o r a column) t o  counterpart.  det(AB) =  Theorem"  permanent f u n c t i o n ,  o f a row  analogy f o r the  that det(A)  istic  no  "Binet-Cauchy  that determinants are  under a d d i t i o n of a m u l t i p l e row  the  computational  In f a c t , i t  uniform  affixing  4.  of _  signs  to the  elements of a m a t r i x  permanent i n t o the no per  linear T(A)  difficult for  operation  determinant on m a t r i c e s  = det(A) f o r a l l A  131.  as T  can  w e l l as  In f a c t ,  of  matrices.  the  that  : A-*T(A) s u c h  problem to e s t a b l i s h i f per(A) >  special classes  convert  there  is  that  i t i s even  a  det(A) or v i c e  versa,  3 Much work has bounds and  inequality  b e e n done r e c e n t l y  relations  j^l  to  f o r the permanent  establish function  by p r e s e n t i n g t h e p e r m a n e n t a s a n I n n e r p r o d u c t i n t h e symmetric  class  o f c o m p l e t e l y symmetric  Cauchy-Schwarz I n e q u a l i t y ) .  The  t e n s o r s (and u s i n g the  best r e s u l t  t h a t can  be  o f f e r e d a t the p r e s e n t time r e g a r d i n g the permanent o f  a  p r o d u c t i s the f o l l o w i n g i n e q u a l i t y  approach.  |per(AB)| <  t h e t r a n s p o s e d c o n j u g a t e o f A.  useful  trivially  inequality  (for a l l 1 = 1 , o f A*A,  and  (J^w^/n)  . . . , n )  the Binet-Cauchy  examples of r e s u l t s  (For unitary matrix U  g i v e s the r e s u l t  |per AJ ^  2,  2  i s large,  computation  this  even f o r a h i g h speed  V a r i o u s methods have b e e n d e v e l o p e d  o b t a i n e d from L e t S(X)  be  The  roots  earlier,  are  i s a formidable task i f  (On an IBM  this 7040  5 months i f n =  of p e r ( A ) i  this 13.)  The  best  t o RYSER [ 5 ] .  m a t r i x and  let B  r  denote  B by r e p l a c i n g some r columns o f B by  t h e p r o d u c t o f t h e row  this  to avoid t h i s e v a l u a t i o n  i n the computation  known i s t h e f o l l o w i n g f o r m u l a due  T  w^  computer, s i n c e  i f n = 11 and  L e t B be a n - s q u a r e  1).  A ,  technique.  involves nj permutations.  o f n! p e r m u t a t i o n s  where  r e l a t i o n mentioned  o b t a i n e d by  w o u l d t a k e a l m o s t a day  |per uj ^  are the c h a r a c t e r i s t i c  To e v a l u a t e p e r ( A ) d i r e c t l y n  this  ( p e r ( A A * ) ) ( p e r ( B * B ) ) where A* =  2  inequality  o b t a i n e d from  a matrix  zeros.  sums o f t h e m a t r i x  X.  4-  Then  where  *£ V "• • • S(  per (B) = S(B)  -  £  S  (  B  1 '  S(B ) denotes the sum over a l l (p) replacements r  <- >" E  of r  of the columns by columns of zeros. (b) The Matrix A^. A  n  i s defined to be the n-square matrix over the entry 6  complex f i e l d with general i j th primitive n root of unity:  e  6  e  e-  e -  e  2  n  e9  e3  i.e.  , where 6 i s a  e  2  i  n-3  A = n  e~ n  e  2  n - l  Q  Q  n  "  n-2  e "  k  n  Q  6  n-3  0  3  l  I t i s r e a d i l y seen that A^ i s independent th a primitive n  of the choice of  root of u n i t y .  This matrix, which i s met frequently i n problems concerning extreme values of hermitian forms, also occurs very naturally i n the study of c i r c u l a n t s , which are matrices of the type?  1  n 1  s(B  5 C  C  1 n  1  2  3  n - l«  C  2 2  C  c  n-2  C  n n-1  C =  All  circulant  matrices  C  t k - 1, 2,  . . .  n}  .lk '  e  where  e U  k  2k th  =  for 0 a primitive n  0 The e i g e n v a l u e s U =  l  C  o f o r d e r n h a v e i n common t h e s e t o f  orthonormal eigenvectors { l / / n U  Let  n  nk  of a c i r c u l a n t  (U , U »..•,U )//n. 1  2  which transforms  matrix  of t h e i r  A  = ^  c  i  0  k  •  •  matrices  )  "  1  )  »  k=l,...,n.  to the d i a g o n a l  0  , where  .  ;  0  U C U =  o  (  [6],  Xi •  (Note t h a t U i s j u s t  k  a l lcirculant  eigenvalues  o  are A  Then t h e m a t r i x U i s t h e u n i t a r y  n  matrix  i.e.,  root of u n i t y .  .  the m a t r i x  .  A  n  A^/pi.)  C is a  circulant.  6 By  the b a s i c m u l t i p l i c a t i v e  the determinant  law  f o r determinants  o f a u n i t a r y m a t r i x has  det  since  absolute value  1,  C =  i.e.,  det C =  lT(2  e ^~ ^)  a circulant  i s thus  easily  obtained.  c  k  1  permanent f u n c t i o n f o r c i r c u l a n t s very d i f f i c u l t problem  In  and  Theorem*  1  we  the d e t e r m i n a n t  To d e t e r m i n e  the  t h i s problem  by a p p l y i n g  obtain  w  J^V/J{v)  A  a  unresolved.  p e r U * [ l , 2 , . . . ,n| w ] p e r u[w|l,2,...,nj  per C = ^lA/(w)  =  of  on t h e o t h e r hand, p o s e s  which i s s t i l l  attempting to resolve  the "Binet-Cauchy  , and  p e r u[l,2,...,n|w]  2  J~JA  ,  w  where w =  w,,w v  \  w  =A  1 w^  ,X  multiplicities s e q u e n c e w.  w), nJ ,...» A  2 w  w  2  n  l ^ w . £ w ^ n; i n ; and U(VJ) i s t h e p r o d u c t o f /  o f the d i s t i n c t  i n t e g e r s appearing i n the  T h i s l e a d s to the study of p e r  s i n c e U = A /fn n  to the study of p e r A  (U)  or  . n  v  This matrix A  the  n  i s indeed i n t e r e s t i n g  i n i t s own  right. A  i s normal (i.e., A A * = A *A ) . n ' n n n n A J J n i s unitary (i.e., A "V/n = A *//n). n n n A  n  c a n a l s o be p u t i n e q u i v a l e n t f o r m s by  column o p e r a t i o n s such  elementary  t h a t the permanent remains  row  and  invariant.  W  7 In  one e q u i v a l e n t f o r m  i.e.  i t i s a Vandermonde m a t r i x ,  a matrix o f the type,  1 r2 11 12 2 2  n-l  r  R  B =  ( i ^  ) =  r  Since  n-l  R  per A  n  n  1 r2  r  n  3  n-l  n  n  =  per(0  =  (e .e .....e " )per(0 ^" ), 1  J  )  by  definition,  2  n  1  I  1 )  0  1  by t a l c i n g out of 1 row o f A V l . t h  n  /  per A  n  where In  another  (© ( i + j f )  A , n  1  1  1  i f n odd,  1  per^ **  (e ^" ^)  5 - 1  *)  i fn  even,  i s a Vandermonde m a t r i x .  e q u i v a l e n t form A  i s a circulant  with  per A  The are  1  n  i s a circulant.  If  .th (i+jf the matrix with general i j entry 0  denotes  to  =•<  per(0 ^" ^)  readily  n  =  and i s e a s i l y  (0^ ^) I+  then  shown t o be e q u i v a l e n t  per(0* ^).  determinants  I+;I  of a l l the m a t r i c e s mentioned  f o u n d b u t a l m o s t n o t h i n g c a n be s a i d  p e r m a n e n t o f any o f them.  above  about t h e  8 (c)  The  Permanent o f  A . n  P e r C A ^ ) c a n be difficulty  f o r n = 2,  3,  computed by hand w i t h o u t t o o much 4,  5 to give;  per(A ) = 0 . 2  per(A ) = 3  -3.  per(A^) = 0 . per(A^) = One  would  perhaps  c o n j e c t u r e from these v a l u e s t h a t  e q u a l s 0 f o r n e v e n and p r o v e s t o be result  correct.  for n =  -5.  e q u a l s -n f o r n odd. The  latter  i s d e s t r o y e d by  ?  use  and  t h o s e f o r n = 9»  of the U n i v e r s i t y  of B r i t i s h  p e r ( A ) = +3  =  4  9  D.H.  Columbia's  IBM  = 11»13»1229 =  1 3  )  70k0  computer.  +81.  per(A  1757^7.  Lehmer o f t h e D e p a r t m e n t o f M a t h e m a t i c s , do n o t a p p e a r  Professor University  t o p r e s e n t any  pattern. As we  Q  the  13 were o b t a i n e d by  = 3»5»ll*4l = 6765.  Santa Barbara, C a l i f o r n i a ,  A  11»  r e s u l t s w h i c h were a l s o communicated by  simple  former  -105.  per(A ) n  These  n  7: p e r ( A ) = - 3-5«7 =  This r e s u l t  The  per(A )  Is always  shall  s u b s e q u e n t l y see, t h e permanent  a n i n t e g e r and  i s always  of  d i v l s a b l e by n .  In  2 particular divlsable  i f n=p by p  h,  .  , where p i s a p r i m e , By u s i n g any  then p e r ( A ) i s  of a v a r i e t y  n  of permanent  of  9 inequalities  [ 7 ] we c a n show -Jn* ^ p e r ( A ) ^ JrP~  equivalently  that  (since  n  - |det(A ) | ^ p e r ( A ) ^ |det(A )| n  2  2  ( d e t ( A )) n  = n ).  IV o f t h i s  n  c a n be n a r r o w e d  generally unresolved.  t h e s i s we i n v e s t i g a t e  n prime, n >3; the best r e s u l t of A  n  F o r n even, p e r ( A ) i s d e t e r m i n e d n  (=0) b u t f o r n odd t h e p r o b l e m r e m a i n s In Section  or  1  the case of  obtained, i s that  t h e permanent  down t o be one o f a r e s t r i c t e d  s e t of  integers. Since  pertA^  cr(t)  =  )'  k k-0  where a, d e n o t e s s.t.  t h e number o f p e r m u t a t i o n s CTe S  / icrti) = K(mod n ) , we c a n a t t e m p t c-i }  resolving  t o f i n d p e r ( A ) by n  t h e a l t e r n a t e number t h e o r y p r o b l e m ,  t h e number o f p e r m u t a t i o n s CT i n t h e s y m m e t r i c such that It  ^iO~(i)  i s easily  = k(mod n ) ,  seen t h a t  are equivalent.  i f n i s a prime  t h e s e two  I n the proof of the r e s u l t s  This  symmetric  group  involves S^.  that  the approach  t h e p e r m a n e n t o f A^ by, s o l v i n g  problem.  group  S » n  f o r k=0,1,2,...,n-l.  a l m o s t no l i n e a r a l g e b r a i s u s e d ; being to find  of f i n d i n g  problems follow,  generally  this  second  f o r t h e most p a r t a s t u d y o f t h e  10  II  PBELIMINARY THEOREMS  The f o l l o w i n g lemma shows t h a t p e r A of  the choice  Lemma 2 . 1 . root  of the p r i m i t i v e n  If  of unity.  and k i s a p o s i t i v e i n t e g e r such  Since  h  that  ) =  per(0  k i j  ).  Thus  per(0 The m a t r i x  i j  ( k , n ) = 1, k j ( m o d n) = <T(j) where cr i s a  permutation i n S .  (9  u  k i J  )  =  ), however,  P  er(0  i O  "  ( J )  i s just  t h e permanent  permutations  ).  the matrix  (e  J  )  t o the permutation<r.  w i t h i t s columns p e r m u t e d a c c o r d i n g Since  t  = 1, t h e n per(9  Proof:  i s Independent  = (0*^) i s n x n , where 6 I s a p r i m i t i v e n  of unity,  (k,n)  root  n  o f a matrix i s i n v a r i a n t under  o f rows o r c o l u m n s , per(0  k i j  )  = per(©  i j  ). Q.E.D.  The p e r m a n e n t  of A  i s obviously  A  per A  = perfe ^)' 1  n  Eft. ™ 10  9  i  -  ,  a p o l y n o m i a l i n 0:  Hence  < per(0  i ; )  ) = a  Q  + a 9 1  + . . . , + a  e " , 1 1  where a ^ i s t h e number o f p e r m u t a t i o n s 0" € S^ s u c h  ^io-(i)  s j(mod  (1)  1  that  n),  (2)  We a r e t h u s p r e s e n t e d w i t h a n i n t e r e s t i n g p r o b l e m  i n number  t h e o r y , which t o t h e b e s t o f o u r knowledge, has n o t been solved. Not  a l l of the c o e f f i c i e n t s  More p r e c i s e l y , Theorem 2.2. per A a  i n (1) c a n be d i s t i n c t .  we have  I f ( k , n ) = 1, t h e n i n t h e r e p r e s e n t a t i o n n  i  = a  Q  + a 6 + . . . . +  a  1  = ^Kmod  Proof:  n)' v  per(0  i  f  o  r  1  _ i  k  i K  ~k + a1e lei 1 ii per(6 ) = per(0 ) ,  By Lemma 2.1,  J  therefore  Z^®!®^  " »  i  ) = per((9 ) = a  e  =  1  l c l ; )  n  Q  1 J  ) .  , „k(n-l)  + . . . . +  ;  '*  =  2 n-l S i n c e 0, 0 , . . . , 0 a r e l i n e a r l y independent the r e a l  e  J  over  numbers, i  ki(mod  n) Q.E.D.  Corollary  2.3.  I f n i s a prime,  n > 2, t h e n i n t h e  representation p e r A = a + a.0 + . . . . + n o 1 a  Proof:  i  =  a  2  =  I f n i s prime,  * ' * ' (k,n)  =  a  n— l a .0 , n-l  (1)  n-l *  = 1 for a l l l£k6n-l.  Thus hy  Theorem 2.2, a^ = a^,  for l ^ k ^ n - 1 . Q.E.D.  I n Theorem 2.2 we showed a r e l a t i o n s h i p b e t w e e n t h e a^ f o r l ^ i ^ n - 1 . any  The q u e s t i o n w h e t h e r a  Q  c a n be r e l a t e d t o  o f t h e o t h e r a ^ , i s answered i f n i s even i n t h e next  Theorem.  We f i r s t  require  the following  Lemma 2.4.  I f cr i s a n y p e r m u t a t i o n £  is  c y c l e permutation;  the f u l l  j° =  lemma. and j°  where n i s e v e n , ( 1 , 2, 3>....» n ) ,  then + n/2 (mod n ) .  Proof:  Yl[(T/>)(!)  since .'.  = ] T i [ ( ( r ( i ) + l ) ( m o d n)]  (<T/>)(i) = (CT(i) + l ) ( m o d n ) .  ,Ti(cr/))(i)  = ^icr(i)  + £ \ (mod n)  J ^ i c r ( i ) + (n+1)n/2 (mod n) ^icr(i)  + n/2 (mod n ) ,  s i n c e n i s even. Q.E.D.  13 Theorem^. for Proof:  I f n i s even,  &  = a  ±  (  1  +  n  /  2  )  m  d  n  ,n-l.  1 = 0 , 1,  1 to n.  L e t k be any n a t u r a l number f r o m  Consider  o  the s e t  \  =  I f P = (1,  { y  &  2,  S  n I  3,  = Mmod n ) J ;  ^A^ ) 1  k = 0,...,n-l.  • . • . , n) we have by t h e p r e v i o u s  Jl((Tp)(i)  = 2^(1)  + V 2  (mod n)  lemma  VcTe  i=i  = k + n/2 (mod n ) • Since  f o rcr,t £ S  Jx  Therefore  we  J  ( k + n / 2 ) m o d  number o f e l e m e n t s Similarlly  cr^T*  with  r  >  |^|  where  ^  I denotes the  i n X^.  consider ce  i f we  Of * TP  X  (k+n/2)mod n  obtain '((k+n/2)+n/2)mod n i.e.,  Therefore  we  '(k+n/2)mod n "  k  h a v e t h a t t h e number  (k+n/2)mod  n  of permutations  cr e S n  YI  that give  ^icr(i)  ti h .a e .t , g i v e - ^a l t ( l ) &  1  (  i  +  n  /  = k(mod n) i s e q u a l  2  )  t o t h e number  = k + n/2 f(mod o r in ) = .0 , . . . , n - l , m  o  d  n  Q.E.D.  Observe  that k=0  14  Theorem 2.2  X. = X„ , j I jk(mod n) t o l o o k a t the p a r i t y o f  g i v e s the r e l a t i o n  1  where the  (k,n) =  1.  We  permutations  w o u l d now  in X  +  like  in X  1  .  3  .  L e t X. and X. d e n o t e J J permutations  1  the s e t s  o f e v e n and IX  respectively, with  IX  = a ,  +  odd  +  where a * + a~ = a .  J  J  J  The  ^  w i t h X.  a n a l o g y t o Theorem 2.2  or X  «  X  i s not generally J  the  true.  replacing J  F o r t h e c a s e k = n - l we  can  state  following.  Theorem 2.6.  (a) I f n i s odd,  (n-2)/2 a r e b o t h even,  +  +  a, = a . , , and j j ( n - l ) m o d n' 1 (  K  ( n - l ) / 2 even,  a  J  =  Proof;  a  o(n-l)mod  Let  cr e S  n  f  °  -  -  a . = a,, , j J(n-l)mod n  6  ~  ( n - 2 ) / 2 odd,  r  »1»• • • »  Thus  n _  0  ^<r(l),<r(2),  ^ ) *  and  1•  3  .  .  .  . ,  .  . • .  1  )  1  ,  n n  , 0-(n)y l ( n - l ) , ( n - 2 ) , v  • .  , n ,n-cr( ) n  ( C r y ) ( i ) = n - CT(i).  ^ i *  or i f n  be a n a r b i t r a r y p e r m u t a t i o n and l e t  r  1 » 2 , n-C7(l) , n - a ( 2 ) , i.e.,  j=G,l,...,n.  then  y _ f 1 , 2 , " V(n-l),(n-2),  u  and  then  (b) I f n i s e v e n , ( n - l ) / 2 a r e b o t h odd,  or i f n  =  ^i(n-cr(i))  =  ( n - l ) / ivr(i)(mod  n),  .  n  15 i.e.,  If  ( T ^ X , then cry £ X .,, j j\n-l)mod one-to-one mapping o f X o n t o X., .. 4 /  j cry = tjT an  (Tat.)  even p e r m u t a t i o n  (n-2)/2 if  then  are both  j\n-1)mod I t i s readily  even.  This gives a •  X  Similarly  (Since i f  n  checked  i f n i s odd, ( n - l ) / 2  (n-2)/2  n i s even,  . n  J  that  even,  2f i s  o r i f n,  i s a n odd p e r m u t a t i o n  odd, o r i f n and  (n-l)/2  a r e both  odd. Finally is  even,  since  t h e p r o d u c t o f two e v e n  permutations  t h e p r o d u c t o f a n odd a n d a n e v e n i s a n odd  permutation,  e t c . , the r e s u l t  i s proved. Q.E.D.  Theorem are  2.7.  I f n i s even,  both odd, then X  (n-2)/2  (n-l)/2  odd, o r i f n and  h a s a n e q u a l number o f e v e n a n d o  odd  Proof:  permutations.  C o n s i d e r any  cr n X  Q  with  cr e v e n .  As i n t h e p r e v i o u s  theorem, i f  y then  _ / l . 2 , " \(n-l),(n-2),  •n  3  .  ,  .  .  .  .  ,  .  1  ,  ,  n  .  n  ^Ti(cry)(i)  == ( n - l ) ^ i O - ( i ) =  0,  since  (mod n) / i C 7 X i ) ( m o d n) =  0.  (CTtf) £ X . Since  ^ under the c o n d i t i o n s  permutation,  of this  t h e o r e m i s a n odd  t h e r e i s thus a one-to-one mapping o f the  even permutations  of X  onto o  t h e odd p e r m u t a t i o n s  of X . o Q.E.D.  16 Theorem 2.8.  I f r j n , say  if  and  R =(x|x  then  • n^  =  n  ~= k r ( m o d n)  ©  S  r  i s an  (k,n)=l,  l ^ k  integer.  Proof: (a) L e t  r„,  r  1  divisors  2  r  m  o f n,  with  =  1 be  an  ordered l i s t i n g  r^ >  i =  o f a l l the  l,...,m-l.  Let  2r^  = ( l ^ ,  R  2 = { 2»  H  m  lr  and  R  1  =  = R  2  7  2  _  » • • • >  2  (R  Is e a s i l y  x  we  (  • ^ r  1 ) r  f  1 1  2J  n  " ! 1  2  =  n,  -  n,  2  n  *  1  =  n  »  ;  B  =[ |  (b)  »  1  V **'' V  2  where ^  define B  It  {  =  (n^D^j  . . . ,  To  x  /  2  /l R  1  )  seen that a l l  are  = kr^wo</n),(k,n)=l,  show  p r o c e e d by  S  =  i  s  i n d u c t i o n as  8 1 1  i  disjoint,  l ^ k ^ n  n  t  e  g  e  r  follows.  V"  "I  J =  and  that  j = 1,2,..,m  l,...,m  17 r  i  - 1  = J  Q  r  (1)  S^  =  (2)  Assume t h a t  (3)  To  -1,  x  show S  an  a l l S^ i s an  Integer  are  integers  integer,  for  i =  l,...,k-l  consider  "K-I  k-i By  definition  I f r ^ r ^ t h e n fl£ f| If  r ^T ]/i  since Let  r  k  be  l  Since  r  than r since  R  R^,  L.C.M. o f  i s higher  ki  •  construction  o f R^  and  R^.  0,  r ^ and  i n the  list  x 6 R^,  implies  are  disjoint.  can  now  We  \)  r  .  r, , / n ki /  , this  0  =  ±  also  fl by  x £ R^ f)  and  A  «  R^ f l R  the  ,', r, / x kl /  R  IJ(R^  then  1  say  -  =  write  S  as  r  1  , r_,..., ^  which g i v e s  r  a  n  contradiction,  follows.  k S^  = Z"Q  X  -  \  f^t® J  r—>  X  where t h e  is for a l l s.t.  = the  (-1)  -  induction  J~\integer) ,  summation o v e r i ,  since  the  1,  R C\ X  S^^ a r e  4  t  integers  by  hypothesis. Q.E.D.  18  III  Theorem  3.1. *—  Proof:  Per(A )  SOME GENERAL RESULTS ON PER ^ .  I f n i s even, p e r A  n  1  = a 0° + Q  = (v  0 +  V  • •••  +  n  = 0.  + . . . . + e n / 2  2  (  a  n  -  1  e  n 1 "  ) (v -<n/a +  ^  1  /  ^  (D  + 1 )  «  < n / 2 + 1 ,  • v ^ -  1  )  +  ) -  By Theorem 2.5 a, = a , . 1 (i+n/2)  f o r 1 = 0,....,n-l  t  Therefore  P e r ( A ) = a (9° + 0 n o  n / 2  + .  But  e  k  + e  ( n / 2 + l £ )  = o* • e = 0  Thus t h e r e s u l t  n / 2  ) + a . , ^ + e< / l>) l 1  (n/2-1)  •e  k  - s  i ^ k  2  n  -  1  2 +  '  • (-i)e  k  f o r any k .  i s proved. Q.E.D.  19 Theorem 3.2, Proof:  P e r A ^ i s an  I t i s easily  s e e n t h a t we  per A where and  (Note t h a t Since  /  per A  per A  = a  n; h e n c e a 0 Q  t e r m i n (3)«)  J}0  i s an  l,...,n  x Z> } L**l  + o  2 .8  r  1-^k^n  a, = a,, . i f o r a l l i = i ik(mc<fvO (k,n)=l,  n  Therefore  (k,n)=l,  i s over a l l i , such t h a t r j n.  Ifk^n,  by Theorem  (3)  n)  does n o t c o n t a i n  therefore  But  £  o  by Theorem 2.2,  for  can w r i t e  = a a° +  n  = | xjx = kr^mod  t h e summation  and  integer.  i s an  integer.  integer.  Q.E.D. Per A  Theorem 3.3. "— Proof:  n  = O(mod n)  I f n i s even the theorem i s o b v i o u s l y  per  A  =  n  the p o s i t i o n  Theorem 4.2 This  fact  since  0.  The t h e o r e m i s a l s o in  true  true  i f n i s odd, b u t we a r e n o t y e t  to prove t h i s .  t h a t n/a^  together  It will  follow  from  f o r i = 0,1,2,...,n-l.  w i t h Theorem 2.8  gives  the r e s u l t .  Q.E.D.  20 Theorem 3.4. —  p e r A = a + a„e n o 1  Let  I f n i s a n odd p r i m e ,  + . . . + a „e n-l  yi 1 ,  then  per A  Proof:  1  = a  n  - a ^  Q  By C o r o l l a r y 2.3  a  = a  1  = . . . . = a  2  n  _  1  1  Therefore  p e r A = a + a (6 + 6 n o 1 = a + a (-l) Q  + . . . . +  1  p e r A^ = a  Q  Q.E.D.  + a^e  + . . . . +  where n i s t h e s q u a r e o f a p r i m e p . per Proof:  A  = a n o  r e l a t i v e l y prime t o n. i  a^  n-l 0 ,  Then  - a . p  L e t Y he t h e s e t o f r e s i d u e s n  a  n-l 6 )  - a • o  Let  2  1  = a  Theorem 3.5.  #  mod n w h i c h a r e  T h e n by Theorem  " i k ( m o d n)» a  f  o  r  k  &  2.2 V  2 For  n = p , t h e o n l y numbers l e s s t h a n n n o t r e l a t i v e l y  prime It  t o n a r e p , 2p, • • . . , ( p - l ) p .  follows  that  -  I?  1  2 °  J P =  J  Subtracting, Thus  o  -p'.j  \L->  p e r A „ = a_ + a„ J ~ 0 + a ^ ^ V .  Now  and  n  k  -u  ~ * 1  °*  =  per A n  5  = a o = a  + a„(0) + a (-1) 1 P - a . o p  n  Q.E.D.  21  IV  The n  > 3,  PER  > 3-  I F n IS A PRIME  a i m I n t h i s s e c t i o n i s t o show t h a t  i fn  prime,  t h e n t h e p e r m a n e n t o f A^ i s l i m i t e d t o be one o f a  restricted  c l a s s o f odd I n t e g e r s .  Theorems u s e d h e r e a r e s t a t e d  Most o f t h e p r e l i m i n a r y  and proved  i n greater  generality  t h a n i s n e e d e d f o r t h e above r e s u l t . L e t cr d e n o t e the  full  n  (1,  cycle permutation ..e.  It  an a r b i t r a r y p e r m u t a t i o n i n S , and P  i s easy  '1, 2, 3, .  f=  2  > n)  that  A» 2, 3* •  1, 2, 3»  12, 3, k, •  2, 3» ^» • • • » 1J  \3. i n general  . n>  2, 3, .  and  3  i2, 3, 4, .  t o ckeck D  2,  n  5, .  that  (3)  D / ( i ) =(k+i)mod n .  •  • »  n  •  • t  Pri  •  • »  n  k  where  CT =1  ft  If  , 2  , 3  IffTCrt , TO , CTC3)  J  • • • » n  22 then  1 , 2 , 3 , k  l , 2 , 3 , « » » , ^),OD), and  n  . . . . . n  0?i), OTP), (TO), . . . . , or*),  \  N  , on;/  i n general  where  / ( T U ) s cr[(i+k)(mod  n)J .  By g i v i n g k, v a l u e s f r o m  1 t o n , we o b t a i n t h e s e t  of n permutations;  pa-fpV, which of  • • • ./cr  (with  are a l l obviously d i s t i n c t  1 under  (just  l o o k i n g a t t h e image  e a c h p e r m u t a t i o n shows them a l l t o be Similarly  the permutations  (5)  =cr),  /cr  different)•  o b t a i n e d by m u l t i p l y i n g  on t h e r i g h t by powers o f p , a r e o f t h e g e n e r a l f o r m kJ ;  where  »2  1  m)(o (p^(^3 9  • 3  ' » • • • »  permutations ( w i t h 07?"= cr s i n c e  f=  1)  (6)  a r e n o t n e c e s s a r i l y a l l equal to those i n the f i r s t s e t . The  fact  that  £ityfir/)(l) = C>|  f o r a l l k a n d 0, i s p r o v e d All  but  •  ( G " / ) ( i ) = [ p ~ ( i ) + k j (mod n ) .  Q-p,(Tp\ . . . , c r /  and  \  . . .  h  T h i s a g a i n g i v e s us n d i s t i n c t  which  n  this  [ ^ i C T U ) ] (mod n) f o r n odd (.'=1  i n t h e f o l l o w i n g two  leads to the f a c t ,  theorems.  t h a t w i t h a n y cr e s  cr I G , where G i s a c e r t a i n s u b g r o u p n* n  of S , n'  n  23 we  can a s s o c i a t e a b l o c k of n  permutations  d i s t i n c t permutations  ( pb~/f) where k t  = 1,2,..,,n) s u c h t h a t i f fl p * ~  9  cr and X b e l o n g t o s u c h a b l o c k , t h e n  ) l(T(i) = 7=1  Theorem ^ . 1 .  {mod  A ^ ) 1  Lie.  I f cr e 3^ and Z = ( l , 2 , . . . , n ) a f u l l 3  permutation,  ( v i z . the  1  n)  J  cycle  then  2  i(pV)(i)  i(«rf)(i) =  (mod n ) ,  k =  1,2,...,n.  Proof: ^i((r^)(i)  = ^ i ( [ ( T ( i ) + kj(mod n)) -  =J"2  <r[(l + k) (mod n)j  iCr(i) +  = 2k ^ i ( m o d  ^A^  1  - ( J  1  ^  1  )  " k J i ) ] (mod n)  n)  = 2k(n+1)n/2 (mod n) = O(mod n ) . Therefore  Xi(crp )(l) k  =  ^ A " ) ( i ) (mod n ) • Q.E.D.  2k _Theorem __________________k.Z. _  Ifcr  permutation  e s  e S  (a) i f n odd  n  and J* =  (1,2,...,n) a f u l l  cycle  then  n  Yj-OTj^)  ( i ) s ]__ifr"(i)  t  (mod n)  f o r any k ,  in  1(0"/^) ( i ) = Z ^ i G l i ) (mod ) n  ^i«rp )(i)  Z]lo1i) l n / 2  =  k  CM  f  o  r  k  (mod n)  e  v  e  k  n  i odd.  i-l  Proof: J i ( ( T / > ) ( i ) = Zj.[((T(i) + k) mod k  n ] mod  = ^ J L ( T ( i ) m o d n + k])jL mod = ^\cr(l)mod n + k(n+l)n/2  n  n mod  n .  t'-i (a) I f n I s odd, k ( n + l ) / 2 Therefore  i s an  integer.  (1) = ])_icr(i) (mod n) C--I  f o r a l l k,  («l  (b) I f n i s e v e n ,  k(n+l)n/2  7_ H(r/ )(i) :  s  i s an  integer,  = )_i<ni)(mod n ) ,  i f k even,  n and  2 j L C T ( i ) * n / 2 mod  n  i fk  odd. Q.E.D.  C o r o l l a r y k.3»  I f n 6dd, then  ^i(p Tp )(i) k  Proof:  1  = fj.*(l)  (Prom p r e v i o u s two  mod  n  theorems).  f o r a l l k,  1.  25 For  any  b,  O^b  ^-n-1, and  m fe Y , we n  f u n c t i o n T* T(i)  = b +  (i-l)m  l * T ( i ) * n .  where since  X"U)  i =  Moreover, d i s t i n c t permutations.  implies  values  o f b and  +  (i-l)m  2  1  = T(2)  + m  We  define  of  the  G  form  G  (b  the  n)  (mod  n).  Y « n  rise  to  distinct  and  + m)  2  =CT(1) = since  2  b  g  T(2)  =CT(2).  s e t of a l l permutations  T that  are  0(n)  show t h a t  show t h a t o ~ , ^ g  G  G  TU) (m ,n) =  choices  Function.  + ( i - D m ^ (mod n)  1  2  2 3 m  n  m.  CT7J e G .  s b + (i-l)m 1, t h e r e e x i s t s m  for  to  (a)  i s a group i t i s n e c e s s a r y o n l y -i  Implies  N  0~(i) = b  2  Euler  I n n«|6(n) ways, c o r r e s p o n d i n g  f o r b and  To  i s the  nv. 0 ( n )  above d i s c u s s i o n t h e p e r m u t a t i o n X i n  specified  choices  containing  n  From the  Since  (mod  i s a subgroup of S  n  be  e  m give  =T(l)  b  e l e m e n t s , where ^ ( n )  can  m  which i n  (a).  Theorem 4.4. ______________  Proof:  (a)  2  that =  t o be  n  1,2,...,n.  jm(mod n ) ,  since  + U-Da^  CT(i) = b  b  i =  suppose  T(i)  and  a ^  n),  im =  j(mod n)  For,  Then t = 0" i m p l i e s  define  i s a permutation of {l,2,...,n}  = l~(j)  turn implies  (mod  c a n now  2  S  i( °d m  Suppose  and  (mod n ) . m^ s u c h t h a t .  to  26 It  i s readily  checked  f'(i)  = (b  3  that + (i-l)m )(mod n ) , 3  where b ^ = m ^ l - b ^ ) + 1 (mod n ) . Then ( c r r ) ( i )  t V ( D )  =  Thus CT T"' e G„ . n Q.E.D.  Theorem 4 . 5 .  I f n i s odd a n d ( n , 3 ) = 1, ^i(T(i)  Proof:  then  = O(mod n) f o r a l l cr  6  G  R  •  L e t CT(i) =(b + (I-l)mXmod n ) . T h e n f\v(l)  = b|jL + m j j  2  - rn^J.  = b n(n+l)/2 + m n(n+l)(2n+l)/6 - m  n(n+l)/2  = 0 (mod n ) , Q.E.D.  Corollary  4.6.  ^iO~(i)  I f n i s a n odd p r i m e , n ^ 3 ,  then  s 0 (mod n) f o r a l l (T £ G .  c--i  n  Thus i n c a s e n i s a p r i m e , n > 3 we have o b t a i n e d a subgroup  of S  n  e a c h e l e m e n t <r o f w h i c h has t h e p r o p e r t y  Jj.<r(i) C--1  s  O(mod n ) .  T h e r e may however be o t h e r f e  with this  property.  27 We now p r o c e e d t o show t h a t S  n  consists  the remaining p o r t i o n o f  2  of d i s j o i n t  s e t s K, e a c h c o n t a i n i n g n j  elements, each o f which g i v e r i s e  t o t h e same r e s i d u e  class. Theorem 4 . 7 . Then H K,»  n  i s the union of d i s j o i n t  n  = S„ - Gn . n  > 3; a n d l e t H  L e t n be a p r i m e  ————————J-  j = l,...,r  such  complexes  that  2  J  (I)  each K  contains n  elements, which a l l  have t h e same p a r i t y , a n d (II)  f o r each  j there exists  c^ s u c h  r>  f o r a l l cr e K * j  ) i ( T ( i ) = c ( m o d n) 4  w  D e f i n e K„. = The n  {P^P**  permutations  p\p > m  =  y  L e t cr e H ; a n d l e t P = ( 1 , 2 , 3 , . . . ,n) n  Proof; .  i  that  / <T/  />V"*;  =  l,2,...,n].  i,m = >  are distinct,  )  then,  = f  0 1 i)  f o r suppose  V ^ ' % )  A  for  1,2,...,n.  Specifically, CT(i)  °"(  i +  f o r each i ,  ~ (T( 1+2^1^  ^2"A)  Since n i s prime,  + m ~ l  ^  m  2  s < r ( i ) +.1*^111 i f i>  2  1  -  m  o  d  n  *  o  r  (mod n ) .  t Q  3  there e x i s t s k such  (2-2) k s 1 (mod n ) . 2 1 T h e n ( T ( i + 1 ) = CT(i + k f i - i ^ ) . that  =  0 ~ ( i ) + k(m -m ) (mod n) . 1 2  T h i s means t h a t cr e G that  ere  H . n  q  , c o n t r a d i c t i n g our assumption  Therefore 1 - 1 .  2  1  =0;  i t follows  f r o m (7)  28 that  m  - m  1  = 0 also.  2  By C o r o l l a r y  4.3  we  Thus K  =L  1-1  complex K  all  T  l,2,...,n.  (mod n)  permutations  0" e K^.  now  K ( r  show t h a t R  0  K  t h e same r e s i d u e f o r  r  o-/ .  w  f o r two = ^  n  c o m p l e x e s K^, K ,  Cj  13 = i 2 - i 1  =  i » 2  or  T  m,  m  .  r  pV/> '=  J^TP**  I t follows  2#  that  J> 'XP > l  r  (mod n ) ,  = K  K  J>^ jr^  Thus  Ijt™^  m  either  r  then 1  for a l l  gives  n V(r7ti  0  f o r some J ^ , m ,  1£  Thus f o r any p a r t i c u l a r  have  K If  i(r(i) (mod n)  ,  n We  d i s t i n c t elements,  i=i  /_i<r(i)  We  2  have  ^iCPVj^Mi) for a l l k,X=  has n  r  =  m  3  CT e K , r  1 ^ i,m £ n.  = m and  2  - m  M  (mod n ) , and  1  j CrP e K 5  where  9  m  Therefore  T  £  2 S i n c e IT and K „ e a c h have n  elements,  T h e r e f o r e complexes a r e e i t h e r d i s j o i n t o r e q u a l .  29 To show a l l p e r m u t a t i o n s i n a complex same p a r i t y ;  we n o t e t h a t f o r n o d d ,  P = ( 1 , 2,..., n) = ( 1 , 2 ) ( l , 3 ) , . . . , ( l , n ) o f a n e v e n number o f t r a n s p o s i t i o n s . of  have t h e  i s a product  Also,, s i n c e a p r o d u c t  even p e r m u t a t i o n s i s even and t h e p r o d u c t o f an  and a n odd p e r m u t a t i o n i s odd, t h e r e f o r e o r odd a c c o r d i n g  i ft  0" e K  even  i s even  i s even o r odd.  2 Thus t h e n  elements  i n t h e complex have t h e same  parity. Q.E.D. Note:  I f r i s t h e number o f d i s j o i n t K Q - ^ , S  Considering  Q  = G  N  U K  X  U  . . .  i n; = n ( n - l )  + r n  Thus  (n-l)I  = n - 1 + rn,  or  (n-l)i  = - l ( m o d n) .  i s just  Theorem 4.8.  r  t h e number o f e l e m e n t s  s e t s , we g e t  This  , t i K ,  Wilson's  i n each o f these  2  (n prime) .  Theorem!  I f n i s a p r i m e , n > 3» a n d i f a^. i s t h e  number o f p e r m u t a t i o n s i n S s u c h n  that  £]icr(i) = k(mod n ) ,  then  (I)  Q  n(n-l)  divides a ,  p and  (II) n  divides  a^ i f k =  1,2,...,n-l,  30 Proof:  By  Theorem S  4.7, = G  n  UK.,  . , . . UK  1  n  §  (8)  ;  and i f JjLcr(i) = k 4 o ,  t h e n cr e some K; n  It  follows  that  t h o s e o- s u c h t h a t  c o m p l e t e l y occupy e a c h K„ has n j  2  a c e r t a i n number, r  elements, a  By C o r o l l a r y ^ 3 »  = &  = rn  Now  a  Q  Therefore  + a  a a  and  »•••*»  2  =  ?  n)  o f K..5, S i n c e  k  j  ; t h i s proves ( I I ) . a  n  l^k^n-1;  ±* say  r^ = r.  2  +  1  = r, «n k  k  =  2  Hence, a l l r ^ a] are equal, Then  ^jLCT(i) = k(mod  ».«.»* + ^ - 1 +  o  (n-l)rn  2  =  n  • •  I = n! >  = n ( n - l ) [(n-2)! - r n ] ;  o  (I) i s proved.  Q.E.D. Theorem 4 . 9 .  i n t e g e r s y and  z such  per A Proof:  o  that  n  = a  Q  -  i s t h e number o f CT e. s_ s u c h t h a t n  S u c h CP o c c u p y decomposition  G  n  non-negative  3.4,  From Theorem  a  there exists  = n [ ( n - l ) + y ( n - l ) n - zn].  n  per A Now  > 3,  For n a prime, n  / icr(i) = ft  and a c e r t a i n number o f t h e K^*s  (8).  0. i n the  31 2  Thus  a  Since  = n(n-l)  Q  + wn .  n - l divides a , i t also divides o  Therefore i n t e g e r y. Since  n  a  = n(n-l)  Q  2  + y(n-l)n ,  w. f o r some n o n - n e g a t i v e  d i v i d e s a, ,  therefore  a, = z n  2  1  f o r some n o n - n e g a t i v e i n t e g e r z . Therefore  per A  = n(n-l)  n  + y(n-l)n  2  - zn  2  n[(n-l) + y(n-l) - z ] .  Q.E.D. Theorem 4.10. Integer  F o r n a prime  y such  > 3» t h e r e  that  per A„ = n  2  n  Proof:  From t h e d i s c u s s i o n a  and  e x i s t s a non-negative  a^ = z n , 2  3  i n Theorem  = n(n-l)  Q  - n(n-2)! + n y , 4.9,  + yn (n-l), 2  k = 1,2,....,n-l  r,-l Since  n! =  J^^t i-0  I n! = n ( n - l ) Hence •'•  zn = p  e  r  A  n  =  a  (n-2)i  o -  a  i  = n(n-l)  = n  2  2  2  + yn (n-l) + (n-l)zn ,  -  1 - yn, 2  + yn (n-l) + (yn + 1 3 I  I (n-2)i)n  + n y - n(n-2)J <  Q.E.D. Remark:  Computed v a l u e s indicated  f o r t h e x and y above w i l l  i n Section VI.  be  32 This value  of A  n  does n o t  answer the  , even f o r n a prime, but  considerably  the  We result  result  note  possible  i t does  as  to  restrict  values.  t h a t A^/fh  o f M a r c u s and  question  i s a unitary matrix.  By  a  Newman f_ 7 J  pepA/mUl, n ' | per A |^  which implies  n  Thus i f n to -n  n  the  values  and  + n , 11  of  n  .  i s a prime, then per n  2  where y  3 + n^y  -  I  n(n-2);  is a positive  A  n  is  restricted  t h a t l i e between integer.  33  the  V  THE  In  this  CASE OF n = p  s e c t i o n we  square of a prime  Section The  G , w h i c h was n  enough f o r o u r p u r p o s e s F  n  s h a l l obtain  somewhat s i m i l a r  IV f o r a prime.  group  , WHERE p IS A PRIME  L e t n=p  2  to those obtained i n  , where p i s a  useful i n Section here.  some r e s u l t s f o r  We  prime.  IV i s not  large  s h a l l form a l a r g e r  group  c o n s i s t i n g of permutations of the f o l l o w i n g t y p e . L e t cr be a p e r m u t a t i o n o f { l , 2 , . . . , p } .  Define:  2 <T(i + cp) =cr(i) + for  i = 1,2,...,p and  where  {a^}  and  l ^ s  We  permutation of <T(J) = 0 " ( k ) , Then C f U J  +  1  + c s ) p (mod  1  s are constants such that O ^ - a ^ p - l show t h a t  {l,2,••.,p J. 2  Suppose  where, s a y , j = i  1  + c p and k = ±  (a, + c s)p =T(i ) + 1 < T ( l ) = ( T ( i ) mod 2  2  Hence c implies  (21), c^s = c s 2  = c , and that  j = k,  (mod  finally  2  ( a , + c s ) p (mod U p.  t h e d e f i n i t i o n o f (f, i t f o l l o w s from  7  e a c h s u c h f u n c t i o n <x i s i n d e e d a  t  and,  p )  0,l,...,p-l;  1  and By  c =  (a  +  2  p ), 2  2  that  i  1  = i ,  = a^ ,  2  p).  j = k.  c p.  Thus CT( j ) =  so t h a t 0" i s a p e r m u t a t i o n .  <T(k)  34 Theorem 5 . 1 . form  The s e t F  a subgroup o f S  permutation X i n S T(i+p) is  of permutations  n  ft  of order p  inS  n  o f the form  • pj • (p-1).  p  (20)  Every  with the property  n  == T ( i ) + k p (mod p ) ,  f o r a f i x e d k,  2  l-Sk^p-l,  a member o f F . n  Proof;  Suppose CT(i+cp)  Then <r~  1  = c T ( i ) + (a-.+cs)p  (Z0)  (mod p ) . 2  I s g i v e n by  0-" (i+cp)  =cf {l)  1  + ( b j + c t j p (mod p ) ,  1  where O ^ b ^ p - 1 ,  2  t i s such that  s t = 1 (mod p ) , a n d l s b ^ p - 1 ,  l ^ t ^ p - l , b =-a t(mod p ) . For, 1  i  C r c r ~ ( i + c p ) s c r ^ C X U ) + ( a j + c s j p ] (mod n) 1  = (TCT" (i) +  [b_ + ( a j + c s j t j p  1  = i +  [-a^t +  (mod n)  + c ] p (mod n)  = i + cp (mod n ) . Thus i f C T e F , c r " n  then  e F . n  i f JJ i s d e f i n e d by  Similarly, ^(i+cp)  1  = JJ(1)  + (o^+ciOp  ay>(i+cp) = ^[cr(i) + ( a ^ c s j p ) (mod ri) = CTyL/(i) + =  where 0 —X, S p - 1 , I group.  \x  ±  + (a^csjujp  CJ/;(i) + [ o ^ + a^u + c s u ] p  = fjJil)  is a  (mod n ) .  (mod n) (mod n)  + [X + cw]p (mod n ) ,  and l ^ w ^ p - l .  Hence Q"E e F , a n d F , n n  35 To o b t a i n t h e number o f e l e m e n t s  i n F , we  note  n  t h a t t h e r e a r e p ! ways o f c h o o s i n g CT; p ways o f c h o o s i n g each a pl  * P  i  i = l , 2 , . . . , p ; a n d p-1 ways o f c h o o s i n g s ; y i e l d i n g  ?  • (p-1) ways o f c h o o s i n g CT.  P  distinct;  (a^cs)?  (mod p )  y j ( i + c p ) = JJ(1) + ( b ^ c t j p  (mod p )  P  d e f i n e two members T a n d T j,  l < j ^ p ,  such that  I f ( f =yU,  a±  If  a l l  (f=yL/,  £  D  o f F^.  I f CT $p  C f U ) t yO(j);  = b  then  1 ?  •> t h e r e  and s ^ t ,  .  then P  t h a t t i s a member o f S  = T ( i ) + k p (mod p ) ,  • (p-1) d i s t i n c t  for a l l i=l,...,n. TT(i) = d  i  +  l^d <p, 1  ThenT(i) a j  p,  and  n  such  that  l<k<p-l,  2  c a n be w r i t t e n  1=1,2,...,p, OSa^p-1.  We  show f i r s t  that  i s a permutation o f {l,2,...,p}.  Choose r s u c h t h a t dj^ = d^  for  t[i  r k = l(mod p ) . I f  U j < p ,  + Uj-a^rp]  then = X ( i ) + (a^-a^rkp = d = d  i  J  + a  l  P  (mod n)  + (a^-a^p  + a p (mod n)  s T U )  exists  CT(j) t  CT(i) t  Thus t h e r e a r e p l • p  suppose  T(i+p)  {d^  2  in F • n  Now  where  2  f o r some i , t h e n  ±  Q~(i+p) ^ y ; ( i + p ) . elements  choices are  f o r , suppose  CT(i+c ) = CT(i) + and  These  j  (mod n ) .  (mod n)  36 Since T  i s a permutation,  which i m p l i e s We  c a n now  i = j (mod  write  &^  we  =T(i)  T(i+p)  +  +  finally  where  = T(i) +  T(I+cp) = t ( l )  have  ( a ^ - a ^ r p = j (mod  p ) , and  =T(i),  t(i) Since  i +  & i  that  t e S ; p  n),  i = j .  and  p.  kp,  (a^+ckjp.  T  i s t h e r e f o r e a member o f F . n of Theorem 5.1.  This  completes  the proof  Q.E.D. We  n  n e x t examine t h e r e s i d u e c l a s s  ^}.Cr(i) CM Theorem 5.2.  of  f o r CT 6 F . N  I f CT 6 F , r  then  j ] i < T ( i ) = p ^ i O l i ) (mod n) , I'M (a I where CT i s t h e p e r m u t a t i o n o f l , 2 , . . . , p , g i v e n i n (3d). The  n  number o f p e r m u t a t i o n s CT I n F  ^iCT(i)  =  j p (mod  such that n O ^ j ^ p - I , i s equal to  n),  I'M  p  p  • (p-1)  such  times  t h e number o f p e r m u t a t i o n s CT £  S  p  that £i<?(i) =  j (mod  p).  I'M  Proof:  JiQ-(i) = t'M ?  £i[3u) I'M  +  a  ip) ij +  i + p )  +  777  ( a  i  + s ) p  + £(i+2p) [<f(i) + ( + 2 s ) p ] + . . . . aj  + £ji  +  ( P - D p ] [(T(i) + {a  ±  +  (p-l)s}pl  3  37 F  = p ^ i < T U ) + P Yj- & I P + Yj- [ IM i-l CM  S +  2  + • • •  S  +  (P-l)J P  v  + y ^ i C T ( i ) [p + 2p + . . ; +  (p-l)p]  = p y \ < T U ) + p ( p + l ) / 2 [ s + 2s + . . . + + p ( p + l ) / 2 [ p + 2p + . . . + - P ^ f f l i ) The  (p-l)p]  (mod n ) .  l a t t e r statement  immediately  (p-l)s]p  from  Theorem  i n t h e theorem  follows  5«1«  Q.E.D. As e a c h 0~ e S  (see  n  i n t h e p r e v i o u s s e c t i o n , we now c o n s i d e r f o r - F , t hhee s e t n  = [i Vi )  )m  | i,m =  0,l,...,n-l}.  page 27).  I Theorem 5.3. For  I f Q~ e S  a l l elements  - F ,  n  R  T £  ^iT(i)  2  then IK^I = n ,  K,  = /J-Oli)  CM  I  (mod n ) .  C-. )  2 Proof:  As J , n r u n t h r o u g h 0 , l , . . . , n - l ,  P^Q~P are  a r e produced.  different.  P V P  m  =Cr  then  CT(l+i) + m  I t i s required  It i s sufficient  implies  l=m  = CT(i)  = 0.  Then  permutations t o show t h a t  t o show If  they  that  fiVP"  = CT,  (mod n ) .  F i r s t , j = 0 i m p l i e s m=0. that ri=l(mod n)•  n  If (i,n)=l,  choose  r so  38  <X(i + r i ) = c r ( i ) - r m  (mod n ) ,  ( T ( i + 1) s C T ( l ) - r m  (mod n ) .  or Then  r m ^ 0 (mod n ) , and CT(i + p) = CT(i) - r m p  (mod n).  By Theorem 5 . 1 , CT e F , a c o n t r a d i c t i o n .  The r e m a i n i n g  a l t e r n a t i v e f o r 5 i s $ = cp,  I n t h i s event  l^c^p-1.  CT(I + p i ) = ( T ( i + c p ) = CT(i)  (mod n ) ,  2  and  hence  ( T ( i ) = <T(1)  I t follows that  - pm  (mod n ) .  m = 0 (mod p ) . Moreover m ^ 0 (mod n ) ,  s i n c e , i n that case, GT(i + cp) =CT(i) which i s impossible. By Theorem 5 . 1 ,  Thus  (mod n ) , l^k^p-1.  m = kp,  CT £ F , a c o n t r a d i c t i o n . n  Thus JK^J = n . 2  Let t = P V P " ;  0 < i,m 6 n - l .  Then  £Yc<u =  ^ i P V F ( i ) C•I n  = £j-[(T(i+J) +  m]  L--|  = Y (i+i)CT(i+i) . t=|  CT(i+i) + C M  = ^jKTU) - in(n+l)/2 ' M  Tt  ™ C M  + m n(n+l)/2  Q.E.D. Theorem 5 . 4 .  For<T",T. j. F, N  either  = K  r  , or  K^O  = (J).  39 Proof:  fl K ,  If U e K  X - P'  which implies It  follows  Since  K  that I =  Thus S  then  r  n  1/ = p V p ' =  f^Xp^i  m  x  Q~ft '~ '', m  m  and hence t  6 K . r  K-w S K^. K  i s p a r t i t i o n e d as f o l l o w s ;  where t h e number o f e l e m e n t s i n t h e v a r i o u s  subsets are  shown i n b r a c k e t s . We  a r e now i n a p o s i t i o n t o g e t some  on p e r A . n per  Recall ^  that  = a  Q  + a 9 + . . . . + 1  where a . i s t h e number o f CT e S such j n ^icr(i)  = j (mod n ) . per  By  Theorem 5»2,  information  A  n  In fact,  n-l a ^ e that  f o r n = p , by Theorem 2  = a - a„, o p  t h e number o f Q**s i n F  f o r which n  / ~ ] i c r ( l ) = 0 (mod n)  is p  p  • (p-1) t i m e s t h e number  3.5,  40 o f (f 6 S  such  that  the  = o  ^icf(i)  P  2 + k^p  (mod p ) .  By  Theorem  l > l  latter  is  T h e r e may,  p(p-l)  f o r some i n t e g e r k^.  i n a d d i t i o n be CT ^ F  such t h a t  /  10~(1) = 0. 2  The number o f t h e s e w i l l 5.3  Theorems  % Similarly,  a n d 5.4. = P  P + 1  be a m u l t i p l e k  4  o f n =p  , by  Thus  (P-1)  e a c h CT i n F  + k  2  p + 2 l P  (p-l)  such that  n  + k  2  ? \  / iCr(l) = p ^rp  p  t o a cr i n S  corresponds  such that  ^ i C T ( l ) = 1 (mod p ) . C-l  The number o f t h e l a t t e r Thus t h e is  k^p  p + 2  number o f CT £ F (p-l):  i s k^p , by Theorem such that  n  Outside F  n  4  ^iCT(i) = p  there w i l l  (mod n)  be a  multiple  type.  We have  4 k^ o f p  f u r t h e r permutations a  and  p + 2  3  (p-l) =  then  k^pS  as a r e s u l t per A  Setting k Theorem  = k p  p  of this  5«5»  1  n  = p  k,l  +  1  (p-l)  2  + (k k )p r  + k ^ + 1 = k, 2 F o r n=p , p^3» per A  where  P  n  = P  P + 1  and  n  k  2  (p-l)  + k ^ - JL>  +  (k -k^)p\ 2  we  ( P - D (kp-1) + .2p\  are positive integers; per A  p + 2  3  =0  In p a r t i c u l a r  4 (mod p ) .  have  41  VI  COMPUTER RESULTS  (a) Computer Programme, Per  n=5,7, using  was c a l c u l a t e d  11, 13, o n a n IBM 7040 c o m p u t e r .  by  T h i s was done  t h e f o l l o w i n g w e l l known f o r m u l a d u e t o R y s e r  L e t B he a n - s q u a r e matrix  f o r t h e odd p r i m e s ,  m a t r i x and l e t B  o b t a i n e d from B by r e p l a c i n g  zeros.  r  denote  a  some r columns o f B  L e t S ( X ) be t h e p r o d u c t o f t h e row sums o f t h e  m a t r i x X.  Then  p e r B = S(B) - ZjSfB^ where J~*S(B ) d e n o t e s r  +  &  ( B  " ••• ^  } 2  1 ) n  " & 1  ( B n  .  ) 1  t h e sum o v e r a l l ( £ ) r e p l a c e m e n t s o f  t h e r columns b y columns o f z e r o s .  If  B = A  r  , where n i s o d d , a n d i f A ^ ^ j  matrix  o b t a i n e d by r e p l a c i n g  zeros,  then i t i s e a s i l y (l/r)S(A  If r  0  M  l's  su»s  o  f  S (A  r columns o f A b y c o l u m n s o f n checked that  , ) = (l/(n-r))SU , ). n(r) n(n-r)  ) denotes  /  A , ^tL n(r)  denotes the  since  the product o f the f i r s t n - l «•» ^  ™  «  A oons n  o n l y , we h a v e  .» " ' 'W-  8 ( A  r  ( r )  S(  i S t S  ot  42  Thus we  can  per A  rewrite  (?)  = -lI>'<A  n  as  n ( 1 )  .  )  z£*'l^ )  •  -  m  . . . +  3Es'(A  (-l) " (n-l)^S(A n  .  1  n ( n  n(3)  1 )  )  ) .  Therefore per ^  =  ( n - 2)JV  (  "  n  6  )  (A  E  S  Thus t o e v a l u a t e p e r A  ,  A  n ( 1 )  )  n(3)  -  (n -  • • •  +  i f n i s odd,  \  ^  + {  z  )  t " > ° ' E ' - ( » - i : )/2 .  +  1  1  8  i  i t i s only necessary  to  n compute t h e p r o d u c t matrices (?) (?) +  +  o f the f i r s t  for r = • • • The  1,. •., ( n - l ) / 2 .  (<n-?)/ )  +  n - l row  m  a  t  r  l  6  e  S  l  n  sums o f a l l p o s s i b l e  That a 1 1  2  is for  -  programme u s e d t o o b t a i n v a l u e s  f o r per A  , n  Ut  f o r n = 5»  7»  t h e above  paragraph. It  a t a time,  matrices  13,  was  b a s e d on  consisted essentially  which generated r  and  the equation  of a combination  a l l p o s s i b l e combinations  for r =  1,  2,...,(k-l)/2.  of n  (10)  in  generator,  things  From t h e s e  the  A  , , were f o r m e d f o r e a c h v a l u e o f r , a n d / S A . n(r) n( ) evaluated. By e q u a t i o n (10), p e r was t h u s o b t a i n e d . r  T h i s programme was and  print  out  S A  designed  to  for a l l r, i n a particular n  with  originally  compute  order;  (r)  t h e hope o f o b s e r v i n g p a t t e r n s w h i c h w o u l d a l l o w  conjecture f o r per A  n  t o be  obtained  from e q u a t i o n  a  (10).  43 Due  to the e x c e s s i v e checking i n v o l v e d  o r d e r i n g of the combinations, very  inefficient 17,  For n = time.  no  i f used  result  in less  for n >  n  c o u l d be o b t a i n e d i n two 7,  than f i v e minutes.  g e n e r a t o r , A ^ „ and A _  17  t h i s programme p r o v e d t o  to calculate per A  Whereas, f o r n = 5 .  11,  13,  per A  hours  was  n W i t h an e f f i c i e n t  s h o u l d be r e a d i l y  19  i n the be 13. computing  computed  combination  o b t a i n e d by  the  IBM 7040.  (b)  Results. n >3  F o r n a n odd p r i m e , computer  have t h e  following  results. = - 5  per per A  Theorem 4 . 9 or  we  n  per A  1 3  (Theorem 4.10)  Thus f o r n = 5 ,  = 3 • 5 • 11  per A  gives  Per A Per A  7,  11,  = - 3 • 5 • 7  ?  =  11  • 41  • 13 • 1229 .  = n [ ( n - l ) + y ( n - l ) n - zn] ,  n  = n  n  and  2  13,  I  - n(n-2)i we  + n  can l i s t  n  y  z  5  0  1  7  2  15  11  3004  29985  13  36274  2834249  3  y.  t h e v a l u e s o f y and  z.  C '  COMPUTING  P F R M A N E N T OF A ( N ) RY RYSFRS MFTHOD.  j  c c  GOMPI FX XI «TH( 1 7 I »PROn« R^l IM.THFTAt INTEGER SP ( 17 ) , PER . DIMENSION KOL(1431.8)  1 7 . 1 7 1  .FN  ' -'  DT MFNSTON MOI (17)  79  D I M E N S I O N M0T( 1 7 ) P R I N T 1 •• F 0 R M A T ( 3 4 H ,COI UMNS GO TO 1 1 2 PER=0• '  '  i  '' , PRODUCT  j  •  O.F R.O.W.S11MS  '  .  )  •  •  :  •  '1 • .  '  SP(1)=1  m  S P ( 2 ) = ( N - l ) /2 DO 1 1 3 I = 1 » MO  •'  P F R - P F R + ( N-?# T ) *N*.SP ( T ) * ( -1 ) W R I T F ( 6 » 1 1 1 ) PER 1 1 2 . .R E A D ( 5 . 2 ) N 2 FORMAT ( T ? ) P R I N T 19,N 19 FORMAT ( I X » 12 ) • -  • •  MO= ( N - i ) / ?  •  ,  •.  T  -  •  '• '•' *•  •  ' '  ' '  •-. •  •  M=3 GO TO 5 1 .. 3 8 M = M+1 51 M1=M-1 M2-M-2 I F ( M . G T . M O ) ' G O TO 7 9 T=N ; • X1=CMPLX(0.,2.*3.1415927/T)  . •  •  •  . •  •  "  •  NT = N-1  40  44  43  DO 4 0 I = 1 » N I • EN=FLOAT(I) TH ( I ) =CEXP ( E N * X 1 ) TH(N) = (1.0,0.0 ) DO 1 0 1=1,N DO 4 3 J A = 1 » N  KA=I*JA  I F ( K A . L E . N ) GO TO 4 3 KA=KA-N GO TO 4 4 THETA( I >JA)=TH(KA)  .  ...  ' • -  • '  •  .  '  •  "•• •  iJ  U1  ffl  >sj  03  (£1  CO  o  I  i +  *  II  * _l  O  iTl m II II r H <—> cr -H O o - H o; •-H •J. „ o r - ~:|- + H H (<• in — CO ^ 4 — UJ II II II II II _l r O CL ixl O O o ~ o; o o o o o c O O ll z z c z z zQ ^ Q 2 C S U V LU  •JO O  I—I  II  I—I  l-H  »"  rH II  *—1  ^ 11  II  I-  n!  i—•  -  32  II  I  —  co  CO iTl  O  o _l II o  m  II  rH  o O o; i4 v  II  rH II i-<  i-H  O  CO  9* rH II —  V  ^ ||  o  r-l  Q  CO  m  O rH  o • co a  + UJ CL . O' co V h- ~) + _|  H  m— _J OO s:  OV  •  r-i  II  II  O  ii a _ i s: rro  a  LL  Q  O  CM CO  LL  II  o  co  co  f\J CO  B  •  (NJ  r- ocn  co N to m  ro  £  S • . . 36 KOL ( K , I ) = KOL( K» I 1 ), - KOL ( K » M ) = K M 300 C 200 93 55  17 16 52 .201  • •  39  m  24  12  Ji  .25  >io  9 8  )7  26 41  U  30  6 5  3  GO TO 62 I F < M O L ( M ) . L E . 1 ) GO GO TO 6  TO  '' ' ' 24  .  9  '  L 8  6  '  MOT(1 ) = 1 DO 93 I= 2 » M MOT(I)=MOT(1-1)+MOL(I-1) PROD = ( 1 • 0 » 0 • 0 ) / FLOAT. (M ) ' DO 16 I=1 »N RSUM= ( 0.0»0..0) DO 17 LA=1»M J.A^JM.O_T LLA ) • RSUM=RSUM+THETA(I» JA) PR0D=PRODORSUM S P ( M ) = S P ( M ) + T N T ( .5+RFAI (PROD) ) • W R I T E ( 6 » 5 2 ) PROD, (MOT('LA) •LA=1»M)' FORMAT ( 2 F 1 0 . 2 »4X, 20 I 3 ) I F ( K .FO . 1 ) GO TO 11 K = K+1 <'1 = K-1 ' ' I F ( K . G T . N O ) GO TO 39 GO TO ' 300 WRITEC6-, 111 ) S P ( M ) •• FORMAT(60X,110) GO TO 38 L-L+i • ML1 = M-L+1 ' ML=M-L DO 2 5 I = 1»M K0L(K,I)=MOL(I) KOL( K , ML ') = MOL ( ML ) + 1 I F I L . E Q . 2 ) GO TO 41 DO 26 I=ML1,M1 K O L ( K »I )=1 KOL< K,M1)=1 KOL(K,M)=0 ' DO 30 I=1» M1 KOL(K»M)=KOL(K»M)+KOL(K»I)  OL •  A i  •  -  •. ' ' '. •• ' • • • '.  ' '  • .  ' '  • '"  •  TT  Nivyo -n  II  - _i rH  O  ii \i r" II w  v O  CM  C o  o o o Q 2 U  X LU  O < U  O Z LU  CNJ •4-  rH  LL  CM  fcfl  44  BIBLIOGRAPHY  1  A.C. A i t k e n , D e t e r m i n a n t s and M a t r i c e s , E d i n b u r g h , 1946.  4  ed.,  2  G. P o l y a , A u f g a b e 424, A r c h . M a t h . P h y s . ( 3 ) ,  20 (1913), P. 271. 3  M a r v i n M a r c u s and H e n d r y k M i n e , On t h e R e l a t i o n Between t h e D e t e r m i n a n t a n d t h e P e r m a n e n t . I l l i n o i s J . M a t h . , v o l 5 ( 1 9 6 1 ) , p p . 376-381.  4  M a r v i n M a r c u s and Hendryk M i n e , P e r m a n e n t s , Amer. M a t h . M o n t h l y , v o l 72 ( 1 9 6 5 ) , p p .  577-591.  5  H.J. R y s e r , C o m b i n a t o r i a l M a t h e m a t i c s , Carus Math. Monograph n o . 14, 1963.  6  H.L.  7  M a r v i n M a r c u s and M o r r i s Newman, I n e q u a l i t i e s f o r t h e Permanent F u n c t i o n . A n n a l s o f M a t h e m a t i c s , v o l 75 n o . 1, J a n u a r y 1962, p . 55.  Hamburger, and M.E. Grimshaw, L i n e a r Transformations In n-Dimensional Vector S p a c e . Cambridge u n i v e r s i t y , L o n d o n (1951).  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080613/manifest

Comment

Related Items