THE PERMANENT FUNCTION by PRANK COLIN MAY B.A,, University of B r i t i s h Columbia, 1959 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Arts i n the Department of Mathematics ¥e accept th i s thesis as conforming to the required standard THE UNIVERSITI OF BRITISH COLUMBIA A p r i l , 1961 In presenting t h i s t h e s i s i n 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 th a t 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 reference and study. I f u r t h e r agree that permission f o r extensive copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted 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 . I t i s understood tha t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be allowed without my w r i t t e n permission. Department of ^gZ^^tC^a The U n i v e r s i t y of B r i t i s h Columbia, Vancouver 8 , Canada. Date oyasUJi /X , ABSTRACT Let X be a square matrix of order k over a f i e l d F. The permanent of X i s given by per(X) . ^ U i o ( l ) x 2 o ( 2 ) - " x k a ( k ) ) a where a ranges over a l l the permutations of l,2,...,k. The o r i g i n a l o b j e c t of t h i s i n v e s t i g a t i o n was to c h a r a c t e r i z e those l i n e a r maps which leave the permanent u n a l t e r e d ; t h a t i s , per(X) = p e r ( T ( X ) ) , a l l X. Let M denote the v e c t o r space of a l l matrices m,n having m rows and n columns with e n t r i e s taken from F, F i x an i n t e g e r r , 2 < r < min(m,n). The r - t h permanental compound of X e M i s d e f i n e d i n an analogous way to the m,n r - t h compound of X, and i s denoted by P_(X) e M̂ m̂ (_;) • Subject to m i l d r e s t r i c t i o n s on F, the f o l l o w i n g theorem can be proved. Let T be a l i n e a r map on M i n t o i t s e l f , l e t S be a non-singular l i n e a r map on m, n * r M^m) (TL) onto i t s e l f . Suppose t h a t P r ( T ( X ) ) = S r ( P _ ( X ) ) f a l l X e M_ _« Then f o r max(m,n) > 2, we have T(X) = DPXQK when m j£ n ; when m = n , we have e i t h e r T(X) = DPXQK, a l l X , or T(X) ss DPX'QK, a l l X. Here P,Q are permutation matrices and D,K are di a g o n a l m a t r i c e s , of ap p r o p r i a t e orders. For the case r = m = n = 2 , there i s a c e r t a i n non—singular l i n e a r map B on 2 onto i t s e l f such t h a t BTB(X) = UXV, a l l X, or BTB(X) = ' u X « V , a l l X. Here U,V are non-singular* The o r i g i n a l problem a r i s e s i n the case r = m = n , with S =1, the u n i t of F. r hereby c e r t i f y that t h i s abstract i s satisfactory,. TABLE OP CONTENTS PAGE INTRODUCTION 1 DEFINITIONS AND NOTATION . 3 RESULTS • • • • • • • • • • • • • • • * * 6 BIBLIOGRAPHY 25 ACKNOWLEDGEMENT The author wishes to express his appreciation for the very generous assistance given him by Dr. Marvin Marcus i n the preparation of thi s t h e s i s . He i s also pleased to acknowledge the f i n a n c i a l support given him by the National Research Council of Canada. INTRODUCTION Let X be an n—square matrix with elements i n a f i e l d F. The permanent of X i s defined by (1) per (X) = | x l a ( l ) x 2 a ( 2 ) ... x n a ( n ) where a runs over the symmetric group of permutations on the integers l,2,...,n. This function makes i t s appearance i n certain combinatorial applications [ l 3 ] , and i s involved i n a conjecture of van der Waerden [6], [9]. Certain formal properties of per (X) are known [ l ] , and an old paper of Polya [12] shows that for n > 2 one cannot multiply the elements of X by constants i n any uniform way so as to convert the permanent into the determinant. Indeed, i t can be shown that no l i n e a r operation on X ( for n > 2 ) w i l l transform the permanent into the determinant. The purpose of th i s thesis i s to characterize those l i n e a r operations on matrices which leave the permanent unaltered. This problem and i t s generalizations have been considered f o r the determinant function by Probenius [3] and Kantor [5], l a t e r by Schur [14], Morita [ l l ] , Dieudonne [ 2 ] p Marcus and Moyls [8], Marcus and Purves [ l O ] , Marcus and May [7]. In view of the res u l t of Polya [ l 2 ] f i t does not seem l i k e l y that many of the techniques used i n the above papers can be used to investigate the permanent (2) function. Most of these r e l y heavily on certain properties of the determinant function which are no longer v a l i d for the permanent function. For example, i t i s i n general f a l s e that per (AB) *= per (A) per (B). (3) DEFINITIONS AND NOTATION0 Let M denote the vector space of a l l m x n m,n matrices over a f i e l d F 9 with the natural basis of unit matrices E. ., where E. . i s the matrix with 1 i n position ( i , j ) and 0 elsewhere. In the sequel, r w i l l denote a fixed integer s a t i s f y i n g 2 < r < min(m,n). When dealing with index sets, the following notation w i l l be used, Q denotes the t o t a l i t y of s t r i c t l y increasing sequences n,r of integers s a t i s f y i n g 1 < < ± 2 < ,,, < i r < n. As usual, a = ( i 1 , , , , , i r ) precedes P = ( j 1 » » » » » 3 r . ) i n "the lexicographic ordering of Qn r, <x < P, i f there i s t such that i ^ < and i < i , a l l s < t . s — •'s ' Let X e M „ We define the r-th permanental m,n compound of X, denoted by P r(X) e M/m̂ ^nj as follows : i f co = ( i j ^ . . . , ^ ) e Qm^r and 6 = ( j l f . . . , j r ) e Q n > r , then the (o),6) entry ( i n the doubly lexicographic ordering) of P r(X) i s X^g, where X^g i s the permanent of the matrix i n M whose (s,t) entry i s x. . , (s,t = l , , . , , r ) . We denote r ' r s 3 t the (<o,6) unit matrix i n M̂ m̂ ^n^ by E ^ 0 Let x a = ( x a l , . . . ,x a n) , (a = 1, <, „ . ,r) , be any vectors over F, Then the permanental product of the vectors x a t (a = l , . . , , r ) , denoted by V x 2 V , , , V x r , i s defined to be the (?)-* vector whose 6 = (j-, , •. • ,j_) e Q„ ,. x r n $ r coordinate i s per( x„. ) » (a = l , , , . , r ; p = l , , . . , r ) , i n the lexicographic ordering,, (4) We denote the rank of X by Q(X), the transpose of X by X', the row of X by X(^)> "kne 3̂ ** column of X by X^^, and the determinant of X by det (X) 0 Let A be an s x t matrix. If j > 0, k > 0, we define A 0 A + 0 s,k 0. . 0. . where 0. , denotes the j x k zero matrix 0 I f j s k = 0, ve 3 l e t the matrix A + 0. , be A, If j = 0, k > 0, or j > 0, k = 0, 3 » K © then we l e t A + 0. , be 3 » K A s,k or A 0. . 3»t respectively* If u = (u^,.,.,^) and v = ( v ^ . , . , ^ ) are n-vectors, the symbols u _j£ v and u//v w i l l indicate respectively that <E ^ VLjY± ^ ® a n < * ^kat u a n < * v a r e l i n e a r l y dependent. I f C e M and X c M , we define the Hadamard product :m,n m,n' of C and X to be the matrix X = C * X e M „ given by m, n y i j = C i 3 X i 3 * ^ ~ 1 » " , » m ' J = l f * f n ) » Next, l e t T be a l i n e a r map of M into i t s e l f , * r m,n If T i s non-singular, the inverse of T i s denoted by T"**„ Let P and Q be permutation matrices i n M and M. c m,m n,n respectively. In the sequel, we sh a l l have occasion to use maps H obtained from T as follows : H(X) = P T(X) Q , a l l X e M ^ . (5) We sh a l l say that such a map H i s the same as T to within permutation. In the case m = n = 2 we s h a l l need the special map B defined on M2 2 a s follows : B(E..) = E.. i f i < j U ) B ( E 2 1 > - - E 2 1 Clearly B i s non-singular, B = B***t and per (B(X)) m det (X) for a l l X c M 2 2 < > ( 6 ) RESULTS. Our main results are contained i n the THEOREM. Let T be a l i n e a r map of M into i t s e l f , and m,n ' l e t r be an integer s a t i s f y i n g 2 < r < min (m,n)0 Suppose that the ground f i e l d F contains at least r elements, and i s not of char a c t e r i s t i c 2 „ Assume that there exists a non—singular l i n e a r map S y of M̂ mj ^nj into i t s e l f such that ( 3 ) P r(T(X)) . S r(P r(X)) for a l l X e M « m,n Then, for m + n > 4, there are permutation matrices P e M , Q e M and non-singular diagonal matrices B e M , m,mf n,n ° ° m,m* K e M such that i f m i n, n,n * (4) T(X) = D P X Q K for a l l X e M : i f m = n ( > 2 ) , T has the form (4) or m,n (5) T(X) = D P X» Q K for a l l X e Mm . m,n For m ss n = 2 , there are non-singular matrices U and V i n j such that ( 6 ) [BTB] (X) = U X V for a l l X e M2 2» o r else ( 7 ) [BTB] (X) = U X* V for a l l X c M 2 ^ 2 » (7) We note here that i n case r = m = n > 2 and S n = 1, then t h i s r e s u l t t e l l s us that the only l i n e a r operations which hold the permanent fixed, i . e . , (8) per (T(X)) = per (X) , a l l X e *! „ , n, n must be obtainable, to within taking the transpose, by pre- and post-multiplication of X by diagonal matrices whose product has permanent 1 together with pre- and post-multipli ation of X by permutation matrices© We s h a l l prove the theorem i n a sequence of lemmas, some of which may be of inter e s t i n themselves. Lemma 1. Let X c M , l e t Q e M be a permutation matrix, m,n* m,m and l e t D c M be a diagonal matrix. Then m,m (a) P r (QX) = P r (Q) P r (X) (b) P r (DX) = P r (D) P r (X) (c) P r (X«) = P r'(X) where P *(X) denotes the transpose of P„ (X). r r Proof : F i r s t note that i f x^ « (x^^» • • • »X|in^» (p- ~ 1»»»«»*) are any n-vectors, then x x V ... V x r = x x ( l ) V ... V x x ( r ) f o r any permutation X on l , . . . , r . In p a r t i c u l a r , i f o> = ( i 1 , . . . , i r ) c Q then x ( i x ) v — v x U r ) = x ( x ( i 1 ) ) v • • • v x ( x ( i r ) ) for any permutation X on i^»...,i r < s This i s an immediate ( 8 ) consequence of the fact that the permanent of a matrix i s unaltered by a row (or column) permutation^ Let a be the permutation corresponding to Q. The rows of QX are X(o-(l))'* , , , X(o(m))° e k ^ e n o ^ e ^ e ^ i i * vector (of appropriate length) with 1 i n position k, and 0 elsewhere. Now row co of P r(Q) i s e 0 ^ j V V e ^ ^ )© Let i / r > « » » » i / v D e the rearrangement of i , , . . . , i such that X r * ( i ) < fl(i ) < . . . < o ( i 0 ). Then . t f ( } V ... V e o ( . } w e / . \ V . . # V e / . \ i s the unit (r)-vector with 1 i n o(xa ) o U a ) 1 r position (a(i„ ),..»,a(i„ )) e Q „ and 0 elsewhere. Thus row co of the product P r(Q) P r(X) i s x ( a ( £ ) ) V ••• v X ( o ( i a l a & X ^ o ^ V ... Y X ( c ( ^ ))» which i s c l e a r l y row co of 1 r P (QX) 0 Thus (a) i s established,, r Let 6 = ( j l f . . . , 3 r ) e Q Q > r . Then row 6 of P r ( X » ) i s X ^ l ^ V ... V X^r^„ On the other hand, row 6 of P 8(X) r i s column & of P (X) which i s ce r t a i n l y X ^ l ^ V V X ^ r * r This proves ( c ) . Let d-̂ be the diagonal element i n row k of D 0 Let co ss ( i , , . . . , i ) e Q . Now P ( D ) i s again a diagonal i. T m,r r matrix whose diagonal element i n row co i s d. d. «..d. • xl x2 r Part (b) follows at once from the fact that the permanent function i s li n e a r i n each row (and column). In p a r t i c u l a r , which i s row co of P r(DX). The lemma i s proved. (9) Corollary . Let X e M , l e t Q e M be a permutation J m,n' n,n matrix, and l e t D e M be a diagonal matrix. Then * n,n (a»)' P r UQ) = P r U) P r (Q) (b«) P • (XD) = P (X) P^ (D) r r r Proof : An i d e n t i c a l computation proves both (a 1) and (b*). We prove ( a 1 ) . P r(XQ) = P r«(Q*X») = (P r(Q«) P r(X'))» = P r(X) P r(Q) Lemma 2. T i s non-singular. Proof : Suppose that T(U) = 0. Then for any X e M , ve have, using (3), S (P (U + X)) = P (T(U + X)) = P (T(U) + T(X)) r r r r = P r(T(X)) = S r ( P r ( X ) ) . Since S i s non-singular, (9) P r(U + X) = P r(X) holds for a l l X e M » For any permutation matrices m,n P and Q of appropriate sizes, Lemma 1 and i t s cor o l l a r y t e l l us that Pr(PUQ + PXQ) = P r(P(U + X)Q) = P r(P) P r(U + X) P r(Q) = P r(P) P r(X) P r(Q) =P r(PXQ). Now as X runs over M so does PXQ. It suffi c e s then to m,n show that (9) implies u,, =0. (10) Choose X e M such that m,n x u = 0 xkk = t ~ u k k ' 2 ^ k ^ r x i j = ~ u i j » 1 ^ 0 a n d 1 < i»0 < r x. . s 0 , otherwise . Then the ( l , l ) entry of P r(U + X) i s u^^t*"" 1. On the other hand, the ( l , l ) entry of P r(X) i s a polynomial i n t of degree at most r-2 e Since P contains at least r elements, we conclude that u-^ = 0, Lemma 3. Let s be an integer s a t i s f y i n g 1 < s < min(m Then there i s a basis for M̂ m̂ ^nj of the form P g(X), with X e M . m,n Proof : Let co = ( i . , . . . , i ) e Q and l e t S = (j-i»***>j x s ni y s x e Q o If X e M i s the matrix with x. . =1, *n,s° m,n 1 t 3 i , (t = l , . . . , s ) , and x.. = 0 otherwise, then P (X) = E ' I J s coo Lemma 4. There exists a non-singular linear map S 2 of M̂ m̂ ^n^ into i t s e l f such that (10) P 2(T(X)) = S 2(P 2(X)) for a l l X e M . That i s , i f (3) holds for r > 2 , m,n i t holds for r = 2 as well. Proof : Let I = T(X), Using (3) we can write Yto6 = ̂ <x,p X a , p (11) for any co e Q and 6 e Q ; here we sum over a l l m, r n, r ' oc 8 « e Q t P e Q • In ( l l ) the scalars s are the Km,r ' *n,r x to,o entries i n the matrix representation of S^ with respect to the natural basis i n M^raj ^ , ordered doubly lexicographically. Since T i s non-singular, we may write , m , n X m ^ ff1^ V st p=l,q=l 6 s , t "'pq where the scalars g^'+ are the entries i n the matrix representation of T"̂ " with respect to the natural basis i n M . Now ( l l ) may be regarded as a polynomial i d e n t i t y in f xk i n the variables y_ . pq. ¥e compute that 3 y P q a ' p ^ T S T pq < a,0 < m » n > x U „ f l a, 8 co,6 u=l,v=l — - — — r X-* r ' f 9 y 9 x 17 pq uv - ^ a,6 u=l,v=l v sco,6 gu,v ' » * xuv where we take p e co and q e & » Now s a ' f g?':!: , the ^ co,o u,v 3 X co e f f i c i e n t of aB i n the l a s t expression of th i s h x uv equation, i s a scalar independent of X and Y . (12) We conclude that any (r-l)-order permanental minor of X = T(X) i s expressible as a fixed l i n e a r combination of the (r-l)-order permanental minors of X. In other words, there i s a l i n e a r map RQ of M^m-jj ( r ^ l ) into i t s e l f such that (12) P r ^ 1 ( T ( X ) ) = E O ( P R _ 1 ( X ) ) for a l l X e M . m,n Since T i s non-singular, we see from (3) that (13) P J . (T- 1 (X)) = s; 1(P r (x)) for a l l X c M « If we apply the above reasoning to (13), m,n we conclude that there i s a l i n e a r map B° of ^ ( r 2 i ) ( r - l ) into i t s e l f such that for a l l X e M , m,n' p^er ^ x ) ) = R ^ P ^ U ) ) . That i s , for a l l X c M , we have ' m,n (14) P R _ X ( X ) = R 0 ( P r _ _ 1 ( T ( X ) ) ) . Combining (12) and (14) we have (15) P r _ l ( X ) = E ° V P r - l ( X ) ) for a l l X e M . Lemma 3, with s = r - l , t e l l s us that m,n R°R Q i s the i d e n t i t y map of M^rn^j ( r 2 i ) on^° i t s e l f . Consequently R Q i s non-singular i n (12), and we set S = R , Then, using (12), we proceed to reduce r - l to r-2, etc., f i n a l l y obtaining (10) . (13) Let A e M • If A has at most one non-zero m,n row (column), we s h a l l c a l l A a row (column) matrix* If A i s a row (column) matrix, then the number of non-zero entries i n A i s denoted by <p(A)e Lemma 5« Let A e M , and suppose that P~(A) *= 0« Then 6(A) =0, 1, or 2 # Moreover, i f A has rank 1, then A i s a row (or column) matrix j i f A has rank 2, then to within permutation of the rows and columns of A, A has the form + °m-2,n-2 » (16) \ a p X jx where oca. + p* = 0 t and <Xp » pX £ 0. Proof : Assume that A j£ 0. Suppose f i r s t that 6(A) = 1<> We may write row t of A as some multiple of a fixed vector z r= ( z l t . . . , z n ) , say c^z, (t = l,...,m). Since P 2(A) = °» we see that 2c,c z. z . = 0 i f t ^ s and i j£ j . Since P i s x s x 3 not of cha r a c t e r i s t i c 2, we have c.c z.z. = 0 i f t j£ s x s 1 J and i £ j . Since A j£ 0, some c^ £ 0, and some z^ ^ 0, o o If there i s j ^ i for which z. j£ 0, then c = 0 0 3 s whenever S jc X © o Suppose next that 6(A) > 1. By a suitable permutation we may bring A to the form (14) A 0 . d, b l b2 Cm-2 dm-2 H "n-2 n~2 where H e M 0 „ » au ?= 0 , and au - 0X j£ 0 0 ¥e have 0 b , + Xa, = 0~\ + ua^ = 0 J (t = l,...,n-2) ad + B e SB 0 s s Xd s + ̂ c g . 0 t ( s = l y . . . ,m—2) But au - 8X a= 0. Hence c ss d = 0, (s s= l,...,m~2)» and s s a. =s b . = 0, (t = l,...,n-2). Therefore nn. . = 0 for each element h. . of H, Since u £ 0 t we have H = 0. Also, we note X J that aBXu £ 0* This proves Lemma 5. Corollary. Let P., = T(E. ). Then 6(F.,) = 1 or 2. X J X J X J Proof : From (10) we see that P2<V =S2<P2<V> = S 2 < ° > " • • (15) Lemma 5, together with i t s c o r o l l a r y , enables us to describe p a r t i a l l y the structure of the images F ^ of the unit matrices E.. . We now make the additional 3 assumption that m + n > 5 • In this case we are able to obtain the exact structure of the F ^ . Lemma 6. Q(F..) = 1 » Proof : By Lemma 2, F ^ £ 0. Suppose that S ( F i ; j ) = 2. We lose no generality i n assuming that i = j = 1 and that F ^ has the form (16). Consider F l t , (2 < t < n). From I ^ ^ l l + ° E l t ^ = a l l a e F, we have using (10), I ^ ^ l l + ° F l t ^ = °* a 1 1 0 E F Since cxBAu ^ 0 i n (16), we see at once that <p(F^^) = 2 i f e(F2^.) = 1 > moreover, F̂ .̂ would be zero outside of positions (1,1), (1,2), (2,1), and (2,2). If 6 ( F l t ) = 2, then by l e t t i n g o vary over F, we see again that F ^ i s zero outside these same positions, A similar argument leads to the same conclusions concerning (2 < s < m) . We next show that (t = l,...,n) and P g^» (s = l,...,m), a l l l i e i n the space spanned by the following three matrices : G l " a B 0 0 4- 0 m-2,n-2 * G2 " 0 B 0 u a 0 + 0 m—2,n~2 , and + 0 m—2,n-2 (16) Observe that G„ s and that 11 0 0 X u G l + G4 m~2,n-2 G2 + G 3 * G2 + G3 "* °1 ' F i r s t l e t us assume that 6 ( F ^ ) = 1, We may further assume without loss of generality that b ^ j ^ l ̂ ® sa 0, where we have set and 8 8 b 2 2 I t b l l b12 b21 b22 m-2,n-2 * Now P 2^ F11 + P l t ^ ~ 0 i m P l i e s t h a t b n a + b 2 i ^ = °* a n d hence F ^ i s a multiple of G^. For ( D n » b 2 l ^ _J_ (p»P) J _ (a,A) , and so ( b l l t b 2 1 ) / / ( * , X ) . Next assume that 6(F^^.) = 2» We have b l l b 1 2 b 2 1 b 2 2 * 0 and P 2^ P11 + F l t ^ = 0 s h o w s t h a t b l l ^ + b 2 2 a + b 1 2 X + b 2 1 P " 0 • Now au + pX = b n b 2 2 + b 1 2 b 2 1 = 0 . So there are non-zero constants c and d such that X s= c<x t u ss —cp t b 2 ^ = db^j , and b 2 2 = — d b ^ © Consequently we have 0 = b l l ( i + b22<x + b l nX + b^,p m (c - d ) ( a b 1 0 - pb., 1) Thus either c = d or ab 12 "12 = Pb 11' 21 r ~ v" ' x 12 ^"11 If c = d we see that (17) ( b 1 2 , b 2 2 ) ^ {X,*)J_ and 0> n,l> 2 1).jl ( u . B ) ^ (a,A), whence (b 1 2,b 2 2)//(8,a) and ( b 1 1 , b 2 1 ) / / ( a , X ) . Therefore i f c SE d , F̂ .̂ i s a lin e a r combination of G 2 and One shows s i m i l a r l y that i n case a b ^ 2 = Pt>̂ ^ » i s a linea r combination of G^ and G^0 Thus the matrices F 1 V ^ = x f » * n ) t and, s i m i l a r l y , the matrices (s = l,...,m), a l l l i e i n the space of dimension 3 spanned by G^f G 2, and G^, But m + n — 1 > 3 . We have contradicted Lemma 2, Hence Q(F..) = 1. «i Lemmas 5 and 6 t e l l us that each F. . i s either a row or column matrix. Lemma 7. cp(F. .) = 1. Proof : We lose no generality i n assuming that i = j = 1 and that F ^ i s a row matrix with i t s non-zero row i n row 1. By a suitable permutation of columns we may assume that row 1 of F-^ has the form (a^,a2,••.,a^,0,•..,0) , where we have set 9 = <p(F1]L) for the sake of brevity. Note that a ^ a s O , (t = l,...,q>). If <p > 3, then Lemma 5 t e l l s us at once that F l t , (t = l , . . . , n ) , and F g l > (s = l,...,m), would a l l be row matrices each with i t s non-zero row i n row 1. For P2* F11 + *W = P2* F11 + F s l * = G # S i n c e m + n - 1 > n , we have contradicted Lemma 2. (18) Suppose then that q> = 2 0 We have *11 | a l a 2 | + °m-l,n~2 with a^a 2 j£ 0» We f i r s t show that F^ 2 x s a r o v matrix with i t s non-zero row i n row 1. If not, then by permuting the l a s t m — 1 rows of F ^ 2 9 we can take F^ 2 i n the form (17) 1 b2 + 0 m~2,n-2 * where b^b 2 s£ 0 and a^b 2 + &2b^ (18) We next remark that P 2(T 2(X)) = S 2(P 2(T(X))) « S 2(P 2(X)) for a l l X e M « Consequently a l l our results concerning the m, n 2 2 nature of T apply equally well to T # In p a r t i c u l a r , T (E-Q) i s either a row matrix or a column matrix. But T 2(E 1 ; L) = T ( a 1 E 1 1 + a 0 E 1 0 ) « a ^ . , + a 0F a 2 b 1 "1"11 a l a 2 a2 b2 + k2"12 G Til 2^12 m— 2,n—-2 However, a^a 2b^b 2 jc* 0. This contradiction shows that F^ 2 i s a row matrix l y i n g i n row 1«, Consider F ^ , (t > 2). If F ^ i s not a row matrix lying i n row 1, then we may assume that F ^ has the form (17)«, Again, ( a l f a 2 ) _ / ( b ^ b ^ ) . From F 2^ F12 + P l t ^ = 0 w e s e e immediately that F^ 2 has the form 0 F -*12 "" © + m«l,n-2 ' (19) with £ 0. So ( c - ^ , C 2 ) _ ^ (b2»b^), ^ 0 i X S implies that ^ s a multiple of and we contradict Lemma 2. Now again by Lemma 2, F2^ cannot l i e e n t i r e l y i n row 1. Since ^ ^ l l + F21^ 1 5 ^* W e m a ^ a s s u m e "t n a"t ^21 b a s the form (17). By an argument exactly analogous to that given above, we see that each of F ^ , (t = l , . . . , n ) , i s a row matrix lying i n row 2. There are two cases to consider : (i) m ss 2 , n > 3 , ( i i ) m > 3 . In case ( i ) there i s j > 1 such that F.. has a non—zero ° 3o entry i n column 3. Now from P 9(F,. + F_. ) = 0, we see that 3o 3o the non-zero entries of F-. l i e i n precisely the same columns ^ Jo as do those of F, . • Moreover, we have <p(F. . ) = <p(F_ . ) m 1, A J o 3o ^ 3o or 2. Now P 2( E11 + E21 + ° Elj ° E2j ^ = 0 , a 1 1 ° e F * Consequently P 2^ F11 + F21 + " P l j * o F 2 j ) = °» a 1 1 0 e F « But this contradicts Lemma 5. In case ( i i ) , note that F2^ E11 + E21 + ° E31^ = °' a l i °' 8 , 1 1 ( 1 s 0 w e m u s " t n a v e F2^ F11 + F21 + ° F31^ = ^' a 1 1 0 0 ^ ^ e m m a 5» this implies that a l l the non-zero entries of F ^ are i n i t s f i r s t two rows. This contradicts Lemma 2 once again. Thus q> = 1. Lemma 7 t e l l s us that for m + n ̂ 5, we can write T(E..) s= c..E... t o By Lemma 2, c. . »= 0, and moreover, ( i , j ) (s,t) implies that ( i S j 1 ) £ ( s ' , t ' ) . We set (20) i * = 0(1,3) and j 1 m w(i,j) so that T(E..) s c .E /. .\ 1. . \© Lemma 8. (Let m + n > 5.) If m n , then there are permutation matrices P e M and Q e M , and a matrix r m,m n,n C = (c..) e M with each c.. / 0 . such that for a l l X e M xo m,n m » n (19) T(X) * C * (PXQ) . I f m = n (>2) , then T has the form (19) or else (20) T(X) = C * (PX'Q) for a l l X E Mm . m,n Proof : ¥e may assume without loss of generality that m < n 0 Now by a suitable permutation of the rows and columns, we may take o ( l , l ) = c o(l,l) = 1 . Then P 2( E n + E 2 2 ) ^ 0 shows that P 2( F 1 ; L + P 2 2) j£ 0 , and so o(2,2) > 1 , to(2,2) > 1 «, By a suitable permutation of the l a s t m - 1 rows and the l a s t n — 1 columns we may take o(2,2) =co(2,2) *=2 « In a similar way, the conditions P 2( E.^ + E ^ ) £ 0 and P 2( E 2 2 + E 3 3 ) £ 0 show that o(3,3) > 2 and to(3,3) > 2. Proceeding i n this way, i t i s clear that we may assume that o(k,k) = to(k,k) s= k , (k = l,..,,m) 0 Fix a < m , B < m , so that a ^ p . Now from P 2( E a a + E ap) 8 0 we see that o(a,B) = a or co(a,6) = a . Also P 2(Epp + E ap) m 0 implies cr(a,B) = p or ©(a,8) «, 8 0 Therefore we must have either (21) (21) a(a , p ) = a and co(<x,p) = P , or (22) a(a,3) = P and co(a,p) = a , f o r the non - s i n g u l a r i t y of T shows that we cannot have o ( a , p ) = co(a,p) , Suppose f i r s t that (21) holds* Let 6 < n , 6 a = a , 6 as B e From P 2 ( E a p + Ea6^ = 0 we have o(oc,&) = a or co(a,6) m B o From P 2 ( E a a + Ea&^ 0 w e h a v e °^ a» 6^ m a o r co(a,S) ss a . I t follows that a(a,6) ss a . If i n addition we have 6 < m , then ? 2^ EaS + Ed&^ * 0 s h l 0 W S "fcb-at °( a» s) = °* or co(a,6) = 6 „ Hence o>(a,6) = & s Let k ss a and consider , From ? 2 ^ E a p + ^P^ = 0 we conclude that o(k,P) «= a or co(k,P) ss B . But a(k,P) as a because c (a,t) = a , (t = 1,.. 0,n) fand T i s non - singular. Hence co (k,P) = p . Also ^ ( E j ^ + Ej^p) m 0 shows that o(k , p ) n k or co(k,p) = k 0 Hence o(k , p ) = k 9 co(k,P) m p » If we repeat t h i s argument now with k replacing a i n (2l) we conclude that (23) c ( i , j ) s= i , co(i,j) = j , ( i = l,...,mjj = l,...,m) e Moreover, i f j > m , the non - s i n g u l a r i t y of T ensures that co(i,j) > m o Now we already know that c ( i , j ) ss i for such j „ Furthermore, P 0 ( E . + E. .) =0 shows that co(s,j) = co(t,j) . Thus i f (21) holds, T may be reduced to the form (19) by a suitable permutations of the l a s t n - m columns of X . Suppose next that (22) holds. We s h a l l show that actually m s= n and that (24) a ( i , j ) ss j , co(i,j) = i , ( i = l,...,m;j = l,...,m). From F 2 ( E a p + E a k ) = 0 we have o(a,k) = p or co(a,k) ss a 9 Also P~(E + E , ) ss 0 shows that a(a,k) = a or (22) co(<x,k) = a . I t follows that co(a,k) = a , (k = l,...,n) , because a j£ 0 „ Thus m «= n , for T maps the n - dimensional space spanned by E a ^ , (t = l,...,n) , into the space spanned by E , (s = l,...,m) , an m - dimensional space, and m < n « s ¥e conclude also, from P 2^ Eak + **kk̂ ~ 0 ' "that o(a,k) = k or co(a,k) = k » Since co(a,k) = a , i t follows that a(a,k) ts k , (k = l,...,m) , which establishes (24). So T has the form (20). Lemma 9« Q(C) = 1 0 Proof : Let 1 < i < s < m , l < j < t < n . If (19) holds, choose X so that PXQ = E.. + E.. - E . + E . ; i f (20) holds. 13 i t S 3 sX ' choose X so that PXrQ has thi s same form. We can ce r t a i n l y do t h i s because T i s non — singular. In either case, P 2(X) xs P 2(PXQ) = 0, by Lemma 1 together with i t s c o r o l l a r y . Therefore 0 . P 2(T(X)) - V ^ E . . + c . ^ ~ c s . E s j + c ^ ) , and so c.-c . — c..c. = 0 „ Thus each second order X 3 st i t 3s subdeterminant of C vanishes. We r e c a l l that each c.. j£ 0 a Using Lemma 9 we can write c.. = d.k. , ( i = l,...,m;3 = l , . . . , n ) . We set D = diag(d l f•..,d f f l) e M m t m *> and K = diag(k,,...,k ) e M . Using Lemma 8 we can write X Zx H y u (4) for m £ n and (4) or (5) for m = n (>2) . The proof of the theorem i s complete for the case m + n > 5 • Suppose that m = n = 2 . Then (3) reduces to the equation (25) per(T(X)) = a. per(X) (23) for a l l X e M_ _ , where a i s some nonzero element of F. <LteL Using (2) together with (25) we see that det[BTB(X)] = per[B 2TB(X)] = per[TB(X)] = a.per [B(X)] = a.det[x] for a l l X e M2 2 • Thus BTB preserves the rank of each matrix i n M2 2 • Moreover, (BTB)*~* = BT~^B exists and has the same property. Consequently we may appeal to a theorem of Jacob [4] to conclude that BTB has the desired form. The proof of the theorem i s complete. We observe that i f m / n , we have P r(T(X)) = Pr(DPXQK) = P r(D)P r(P)P r(X)P r(Q)P r(K) = S (P (X)) r r for a l l X e M . I t follows from Lemma 3 that m,n S (X) = P (D)P (P)YP (Q)P (K) = D P YQ K r r r r r o o o o for a l l Y e M / H K ,n\ , and so S has the same form as T . \T) T\T) r Simila r l y , i f m = n > 2 , and T has the form ( 4 ) , then S r has the above form. Also, i f m = n > 2 , and T has the form (5), then S (Y) = D P Y'Q K r x 0 0 * 0 0 for a l l Y e M/m\ /n\ . In conclusion, we present an example to show that neither (4) nor (5) need hold i f r = m = n = 2. We put (24) T ( E n ) « E X 1 + E12 + E22 ~ E21 T ( E 1 2 ) = E11 + E12 T ( E n ) = E12 + E22 T ( E 2 2 ) = - E 1 2 any X e M 2 2 we have X l l X12 X21 X22 ( x i x + x 1 2 ) ( x i ; L + x 1 2 + x 2 1 - x (-* X - Q ) ( x l l + X21> and an easy computation shows that per(T(X)) = per(X) a Observe that T(E.j^) has rank 2. I t i s obvious that T(X) cannot be put into either of the forms (4) or (5). However we can write BTB(X) = UX'V where U 1 1 1 0 and V = 1 1 0 -1 (25) BIBLIOGRAPHY. l e A.C.Aitken, Determinants and Matrices, (5th e d i t i o n ) . Edinburgh, Oliver and Boyd, (1948)© 2© J.Dieudonne, Sur une generalisation du groupe orthogonal a quatre variables, Archiv der Math., 1, (1948), 282 - 287. 3© G.Frobenius, Uber die Darstellung der endlichen Gruppen durch l i n e a r e r Substitutionen, Sitzungber. der Berliner Akademie, 994 - 1015, ( 7 ) 0 4, H.G.Jacob, Coherence invariant mappings on Kronecker products, Amer. J« Math., Vol.77, (1955), 177 - 189 0 5. S.Kantor, Theorie der Aquivalenz von linearen °° ̂ "-Scharen b i l i n e a r e r Pormen, Sitzungber. der Munchener Akademie, (1897), 367 - 381, ( 2). 6 0 D.Konig, Theorie der Graphen, New York, Chelsea, (1950), 238. 7. M0Marcus and P.May, On a theorem of I.Schur concerning matrix transformations, accepted for publication, Archiv der Math. 8, M.Marcus and B.N.Moyls, Linear transformations on algebras of matrices, Can. J . Math., Vol.11, (1959), 61 - 66, (26) 9. M.Marcus and M0Nevman, Permanents of doubly stochastic matrices, Proc e of Symposia of Applied Matho, Vol.10, Amer0 Math. Soc e, (i960), 169 - 174. 10 e M.Marcus and R©Purves, Linear transformations on algebras of matrices}the invariance of the elementary symmetric functions, Can. J . Math e, Vol.11, (1959), 383 - 396 0 l l e K.Morita, Schwarz's lemma i n a homogeneous space of higher dimensions, Japanese J© Math., Vol.19, (1944), 45 - 56. 12 0 G.Polya, Aufgabe 424, Archiv der Math, und Phys., Vol.20(3), 271. 13. H.J.Ryser, Compound and induced matrices i n combinatorial analysis, Proc. of Symposia of Applied Math., Vol.10, Amer. Math. S o c , (i960), 166. 14. I.Schur, Einige Bemerkungen zur Determinantentheorie, Sitzungber. der Preussischen Akademie der Wissemschaften zu B e r l i n , Vol.25, (1925), 454 - 463«
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The permanent function
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The permanent function May, Frank Colin 1961
pdf
Page Metadata
Item Metadata
Title | The permanent function |
Creator |
May, Frank Colin |
Publisher | University of British Columbia |
Date | 1961 |
Date Created | 2012-01-19 |
Date Issued | 2012-01-19 |
Description | Let X be a square matrix of order k over a field F. The permanent of X is given by [Formula omitted] where σ ranges over all the permutations of 1,2,...,k. The original object of this investigation was to characterize those linear maps which leave the permanent unaltered ; that is, per(X) = per(T(X)), all X. Let M[subscript m,n] denote the vector space of all matrices having m rows and n columns with entries taken from F. Fix an integer r, 2 ≤ r ≤ min(m,n). The r-th permanental compound of X ε M[subscript m,n] is defined in an analogous way to the r-th compound of X, and is denoted by P[subscript r](X) ε M[subscript (m over r) [comma] (n over r)]. Subject to mild restrictions on F, the following theorem can be proved. Let T be a linear map on M[subscript m,n] into itself, let S[subscript r] be a non-singular linear map on M[subscript (m over r) [comma] (n over r)] onto itself. Suppose that P[subscript r](T(X)) = S[subscript r](P[subscript r](X)), all X ε M[subscript m,n]. Then for max(m,n) > 2, we have T(X) = DPXQK when m ≠ n ; when m = n , we have either T(X) = DPXQK, allX, or T(X) = DPX'QK, all X. Here P,Q are permutation matrices and D,K are diagonal matrices, of appropriate orders. For the case r = m = n = 2 , there is a certain non-singular linear map B on M[subscript 2,2] onto itself such that BTB(X) = UXV, all X, or BTB(X) = UX'V, all X. Here U,V are non-singular. The original problem arises in the case r = m = n , with S[subscript r] =1, the unit of F. |
Subject |
Functions |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | Eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2012-01-19 |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080639 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
URI | http://hdl.handle.net/2429/40186 |
Aggregated Source Repository | DSpace |
Download
- Media
- UBC_1961_A8 M28 P3.pdf [ 1.82MB ]
- [if-you-see-this-DO-NOT-CLICK]
- Metadata
- JSON: 1.0080639.json
- JSON-LD: 1.0080639+ld.json
- RDF/XML (Pretty): 1.0080639.xml
- RDF/JSON: 1.0080639+rdf.json
- Turtle: 1.0080639+rdf-turtle.txt
- N-Triples: 1.0080639+rdf-ntriples.txt
- Original Record: 1.0080639 +original-record.json
- Full Text
- 1.0080639.txt
- Citation
- 1.0080639.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 4 | 0 |
France | 3 | 0 |
China | 3 | 2 |
Japan | 3 | 0 |
Canada | 1 | 0 |
City | Views | Downloads |
---|---|---|
Unknown | 3 | 13 |
Tokyo | 3 | 0 |
Changsha | 2 | 2 |
Ashburn | 2 | 0 |
College Station | 2 | 0 |
Beijing | 1 | 0 |
Calgary | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
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>
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-0080639/manifest