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 yP 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 Issued | 1961 |
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 |
Date Available | 2012-01-19 |
Provider | Vancouver : University of British Columbia Library |
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 |
URI | http://hdl.handle.net/2429/40186 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1961_A8 M28 P3.pdf [ 1.82MB ]
- Metadata
- JSON: 831-1.0080639.json
- JSON-LD: 831-1.0080639-ld.json
- RDF/XML (Pretty): 831-1.0080639-rdf.xml
- RDF/JSON: 831-1.0080639-rdf.json
- Turtle: 831-1.0080639-turtle.txt
- N-Triples: 831-1.0080639-rdf-ntriples.txt
- Original Record: 831-1.0080639-source.json
- Full Text
- 831-1.0080639-fulltext.txt
- Citation
- 831-1.0080639.ris
Full Text
Cite
Citation Scheme:
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>
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