UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The permanent of a certain matrix 1966

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

Item Metadata

Download

Media
UBC_1966_A8 H64.pdf [ 2.55MB ]
Metadata
JSON: 1.0080613.json
JSON-LD: 1.0080613+ld.json
RDF/XML (Pretty): 1.0080613.xml
RDF/JSON: 1.0080613+rdf.json
Turtle: 1.0080613+rdf-turtle.txt
N-Triples: 1.0080613+rdf-ntriples.txt
Citation
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 i n the Department of Mathematics We accept t h i s t h e s i s as conforming to the standard r e q u i r e d from candidates f o r the degree of MASTER OF ARTS. THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1966 In p resen t ing t h i s t h e s i s in p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r re ference and s tudy. I f u r t h e r agree that permiss ion fo r ex- tens ive copying of t h i s t h e s i s fo r s c h o l a r l y purposes may be gran by the Head of my Department or by h i s r e p r e s e n t a t i v e s . It i s understood that copying or p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n - c i a l ga in s h a l l not be a l lowed wi thout 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 of t h i s t h e s i s i s to attempt to evaluate the permanent f u n c t i o n of a nxn complex matrix w i t h e n t r i e s a. ± = 9 , 9 being a p r i m i t i v e n root of u n i t y . I f t h i s matrix i s denoted by A then i t s permanent n f u n c t i o n i s given by p e r An=lfK<r<i> T£S„ ^ (r<tS„ I n 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 per = 0 mod n. I f n i s even per A =0. n Por n odd however, the problem i s i n general not r e s o l v e d . 2 I t i s shown th 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, per A^ can be narrowed down to be one of a r e s t r i c t e d c l a s s of numbers. TABLE OF CONTENTS PAGE I I n t r o d u c t i o n 1 I I P r e l i m i n a r y Theorems 10 I I I Some General Results on Per A Q 18 IV Per A n i f n i s a Prime 21 p V The Case of n=p , Where p i s a Prime . . . . 33 VI Computer Results *H Bi b l i o g r a p h y . . . . . kk ACKNOWLEDGMENTS I wish to express my s i n c e r e thanks t o Dr. B.N. Moyls f o r a l l the he l p he has g i v e n me i n the p r e p a r a t i o n of t h i s t h e s i s , and to whom many of the theorems and p r o o f s are due. I am a l s o indebted to Dr.W. McWorter f o r h i s h e l p f u l suggestions and encouragement, and to Ted Powell f o r programming a s s i s t a n c e . I INTRODUCTION The purpose of this thesis i s to attempt to evaluate the permanent function of an nxn complex matrix with entries a^j = 6 , 6 being a primitive n root of unity. (a) Permanents. For a matrix A of order n with entries i n some f i e l d , the permanent function of A Is defined by p e r A = g t t l 0 U ) . where S i s the symmetric group of order n. This s c a l a r n function of the matrix A appears frequently i n combinatorial problems concerning enumerations [ l ] , and has the following formal properties. The per(A) remains invariant under a r b i t r a r y permutations of the rows and columns of A and i s also Invariant T under transposition; i . e . , per(A) « per(A ). If oc i s a sc a l a r from the underlying f i e l d of A, then the m u l t i p l i c a t i o n of a row or column of A by cx replaces per(A) by o<'Per(A). The s i m i l a r i t y of the above d e f i n i t i o n to that of a determinant function of a matrix suggests the p o s s i b i l i t y of a computational procedure f o r per(A) analogous to the well known theory f o r det(A). Certain determinantal laws such as 2 t h e " L a p l a c e Expansion Theorem", and the "Binet-Cauchy Theorem" f o r example have a n a l o g i e s f o r the permanent f u n c t i o n , but the most u s e f u l p r o p e r t y , t h a t determinants are i n v a r i a n t under a d d i t i o n of a m u l t i p l e of a row (or a column) to another row ( o r column), has no c o u n t e r p a r t . T h i s alone u n f o r t u n a t e l y i n v a l i d a t e d the analogy f o r the permanent of the b a s i c m u l t i - p l i c a t i v e r e l a t i o n , det(AB) = (det A ) ( d e t B) as w e l l as the f a c t t h a t det(A) can be expressed i n terms of the c h a r a c t e r - i s t i c r o o t s A. of A (namely det(A) = 1 i'l x I t i s these p r o p e r t i e s t h a t are not possessed by the permanent f u n c t i o n t h a t a l l o w the determinants of most m a t r i c e s to be e a s i l y e v a l u a t e d , and the l a c k of them g r e a t l y i n h i b i t s the computation of per(A) and, i n f a c t , make i t an extremely d i f f i c u l t problem. Many mat r i c e s have e a s i l y e v a l u a t e d determinants and undetermined permanents. E f f o r t s to r e l a t e permanents to o t h e r more t r a c t a b l e m a t r i x s c a l a r f u n c t i o n s , to overcome t h i s i n h e r i t computational d i f f i c u l t y , have not been o v e r l y s u c c e s s f u l . In f a c t , i t has been shown f o r determinants, t h a t no u niform a f f i x i n g 4. of _ s i g n s to the elements of a m a t r i x can convert the permanent i n t o the determinant as w e l l as t h a t there i s no l i n e a r o p e r a t i o n on m a t r i c e s T : A-*T(A) such t h a t p e r T(A) = det(A) f o r a l l A 131. In f a c t , i t i s even a d i f f i c u l t problem to e s t a b l i s h i f per(A) > det(A) o r v i c e v e r s a , f o r s p e c i a l c l a s s e s of m a t r i c e s . 3 Much work has been done r e c e n t l y j ^ l to e s t a b l i s h bounds and i n e q u a l i t y r e l a t i o n s f o r the permanent f u n c t i o n by p r e s e n t i n g the permanent as an Inner product i n the symmetric c l a s s of completely symmetric t e n s o r s (and u s i n g the Cauchy-Schwarz I n e q u a l i t y ) . The b e s t 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 o b t a i n e d from t h i s approach. | p e r ( A B ) | 2 < (per(AA*)) (per(B*B)) where A* = A T, the transposed conjugate of A. ( F o r u n i t a r y m a t r i x U t h i s i n e q u a l i t y t r i v i a l l y g i v e s the r e s u l t |per uj ^ 1). The u s e f u l i n e q u a l i t y |per AJ ^ (J^w^/n) 2 where w^ ( f o r a l l 1 = 1 , 2, . . . , n ) are the c h a r a c t e r i s t i c r o o t s o f A*A, and the Binet-Cauchy r e l a t i o n mentioned e a r l i e r , are examples of r e s u l t s o b t a i n e d by t h i s t echnique. To e v a l u a t e per(A) d i r e c t l y i s a f o r m i d a b l e task i f n i s l a r g e , even f o r a h i g h speed computer, s i n c e t h i s computation i n v o l v e s nj permutations. (On an IBM 7040 t h i s would take almost a day i f n = 11 and 5 months i f n = 13.) V a r i o u s methods have been developed to a v o i d t h i s e v a l u a t i o n of n! permutations i n the computation of p e r ( A ) i The b e s t known i s the f o l l o w i n g formula due to RYSER [5]. L e t B be a n-square m a t r i x and l e t B r denote a matrix o b t a i n e d from B by r e p l a c i n g some r columns of B by z e r o s . L e t S(X) be the product of the row sums of the m a t r i x X. 4- Then per (B) = S(B) - £ S ( B 1 ' * £S(V " • • • <-1>n"1Es(Bn-l> » where S(B r) denotes the sum over a l l (p) replacements of r of the columns by columns of zeros. (b) The Matrix A^. A n is defined to be the n-square matrix over the complex f i e l d with general i j entry 6 , where 6 is a th primitive n root of unity: i.e. A = n 6 e 2 e3 e e e- e 9 e n ~ 2 Q n " k e n " 6 e n - l Qn - 2 Qn - 3 e n - 2 i e n-3 0 3 l It is readily seen that A^ is independent of the choice of th a primitive n root of unity. This matrix, which is met frequently in problems concerning extreme values of hermitian forms, also occurs very naturally in the study of circulants, which are matrices of the type? 5 C = C C 1 2 n 1 2 C « c n - l n Cn-2 Cn-1 2 3 C n C l A l l c i r c u l a n t m a t r i c e s of o r d e r n have i n common the s e t of orthonormal where e i g e n v e c t o r s { l / / n U t k - 1, 2, . . . n} .lk ' U k = e e 2k 0 nk t h f o r 0 a p r i m i t i v e n r o o t of u n i t y . The eigenvalues of a c i r c u l a n t are A k = ^ c i 0 k ( ; ) " 1 ) » k=l,...,n. L e t U = ( U 1 , U 2 » . . • , U n ) / / n . Then the matrix U i s the u n i t a r y m a t r i x which transforms a l l c i r c u l a n t m a t r i c e s to the d i a g o n a l m a t r i x of t h e i r eigenvalues [6], X i • • • 0 o A 0 i . e . , U C U = , where C i s a c i r c u l a n t . o . . . A n (Note t h a t U i s j u s t the ma t r i x A^/pi.) 6 By the b a s i c m u l t i p l i c a t i v e law f o r determinants and s i n c e the determinant of a u n i t a r y matrix has a b s o l u t e v a l u e 1 , det C = i . e . , det C = lT(2c e k ^~ 1 ^) , and the determinant of a c i r c u l a n t i s thus e a s i l y o b t a i n e d . To determine the permanent f u n c t i o n f o r c i r c u l a n t s on the o t h e r hand, poses a very d i f f i c u l t problem which i s s t i l l u n r e s o l v e d . In attempting to r e s o l v e t h i s problem by a p p l y i n g the "Binet-Cauchy Theorem*1 we o b t a i n per C = ^ l A / ( w ) per U * [ l , 2 , . . . ,n| w]per u[w|l,2,...,nj J~JA W w = J^V/J{v) A per u[l,2,...,n|w] 2 , w where w = w,,w w ) , l ^ w . £ w ^ n; v 1 2 nJ i n \ = A , X ,...» A ; and U(VJ) i s the product of the w ŵ  w 2 w n / m u l t i p l i c i t i e s o f the d i s t i n c t i n t e g e r s a ppearing i n the sequence w. T h i s leads to the study of per (U) or s i n c e U = A /fn to the study of per A . n v n T h i s m a t r i x A i s indeed i n t e r e s t i n g i n i t s own n r i g h t . A i s normal ( i . e . , A A * = A *A ). n ' n n n n A J J n i s u n i t a r y ( i . e . , A " V / n = A * / / n ) . n n n A can a l s o be put i n e q u i v a l e n t forms by elementary row and n column o p e r a t i o n s such t h a t the permanent remains i n v a r i a n t . 7 In one e q u i v a l e n t form i t i s a Vandermonde matrix, i . e . a m a t r i x of the type, B = ( i ^ ) = 1 2 r r 1 1 1 2 R2 R2 1 2 3 r r r n n n n - l n - l n - l n S i n c e p e r A n = per(0 J ) by d e f i n i t i o n , = ( e 1 . e 2 . . . . . e n " 1 ) p e r ( 0 I ^ " 1 ) ) , by talcing 01 out of 1 t h row of A n V l . /per(0 1^" 1^) i f n odd, per A =•< n - p e r ^ 1 * * 5 - 1 * ) i f n even, where ( e 1 ^ " 1 ^ ) i s a Vandermonde m a t r i x . In another e q u i v a l e n t form A i s a c i r c u l a n t . I f (0^I+^) n .th denotes the ma t r i x w i t h g e n e r a l i j e n t r y 0 ( i + j f ( i + j f then (© ) i s a c i r c u l a n t and i s e a s i l y shown to be e q u i v a l e n t t o A n, w i t h p e r A n = per(0*I+;I^). The determinants of a l l the m a t r i c e s mentioned above are r e a d i l y found but almost n o t h i n g can be s a i d about the permanent of any of them. 8 (c) The Permanent of A n. PerCA^) can be computed by hand without too much d i f f i c u l t y f o r n = 2, 3, 4, 5 to g i v e ; p e r ( A 2 ) = 0 . p e r ( A 3 ) = -3. per(A^) = 0 . per(A^) = -5. 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 p e r ( A n ) equals 0 f o r n even and equals -n f o r n odd. The former proves to be c o r r e c t . The l a t t e r i s d e s t r o y e d by the r e s u l t f o r n = 7: p e r ( A ? ) = - 3-5«7 = -105. T h i s r e s u l t and those f o r n = 9» 11» 13 were o b t a i n e d by use of the U n i v e r s i t y of B r i t i s h Columbia's IBM 70k0 computer. p e r ( A 9 ) = +34 = +81. p e r ( A n ) = 3»5»ll*4l = 6765. p e r ( A 1 3 ) = 11»13»1229 = 1757^7. These r e s u l t s which were a l s o communicated by P r o f e s s o r D.H. Lehmer of the Department of Mathematics, U n i v e r s i t y of Santa Barbara, C a l i f o r n i a , do not appear to p r e s e n t any simple p a t t e r n . As we s h a l l subsequently see, the permanent of A Q Is always an i n t e g e r and i s always d i v l s a b l e by n. In 2 p a r t i c u l a r i f n=p , where p i s a prime, then p e r ( A n ) i s h, d i v l s a b l e by p . By u s i n g any of a v a r i e t y of permanent 9 i n e q u a l i t i e s [7] we can show -Jn* 1 ̂  p e r ( A n ) ̂  JrP~ or e q u i v a l e n t l y t h a t - |det(A )|^per(A n) ^ |det(A n)| 2 2 ( s i n c e (det(A )) = n ) . F o r n even, per(A ) i s determined n n (=0) but f o r n odd the problem remains g e n e r a l l y u n r e s o l v e d . I n S e c t i o n IV of t h i s t h e s i s we i n v e s t i g a t e the case of n prime, n >3; the be s t r e s u l t o b t a i n e d , i s t h a t the permanent of A can be narrowed down to be one of a r e s t r i c t e d s e t of n i n t e g e r s . S i n c e p e r t A ^ = cr(t) )' k k-0 where a, denotes the number of permutations CTe S s . t . / icrti) = K(mod n ) , we can attempt to f i n d p e r ( A ) by c-i } n r e s o l v i n g the a l t e r n a t e number theory problem, of f i n d i n g the number of permutations CT i n the symmetric group S n» such t h a t ^ i O ~ ( i ) = k(mod n), f o r k=0,1,2,...,n-l. I t i s e a s i l y seen t h a t i f n i s a prime these two problems a r e e q u i v a l e n t . In the proof of the r e s u l t s t h at f o l l o w , almost no l i n e a r a l g e b r a i s used; the approach g e n e r a l l y b e i n g to f i n d the permanent of A^ by, s o l v i n g t h i s second problem. T h i s i n v o l v e s f o r the most p a r t a study of the symmetric group S^. 10 I I PBELIMINARY THEOREMS The f o l l o w i n g lemma shows t h a t p e r A n i s Independent o f the ch o i c e of the p r i m i t i v e n r o o t o f u n i t y . Lemma 2.1. I f = (0*^) i s nxn, where 6 Is a p r i m i t i v e n t h r o o t of u n i t y , and k i s a p o s i t i v e i n t e g e r such t h a t (k,n) = 1, then p e r ( 9 i j ) = p e r ( 0 k i j ) . P r o o f : Since (k,n) = 1, kj(mod n) = <T(j) where cr i s a permutation i n S . Thus p e r ( 0 k i J ) = P e r ( 0 i O " ( J ) ) . The m a t r i x (9 u ), however, i s j u s t the mat r i x (e J ) w i t h i t s columns permuted a c c o r d i n g to the permutation< r . S i n c e the permanent of a mat r i x i s i n v a r i a n t under permutations of rows o r columns, p e r ( 0 k i j ) = p e r ( © i j ) . Q.E.D. The permanent of AA i s o b v i o u s l y a polynomial i n 0: p e r A n = p e r f e 1 ^ ) ' Eft.10™ 9 i - , Hence < p e r ( 0 i ; ) ) = a Q + a 1 9 + . . . , + a e 1 1 " 1 , (1) where a^ i s the number of permutations 0" € S^ such t h a t ^ i o - ( i ) s j(mod n), (2) We are thus p r e s e n t e d w i t h an i n t e r e s t i n g problem i n number theory, which to the best of our knowledge, has not been s o l v e d . Not a l l of the c o e f f i c i e n t s i n (1) can be d i s t i n c t . More p r e c i s e l y , we have Theorem 2.2. I f (k,n) = 1, then i n the r e p r e s e n t a t i o n p e r A n = a Q + a 16 + . . . . + a n _ i e " » a i = ^ K m o d n ) ' f o r 1 = P r o o f : v i 1 k i i p e r ( 0 l c l ; ) ) = p e r ( ( 9 K ) 1 J ) ~k . , „k(n-l) = a Q + a 1 e + . . . . + e ; lei 1 i i By Lemma 2.1, per( 6 J) = per( 0 J ) , t h e r e f o r e Z ^ ® ! ® ^ = '* 2 n - l S i n c e 0, 0 , . . . , 0 are l i n e a r l y independent over the r e a l numbers, i ki(mod n) Q.E .D. C o r o l l a r y 2.3. I f n i s a prime, n > 2, then i n the r e p r e s e n t a t i o n n— l p e r A = a + a.0 + . . . . + a .0 , (1) n o 1 n - l a i = a 2 = * ' * ' = a n - l * Pr o o f : I f n i s prime, (k,n) = 1 f o r a l l l £ k 6 n - l . Thus hy Theorem 2.2, a^ = a^, f o r 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 between the a^ f o r l ^ i ^ n - 1 . The q u e s t i o n whether a Q can be r e l a t e d t o any of the other a^, i s answered i f n i s even i n the next Theorem. We f i r s t r e q u i r e the f o l l o w i n g lemma. Lemma 2.4. I f cr i s any permutation £ where n i s even, and j° i s the f u l l c y c l e permutation; j° = (1, 2, 3>....» n ) , then + n/2 (mod n ) . Pr o o f : Yl[(T/>)(!) = ] T i [ ( ( r ( i ) + l)(mod n)] s i n c e (<T/>)(i) = (CT(i) + l)(mod n ) . .'. , T i ( c r / ) ) ( i ) = ^ i c r ( i ) + £ \ (mod n) J^icr(i) + (n+1)n/2 (mod n) ^ i c r ( i ) + n/2 (mod n ) , s i n c e n i s even. Q.E.D. 13 T h e o r e m ^ . I f n i s even, & ± = a ( 1 + n / 2 ) m o d n f o r 1 = 0 , 1, , n - l . P r o o f : L e t k be any n a t u r a l number from 1 to n. Consider the s e t \ = { y & S n I ^ A ^ 1 ) = Mmod n ) J ; k = 0 , . . . , n - l . I f P = (1, 2, 3, • . • . , n) we have by the p r e v i o u s lemma J l ( ( T p ) ( i ) = 2 ^ ( 1 ) + V 2 (mod n) V c T e i=i = k + n/2 (mod n ) • Sin c e f o r c r,t £ S r w i t h cr^T* Of * TP Therefore J x ( k + n / 2 ) m o d J > | ^ | where ^ I denotes the number of elements i n X^. S i m i l a r l l y i f we c o n s i d e r c e X (k+n/2)mod n we o b t a i n '((k+n/2)+n/2)mod n i . e . , '(k+n/2)mod n " k(k+n/2)mod n The r e f o r e we have t h a t the number of permutations cr e S YI n t h a t g i v e ^ i c r ( i ) = k(mod n) i s equal to the number t h a t g i v e ^ l t ( l ) = k + n/2 (mod n ) . i . e . , & 1 - a ( i + n / 2 ) m o d n f o r i = 0 , . . . , n - l , Q . E . D . Observe t h a t k=0 14 Theorem 2.2 g i v e s the r e l a t i o n X. = X„ , 1 j 1 I jk(mod n)1 where (k,n) = 1. We would now l i k e to look a t the p a r i t y of the permutations i n X . + 3 . L e t X. and X. denote the s e t s of even and odd J J permutations i n X r e s p e c t i v e l y , w i t h IX+ = a + , IX where a* + a~ = a . J J J ^ The analogy to Theorem 2.2 with X. or X r e p l a c i n g « J X i s not g e n e r a l l y t r u e . For the case k = n - l we can s t a t e J the f o l l o w i n g . Theorem 2.6. (a) I f n i s odd, ( n - l ) / 2 even, or i f n and (n-2)/2 are both even, then + + - -a, = a 1 ( . K , , and a. = a,, , j=G,l,...,n. j j ( n - l ) m o d n' j J(n-l)mod n (b) I f n i s even, (n-2)/2 odd, or i f n and ( n - l ) / 2 are both odd, then a J = a o(n-l)mod n f ° r »1»• • • » n _ 1 • P r o o f ; L e t cr e S r be an a r b i t r a r y permutation and l e t y _ f 1 , 2 , 3 . . . . n " V ( n - l ) , ( n - 2 ) , , 1 , n u 6 ~ ^<r(l),<r(2), . . , 0-(n)y l v ( n - l ) , ( n - 2 ) , . n 1 » 2 , • • , n n-C7(l) ,n-a(2), . . ,n-cr( n) i . e . , ( C r y)(i) = n - CT(i). Thus ^ i * 0 ^ ) * 1 ) = ^ i ( n - c r ( i ) ) = ( n - l ) / ivr(i)(mod n ) , 15 i . e . , I f (T^X, then cry £ X 4 / .,, J . T h i s g i v e s a j j\n-l)mod n one-to-one mapping of X onto X., .. • (Since i f j j\n-1)mod n cry = tjT then ( T a t . ) I t i s r e a d i l y checked t h a t 2f i s an even permutation i f n i s odd, (n-l ) / 2 even, or i f n, (n-2)/2 are both even. S i m i l a r l y X i s an odd permutation i f n i s even, (n-2)/2 odd, or i f n and (n-l ) / 2 are both odd. F i n a l l y s i n c e the product of two even permutations i s even, the product of an odd and an even i s an odd permutation, e t c . , the r e s u l t i s proved. Q.E.D. Theorem 2.7. I f n i s even, (n-2)/2 odd, or i f n and (n-l ) / 2 are both odd, then X has an equal number of even and o odd permutations. P r o o f : Consider any cr n X Q w i t h cr even. As i n the p r e v i o u s theorem, i f then y _ / l . 2 , 3 , . . . , n " \ ( n - l ) , ( n - 2 ) , . . . , 1 , . •n n ^ T i ( c r y ) ( i ) == ( n - l ) ^ i O - ( i ) (mod n) = 0 , s i n c e /iC7Xi)(mod n) = 0 . (CTtf) £ X . S i n c e ^ under the c o n d i t i o n s of t h i s theorem i s an odd permutation, there i s thus a one-to-one mapping of the even permutations of X onto the odd permutations of X . o o Q.E.D. 16 Theorem 2.8. I f r j n , say r • n^ = n and then S P r o o f : i f R =(x|x ~= kr(mod n) (k,n)=l, l ^ k © i s an i n t e g e r . (a) L e t r„, r r = 1 be an ordered l i s t i n g of a l l the 1 2 m d i v i s o r s of n, w i t h r ^ > i = l , . . . , m - l . L e t = ( l ^ , 2 r ^ . . . , ( n ^ D ^ j where ^ • ^ = n, R2 = { l r2» 2V * * ' ' ( V 1 ) r 2 J n2 r 2 - n, Hm = { 1 » 2 » • • • > f 1 1 " 1 ! n * 1 = n » and d e f i n e B 1 = B ; R = R7 _ (R / / l R ) 2 2 2 1 I t Is e a s i l y seen t h a t a l l are d i s j o i n t , and t h a t = [ x | x = kr^wo</n),(k,n)=l, l ^ k ^ n "I j = 1,2,..,m (b) To show S = i s 8 1 1 i n t e g e r V" J = l,...,m we proceed by i n d u c t i o n as f o l l o w s . 17 r - 1 i r (1) S^ = J Q x= -1, an Integer ( 2 ) Assume t h a t a l l S^ are i n t e g e r s f o r i = l , . . . , k - l (3) To show S i s an i n t e g e r , c o n s i d e r "K-I k-i By d e f i n i t i o n = - IJ(R̂  fl \ ) • I f r ^ r ^ then fl£ f| R « by c o n s t r u c t i o n of R^ and R^. I f r]/i^T1 then R^ f l R± = 0, s i n c e say x £ R^ f) R^, L e t r k l be the L.C.M. of r ^ and r . ,', r, A / x and a l s o r, , / n k l / k i / S i n c e r i s h i g h e r i n the l i s t r , r _ , . . . , r k i 1 ^ n than r , t h i s i m p l i e s x 6 R^, which g i v e s a c o n t r a d i c t i o n , s i n c e R are d i s j o i n t . 0 We can now w r i t e S as f o l l o w s . k S^ = Z"QX - \ f ^ t ® X J where the summation over i , r—> i s f o r a l l 1 , s . t . RXC\ 4t = (-1) - J ~ \ i n t e g e r ) , s i n c e the Ŝ ^ are i n t e g e r s by the i n d u c t i o n h y p o t h e s i s . Q . E . D . 18 I I I SOME GENERAL RESULTS ON PER ^ . Theorem 3.1. I f n i s even, p e r A = 0 . * — n 1 n 1 P r o o f : P e r ( A n ) = a Q 0 ° + + . . . . + a n - 1 e " ( D = (v0 + V 2 e n / 2 ) + ( v 1 - < n / a + 1 ) « < n / 2 + 1 , ) + • • • • + ( ^ / ^ • v ^ - 1 ) - By Theorem 2.5 a, = a, t . f o r 1 = 0 , . . . . , n - l 1 (i+n/2) T h e r e f o r e Per(A ) = a (9° + 0 n / 2 ) + a . , ^ 1 + e< n/ 2 +l>) n o l + . i ^ 2 - 1 ' (n/2-1) But e k + e ( n / 2 + l £ ) = o* • e n / 2 • e k - s k • (-i)e k = 0 f o r any k. Thus the r e s u l t i s proved. Q.E.D. 19 Theorem 3.2, Per A ^ i s an i n t e g e r . P r o o f : I t i s e a s i l y seen t h a t we can w r i t e per A n = a o a ° + £ where = | x j x = k r ^ m o d n) (k,n)=l, 1-^k^n (3) and the summation / i s over a l l i , such t h a t r j n. (Note t h a t does not c o n t a i n n; hence a Q 0 term i n (3)«) Since by Theorem 2.2, a, = a,, . i f o r a l l i = l , . . . , n i ik(mc<fvO and f o r I f k ^ n , (k,n)=l, t h e r e f o r e per A = a + n o L**l But by Theorem 2 .8 J} Z>x} 0 i s an i n t e g e r . Therefore per A r i s an i n t e g e r . Theorem 3.3. Per A = O(mod n) "— n Q.E.D. P r o o f : I f n i s even the theorem i s o b v i o u s l y t r u e s i n c e per A = 0. n The theorem i s a l s o true i f n i s odd, but we are not y e t i n the p o s i t i o n to prove t h i s . I t w i l l f o l l o w from Theorem 4.2 t h a t n/a^ f o r i = 0,1,2,...,n-l. This f a c t t o g e t h e r w i t h Theorem 2.8 g i v e s the r e s u l t . Q.E.D. 20 1 yi 1 Theorem 3.4. L e t per A = a + a „e + . . . + a „e , — n o 1 n - l I f n i s an odd prime, then per A n = a Q - a ^ Pr o o f : By C o r o l l a r y 2.3 a1 = a 2 = . . . . = a n _ 1 # 1 2 n - l Theref o r e p e r A = a + a (6 + 6 + . . . . + 6 ) n o 1 = a Q + a 1 ( - l ) = a - a • o 1 Q.E.D. n - l Theorem 3.5. L e t per A^ = a Q + a^e + . . . . + a^ 0 , where n i s the square of a prime p. Then per A = a - a . n o p P r o o f : L e t Y he the s e t of r e s i d u e s mod n which are n r e l a t i v e l y prime t o n. Then by Theorem 2.2 a i " a i k ( m o d n)» f o r k & V 2 F o r n = p , the o n l y numbers l e s s than n not r e l a t i v e l y prime to n are p, 2p, • • . . , ( p - l ) p . I t f o l l o w s t h a t j p e r A„ = a_ + a„ J~0 k + a ^ ^ V 5 . n o \L-> -p'. Now I?1 - -u and 2 J ° J P = ~ 1* S u b t r a c t i n g , = °* Thus p e r A = a + a„(0) + a (-1) n o 1 P = an - a . Q.E.D. o p 21 IV PER IF n IS A PRIME > 3- The aim In t h i s s e c t i o n i s to show t h a t i f n prime, n > 3, then the permanent of A^ i s l i m i t e d to be one of a r e s t r i c t e d c l a s s of odd I n t e g e r s . Most of the p r e l i m i n a r y Theorems used here are s t a t e d and proved i n g r e a t e r g e n e r a l i t y than i s needed f o r the above r e s u l t . L e t cr denote an a r b i t r a r y permutation i n S n, and P the f u l l c y c l e permutation (1, 2, 3 ..e. f = '1, 2, 3, . i2 , 3, 4, . I t i s easy to ckeck t h a t D2 A» 2, 3* • 12, 3, k, • 2, 3, . \3. 5, . and i n g e n e r a l t h a t (3) D k where / ( i ) =(k+i)mod n. I f ft , 2 , 3 CT =1 IffTCrt , TO , CTC3) . > n) n> 1, 2, 3» • • • » n 2, 3» »̂ • • • » 1J n • • » n • • t Pri J • • » n 22 then 1 , 2 , 3 , . . . . . n k0?i), OTP), (TO), . . . . , or*), l , 2 , 3 , « » » , n N \ ^ ) , O D ) , , on;/ and i n g e n e r a l where / ( T U ) s cr[(i+k)(mod n)J . By g i v i n g k, values from 1 to n, we o b t a i n the s e t of n permutations; pa-fpV, • • • . / c r (with / c r = c r ) , ( 5 ) which are a l l o b v i o u s l y d i s t i n c t ( j u s t l o o k i n g a t the image of 1 under each permutation shows them a l l to be d i f f e r e n t ) • S i m i l a r l y the permutations obtained by m u l t i p l y i n g on the r i g h t by powers of p , are of the g e n e r a l form k J 1 » 2 • 3 ' » • • • » n \ ; m)(o9(p^(^3h . . . • where ( G " / ) ( i ) = [p~(i) + k j (mod n ) . T h i s a g a i n g i v e s us n d i s t i n c t permutations Q-p,(Tp\ . . . ,cr/ (with 07?"= cr s i n c e f= 1) (6) which are not 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 f a c t t h a t £ i t y f i r/)(l) = [^iCTU)] (mod n) f o r n odd C > | ( . ' = 1 and f o r a l l k and 0, i s proved i n the f o l l o w i n g two theorems. A l l t h i s l e a d s to the f a c t , t h a t w i t h any cr e s n but cr I G , where G i s a c e r t a i n subgroup of S , n* n n' 23 we can a s s o c i a t e a b l o c k of n d i s t i n c t permutations ( v i z . the permutations ( pb~/f) where k9t = 1,2,..,,n) such t h a t i f fl p * ~ cr and X belong to such a b l o c k , then ) l(T(i) = A 1 ^ 1 ) {mod n) 7=1 L i e . J Theorem ^.1. I f cr e 3^ and Z3 = (l,2,...,n) a f u l l c y c l e permutation, then 2 i(«rf)(i) = i ( p V ) ( i ) (mod n ) , k = 1,2,...,n. P r o o f : ^ i ( ( r ^ ) ( i ) = ^i([(T(i) + kj(mod n)) - <r[(l + k) (mod n)j =J " 2 i C r ( i ) + ^A^ 1 - ( J 1 ^ 1 ) " k J i ) ] (mod n) ^ i ( m o d n) = 2k = 2k(n+1)n/2 (mod n) = O(mod n ) . There f o r e Xi(crp k)(l) = ^ A " ) ( i ) (mod n ) • Q.E.D. 2k Theorem k.Z. I f c r e s and J* = (1,2,...,n) a f u l l c y c l e ____________________ n permutation e S n then (a) i f n odd Yj-OTj^) ( i ) s ]__ifr"(i) (mod n) f o r any k , t in 1(0"/^) ( i ) = Z^iGli) (mod n ) f o r k e v e n i ^ i « r p k ) ( i ) = Z]lo1i) l n / 2 (mod n) k odd. CM i-l P r o o f : J i ( ( T / > k ) ( i ) = Zj.[((T(i) + k) mod n ] mod n = ^JL(T(i)mod n + k])jL mod n = ^ \ c r ( l ) m o d n + k(n+l)n/2 mod n . t'-i (a) I f n Is odd, k(n+l)/2 i s an i n t e g e r . T h e r e f o r e (1) = ])_icr(i) (mod n) f o r a l l k, C--I ( « l (b) I f n i s even, k(n+l)n/2 i s an i n t e g e r , even, 7_sH(r/:)(i) = )_i<ni)(mod n), i f k n and 2jLCT(i)*n/2 mod n i f k odd. Q.E.D. C o r o l l a r y k.3» I f n 6dd, then ^ i ( p k T p 1 ) ( i ) = f j . * ( l ) mod n f o r a l l k, 1. P r o o f : (Prom p r e v i o u s two theorems). 25 F o r any b, O ^ b ^-n-1, and m fe Y , we can now d e f i n e a n f u n c t i o n T * ^ T ( i ) = b + ( i - l ) m (mod n ) , i = 1,2,...,n. (a) where l * T ( i ) * n . i s a permutation of {l,2,...,n} s i n c e X"U) = l ~ ( j ) i m p l i e s im = jm(mod n ) , which i n t u r n i m p l i e s i = j(mod n) s i n c e m e Y n« Moreover, d i s t i n c t values of b and m g i v e r i s e to d i s t i n c t permutations. For, suppose T ( i ) + U-Da^ (mod n) and C T ( i ) = b + ( i - l ) m (mod n ) . 2 2 Then t = 0" i m p l i e s t h a t b = T ( l ) =CT(1) = b g and b 1 + m = T(2) = ( b 2 + m 2) s i n c e T(2) = C T(2). We d e f i n e G to be the s e t of a l l permutations T t h a t are n of the form ( a ) . Theorem 4.4. G i s a subgroup of S c o n t a i n i n g n.0(n) ______________ n n v elements, where ^(n) i s the E u l e r F u n c t i o n . P r o o f : From the above d i s c u s s i o n the permutation X i n (a) can be s p e c i f i e d In n«|6(n) ways, corres p o n d i n g to n choices f o r b and 0(n) c h o i c e s f o r m. To show t h a t G i s a group i t i s necessary o n l y to -i show t h a t o ~ , ^ g G N Implies CT7J e G . Suppose 0~(i) = b 1 + (i-Dm^ (mod n) and T U ) s b 2 + ( i - l ) m 2 (mod n ) . Since (m 2,n) = 1, there e x i s t s m^ such t h a t m 2 m 3 S i( m°d . 26 I t i s r e a d i l y checked t h a t f ' ( i ) = ( b 3 + ( i - l ) m 3 ) ( m o d n ) , 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 and (n , 3 ) = 1, then ^ i ( T ( i ) = O(mod n) f o r a l l cr 6 G R • P r o o f : L e t CT(i) =(b + (I-l)mXmod n). Then f\v(l) = b | j L + 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 . C o r o l l a r y 4.6. I f n i s an odd prime, n ^ 3 , then ^ i O ~ ( i ) s 0 (mod n) f o r a l l (T £ G . c--i n Thus i n case n i s a prime, n > 3 we have o b t a i n e d a subgroup of S n each element <r of which has the p r o p e r t y Jj.<r(i) s O(mod n ) . C--1 There may however be o t h e r f e w i t h t h i s p r o p e r t y . 27 We now proceed to show t h a t the remaining p o r t i o n of 2 S c o n s i s t s of d i s j o i n t s e t s K, each c o n t a i n i n g n n j elements, each of which g i v e r i s e to the same r e s i d u e c l a s s . Theorem 4 . 7 . L e t n be a prime > 3; and l e t H = S„ - G . ————————J- n n n Then H i s the uni o n of d i s j o i n t complexes n K,» j = l , . . . , r such t h a t J 2 (I) each K co n t a i n s n elements, which a l l have the same p a r i t y , and (II) f o r each j there e x i s t s c^ such t h a t r> ) i(T(i) = c 4(mod n) f o r a l l cr e K * w y j Pr o o f ; L e t cr e H ; and l e t P = (1 , 2 , 3 ,... ,n) . n Define K„. = {P^P** i,m = l , 2 , . . . , n ] . The n permutations /><T/) are d i s t i n c t , f o r suppose p\pm> = />V"*; then, 0 1 i ) = f A V ^ ' % ) f o r i = 1 ,2 ,...,n. S p e c i f i c a l l y , f o r each i , CT(i) ~ (T( 1+2^1^ + m 2 ~ m l ^ m o d n * o r ° " ( i + ^ 2 " A ) s < r ( i ) +.1*^111 (mod n ) . Si n c e n i s prime, i f i > 2 - 1 t Q3 there e x i s t s k such t h a t ( 2 - 2 ) k s 1 (mod n ) . 2 1 Then (T(i+1) = CT(i + k f i - i ^ ) . = 0~(i) + k(m -m ) (mod n) . 1 2 T h i s means t h a t cr e G q , c o n t r a d i c t i n g our assumption t h a t ere H . Th e r e f o r e 1 - 1 . = 0 ; i t f o l l o w s from (7) n 2 1 28 2 t h a t m 1 - m 2 = 0 a l s o . Thus K r has n d i s t i n c t elements, By C o r o l l a r y 4.3 we have ^ i C P V j ^ M i ) =Li(r(i) (mod n) 1-1 i=i f o r a l l k , X = l , 2 , . . . , n . Thus f o r any p a r t i c u l a r complex K T , /_i<r(i) (mod n) g i v e s the same r e s i d u e f o r a l l permutations 0" e K^. We have n n wV(r7ti n o-/ . We now show t h a t f o r two complexes K^, K r, e i t h e r K R 0 K r = ^ or KT = K r . I f K ( r 0 then pV/> m'= J^TP** f o r some J ^ , m1, i 2» m 2 # I t f o l l o w s t h a t Cj = J>^rjr^ = J>l'XPM>9 where 1 = i - i (mod n ) , m = m - m (mod n ) , and 3 2 1 3 2 1 1 £ Ijt™^ Thus CT e K r, and j 5 CrP me K T f o r a l l m, 1 ̂  i,m £ n. Ther e f o r e £ 2 Si n c e IT and K „ each have n elements, T h e r e f o r e complexes are 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 permutations i n a complex have the same p a r i t y ; we note t h a t f o r n odd, P = ( 1 , 2,..., n) = ( 1 , 2 ) ( l , 3 ) , . . . , ( l , n ) i s a product of an even number of t r a n s p o s i t i o n s . Also,, s i n c e a product of even permutations i s even and the product of an even and an odd permutation i s odd, t h e r e f o r e 0" e K i s even or odd a c c o r d i n g i f t i s even or odd. 2 Thus the n elements i n the complex have the same p a r i t y . Q.E.D. Note: I f r i s the number of d i s j o i n t K Q - ^ , S Q = G N U K X U . . . , t i K r , C o n s i d e r i n g the number of elements i n each of these s e t s , we get i 2 n; = n ( n - l ) + r n (n prime) . Thus ( n - l ) I = n - 1 + r n , or ( n - l ) i = - l(mod n) . This i s j u s t Wilson's Theorem! Theorem 4.8. I f n i s a prime, n > 3» and i f a^. i s the number of permutations i n S such t h a t n £]icr(i) = k(mod n ) , then (I) n ( n - l ) d i v i d e s a Q , p and (II) n d i v i d e s a^ i f k = 1,2,...,n-l, 30 P r o o f : By Theorem 4.7, S = G UK., . , . . U K ; (8) n n 1 § and i f JjLcr(i) = k 4 o , then cr e some K; n I t f o l l o w s t h a t those o- such t h a t ^jLCT(i) = k(mod n) completely occupy a c e r t a i n number, r ? o f K..5, S i n c e k j 2 2 each K„ has n elements, a = r, «n ; t h i s proves ( I I ) . j k k By C o r o l l a r y ^ 3 » = & 2 = »•••*» = a n ±* a] 2 Hence, a l l r ^ re equal, l ^ k ^ n - 1 ; say r ^ = r . Then = r n Now a Q + a 1 + ».«.»* + ^ - 1 = n • • 2 I T h e r e f o r e a + ( n - l ) r n = n! > o a o = n ( n - l ) [(n-2)! - r n ] ; and (I) i s proved. Q.E.D. Theorem 4 . 9 . F o r n a prime, n > 3 , there e x i s t s non-negative i n t e g e r s y and z such t h a t p e r A = n [ ( n - l ) + y ( n - l ) n - zn]. n P r o o f : From Theorem 3 . 4 , p e r A n = a Q - Now a i s the number of CT e. s_ such t h a t / i c r ( i ) = 0 . o n ft Such CP occupy G n and a c e r t a i n number of the K^*s i n the decomposition ( 8 ) . 31 2 Thus a Q = n ( n - l ) + wn . S i n c e n - l d i v i d e s a , i t a l s o d i v i d e s w. o 2 T h e r e f o r e a Q = n ( n - l ) + y ( n - l ) n , f o r some non-negative i n t e g e r y. Si n c e n d i v i d e s a, , 2 t h e r e f o r e a, = zn 1 f o r some non-negative i n t e g e r z. 2 2 T h e r e f o r e p e r A = n ( n - l ) + y ( n - l ) n - zn n n [ ( n - l ) + y ( n - l ) - z ] . Q.E.D. Theorem 4.10. F o r n a prime > 3» there e x i s t s a non-negative I n t e g e r y such that p e r A„ = n 2 - n(n-2)! + n 3 y , n P r o o f : From the d i s c u s s i o n i n Theorem 4.9, a Q = n ( n - l ) + y n 2 ( n - l ) , and a^ = z n 2 , k = 1,2,....,n-l r,-l S i n c e n! = J^^t i-0 I 2 2 n! = n ( n - l ) + yn ( n - l ) + ( n - l ) z n , Hence zn = (n-2)i - 1 - yn, •'• p e r A n = a o - a i 2 I = n ( n - l ) + yn ( n - l ) + (yn + 1 - ( n - 2 ) i ) n 2 3 I = n + n y - n(n-2)J < Q.E.D. Remark: Computed values f o r the x and y above w i l l be i n d i c a t e d i n S e c t i o n VI. 3 2 T h i s r e s u l t does not answer the q u e s t i o n as to v a l u e of A , even f o r n a prime, but i t does r e s t r i c t n c o n s i d e r a b l y the p o s s i b l e v a l u e s . We note t h a t A^/fh i s a u n i t a r y m a t r i x . By a r e s u l t of Marcus and Newman f_ 7J p e p A / m U l , n ' which i m p l i e s | per A n | ^ n . Thus i f n i s a prime, then per A n i s r e s t r i c t e d 2 3 I to the values of n + n^y - n ( n - 2 ) ; t h a t l i e between -nn and + n 1 1, where y i s a p o s i t i v e i n t e g e r . 33 V THE CASE OF n = p , WHERE p IS A PRIME In t h i s s e c t i o n we s h a l l o b t a i n some r e s u l t s f o r the square of a prime somewhat s i m i l a r to those o b t a i n e d i n 2 S e c t i o n IV f o r a prime. L e t n=p , where p i s a prime. The group G , which was u s e f u l i n S e c t i o n IV i s not l a r g e n enough f o r our purposes here. We s h a l l form a l a r g e r group F n c o n s i s t i n g of permutations of the f o l l o w i n g type. L e t cr be a permutation of {l,2,...,p}. D e f i n e : 2 <T(i + cp) =cr(i) + (a1 + cs)p (mod p ) f o r i = 1,2,...,p and c = 0 , l , . . . , p - l ; where {a^} and s are constants such t h a t O ^ - a ^ p - l 7 l ^ s We show t h a t each such f u n c t i o n <x i s indeed a permutation of { l , 2 , • • . , p 2 J . Suppose <T(J) =0"(k), where, say, j = i 1 + c p and k = ± 2 + c 2 p . Then C f U J + (a, + c s ) p = T ( i ) + (a, + c s ) p (mod p 2 ) , 1 1 1 2 U 2 and <T(l t) = ( T ( i 2 ) mod p . By the d e f i n i t i o n of (f, i t f o l l o w s that i 1 = i 2 , = a ^ , and, from (21), c^s = c 2 s (mod p ) . Hence c = c , and f i n a l l y j = k. Thus CT( j) = <T(k) i m p l i e s t h a t j = k, so t h a t 0" i s a permutation. 34 Theorem 5 . 1 . The s e t F n of permutations i n S n of the form (20) form a subgroup of S f t of order p p • p j • ( p - 1 ) . Every permutation X i n S n w i t h the p r o p e r t y T(i+p) == T ( i ) + kp (mod p 2 ) , f o r a f i x e d k, l - S k ^ p - l , i s a member of F . n Pr o o f ; Suppose CT(i+cp) =cT(i) + (a-.+cs)p (mod p 2 ) . (Z0) Then <r~1 Is g i v e n by 0-" 1(i+cp) =cf1{l) + ( b j + c t j p (mod p 2 ) , where O ^ b ^ p - 1 , t i s such t h a t l ^ t ^ p - l , s t = 1 (mod p ) , and l s b ^ p - 1 , b 1=-a it(mod p ) . For, Crcr~ 1(i+cp) scr^CXU) + (aj+csjp] (mod n) = ( T C T " 1 ( i ) + [b_ + ( a j + c s j t j p (mod n) = i + [-a^t + + c]p (mod n) = i + cp (mod n ) . Thus i f CTe F , c r " 1 e F . n n S i m i l a r l y , i f JJ i s d e f i n e d by ^ ( i + c p ) = JJ(1) + (o^+ciOp (mod n ) . then ay>(i+cp) = ^[cr(i) + ( a ^ c s j p ) (mod ri) = CTyL/(i) + \x± + ( a ^ c s j u j p (mod n) = CJ/;(i) + [o^ + a^u + csu]p (mod n) = fjJil) + [X + cw]p (mod n ) , where 0 —X, S p - 1 , and l ^ w ^ p - l . Hence Q"E e F , and F, I n n i s a group. 35 To o b t a i n the number of elements i n F n , we note t h a t there are p! ways of choosing CT; p ways of choosing each a i ? i = l , 2 , . . . , p ; and p-1 ways of choosing s; y i e l d i n g p l * P P • (p-1) ways of choosing CT. These c h o i c e s are d i s t i n c t ; f o r , suppose CT(i+c P) = CT(i) + ( a ^ c s ) ? (mod p 2 ) and y j(i+cp) = JJ(1) + ( b ^ c t j p (mod p 2 ) d e f i n e two members T and T of F^. I f CT $p •> there e x i s t s j , l < j ^ p , such t h a t C f U ) t y O(j); then CT(j) t I f ( f =yU, a± £ D± f o r some i , then CT(i) t . I f (f=yL/, a l l = b 1 ? and s ^ t , then Q~(i+p) ^y ; ( i + p ) . Thus there are p l • p P • (p-1) d i s t i n c t elements i n F • n Now suppose t h a t t i s a member of S n such t h a t T ( i + p ) = T ( i ) + kp (mod p 2 ) , l < k < p - l , f o r a l l i = l , . . . , n . T h e n T ( i ) can be w r i t t e n TT(i) = d i + a j p , 1=1,2,...,p, where l ^ d 1 < p , and O S a ^ p - 1 . We show f i r s t t h a t { d ^ i s a permutation of {l,2,...,p}. Choose r such t h a t rk = l(mod p ) . I f dj^ = d^ f o r U j < p , then t [ i + U j - a ^ r p ] = X ( i ) + ( a ^ - a ^ r k p (mod n) = d i + a l P + ( a ^ - a ^ p (mod n) = d + a p (mod n) J j s T U ) (mod n). 36 S i n c e T i s a permutation, i + ( a ^ - a ^ r p = j (mod n ) , which i m p l i e s i = j (mod p ) , and f i n a l l y t h a t i = j . We can now w r i t e &̂  = T ( i ) , where t e S p; and t ( i ) = T ( i ) + & i p . S i n c e T ( i + p ) = T ( i ) + kp, we have T(I+cp) = t ( l ) + (a^+ckjp. T i s t h e r e f o r e a member of F . This completes the p r o o f n of Theorem 5.1. Q.E.D. n We next examine the r e s i d u e c l a s s of ^ } . C r ( i ) f o r CT 6 F N . CM Theorem 5.2. 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 the permutation of l,2,...,p, g i v e n i n (3d). The number of permutations CT In F such t h a t n n ^ i C T ( i ) = jp (mod n ) , O ^ j ^ p - I , i s equal to I'M p p • (p-1) times the number of permutations CT £ S p such t h a t £i<?(i) = j (mod p ) . I'M J i Q - ( i ) = £ i [ 3 u ) + a i p ) + i j i + p ) + ( a i + s ) p 3 + £(i+2p) [<f(i) + ( a j+2s)p] + . . . . + £ j i + (P-Dp] [(T(i) + {a± + ( p - l ) s } p l P r o o f : t'M ? I'M 777 37 F = p ^ i < T U ) + P Yj- &IP + Yj- [ S + 2 S + • • • + ( P - l ) J P v IM i-l CM + y^iCT(i) [p + 2p + . . ; + (p-l)p] = p y\<TU) + p(p+l)/2[s + 2s + . . . + ( p - l ) s ] p + p(p+l)/2[p + 2p + . . . + ( p - l ) p ] - P ^ f f l i ) (mod n ) . The l a t t e r statement i n the theorem f o l l o w s immediately from Theorem 5«1« Q.E.D. As i n the 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 the s e t = [i )Vi ) m | i,m = 0 , l , . . . , n - l } . each 0~ e S - F , e n n (see page 27). I I 2 Theorem 5.3. I f Q~ e S n - F R , then IK^I = n , Fo r a l l elements T £ K, ^ i T ( i ) = / J - O l i ) (mod n). C M C-. ) 2 P r o o f : As J,n run through 0 , l , . . . , n - l , n permutations P^Q~P a r e produced. I t i s r e q u i r e d to show t h a t they are d i f f e r e n t . I t i s s u f f i c i e n t to show t h a t P V P m = C r i m p l i e s l=m = 0. I f fiVP" = CT, then CT(l+i) + m = CT(i) (mod n ) . F i r s t , j = 0 i m p l i e s m=0. I f ( i , n ) = l , choose r so th a t ri=l(mod n ) • Then 38 <X(i + r i ) = c r ( i ) - r m (mod n ) , or (T(i + 1) sCT(l) - r m (mod n ) . 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 remaining a l t e r n a t i v e f o r 5 i s $ = cp, l ^ c ^ p - 1 . In t h i s event CT(I + p i ) = (T(i + cp 2) = CT(i) (mod n ) , and hence ( T ( i ) = <T(1) - pm (mod n ) . I t f o l l o w s that m = 0 (mod p ) . Moreover m ^ 0 (mod n ) , s i n c e , i n th a t case, GT(i + cp) =CT(i) (mod n ) , which i s imp o s s i b l e . Thus m = kp, l ^ k ^ p - 1 . By Theorem 5 . 1 , CT £ F n , a c o n t r a d i c t i o 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 ) C T ( i + i ) - CT(i+i) + ™ . t = | C M C M = ^ j K T U ) - i n ( n + l ) / 2 + m n(n+l)/2 ' M Tt Q.E.D. Theorem 5 . 4 . For<T",T. j. FN, e i t h e r = K r , or K̂ O = (J). 39 P r o o f : I f U e K fl K r, then 1/ = p V p m ' = f^Xp^i which i m p l i e s X - P' xQ~ftm'~m'', and hence t 6 K r. I t f o l l o w s t h a t K-w S K^. Si n c e K I = K Thus S n i s p a r t i t i o n e d as f o l l o w s ; where the number of elements i n the v a r i o u s subsets are shown i n b r a c k e t s . We are now i n a p o s i t i o n to get some i n f o r m a t i o n on p e r A . R e c a l l t h a t n n - l p e r ^ = a Q + a 1 9 + . . . . + a ^ e where a. i s the number of CT e S such t h a t j n ^ i c r ( i ) = j (mod n ) . In f a c t , f o r n=p 2, by Theorem 3 . 5 , per A = a - a „ , n o p By Theorem 5»2, the number of Q**s i n F f o r which n / ~ ] i c r ( l ) = 0 (mod n) i s p p • (p-1) times the number 40 of (f 6 S such that ^ i c f ( i ) = o (mod p ) . By Theorem P l > l 2 the l a t t e r i s p ( p - l ) + k^p f o r some i n t e g e r k^. There may, i n a d d i t i o n be CT ̂  F such t h a t / 10~(1) = 0. 2 4 The number of these w i l l be a m u l t i p l e k of n =p , by Theorems 5 . 3 and 5.4. Thus % = P P + 1 ( P - 1 ) 2 + k l P p + 2 ( p - l ) + k 2 ? \ S i m i l a r l y , each CT i n F such t h a t / iCr(l) = p n ^rp p corresponds t o a cr i n S such t h a t ^ i C T ( l ) = 1 (mod p ) . C-l The number of the l a t t e r i s k^p , by Theorem 4 Thus the number of CT £ F n such t h a t ^ i C T ( i ) = p (mod n) i s k ^ p p + 2 ( p - l ) : Outside F n there w i l l be a m u l t i p l e 4 k^ of p f u r t h e r permutations of t h i s type. We have then a p = k 3 p p + 2 ( p - l ) = k ^ p S and as a r e s u l t p e r A n = p P + 1 ( p - l ) 2 + ( k r k 3 ) p p + 2 ( p - l ) + ( k 2 - k ^ ) p \ S e t t i n g k 1 + k^ + 1 = k, and k 2 + k^ - JL> we have 2 Theorem 5«5» For n=p , p^3» p e r A = P P + 1 ( P - D (kp-1) + .2p\ n where k,l are p o s i t i v e i n t e g e r s ; In p a r t i c u l a r 4 per A = 0 (mod p ). n 41 VI COMPUTER RESULTS (a) Computer Programme, Per was c a l c u l a t e d f o r the odd primes, n = 5 , 7 , 11, 13, on an IBM 7040 computer. T h i s was done u s i n g the f o l l o w i n g w e l l known formula due to Ryser L e t B he a n-square m a t r i x and l e t B r denote a matri x obtained from B by r e p l a c i n g some r columns of B by z e r o s . L e t S(X) be the product of the row sums of the ma t r i x X. Then per B = S(B) - ZjSfB^ + & ( B 2 } " • • • ̂ 1 ) n" 1& ( B n. 1 ) where J~*S(Br) denotes the sum over a l l (£) replacements of the r columns by columns of z e r o s . I f B = A r , where n i s odd, and i f A ^ ^ j denotes the mat r i x o b t a i n e d by r e p l a c i n g r columns of A by columns of n z e r o s , then i t i s e a s i l y checked t h a t ( l / r ) S ( A , ) = ( l / ( n - r ) ) S U , ) . n(r) n(n-r) I f S / ( A ) denotes the product of the f i r s t n - l r 0 M su»s o f A , ̂ t L s i n c e «•» ̂  ™ « A o o n s i S t S ot n ( r ) n l ' s o n l y , we have 8(A.(r)» " r ' S'(W- 42 Thus we can r e w r i t e (?) as p e r A n = - l I > ' < A n ( 1 ) ) • z£*'l^m) - 3Es'(A n ( 3 )) . . . . + ( - l ) n " 1 ( n - l ) ^ S ( A n ( n . 1 ) ) . T h e r e f o r e p e r ^ = (n - 2)JV ( A n ( 1 ) ) - (n - \ { z ) + ^ )/2 . ( n " 6 ) E S , A n ( 3 ) + • • • + t " 1 > ° ' 1 E 8 ' i - ( » - i : Thus to e v a l u a t e p e r A i f n i s odd, i t i s o n l y necessary to n compute the product of the f i r s t n - l row sums of a l l p o s s i b l e m a t r i c e s f o r r = 1,. •., ( n - l ) / 2 . That i s f o r ( ? ) + ( ? ) + • • • + (<n-?)/ 2) m a t r l 6 e S l n a 1 1 - The programme used to o b t a i n values f o r p e r A , n f o r n = 5» 7» U t and 13, was based on the e q u a t i o n (10) i n the above paragraph. I t c o n s i s t e d e s s e n t i a l l y of a combination generator, which generated a l l p o s s i b l e combinations of n t h i n g s r a t a time, f o r r = 1, 2 , . . . , ( k - l ) / 2 . From these the m a t r i c e s A , , were formed f o r each v a l u e of r , and / S A . n ( r ) n ( r ) e v a l u a t e d . By e q u a t i o n (10), per was thus o b t a i n e d . T h i s programme was o r i g i n a l l y designed to compute and p r i n t out S A f o r a l l r , i n a p a r t i c u l a r order; n ( r ) w i t h the hope of o b s e r v i n g p a t t e r n s which would a l l o w a c o n j e c t u r e f o r per A n to be obtained from equation (10). 43 Due to the e x c e s s i v e checking i n v o l v e d i n the o r d e r i n g of the combinations, t h i s programme proved to be v e r y i n e f f i c i e n t i f used to c a l c u l a t e p e r An f o r n > 13. F o r n = 17, no r e s u l t c o u l d be o b t a i n e d i n two hours computing time. Whereas, f o r n = 5 . 7, 11, 13, per A was computed n i n l e s s than f i v e minutes. With an e f f i c i e n t combination g e n e r a t o r , A^„ and A _ should be r e a d i l y o b t a i n e d by the 17 19 IBM 7040. (b) R e s u l t s . For n an odd prime, n >3 we have the f o l l o w i n g computer r e s u l t s . per = - 5 p e r A ? = - 3 • 5 • 7 p e r A n = 3 • 5 • 11 • 41 per A 1 3 = 11 • 13 • 1229 . Theorem 4 .9 g i v e s Per A n = n [ ( n - l ) + y ( n - l ) n - zn] , 2 I 3 o r (Theorem 4.10) Per A = n - n ( n - 2 ) i + n y. n Thus f o r n = 5 , 7, 11, and 13, we can l i s t the values of y and z. n y z 5 0 1 7 2 15 11 3004 29985 13 36274 2834249 C ' COMPUTING PFRMANENT OF A ( N ) RY RYSFRS MFTHOD. j c c GOMPI FX XI «TH( 1 7 I »PROn« R^l IM.THFTAt 1 7 . 1 7 1 .FN ' INTEGER SP ( 17 ) , PER -' j . DIMENSION K O L ( 1 4 3 1 . 8 ) DT MFNSTON MOI (17) ' i DIMENSION M0T( 17 ) '' • : PRINT 1 •• F0RMAT(34H ,COI UMNS , PRODUCT O.F R.O.W.S11MS ' . ) • • • ' 1 79 GO TO 112 • . ' PER=0• ' SP(1)=1 m SP ( 2 ) = ( N - l ) /2 •' , DO 113 I = 1 » MO PFR-PFR+ ( N-?# T ) *N*.SP ( T ) * ( -1 ) T - 112 . . 2 W R I T F ( 6 » 111 ) PER READ(5.2)N FORMAT ( T ? ) • '• '•' *• ' • • 19 PRI N T 19,N FORMAT ( I X » 12 ) • - • ' ' ' •-. • MO= (N-i)/? • 38 M = 3 GO TO 51 .. . M = M+1 51 M1=M-1 • • • . M2-M-2 • " IF(M.GT.MO)'GO TO 79 • •. T=N ; • • • X 1 = C M P L X ( 0 . , 2 . * 3 . 1 4 1 5 9 2 7 / T ) NT = N-1 40 DO 40 I =1»NI • E N = F L O A T ( I ) TH ( I ) =CEXP ( EN*X1 ) ... ' "•• • TH(N) = ( 1 . 0 , 0 . 0 ) • - DO 10 1=1,N DO 43 JA=1»N • ' • 44 KA=I*JA . . I F ( K A . L E . N ) GO TO 43 KA=KA-N 43 GO TO 44 - THETA( I >JA)=TH(KA) ' • i J U1 ffl >sj 0 3 (£1 LU • J O O II II •J. „ o 4 — UJ O CL ixl H H (<• II II O O z z c i + o - H o; * II I—I II l-H I—I »" •-H in — II II II o ~ o; o o o z z z co Q ^ CO iTl * _l r H O II ^ II *—1 11 I - r H <—> cr CO — r -_ l o o c Q 2 C i—• iTl II m - H O ~:|- + r - ^ O O ll S U V m o II n! - I _ l o II I II r H O 32 o; o i4 v r H O II ^ i-< || CO r - l m — _J O O Q s: CO m O r H II ii a _ i s: r-ro 9* r H V II — H _ | o co V O L L Q CM CO CO o O i -H O V o • co a UJ O ' • r- i h- ~) + O L L II o co f\J CO + CL . II a co B • (NJ r- o cn co N to m ro 12 J i >io 9 8 )7 6 5 U 3 • . . 36 KOL ( K , I ) = KOL( K» I 1 ), '  ' . ' - KOL ( K » M ) = K M ' GO TO 62 ' 300 IF<MOL(M).LE.1) GO TO 24 GO TO 6 • C 200 MOT(1 ) = 1 • DO 93 I= 2 » M 93 MOT(I)=MOT(1-1)+MOL(I-1) 55 PROD = ( 1 • 0 » 0 • 0 ) / FLOAT. (M ) ' DO 16 I=1 »N RSUM= ( 0.0»0..0) - DO 17 LA=1»M J. JM.O_T LLA ) • 17 RSUM=RSUM+THETA(I» JA) 16 PR0D=PRODORSUM SP(M)=SP(M)+TNT( .5+RFAI (PROD) ) • WRITE(6»52) PROD, (MOT('LA) •LA=1»M)' 52 FORMAT ( 2F10. 2 »4X, 20 I 3 ) •. ' ' I F ( K .FO . 1 ) GO TO 11 .201 K = K+1 '. •• ' <'1 = K-1 ' ' • • IF(K.GT.NO) GO TO 39 GO TO ' 300 • '. • . 39 WRITEC6-, 111 ) SP(M) •• • • m FORMAT(60X,110) GO TO 38 24 L - L + i • ML1 = M-L+1 ' • '" ML=M-L ' ' ' ' DO 2 5 I = 1»M .25 K 0 L ( K , I ) = M O L ( I ) KOL( K , ML ') = MOL ( ML ) + 1 • I F I L . E Q . 2 ) GO TO 41 DO 26 I=ML1,M1 26 KOL(K »I )=1 41 KOL< K,M1)=1 KOL(K,M)=0 ' DO 30 I=1» M1 30 KOL(K»M)=KOL(K»M)+KOL(K»I) £ S 9 L 8 6 OL TT A i Nivyo -n II v O C o - _ i r H O ii \i r- " II w C M O o o o Q 2 U CNJ •4- X L U < O U Z L U r H CM L L fcfl 44 BIBLIOGRAPHY 1 A.C. A i t k e n , Determinants and M a t r i c e s , 4 ed., Edinburgh, 1946. 2 G. P o l y a , Aufgabe 424, Arch. Math. Phys. ( 3 ) , 20 (1913), P. 271. 3 Marvin Marcus and Hendryk Mine, On the R e l a t i o n Between the Determinant and the Permanent. I l l i n o i s J . Math., v o l 5 (1961), pp. 376-381. 4 Marvin Marcus and Hendryk Mine, Permanents, Amer. Math. Monthly, v o l 72 (1965), pp. 577-591. 5 H.J. Ryser, C o m b i n a t o r i a l Mathematics, Carus Math. Monograph no. 14, 1963. 6 H.L. Hamburger, and M.E. Grimshaw, L i n e a r Transformations In n-Dimensional V e c t o r Space. Cambridge u n i v e r s i t y , London (1951). 7 Marvin Marcus and M o r r i s Newman, I n e q u a l i t i e s f o r the Permanent F u n c t i o n . Annals of Mathematics, v o l 75 no. 1, January 1962, p. 55.

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 6 11
France 3 0
United States 1 0
City Views Downloads
Beijing 6 0
Unknown 3 0
Ashburn 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}

Share

Share to:

Comment

Related Items