UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The permanent function May, Frank Colin 1961

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

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
[if-you-see-this-DO-NOT-CLICK]
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

THE  PERMANENT  FUNCTION  by PRANK  COLIN  MAY  B.A,, U n i v e r s i t y 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 A r t s i n the Department of Mathematics  ¥e accept t h i s t h e s i s as conforming t o the r e q u i r e d standard  THE UNIVERSITI OF BRITISH COLUMBIA April,  1961  In p r e s e n t i n g  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 r e q u i r e m e n t s f o r an advanced degree a t the  University  o f B r i t i s h C o l u m b i a , I agree t h a t the L i b r a r y s h a l l make it  freely  a v a i l a b l e f o r r e f e r e n c e and  agree t h a t p e r m i s s i o n f o r e x t e n s i v e f o r s c h o l a r l y purposes may  study.  I further  c o p y i n g of t h i s  be g r a n t e d by the Head o f  Department o r by h i s r e p r e s e n t a t i v e s .  g a i n s h a l l not  be a l l o w e d w i t h o u t my w r i t t e n  Department o f  ^gZ^^tC^a  Date  oyasUJi  /X ,  my  I t i s understood  t h a t c o p y i n g 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  The U n i v e r s i t y of B r i t i s h Columbia, Vancouver 8 , Canada.  thesis  financial  permission.  ABSTRACT  Let field  X be a s q u a r e  where a r a n g e s o v e r original  ^ a  unaltered  x  x  a l l the permutations  )  of l,2,...,k.  i n v e s t i g a t i o n was t o  l i n e a r maps w h i c h l e a v e t h e permanent  ; t h a t i s , p e r ( X ) = p e r ( T ( X ) ) , a l l X. Let  having  Uio(l) 2o(2)-" ka(k)  object of t h i s  c h a r a c t e r i z e those  Fix  of order k over a  F . The permanent o f X i s g i v e n b y  per(X) .  The  matrix  M  m,n  denote t h e v e c t o r space o f a l l m a t r i c e s  m rows and n columns w i t h  entries  taken  f r o m F,  an i n t e g e r r , 2 < r < min(m,n). The r - t h p e r m a n e n t a l  compound o f X e M  i s d e f i n e d i n an a n a l o g o u s way t o t h e m,n  r-th  compound o f X, and i s d e n o t e d b y P_(X) e M^m^ Subject to mild r e s t r i c t i o n s  (_;) •  on F, t h e  f o l l o w i n g t h e o r e m c a n be p r o v e d . L e t 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 n o n - s i n g u l a r l i n e a r map on m, n * r M^m) all  (TL) o n t o i t s e l f .  Suppose t h a t P ( T ( X ) ) = S ( P _ ( X ) ) r  r  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, o r T ( X ) ss DPX'QK, a l l X. Here P,Q a r e p e r m u t a t i o n and  D,K a r e d i a g o n a l m a t r i c e s ,  the  case  2 onto  X, o r BTB(X) = ' u X « V ,  with S  r  allX,  matrices  of appropriate orders. F o r  r = m = n = 2 , there i s a c e r t a i n  l i n e a r map B on all  f  itself  such  non—singular  t h a t BTB(X) = UXV,  a l l X. Here U,V a r e n o n - s i n g u l a r *  The o r i g i n a l p r o b l e m a r i s e s =1, t h e u n i t o f F.  i n t h e case  r = m = n ,  hereby c e r t i f y that t h i s a b s t r a c t i s s a t i s f a c t o r y , .  TABLE  OP  CONTENTS  PAGE 1  INTRODUCTION DEFINITIONS AND NOTATION RESULTS • • • • • • • • • • • • • • • * * BIBLIOGRAPHY  .  3 6 25  ACKNOWLEDGEMENT  The author wishes to express h i s a p p r e c i a t i o n f o r the very generous a s s i s t a n c e given him by Dr. Marvin Marcus 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 . He i s a l s o pleased t o acknowledge the f i n a n c i a l support the N a t i o n a l Research C o u n c i l of Canada.  given him by  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 d e f i n e d 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 i n t e g e r s l , 2 , . . . , n . T h i s f u n c t i o n makes i t s appearance i n c e r t a i n c o m b i n a t o r i a l a p p l i c a t i o n s [ l 3 ] ,  and  i s i n v o l v e d i n a conjecture of van der Waerden [ 6 ] , [ 9 ] . C e r t a i n formal p r o p e r t i e s of per (X) are known [ l ] , and an old  paper of Polya [12] shows t h a t f o r n > 2 one cannot  m u l t i p l y the elements of X by constants i n any uniform way so  as to convert the permanent i n t o the determinant. Indeed,  i t can be shown t h a t no l i n e a r o p e r a t i o n on X ( f o r n > 2 ) w i l l transform the permanent i n t o the determinant. The purpose of t h i s t h e s i s i s to c h a r a c t e r i z e those l i n e a r operations on m a t r i c e s which leave the permanent u n a l t e r e d . This problem and i t s g e n e r a l i z a t i o n s have been considered f o r the determinant f u n c t i o n by Probenius [3] and Kantor [ 5 ] , l a t e r by Schur [ 1 4 ] , M o r i t a [ l l ] , Dieudonne  [ 2 ] Marcus and Moyls [ 8 ] , Marcus and Purves [ l O ] ,  Marcus and May  p  [ 7 ] . In view of the r e s u l t of P o l y a [ l 2 ]  f  i t does not seem l i k e l y t h a t many of the techniques used i n the  above papers can be used to i n v e s t i g a t e the permanent  (2) f u n c t i o n . Most of these r e l y h e a v i l y on c e r t a i n p r o p e r t i e s of the determinant f u n c t i o n which are no longer v a l i d f o r the permanent f u n c t i o n . For example, i t i s i n general f a l s e that per (AB) *= per (A) per ( B ) .  (3)  DEFINITIONS AND NOTATION  0  Let M m,n denote the vector space of a l l m x n matrices over a f i e l d F with the n a t u r a l basis of u n i t matrices E. ., where E. . i s the matrix with 1 i n p o s i t i o n ( i , j ) and 0 elsewhere. In the sequel, r w i l l denote a f i x e d integer s a t i s f y i n g 2 < r < min(m,n). When dealing with index s e t s , the f o l l o w i n g notation w i l l be used, Qn,r denotes the t o t a l i t y of s t r i c t l y i n c r e a s i n g sequences of integers s a t i s f y i n g 1 < < ± < ,,, < i < n. As u s u a l , a = ( i , , , , , i ) precedes P = ( j » » » » » 3 . ) i "the lexicographic ordering of Q , <x < P, i f there i s t such that i ^ < and i s <— •'s i ', a l l s < t . 9  2  r  n  1  r  n  1  r  r  Let X e M m,n „ We define the r - t h permanental compound of X, denoted by P (X) e M/m^ ^nj as follows : r  i f co = ( i j ^ . . . , ^ ) e Q ^ and 6 = ( j . . . , j ) e Q , then the (o),6) entry ( i n the doubly lexicographic ordering) of P (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 ' s t the (<o,6) u n i t matrix i n M^m^ ^n^ by E ^ m  r  l f  r  n > r  r  r  r  3  0  Let x  a  = ( x , . . . , x ) , (a = 1, <, „ . ,r) , be any a l  an  vectors over F, Then the permanental product of the vectors x (a = l , . . , , r ) , denoted by V x V , , , V x , is a  t  2  r  defined to be the (?)-* vector whose 6 = (j-, , •. • , j _ ) e Q„ ,. coordinate i s per( x„.  x  r  n $ r  ) » (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 o f X by X(^)>  by X ^ ^ , and the determinant  "k  ne  3^** column of X  of X by det (X)  0  L e t A be an  s x t m a t r i x . I f j > 0, k > 0, we d e f i n e 0  A  A + 0  0.  .  s,k  0. .  where 0. , denotes the j x k zero m a t r i x I f j s k = 0, ve 3 l e t the matrix A + 0. , be A, I f j = 0, k > 0, or j > 0, k = 0, 3» 0  K  ©  then we l e t A + 0. , be 3» A or s,k K  A 0.  respectively*  .  3»t  I f u = ( u ^ , . , . , ^ ) and v = ( v ^ . , . , ^ ) are n - v e c t o r s , the symbols u _j£ v and u//v w i l l i n d i c a t e r e s p e c t i v e l y t h a t <E ^ j ± VL  ^ ®  Y  a n <  * ^kat  u  a n <  *  v  a  r  e  l i n e a r l y dependent.  If C e M and X c M , we d e f i n e the Hadamard product m,n m,n' :  of C and X t o be the matrix X = C * X y  ij  =  C  '  eM  „ given by m, n  i3 i3* ^ ~ » " » J = l f * f ) » Next, l e t T be a l i n e a r map of M * m,n 1  X  ,  m  n  r  into  itself,  I f T i s n o n - s i n g u l a r , the i n v e r s e of T i s denoted by T"**„ Let P and Q be permutation matrices i n M and M. m,m n,n c  r e s p e c t i v e l y . In the sequel, we s h a l l have o c c a s i o n to use maps H obtained from T as f o l l o w s : H(X)  = P T(X) Q , a l l X e  M^.  (5) We s h a l l say t h a t such a map H i s the same as T t o w i t h i n permutation. In the case m = n = 2 we s h a l l need the s p e c i a l map B d e f i n e d on M  a 2  s  2  follows :  B(E..) = E.. i f i < j U  )  B ( E  21>  - -  E  21  C l e a r l y B i s n o n - s i n g u l a r , B = B*** and t  per (B(X)) m det (X) for a l l X c M  2  2 < >  (6)  RESULTS. Our main r e s u l t s are contained i n the THEOREM. L e t T be a l i n e a r map of M i n t o i t s e l f , and m,n ' l e t r be an i n t e g e r s a t i s f y i n g 2 < r < min (m,n)  0  Suppose  t h a t the ground f i e l d F c o n t a i n s a t l e a s t r elements, and i s not of c h a r a c t e r i s t i c 2 „ Assume t h a t there e x i s t s a n o n — s i n g u l a r l i n e a r map S (3) for  y  o f M^mj  ^nj i n t o i t s e l f  such t h a t  P (T(X)) . S (P (X)) r  allX e M  r  m,n  r  «  Then, f o r m + n > 4, there are permutation  matrices  P e M , Q e M and n o n - s i n g u l a r d i a g o n a l matrices B e M , m,m n,n ° ° m,m* f  K e M such t h a t i f m i n, n,n * (4) for (5) for  T(X) = D P X Q K allX e M m,n  : i f m = n ( > 2 ) , T has the form (4) or  T(X) = D P X» Q K allX e M . m,n m  For m ss n = 2 , there are non-singular U and V i n j such t h a t (6) [BTB] (X) = U X V for (7)  for  allX e M  2»  2  o  r  else  [BTB] (X) = U X* V allX c M ^ » 2  2  matrices  (7) We note here t h a t 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 t h a t the only l i n e a r  operations which h o l d the permanent f i x e d , i . e . , (8)  per (T(X)) = per (X) , a l l X e *! „ , n, n  must be o b t a i n a b l e , to w i t h i n t a k i n g the transpose, by pre-  and p o s t - m u l t i p l i c a t i o n  of X by d i a g o n a l m a t r i c e s whose  product has permanent 1 together w i t h p r e - and ation  post-multipli  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 i n t e r e s t i n themselves.  Lemma 1. L e t X c M and l e t D c M  m,m  , let Q e M be a permutation matrix, m,n* m,m be a d i a g o n a l m a t r i x . Then  (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 ' ( X ) r  where P *(X) denotes the transpose of P„ ( X ) . r r Proof : F i r s t note t h a t i f x^ « ( ^^» • • • » | ^» x  X  in  are  (p- ~ 1»»»«»*)  any n - v e c t o r s , 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 , . . . , i ) 1  r  x  (i ) x  v  c Q —  then v x  U ) r  = x  (x(i ))  f o r any permutation X on i^»...,i  1  r<s  v  •••  v  x  (x(i )) r  T h i s i s an immediate  (8)  consequence of the f a c t t h a t the permanent of a matrix i s u n a l t e r e d by a row (or column) permutation^ L e t 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  ^ii*  v e c t o r (of  a p p r o p r i a t e length) with 1 i n p o s i t i o n k, and 0 elsewhere. Now i/r  row co of P (Q) i s > « » » » i / v  X *(i  ) <  we/. o(x  a  1  D  e  r fl(i \V.. )  jV  e ^  r  0  V e^^  )© L e t  the rearrangement of i , , . . . , i ) < #  . . . < o(i  Ve/. oU  a  ).  0  Then .  t f (  }  such t h a t V ... V e  .  o (  }  \ i s the u n i t ( r ) - v e c t o r w i t h 1 i n )  r p o s i t i o n (a(i„ ),..»,a(i„  „ and 0 elsewhere. Thus  )) e Q  row co of the product P (Q) P ( X ) i s ( ( £  ) ) •••  x  r  r  V  a  v  X  (o(i  l & X^ ^ V ... Y X ( ( ^ ))» which i s c l e a r l y row co of 1 r P (QX) Thus (a) i s established,, r a  o  a  c  0  Let 6 = ( j l f . . . , 3 r )  e Q  Q  >  r  . Then row 6 of  P  r  ( X » )  V ... V X ^ r ^ „ On the other hand, row 6 of P ( X ) r i s column & of P (X) which i s c e r t a i n l y X ^ l ^ V V X^r* r This proves ( c ) . is X ^ l ^  8  L e t d-^ be the d i a g o n a l element i n row k of D Let co ss ( i , , . . . , i i.  T  ) e Q . Now m,r  0  P ( D ) i s again a diagonal r  matrix whose d i a g o n a l element i n row co i s  d. d. «..d. • x l 2 r x  P a r t (b) f o l l o w s a t once from the f a c t t h a t the permanent f u n c t i o n i s l i 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 ( D X ) . The lemma i s proved. r  (9) Corollary . Let X e M , let Q e M be a permutation m,n' n,n J  matrix, and l e t D e M be a d i a g o n a l matrix. Then * n,n  UQ) =  P  (b«)  P • (XD) = P (X) P^ (D) r r r  Proof  r  P  U) P  (a»)'  r  r  (Q)  : An i d e n t i c a l computation  proves both ( a ) and ( b * ) . 1  We prove ( a ) . 1  P (XQ) = P «(Q*X») = (P (Q«) P (X'))» = P ( X ) P ( Q ) r  r  r  r  r  r  Lemma 2. T i s n o n - s i n g u l a r . Proof  : Suppose t h a t T(U) = 0. Then f o r any X e M  ,  ve have, u s i n g ( 3 ) , S (P (U + X)) = P (T(U + X)) = P (T(U) + T(X)) r r r r  = P (T(X)) = S ( P ( X ) ) . r  r  r  Since S  i s non-singular,  (9)  P ( U + X) = P ( X ) r  r  holds f o r a l l X e M » F o r any permutation m,n  matrices  P and Q of a p p r o p r i a t e s i z e s , Lemma 1 and i t s c o r o l l a r y t e l l us t h a t P (PUQ + PXQ) = P ( P ( U + X)Q) r  r  = P ( P ) P ( U + X) P ( Q ) = P ( P ) P ( X ) P ( Q ) r  r  r  r  r  r  =P (PXQ). r  Now as X runs over M so does PXQ. I t s u f f i c e s then t o m,n show t h a t (9) i m p l i e s u,, = 0 .  (10) Choose X e M such t h a t m,n x  = 0  u  x  kk  =  x  ij  =  ~  t  u  k k '  ~ i j  »  u  ^  ^ 0  1  x. . s 0  2  ^  k  a  n  d  r  1  < i»0 < r  , otherwise .  Then the ( l , l ) e n t r y of P ( U + X) i s u^^t*"" . On the 1  r  other hand, the ( l , l ) e n t r y o f P ( X ) i s a polynomial r  in  t  least  o f degree a t most r  r-2  e  Since P c o n t a i n s a t  elements, we conclude t h a t  Lemma 3. L e t s  u-^ = 0,  be an i n t e g e r s a t i s f y i n g  Then there i s a b a s i s f o r M^m^ with X e M . m,n Proof : L e t co = ( i . , . . . , i x  ^nj of the form  ) e Q  s  1 < s < min(m P (X), g  and l e t S = (j-i»***>j  ni y s  x  e Q o IfX e M i s the matrix with x. . = 1 , *n,s° m,n t i , ( t = l , . . . , s ) , and x.. = 0 otherwise, then P (X) = E ' I J s coo 1  Lemma 4. There M^m^  for  e x i s t s a n o n - s i n g u l a r l i n e a r map S of 2  ^n^ i n t o i t s e l f  (10)  3  P (T(X)) = 2  such t h a t S (P (X)) 2  2  allX e M . That i s , i f (3) holds f o r m,n  i t holds f o r Proof  r = 2  as w e l l .  : L e t I = T ( X ) , Using (3) we can w r i t e  to6 = ^ <x,p  Y  X  a,p  r > 2 ,  (11) f o r any co e Q and 6 e Q ; m, r n, r ' « e Q m,r  here we sum over a l l  t P e Q • In ( l l ) the s c a l a r s ' *n,r  K  x  oc 8 s to,o  are the  e n t r i e s i n the matrix r e p r e s e n t a t i o n of S^ with r e s p e c t to the n a t u r a l b a s i s i n M^raj ^ ,  ordered doubly  l e x i c o g r a p h i c a l l y . Since T i s n o n - s i n g u l a r , we may w r i t e , m , n X m ^ ff ^ V st p=l,q=l s , t "'pq 1  6  where the s c a l a r s  g^'+  are the e n t r i e s i n the matrix  r e p r e s e n t a t i o n of T"^" with r e s p e c t to the n a t u r a l b a s i s in M  . Now in f xk  ( l l ) may be regarded as a polynomial i d e n t i t y  i n the v a r i a b l e s y_ .  pq.  ¥e compute t h a t  3  q  y P  <  a, 8 *  - ^ a,6  r  a  a,0 co,6  '  <  '  u=l,v=l  ^  p  T  » u=l,v=l m  f  f  s  co,6  T pq  > x U„ — - — — r X9 y 9 x pq uv  n  v  S  l  17  g  u,v  '  »  * uv x  where we take p e co and q e & » Now s ' f g?':!: , the ^ co,o u,v 3 X c o e f f i c i e n t of aB i n the l a s t expression of t h i s h x uv equation, i s a s c a l a r independent of X and Y . a  (12) We  conclude that any  ( r - l ) - o r d e r permanental  minor of X = T ( X ) i s e x p r e s s i b l e as a f i x e d combination of the  ( r - l ) - o r d e r permanental minors of X .  In other words, there i s a l i n e a r map into i t s e l f (12)  R  Q  of M^m-jj ( r ^ l )  such that  P ^ (T(X)) r  linear  =  1  E (P _ (X)) O  R  1  for a l l X e M  . m,n Since T i s non-singular, 1  1  r  J  for a l l X c M  m,n  « I f we  apply the above reasoning  conclude that there i s a l i n e a r map  into i t s e l f  such that f o r a l l X e M  p^er^x))  (14)  P _ (X) R  X  =  (15)  P r  _ l  for a l l X e M R°R  Q  (  X  )  r  m,n  1  (14) we E  = R  Q  P  .  s = r - l , t e l l s us  of M^rn^j ( 2 i ) r  i s non-singular  , Then, using  .  ( X ) )  . Lemma 3, w i t h  r-2, e t c . , f i n a l l y  r  have  °V r-l  i s the i d e n t i t y map  Consequently R  B° of ^ ( 2 i ) ( r - l )  have  0  =  (13),  ,  R ^ P ^ U ) )  = R (P __ (T(X)))  Combining (12) and  to  m,n'  That i s , f o r a l l X c M , we ' m,n  S  see from (3) that  P .(T- (X)) = s; (P (x))  (13)  we  we  itself.  i n (12), and we  (12), we  obtaining  ^°  on  (10)  that  set  proceed to reduce r - l to .  (13)  Let A e M row  (column), we  I f A i s a row  m,n  • I f A has a t most one  s h a l l c a l l A a row  non-zero  (column) matrix*  (column) matrix, then the number of  non-zero e n t r i e s i n A i s denoted by <p(A)  e  Lemma 5« L e t A e M Then 6(A) = 0 , A i s a row  , and suppose  1, or 2  #  Moreover,  (or column) m a t r i x j  that P~(A) *= 0« i f A has rank 1, then  i f A has rank 2, then  to w i t h i n permutation of the rows and columns of A, A has the form (16)  \a  p  X  jx  +  where  oca. + p* = 0  t  °m-2,n-2 and  »  <Xp » pX £ 0.  Proof : Assume that A j£ 0. Suppose f i r s t t h a t 6(A) = 1<> We may w r i t e row t of A as some m u l t i p l e of a f i x e d v e c t o r z r= ( z we  l t  . . . , z ) , say c^z, ( t = l,...,m). Since P ( A ) n  2  =  °»  see t h a t 2c,c z. z . = 0 i f t ^ s and i j£ j . Since P i s x s x 3  not of c h a 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 I f there i s j ^ i f o r which z. j£ 0, then c =0 0 3 s whenever S jc X © o Suppose next t h a t 6(A) > 1. By a s u i t a b l e permutation we may b r i n g A to the form  (14)  0 .  "n-2 b  l  b  n~2  2  d,  A  H  m-2  m-2  C  where  HeM  d  0  » au ?= 0 , and au - 0X j£ 0  „  + Xa, = 0~\ 0b,  + ua^ = 0 J  ad  s  + Be s  s  + ^c . 0  SB  ¥e have  ( t = l,...,n-2)  0 t  Xd  0  ( s = l . . . ,m—2) y  g  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 n n . . = 0 f o r each element h. . o f H, Since u £ 0 we have H = 0. A l s o , we note XJ t h a t aBXu £ 0* This proves Lemma 5. t  C o r o l l a r y . L e t P., = T(E. ) . Then 6(F.,) = 1 or 2. X J  X J  X J  Proof : From (10) we see t h a t P  2<V = 2< 2<V> S  P  = 2<°> " • • S  (15)  Lemma 5, together with i t s c o r o l l a r y , enables us to d e s c r i b e p a r t i a l l y the s t r u c t u r e of the images F ^ of the u n i t matrices E.. . We now make the a d d i t i o n a l  3 assumption  t h a t m + n > 5 • In t h i s case we are able t o  o b t a i n the exact s t r u c t u r e of the F ^ . Lemma 6. Q(F..) = 1 » Proof  : By Lemma 2, F ^ £ 0. Suppose t h a t S (  F i ;  j ) = 2. We lose  no g e n e r a l i t y i n assuming t h a t i = j = 1 and t h a t F ^ has the form  (16). Consider F  , (2 < t < n ) . From I ^ ^ l l  ° lt^  +  l t  a l l a e F, we have u s i n g (10), I ^ ^ l l  +  ° lt^ F  =  °*  a  E  1  1  0  E  =  F  Since cxBAu ^ 0 i n (16), we see a t once t h a t <p(F^^) = 2 i f e(F2^.) = 1 > moreover, F^^. would be zero o u t s i d e of p o s i t i o n s (1,1), (1,2), (2,1), and (2,2). I f 6 ( F ) = 2, then by l t  letting  o vary over F, we see again t h a t F ^ i s zero o u t s i d e  these same p o s i t i o n s , A s i m i l a r argument leads to the same c o n c l u s i o n s concerning  (2 < s < m) .  We next show t h a t (s = l,...,m),  ( t = l,...,n) and P ^ » g  a l l l i e i n the space spanned by the f o l l o w i n g  three matrices :  G  G  l  "  2 "  a  B  0  0  0  B  0  u  a  0  4- 0 m-2,n-2  +  0 m—2,n~2  +  0 m—2,n-2  *  , and  (16) Observe  that G„  s  0  0  X  u  m~2,n-2  2  G  +  G  3 "* °1 '  and t h a t 11  l  G  +  G  4  2  G  +  G  3 *  F i r s t l e t us assume t h a t 6 ( F ^ ) = 1, We may f u r t h e r assume without l o s s of g e n e r a l i t y t h a t b ^ j ^ l ^ ® and  sa 0, where we have s e t  8 8 b 2  2  b  l l  b  12  b  21  b  22  It  Now P ^ 1 1 F  +  P  2  lt^  ~  0  i  P  m  l  i  m-2,n-2 *  e  s  t  h  a  t  n  b  a  2i^  b  +  hence F ^ i s a m u l t i p l e of G^. F o r ( n » D  J_  ( b  (a,A) , and so  l  l  b  t  2  b 2  =  l^  °*  a  n  d  _J_ (p»P)  ) / / ( * , X ) .  1  Next assume t h a t 6(F^^.) = 2» We have b  ll 12 21 22 * b  and P ^ 1 1 P  +  F  2  b  l l ^  b  b  lt^ +  b  =  0  22  s  a  h  +  o  b  w  0  s  12  t  X+  h  b  a  t  21  P  "  •  0  Now au + pX = b b n  2  2  + b  1 2  b  So there a r e non-zero constants X  s=  c<x  t  u  ss —cp  t  = 0 .  2 1  c  and  b ^ = db^j , and b 2  2  2  d  such t h a t  = —db^ ©  Consequently we have 0 =  b i ll(  + b <x + b X + b^,p m (c - d ) ( a b - pb., ) 21 ~ " ' 12 ^"11 "12 22  Thus e i t h e r c = d o r ab 12  l n  = Pb11'  r  If  v  x  1 0  c = d we see t h a t  1  (17) (b  1 2  ,b  2 2  ) ^ {X,*)J_  and 0> ,l> ).jl n  21  ( u . B ) ^ (a,A),  whence ( b , b ) / / ( 8 , a ) and ( b , b ) / / ( a , X ) . Therefore 1 2  2 2  1 1  2 1  if  c SE d , F^^. i s a l i n e a r combination of G and  One  shows s i m i l a r l y t h a t i n case b ^ = Pt>^^ »  2  2  l i n e a r combination of G^ and G^ F  is a  a  1V  ^  =  x  f » *  and, s i m i l a r l y , the matrices  ) t  n  Thus the matrices  0  (s = l,...,m), a l l l i e i n the space of dimension 3 spanned by G^  G , and G^, But m + n — 1 > 3 . We have c o n t r a d i c t e d  f  2  Lemma 2, Hence Q(F..) = 1.  «i Lemmas 5 and 6 t e l l us t h a t each F. . i s e i t h e r a row or column matrix. Lemma 7. cp(F. .) = 1. Proof : We l o s e no g e n e r a l i t y i n assuming t h a t i = j = 1 and that F ^ i s a row matrix w i t h i t s non-zero  row i n  row 1. By a s u i t a b l e permutation of columns we may assume t h a t row 1 of F-^ has the form (a^,a ,••.,a^,0,•..,0)  ,  2  where we have s e t 9 = <p(F ) f o r the sake of b r e v i t y . 1]L  Note that  ( t = l,...,q>).  a^asO,  I f <p > 3, then Lemma 5 t e l l s us a t once t h a t F  l t  ,  ( t = l , . . . , n ) , and F  (s = l,...,m), would a l l be  g l >  row matrices each with i t s non-zero  row i n row 1. F o r  2* 11  m + n - 1> n ,  P  F  +  *W  =  P  2* 11 F  +  F  sl*  =  G  we have c o n t r a d i c t e d Lemma 2.  #  S  i  n  c  e  (18) Suppose then t h a t *11 with a^a  |  j£ 0» We  2  i t s non-zero m — 1  l 2|  a  a  we can take F ^  2 9  +  1  (18)  have  °m-l,n~2  +  f i r s t show t h a t F ^  (17) b  x s  a  r  o  matrix w i t h  v  2  +  2  We next remark t h a t  & b^ 2  S (P (X))  2  2  for a l l X e M  m, n  last  i n the form  2  P (T (X)) = S (P (T(X))) « 2  the  0 m~2,n-2 *  2  s£ 0 and a ^ b  2  We  0  row i n row 1. I f not, then by permuting  rows of F ^  where b ^ b  q> = 2  2  2  « Consequently  2  a l l our r e s u l t s concerning the  nature of T apply e q u a l l y w e l l to T  2 #  2 In p a r t i c u l a r , T (E-Q)  i s e i t h e r a row matrix or a column m a t r i x . But T (E 2  1 ; L  ) = T(a E "1"11 1  a  a b 2  a  1  However, a ^ a b ^ b 2  2  1 1  l 2  + a E ) « a^., Til 2"12 k  0  +  a  1 0  G  2 2  +  a F 2^12 0  m— 2,n—-2  b  jc* 0. This c o n t r a d i c t i o n shows that  F^  2  i s a row matrix l y i n g i n row 1«, Consider F ^ ,  (t > 2). If F ^  l y i n g i n row 1, then we may Again, ( a  assume t h a t F ^  a ) _ / ( b ^ b ^ ) . From F ^ 1 2 F  l f  2  immediately t h a t F ^ F *12 ""  2  2  i s not a row  has the form (17)«,  lt^  =  m«l,n-2  '  +  P  has the form © +  0  matrix  0  w  e  s  e  e  (19) £ 0. So ( c - ^ , C 2 ) _ ^ (b2»b^),  with ^  s  m u l t i p l e of  a  ^  implies  0 i X S  that  and we c o n t r a d i c t 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  +  F  21^  ^*  1 5  W  e  m  a  ^  a  s  s  u  m  "t "t ^21  e  na  b  a  s  the form (17). By an argument e x a c t l y analogous t o t h a t given above, we see t h a t each of F ^ , ( t = l , . . . , n ) , i s a row matrix l y i n g i n row 2. There are two cases t o consider :  ss 2  (i)  m  ,n > 3 ,  (ii)  m > 3 .  In case ( i ) there i s j > 1 such that F.. has a non—zero ° o entry i n column 3. Now from P ( F , . + F_. ) = 0, we see that o o the non-zero e n t r i e s of F-. l i e i n p r e c i s e l y the same columns ^ o as do those of F, . • Moreover, we have <p(F. . ) = <p(F_ . ) m 1, o o ^ o or 2. Now P ( 1 1 2 1 ° lj ° 2j ^ ° * 3  9  3  3  J  A J  E  +  3  E  +  E  E  =  0  ,  a  1  3  1  e  F  2  Consequently P ^ 1 1 F  2  +  F  21  " lj  +  P  *  o F  2j  ) = °»  a  1  1  0  e  F  «  But t h i s c o n t r a d i c t s Lemma 5. In case ( i i ) , note that F  2^ 11 E  +  E  21  +  ° 31^  =  °'  l  i  F  2^ 11  +  F  21  +  ° 31^  =  ^'  1  1  F  E  F  a  a  °' 0  0  8,11(1  ^  s  ^  0  w  e  e m m a  m u s  "  t  n  a  v  e  5» t h i s i m p l i e s  that  a l l the non-zero e n t r i e s of F ^ are i n i t s f i r s t two rows. This c o n t r a d i c t s Lemma 2 once again. Thus q> = 1. Lemma 7 t e l l s us t h a t f o r T(E..) s= c..E... (i,j)  t  m + n ^ 5, we can w r i t e  o By Lemma 2, c. . »= 0, and moreover,  (s,t) implies that ( i S j ) 1  £ ( s ' , t ' ) . We s e t  (20) i*  = 0(1,3)  .\ 1.  so t h a t T(E..) s c .E /. Lemma 8.  and  (Let m + n > 5.) I f m  permutation matrices P e M r  C = (c..) e M xo m,n (19)  (20)  m  w(i,j)  . \©  and Q e M  n,n  , and a matrix  w i t h each c.. / 0 . such t h a t f o r a l l X e M m» . (19)  , then T has the form  or e l s e  T(X) = C * (PX'Q)  for a l l X E M m,n  .  m  Proof : ¥e may Now  1  n , then there are  m,m  T(X) * C * (PXQ)  I f m = n (>2)  j  assume without l o s s of g e n e r a l i t y t h a t m < n  by a s u i t a b l e permutation of the rows and columns, we  take o ( l , l ) = c o ( l , l ) = 1. that P ( F 2  1 ; L  + P ) 2 2  Then P ( 2  E  n  + E  2 2  may  ) ^ 0 shows  j£ 0 , and so o(2,2) > 1 , to(2,2) > 1 «,  By a s u i t a b l e permutation of the l a s t m - 1 rows and the l a s t n — 1 columns we may s i m i l a r way, P ( 2  E  2 2  + E  take o(2,2) =co(2,2) *=2  the c o n d i t i o n s P ( E.^ + E ^ 2  3 3  Proceeding i n t h i s way,  ) £ 0 and  i t i s c l e a r t h a t we may  o(k,k) = to(k,k) s= k , (k = l,..,,m)  2  E  a a  + E p) a  0 we  8  Also P (Epp + E p) 2  a  2.  assume t h a t  0  F i x a < m , B < m , so that a ^ p . Now P (  « In a  ) £ 0 show that o(3,3) > 2 and to(3,3) >  from  see that o(a,B) = a or co(a,6) = a  m 0 i m p l i e s cr(a,B) = p or ©(a,8) «, 8  Therefore we must have e i t h e r  . 0  0  n  (21) (21)  a ( a , p ) = a and co(<x,p) = P ,  (22)  a(a,3) = P and co(a,p) = a ,  or  f o r the non - s i n g u l a r i t y of T shows t h a t we cannot have o ( a , p ) = co(a,p)  , 6 < n , 6 a = a ,  Suppose f i r s t t h a t (21) holds* L e t 6 as B  e  From P ( a p  +  E  2  E  a 6 ^ = 0 we have o(oc,&) = a or  co(a,6) m B o From P ( E 2  +  E  a a  a&^  0  w  e  h  a  v  e  °^ » ^ a  6  m  a  o  r  co(a,S) ss a . I t f o l l o w s that a(a,6) ss a . I f i n a d d i t i o n we have 6 < m , then ? ^ a S E  +  2  E  d&^  *  or co(a,6) = 6 „ Hence o>(a,6) = &  0  s h l 0 W S  " fcb  ° ( » ) = °*  at  a  s  s  Let k ss a and consider  , From ? ^ a p 2  E  +  ^P^  =  0  we conclude t h a t o(k,P) «= a or co(k,P) ss B . But a(k,P) as a because c ( a , t ) = a , ( t = 1 , . . , n ) a n d T i s non - s i n g u l a r . 0  Hence co (k,P) o(k,p) n k  f  = p . A l s o ^ ( E j ^ + Ej^p) m 0 shows t h a t  or co(k,p) = k  0  Hence o ( k , p ) = k  9  co(k,P) m p »  I f we repeat t h i s argument now with k r e p l a c i n g a i n ( 2 l ) we conclude that (23)  c ( i , j ) s= i , co(i,j) = j ,  ( i = l , . . . , m j j = l,...,m)  e  Moreover, i f j > m , the non - s i n g u l a r i t y of T ensures t h a t co(i,j) > m o Now we a l r e a d y know t h a t c ( i , j ) ss i f o r such j „ Furthermore, P ( E . + E. .) = 0 0  shows t h a t co(s,j) = co(t,j) .  Thus i f (21) holds, T may be reduced to the form (19) by a s u i t a b l e permutations of the l a s t n - m columns of X . Suppose next that (22) h o l d s . We s h a l l show that a c t u a l l y m s= n and t h a t (24)  a ( i , j ) ss j , co(i,j) = i , From F ( E p + E 2  co(a,k) ss a  9  a  Also P ~ ( E  a k  )  ( i = l,...,m;j = l,...,m).  = 0 we have o(a,k) = p or  + E , ) ss 0 shows that a(a,k) = a or  (22)  co(<x,k) = a . I t f o l l o w s t h a t co(a,k) = a , (k = l,...,n) , because a j£ 0 „ Thus m «= n , f o r T maps the n - dimensional space by E  spanned by E ^ , ( t = l,...,n) , i n t o the space  spanned  a  , (s = l,...,m) , an m - dimensional space, and m < n «  s  ¥e conclude a l s o , from P 2 ^ E a k + **kk^  ~  ' "that  0  o(a,k) = k or co(a,k) = k » Since co(a,k) = a , i t f o l l o w s t h a t a(a,k) ts k , (k = l,...,m) , which e s t a b l i s h e s (24). So T has the form (20). Lemma 9« Proof  Q(C) = 1  0  : Let 1 < i < s < m , l < j < t < n .  I f (19) h o l d s ,  choose X so t h a t PXQ = E.. + E.. - E . + E . ; i f (20) h o l d s . 13  i t  S3  '  sX  choose X so t h a t PX Q has t h i s same form. We can c e r t a i n l y r  do t h i s because T i s non — s i n g u l a r . In e i t h e r case, P ( X ) xs P (PXQ) = 0, by Lemma 1 together with i t s c o r o l l a r y . 2  2  Therefore 0 . P (T(X)) - V ^ E . . + c . ^ ~ c . E 2  s  and so c.-c . — c..c. = 0 „ Thus each second X3 st i t 3s subdeterminant  + c ^ ) ,  s j  order  of C v a n i s h e s . We r e c a l l t h a t each c.. j£ 0  a  Using Lemma 9 we can w r i t e c.. = d.k. , ( i = l,...,m;3 = l , . . . , n ) . We s e t D = d i a g ( d • . . , d lf  and K = diag(k,,...,k ) e M X  Zx  Hy  ffl  )  e  M m  t  . Using Lemma 8 we can w r i t e u  (4) f o r m £ n and (4) or (5) f o r m = n (>2) . The proof of the theorem i s complete f o r the case m + n > 5 • Suppose t h a t m = n = 2 . Then (3) reduces t o the equation (25)  m  per(T(X)) = a. per(X)  *>  (23) f o r a l l X e M_ _ , where a i s some nonzero element of F. <L eL Using (2) together with (25) we see that t  det[BTB(X)] = p e r [ B T B ( X ) ] = per[TB(X)] 2  = a.per [B(X)] = a.det[x] for a l l X e M in M  2  2  2 • Thus BTB preserves the rank of each matrix  2 • Moreover,  (BTB)*~* = BT~^B e x i s t s and has the same  p r o p e r t y . Consequently we may appeal t o a theorem of Jacob [4] to conclude t h a t BTB has the d e s i r e d form. The proof of the theorem i s complete.  We observe t h a t i f m / n , we have P ( T ( X ) ) = P (DPXQK) = P ( D ) P ( P ) P ( X ) P ( Q ) P ( K ) r  r  r  r  r  r  r  = S (P (X)) r r for a l l X e M . I t f o l l o w s 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 f o r a l l Y e M/HK  ,n\ , and so S r  \T) \T) T  has the same form as T .  S i m i l a r l y , i f m = n > 2 , and T has the form ( 4 ) , then S  r  has the above form. A l s o , i f m = n > 2 , and T has the  form ( 5 ) , then S (Y) = D P Y'Q K r  x  f o r a l l Y e M/m\  0 0 * 0 0  /n\ .  In c o n c l u s i o n , we present an example to show t h a t n e i t h e r (4) nor ( 5 ) need h o l d i f r = m = n = 2. We put  (24) T(E ) « E n  T(E ) 1 2  T(E ) n  +  X 1  E  12  = 11  +  E  12  = 12  +  E  22  E  E  T(E ) = - E 2 2  any X e M  22  X  l l  X  12  X  21  X  22  +  E  22 ~ 21 E  1 2  we have (x  i x  + x  1 2  (-* X - Q )  )(x (  x  + x  i ; L  ll  +  X  1 2  + x  2 1  - x  21>  and an easy computation shows t h a t p e r ( T ( X ) ) = p e r ( X )  a  Observe t h a t T(E.j^) has rank 2. I t i s obvious t h a t T(X) cannot be put i n t o e i t h e r of the forms (4) or ( 5 ) . However we can w r i t e 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 M a t r i c e s , (5th e d i t i o n ) . Edinburgh, O l i v e r and Boyd, (1948)©  2©  J.Dieudonne,  Sur une g e n e r a l i s a t i o n du  groupe  orthogonal a quatre v a r i a b l e s , A r c h i v der Math., 1, (1948), 282 3©  287.  G.Frobenius, Uber d i e D a r s t e l l u n g der e n d l i c h e n Gruppen durch l i n e a r e r S u b s t i t u t i o n e n , S i t z u n g b e r . der B e r l i n e r Akademie, 994 - 1015,  4,  H.G.Jacob, Coherence  ( 7)  0  i n v a r i a n t mappings on Kronecker  products, Amer. J« Math., Vol.77, (1955), 177 5.  189  0  S.Kantor, Theorie der Aquivalenz von l i n e a r e n °° ^"-Scharen b i l i n e a r e r Pormen, S i t z u n g b e r . der Munchener Akademie, (1897), 367 - 381,  6  0  D.Konig, Theorie der Graphen, New (1950),  7.  ( 2).  York, Chelsea,  238.  M Marcus and P.May, On a theorem 0  of I.Schur concerning  matrix t r a n s f o r m a t i o n s , accepted f o r p u b l i c a t i o n , A r c h i v der Math. 8,  M.Marcus and B.N.Moyls, L i n e a r t r a n s f o r m a t i o n s on algebras of m a t r i c e s , Can. J . Math., Vol.11, 61 - 66,  (1959),  (26) 9.  M.Marcus and M Nevman, Permanents of doubly 0  stochastic matrices, Proc Matho, Vol.10, Amer 10  e  0  e  of Symposia of A p p l i e d  Math. S o c , e  ( i 9 6 0 ) , 169 -  174.  M.Marcus and R©Purves, L i n e a r t r a n s f o r m a t i o n s on algebras of matrices}the i n v a r i a n c e of the elementary symmetric  f u n c t i o n s , Can. J . Math ,  Vol.11, (1959), 383 - 396 ll  e  e  0  K.Morita, Schwarz's lemma i n a homogeneous space of h i g h e r dimensions, Japanese J© Math., Vol.19, (1944), 45 - 56.  12  0  13.  G.Polya, Aufgabe 424, A r c h i v der Math, und Vol.20(3),  271.  H.J.Ryser,  Compound and induced matrices i n  Phys.,  c o m b i n a t o r i a l a n a l y s i s , Proc. of Symposia of A p p l i e d Math., Vol.10, Amer. Math. S o c , 14.  (i960),  166.  I.Schur, E i n i g e Bemerkungen zur Determinantentheorie, S i t z u n g b e r . der P r e u s s i s c h e n Akademie der Wissemschaften  zu B e r l i n , Vol.25, (1925), 454 - 463«  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 7 0
China 6 3
Japan 3 0
France 3 0
Canada 1 0
City Views Downloads
Ashburn 5 0
Unknown 3 20
Shenzhen 3 1
Tokyo 3 0
Changsha 2 2
College Station 2 0
Beijing 1 0
Calgary 1 0

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

Share

Embed

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

Comment

Related Items