SOME COMBINATORIAL PROPERTIES OF THE DIAGONAL SUMS OF DOUBLY STOCHASTIC MATRICES by EDWARD TZU-HSIA WANG B.Sc, National Taiwan University, Taipei, Taiwan, 1965 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in the Department of MATHEMATICS We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA September, 1971 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l an advanced degree at the U n i v e r s i t y the L i b r a r y I further s h a l l make i t f r e e l y f u l f i l m e n t o f the r e q u i r e m e n t s of B r i t i s h C o l u m b i a , I agree available for 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 r e f e r e n c e and copying of t h i s representatives. It is understood that copying or thesis permission. Department of I v^A^r^l WJL\ \C ^ The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date or publication o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my written that study. f o r s c h o l a r l y purposes may be g r a n t e d by the Head of my Department by h i s for Supervisor: Professor R. Westwick ABSTRACT Let ft n denote the convex polyhedron of a l l (doubly stochastic) matrices. nxn d.s. The main purpose of this thesis is to study some combinatorial properties of the diagonal sums of matrices in Q . In Chapter I, we determine, for a l l d.s. matrices unequal to sum. J n ; the maximum number of diagonals that can have a common diagonal The key w i l l be a Decomposition Theorem that enables us to characterize completely the structure of a d.s. matrix when this maximum number is attained, provided that the common sum is not one. When the common sum is one, the question is more d i f f i c u l t and remains open. Several applications of the Decomposition Theorem are also given. In Chapter II, we concentrate on the diagonals with maximum diagonal sum h and the diagonals with minimum diagonal sum k . We obtain the best possible bounds for entries on these diagonals and for various kinds of functions of h and k . The key w i l l be a Covering Theorem that enables us to analyze the cases when those bounds are attained. A conjecture is given. In Chapter III, we study the properties of the h-function and the k-function, the functions that associate with each d.s. matrix i t s maximum and minimum diagonal sums respectively. In particular, we investigate the behavior of these functions on the Kronecker product of d.s. matrices. Furthermore, we show that the h-function is very similar to the rank function A e fi^ , h(A) <_ p (A) M. Marcus and H. Mine. p in many respects. and per (A) <^ {b ^ We also prove that for }^ A conjecture is given. which improves a result by INTRODUCTION CHAPTER CHAPTER 1 I : DIAGONAL SUMS OF d.s. MATRICES 6 II : MAXIMUM AND MINIMUM DIAGONAL SUMS OF d.s. CHAPTER III : PROPERTIES OF THE h-FUNCTION AND THE k-FUNCTION OF d.s. BIBLIOGRAPHY MATRICES MATRICES 24 51 71 ACKNOWLEDGEMENT I am deeply indebted to my supervisor, Dr. R. Westwick for rending geneous assistance and invaluable guidance throughout the research and preparation of this thesis. My further thanks are due to Dr. B. N. Moyls, Dr. D. C. Murdoch, and Dr. A. Adler who carefully read the draft of this thesis and gave helpful suggestions and criticisms. The financial support of the National Research Council of Canada and the University of British Columbia is gratefully acknowledged. I dedicate this work to my wife for her constant encouragements during my research and for her excellent typing of this thesis. INTRODUCTION Let If a A is any nxn matrix and l o ( l ) ' a 2o(2)' to 0" . denote the f u l l symmetric group of degree 3 na(n) , then the sequence of elements ac "*"S c a ^ e d t n e diagonal of A corresponding Following the usual convention, we shall use both the permutation a n . a to denote and the diagonal corresponding to i t . If a is the identity permutation, then the diagonal corresponding to i t is called the main diagonal of a. , . s =1 ia(i) , i=l, 2, A . If for some n , and a.. = 0 ij a e , otherwise, then A is called a permutation matrix. If a is a diagonal of A , then the sum n £ -£0(-j\ ^ s called the diagonal sum of a . Diagonal product is i=l a defined in a similar way. An n-square real matrix A = (a..) , where 1J for a l l i , j = 1, 2, n 0 < a. . < 1 - ij ~ is called row stochastic i f each row sum is one, column stochastic i f each column sum is one, stochastic i f i t is either row stochastic or column stochastic and doubly stochastic i f i t is both row stochastic and column stochastic. The fundamental theorem in the theory of doubly stochastic matrices is the theorem of Birkhoff [1] which states that the set of a l l n-square doubly stochastic matrices is a convex polyhedron with permutation matrices as vertices. (For more about this theorem, see [15, 18]). Much of the study of doubly stochastic matrices is motivated by the well-known, long-standing and challenging van der Waerden conjecture [22] which states that for per(A) _> n ! / n n with equality i f and only i f A= stochastic matrix with a l l entries equal to 1/n Ae , , the doubly . Here, per denotes the permanent function. Desipte a great deal of effort, this conjecture is s t i l l unsolved though i t is generally believed to be true [13]. has been verified to be true for The conjecture n <_ 5 [4, 5, 16], and many partial results, mainly due to Marcus, Mine and Newman have also been obtained [4, 5, 13, 16]. It has been pointed out by P. Erdos that the following two statements are consequences of the van der Waerden conjecture: n (1) There exists a diagonal a of A such that | | a. /•. \ >. 1/n (2) There exists a diagonal a. . . . > 0 icr(x) that for and for a of i = 1, 2, A such that n . n ) a. , . s > 1 and i=l i a ( 1 ) ~~ In 1958, Marcus and Ree [18] verified (2) by proving n n A e tt , there is a diagonal o* such that ) a. , . s > ) a?. i-1 i a ( l ) ~ i , j = l 1 J a. / < N > 0 ia(x) for i = 1, 2, . . . , n . [10] verified (1) by proving that for Then in 1962, Marcus and Mine A e tt , n with equality i f and only i f A= n max | | a. a i=l , . . _> 1/n . Erdos' observation and the proofs furnished by Marcus, Mine, and Ree suggested that local properties such as diagonal sum (as well as diagonal product) are closely related to the structure of doubly stochastic matrices. sum is As an extreme case, notice that i f any diagonal n , then the doubly stochastic matrix must be a permutation matrix. A less t r i v i a l proposition, which w i l l be used frequently in this work, also illustrates Proposition: If A e ft^ , then n max V a. / > N _ . i ia(i) aeS i=l n n min Y a, , . x ceS 1-1 l a ( l ) n (i) (ii) > 1 with equality i f and only i f — J J A= J < 1 with equality i f and only i f " A= J Since for only i f a^j = 1/n A = J"n , (i) (ii) this point. Ae Q for a l l N n n , Y a?. > 1 with equality i f and i,J=l J i , j = 1, 2, n , i . e . , i f and only i f is an immediate consequence of Marcus and Ree's result, follows by applying (i) to the doubly stochastic matrix B = (nJ n - A)/(n - 1) . As we w i l l see later, the above proposition can also be obtained independently as a corollary of one of our theorems (Theorem 1.3) With this picture in mind, the main purpose of this work is to study some combinatorial properties of the diagonal sums of doubly stochastic matrices. The starting point w i l l be the theorem of Marcus and Mine [10] which states that i f (n-l)(n-l)! A = J . AeQ n has more than diagonals with a common non-zero diagonal product, then In Chapter I, we f i r s t show that the above theorem s t i l l holds i f we replace "non-zero diagonal product" by "diagonal sum". we pose this question, "For Ae n Then , what is the maximum number of diagonals with sum greater than one and what is the maximum number of diagonals with sum less than one?" To answer this question, we obtain a decomposition theorem (Theorem 1.11) which shows that this common maximum number is again significant, result. (n-1)(n-1)! , a somewhat surprising, i f not This theorem also enables us to characterize completely the structure of a doubly stochastic matrix when i t has precisely (n-1)(n-1)! diagonals with a common sum decomposition theorem gives no information for a a = 1 / 1 . The in which case the question becomes more d i f f i c u l t and we are only able to obtain partial answer. Several consequences of this theorem are also derived. In Chapter II, we confine ourselves to the diagonals with maximum diagonal sum h and the diagonals with minimum diagonal sum k. The key w i l l be a covering theorem (Theorem 2.3) which enables us to obtain the best possible bounds for entries on these diagonals and for various kinds of functions of these bounds are attained. h and k , and to analyze the cases when When investigating the lower bound for h + k , a conjecture (Conjecture 2.21) naturally presents i t s e l f . In Chapter III, we study the properties of the h-function and the k-function, the functions that associate with each doubly stochastic matrix its maximum and minimum diagonal sum respectively. In particular, we show that the h-function is convex and is very similar to the rank function p in many respects. We also investigate the behavior of these functions on the Kronecker product of doubly stochastic matrices. Furthermore, we prove that for per(A) <_ {h(A)/n}2 A e fiR > h(A) £ p(A) which improves a result of Marcus and Mine [ l l j . We also make the conjecture that the h-function defined on Sylvester's for and law for the rank function, i . e . , obeys h(A) + h(B) - h(AB) j< n A,B e £2 . n On the whole, our study w i l l be of a combinatorial nature. In particular, we w i l l apply twice in this work (cf. Theorem 2.13 and Proposition 3.18) the well-known theorem of P. Hall [20] on systems of distinct representatives which states that the subsets S^, S2, • • • » S^ of a set i f and only i f for each k terms such that |S 1 US 2 S have a system of distinct k = 1, 2, 1 <_ a>^ < U " * U S | > k . k < ••• < n representatives and for a l l sequences _< n , i t is true that u of CHAPTER I DIADONAL SUMS OF d.s. MATRICES In this chapter, we show that for d.s. matrices unequal to J r , the maximum number of diagonals that can have a common sum is (n-1) (n-1)! . We then pose the questions, "For A e °, , what is the maximum number of diagonals with sum greater than one and what is maximum number of diagonals with sum less than one?" the To answer these questions, we obtain a decomposition theorem which shows that the answers to both questions are again (n-1)(n-1)! . This theorem also enables us to characterize completely the structure of a d.s. matrix when there are precisely a ^ 1 . For (n-1)(n-1)! diagonals with a common sum a = 1 , the question is more difficult and remains open. In [10], Marcus and Mine proved the following results: Lemma 1.1: (n-1)(n-1)! Theorem 1.2: Let A be an nxn matrix such that more than diagonals have a common non-zero product. Let A E tt n be such that more than have a common non-zero product. Then A= Then p(A) = 1 . (n-1)(n 1)! diagonal . We begin this chapter by obtaining, using Lemma 1.1, an analogue of Theorem 1.2 concerning the diagonal sums of d.s. Theorem 1.3: Let have a common sum. A e tt be such that more than n Then A=J n matrices. (n-1)(n-1)! diagonal Proof: Let B = (b..) ij all as: i,j a denote the common diagonal sum. b. . - exp(a..) . ij ij = 1, 2, n . Then Hence b,. > 0 ij n £n I I b i=i II b. ..v = exp(a) ^ 0 Lemma 1.1, p(B) = 1 for more than Define the matrix and £n b. . = a., ij iJ n , . = Y a lCT ^ -' 1 . . = a OK^-) (n-l)(n-l)! diagonals and hence there Is one row of Hence exp (a = exp(a i n )/exp(a l n ) = a. > 0 or = a. - a, = Zn (a.) = 8. in In i i n n £ a. . = n 8. + £ 1 j=l 1 J j=l 8. = 0 or a i = 2, 3, for a l l ± a.. . ±1 n . . , a±2 = a^, n Proof: have of i t , exp(a i 2 )/exp(a 1 2 ) = • • • = = a.2 - a 1 2 = . . . = ±± i=2, 3, • • • , n . • • •, a ± a - n Since each column sum of n a lj Let A e o, . = i Then n A= J By Therefore, A is one, we get D r l for a l l n A is also one, we get, a „ = an „ = • • • = a, = 1/n , 11 12 In n Corollary 1.4: iff - a • B , the 1st row Since each row sum of j = 1, 2, • • • » n , A= J ±± for each J Hence a = a 1 3 = a 1 ) /expia^) or X say, such that every other row is a scalar multiple i = 2, 3, . . . , n . for II aeS . n Y a. i=l l a n ( l ) < 1 , with equality " By the elementary arithmetic-geometric inequality, we TT I a . 0 i=l l o = (n!/n!) t n ( = 1 . l ) <( - 7 I I a. 0 i-1 We have equality i f f = U- (n-l)! j[ a..)n! = l i,j=l J n n £ I j_ ^ a g 1 a r e J equal for a l l diagonals a , and hence i f f A= J n The next corollary w i l l be used frequently. Corollary 1.5: Let Ae ft Then n (i) (ii) max Y a . v , . N > 1 with equality i f f oeS i=l n n A= J min Y a. asS i i i n A= J l (i) Proof: n l ) < 1 with equality i f f ~ Since n £ a. . = n! i,j=l 1 J Y a. ± ( n! • max cr = (n-1)! iff a ^ ,.N , we get n Y a. ^ io , ... > Y Y a. (I) - £ ^ n max £ a. • . \ >. 1 • a i=i are equal for a l l diagonals ... = io (I) Equality holds a and hence i f f A n 10 (l) The proof of ( i i ) is similar. The next theorem is an analogue to a result of Sinkhorn and Knopp [21, corollary 4]. Theorem 1.6: Let A,B e Qn corresponding diagonals of Proof: (n-1) (n-1).' Put Remark 1.7: Therefore (i) A and (n-1)(n-1)! B have equal sums. C = — (A-B + n J ) . n n diagonals of by Theorem 1.3. be such that more than Then Then Ce Q n C have the common sum one. A= B . and more than Hence C= J A= B . The number (n-1)(n-1)! n in Theorem 1.2 and 1.3 above is best possible in the sense that i t is attainable for a l l n A= where clearly 0 <_ x,y,z _< 1 Ae . y z • • y z are such that ••• • ••• A(x, y, z) . If we choose x, y, (x,y,z)-matrix, and denote i t and x A 4 3^ and there are x, y, x + (n-l)z ? 2y + (n-2)z has precisely and z (n-1)! xz11 ^ ( i . e . , 2y ± x + z) , then (n-1)(n-1)! y2zn 2 ^ xz" ^ diagonals passing and (n-1) (n-1) ! y2zn 2 . such that A ? J n a n d A diagonals with the common sum 2y + (n-2)z . In fact, we shall prove later on that i f (n-1)(n-1)! such that with the common non-zero product Similarly, i f we choose A e £2^ has precisely diagonals with a common sum a ^ 1 , then for some suitable choices of (ii) z x with the common non-zero product diagonals missing Then Since this particular matrix w i l l be considered ( i . e . , y 2 f xz) , then through z x + (n-l)y = y + (n-l)z = 1 . frequently in the sequel, we c a l l i t a by z x, y, and A = A(x, y, z) z . Later on we shall show via a decomposition theorem that Theorem 1.3 and Theorem 1.6 are in fact equivalent. (iii) In Theorem 1.6, the assumption "corresponding" is clearly indispensable for we can always permute the rows and columns of to get B£ A. Obviously, A and A e ^n B have a l l the diagonal sums equal (not corresponding diagonals). Furthermore, the number in Theorem 1.6 is attained for n = 3 . For example, let (n-1)(n-1)! A= » B = 1/2 1/3 1/6' 1/6 1/2 1/3 1/3 1/6 1/2 Then A ^ B , and there are precisely 4 corresponding diagonals with equal sums. that the number (n-1)(n-1)! However, we are unable to show is attained for a l l n or for any n ^ 4. The next proposition shows that this question is equivalent to the existence of a d.s. matrix having precisely (n-1)(n-1)! diagonals with the common sum one. Proposition 1.8: (i) There exist The following two statements are equivalent. A,B e , Af B corresponding diagonals of ( i i ) There exists Ce n such that precisely A and (n-1)(n-1)! B have equal sums. with precisely (n-1)(n-1)! diagonals having sum one. Proof: and, since (i) => ( i i ) . A ^ B , C f 3^ . Put C = — (A - B + nJ ) . n n Since C has at least diagonals with sum one, i t has precisely Then C e Jl n (n-1)(n-1)! (n-1)(n-1)! diagonals with sum one by Theorem 1.3. ( i i ) => (i) . diagonals with sum one, precisely (n-1)(n-1)! Since C f 3_^ C has precisely by Theorem 1.3. (n-1)(n-1)! Now, C and have corresponding diagonals with equal sums. Since for a d.s. matrix A , each row sum and column sum is identically one, i t is natural to ask the following questions, "How many diagonals of A can have sums greater than one, and how many diagonals of we A can have sums smaller than one?" In the following, shall obtain a decomposition theorem from which the answers to both questions follow immediately. Since this theorem is a combinatorial theorem concerning the positions in a matrix without reference to the actual entries, we find i t convenient to extend the notion of diagonal as follows: Definition 1.9: a e S^ . Let By a a-diagonal or simply a diagonal we mean the set of ordered pairs Two diagonals a i = 1, 2, n , and x {(i, cr(i)); i = 1, 2, n} are said to be disjoint i f for a l l a(i) f T(1) . A collection mutually disjoint collection i f for a l l E of diagonals is a a,TeE, a^x, a and x are disjoint. Definition 1.10: matrix of E . A collection A i f each entry of If, in addition, A appears in at least one of the diagonals E is a mutually disjoint collection, then we say the covering is exact. collection E Theorem 1.11: E of diagonals is said to cover a It is clear that a mutually disjoint of diagonals covers A exactly i f f |E| = n . (Decomposition Theorem for the set of a l l diagonals.) Let D be the set of a l l diagonals of order there exists a decomposition of subsets each containing D into (n-l)! n . Then mutually disjoint n mutually disjoint diagonals. Proof; G = Let O e be any f u l l cycle permutation, and let Q be the cyclic subgroup of order <0 > Q Consider the class of a l l (left) cosets |aG| = |0| = n for a l l a e S n generated by . a E S . Since n \ \aG\ = |S | =n! , where the and aG of a G, a summation is taken over a complete set of coset representatives is clear that there are since a Q (n-1)! such (disjoint) cosets. is a f u l l cycle, we have, for each for a l l e g^'^l G » c in each coset are mutually disjoint. E S n " i = 1, 2, T n e r e f°re> , it Furthermore, n , that (ag-^ (i) = (ag 2 )(i) => a(g-L(i)) = a(g 2 (i)) => g 1 (i) = g 2 (i) ~> crg-^ = ag 2 c => g = g2 ± = > the diagonals This completes the proof. As an immediate application, we have the following: Theorem 1.12: Let m be an integer, 1 —< m —< n . Let K be the m smallest positive integer with the property that any collection of diagonals would contain Proof: Let m disjoint ones. Then Km = (m-1)(n-1)! + 1 . E be a collection of diagonals such that |E| _> (m-1) (n-1)! + 1 . Let D = D 1 \j T> <J • • • \j u(n_-jj j decomposition of the set D of a l l diagonals as described in Theorem 1.11. By the pigeon-hole principle, 1 _< i _< (n-1)! , Since follows. 2 |E H D^| >^m for otherwise for some On the other hand, let |F| = (m-1)(n-1)! . a^ Clearly, e a i , |E| _< (m-1) (n-1) ! , a contradiction. is a mutually disjoint collection, passing through any one of b F be the collection of a l l diagonals , i = 1, 2, F <_ (m-1) (n-1) ! + 1 m-1 . does not contain Then m mutually disjoint diagonals for otherwise the pigeon-hole principle would imply that some two of these disjoint diagonals must pass through the smae some i , which is obviously absurd. Therefore, Let number of diagonals of one, respectively. A e ft . n Let If and A (A) > (n-l)(n-l)! + 1 n — Hence and 6 (A) n be the maximum 6 = max 6 (A) . Aeft n Then This bound is always attainable, Since they cover contradiction. A (A) n A = max A (A) Aeft n Theorem 1.12, we can select sum > 1 . Let A with sums greater than one, and smaller than A = <5 = (n-l)(n-l)! . n n Proof: for Hence K > (m-1)(n-l)! + 1 . m — K = (m-1)(n-l)! + 1 . m Corollary 1.13: * a^ for some A e ft , then by n n mutually disjoint diagonals each having n A exactly, we get £ a.. > n , a A n <_ (n-l) (n-l) ! . Similarly, 6^ <_ (n-l) (n-l) ! . To see that this bound is always attainable, consider the d.s. matrices A(0, l / ( n - l ) , (n-2)/(n-l) 2 ) Remark 1.7.(i)). and A ( l , 0, l/(n-l)) In both cases, there are precisely diagonals with sum 2y + (n-2)z , which is equal to in the f i r s t case and (n-2)/(n-l) in the second. respectively (cf. (n-l)(n-l)! [(n-l) 2 + l ] / ( n - l ) 2 This completes the proof. In [10], i t was shown that for any d.s. matrix n max I I a. II ia(i) aeSn i-1 > 1/nn - . A, The next corollary is now clear from the elementary arithmetic-geometric inequality and Corollary 1.13 above. Corollary 1.14: Let Aeft can have diagonal product > . Then at most n l/n* 1 . (n-l) (n-l) ! diagonals We mention that Corollaries 1.13 and 1.14 are in fact true for the class of stochastic matrices. As another immediate application of the. Decomposition Theorem, we show that Theorem 1.3 and Theorem 1.6 are indeed equivalent. Theorem 1.15: (Remark 1 . 7 . ( i i ) . ) The following two statements for d.s. matrices are equivalent. (i) If A e ft^ has more than sum, then (n-l)(n-l)! diagonals with a common A= J n (ii) If A,B e ft^ have more than with equal sum, then Proof: (i) => ( i i ) . (ii) => (i) . (n-l)(n-1)! have more than A = Jn For n max aeS V i=l a. ... > 1 n both) equality i f f a > 1 This is just Theorem 1.6. Let or Aeft n a < 1 . (n-l)(n-l)! by (ii) Aeft and A= . n corresponding diagonals A= B . be such that more than diagonals have the common sum a i t is impossible that Therefore (n-l) (n-l)! . Then by Corollary 1.13, Hence a = 1 and so corresponding diagonals with equal sum. This completes the proof. , we have seen (Corollary 1.5) min aeS . A and n Y i-i a. ... < 1 with e i t h e r Regarding Corollary 1.13, that (and hence the follox^ing question naturally presents i t s e l f . "If maximum number A (A) n a of diagonals b what is the maximum number Sn(A) n . . < 1 ?" .Y -i a.ix .(I) _ A = n Let i=l A E ft , A f J , what is the n such that Y a. . . . > 1 , and io (1) - ° f diagonals _ max A (A) nv ' Asft ^{J } n n It can be easily seen that for n = 2 , A2 = such that T _ and ^ n 1 • = however, the question seems to be quite d i f f i c u l t . the following matrices show that A = "1/2 1/3 1/6" 1/6 1/2 1/3 1/3 1/6 l/2_ , A 3 = 6 = 5 . 3 "1/2 1/4 1/4 1/4 1/2 1/4 _l/4 1/4 1/2 B A =6 n n obtain an upper bound for this value in general. n ] Proof: A f J n - iff n Y a. . . . ^ ia(i) E n = 2 and where n This bound is n = 3 . nJ - A A e ft , i t is clear that z— E n n - 1 n > 1 iff r — ± J . Since Y a. . . . n-1 n ^ xa (l) For any nJ - A J n-1 Let n— denotes the greatest integral part function. attained for and T T / -I \ / -i \ i i r ( n - l ) (n-1) ! , A = <5 < (n-1) (n-1) ! + [— —1 c [ 1 ° general, When n = 3, for In the next proposition, we show that T. i Proposition 1.16: _ max 6~ (A) .n rT , n Asft ^{J } n n 6~ = < 1 , i t follows that — A =6 . n n Since A 4- J n Now, let ft n and that A E ft , A 4 J . n n , we have, by Theorem 1.3 that | E| <_ (n-1) (n-1)! . Let D= D (J D £ U " " U ± D (n_i)j b e a decomposition of the set D of a l l diagonals as stated in Theorem 1.11. Let D.'s such that m m be the number of 1 < r (n-l) (n-1)! j ^ — n e a c h one diagonal with sum < 1 . (n-1)! - [ ^ n A n ± n! n = 2 '] l Hence there are at least diagonals with sum < 1 . -{(n-1)! - [(n-D (n-1) 1 j| and n = 3 , we get Remark 1.17; g u c h A2 = ^2 = ( n = 1 (n-1) (n-1) ! + [ ( n " 1 ) ( - n ~ 1 ) ! ] = 22 . where 1 } ( n a n d _ 1 } , + (n-1) (n-1) 1 { } A^ = < 5^ = 5 For x + y = 1/2 , and ^ f Q T respectively. n = 4 , The best we can get for n so far is 20 as shown by the matrix below: X y X y y X y X X y X y y X y X x > 1/4 , y < 1/4 . there are 16 diagonals with sum 4x > 1 _ Therefore, We are unable to determine i f the bound given in the above proposition is attainable in general. 6.(A) D . C E . Then l t h a ( . D_ < £ E there is at least l 4 Then A , (A) and H Ae , A± and 2x + 2y = 1 , 4 diagonals with sum diagonals with sum 4y < 1 . Hence A^(A) = <5^ (A) = 20 . In what follows, we w i l l derive more consequences of the Decomposition Theorem. Proposition 1.18: remaining Let (n-l)! Aeft . n If A (A) = (n-l)(n-l)! , n diagonals must have sums s t r i c t l y less than one and i f 6 ( A ) = (n-l)(n-l)! , then the remaining (n-l)! r sums s t r i c t l y greater than one. Proof: Let Let D= E = (a I T I it=i U' n 2 U • • • U Theorem 1.11. If diagonals must have (For notations, cf. Corollary 1.13.) a. , . ^ , D. C E for any . > ll s J Then so are the = |E (1 ( (n-l)(n-l)!. i , then since D. covers A l exactly, we get a contradiction. or I El = be a decomposition as stated in l D. <£. E then the |E fl D.l < n - l . E O D_^'s . Hence Hence for a l l i = 1, 2, Furthermore, since the D.'s (n-l)! , are disjoint, (n-l) (n-l)! = | E| = |E H D| = (n-l)! (n-l)! (n-l)! U D.)| = | U (E fl D.) I = I |E n D.| < (n-l)(n-l)!. Thus 1 1 1 1=1 1=1 1=1 |E n D j = n - l for a l l i = 1, 2, there is exactly one diagonal exactly, these cr^'s e (n-l)! . ^ E . Therefore, for each Since each must have sum s t r i c t l y less than one. assertion follows by a parallel argument. (n-l)(n-l)! covers A The other This completes the proof. We are now in a position to characterize a l l matrices that have precisely i, nxn d.s. diagonals with the common sum a * 1 . Lemma 1.19: If Aeft n has precisely common sum a ^ 1 , then the remaining common sum which is 8 = n - (n-l)a f a (n-l)(n-l)! (n-l)! diagonals with the diagonals also have a Let Proof: E = {\ a ; £T= 1 a. ... = at w ( i ) j . Then I El = (n-l) (n-l)! . Following the notations and arguments given in Proposition 1.18, we get | E H D\| = n - l for a l l j = 1, 2, (n-l)! , and hence for each there is exactly one a.c D. % E . J n y a. Since D. J . . . = n - (n-l)a covers j , A exactly, J for a l l i = 1, 2, (n-l)! . Since a ^ 1, ill ^ j W i t is clear that Theorem 1.20: If g ^a Ae has precisely (n-l)(n-l)! diagonals with the common sum a £ 1 , then there exist permutation matrices such that for some suitable choices of x, y and z , P and Q PAQ = A(x, y, z). (cf. Remark 1.7.(i).) Since by Lemma 1.19, A has only 2 distinct values Proof: 3 a and for diagonal sums, a theorem by J. Kapoor ([7], Theorem 2.15) implies that there exist permutation matrices k , 1 < k < n such that PAQ or (g-n)+Xn-H51 ($-a)+\ +6 n A e ftn , k 1+ Xn +5,k X X +6 n n X..-H nX.+ k ± l*k n-l k-1 n-l k X ,+S n-l n I n n ^ 5± = 1 has the following form: Xn-1.+5, 2 +5 X 6_ 1 Q and a positive integer Xn-lT+5 1 i2 x (B-a)+X +S _ Since (PAQ)fc X 1 +6 1 2 n P and for a l l j = 1, 2, n-l . Hence X (0tt) + ( I i=l for some A -= A n-l X .) + n < 5 . = 1 1 for a l l n 5. + Also J From Similarly, j = 1, 2, • • • , k-1 . J A. = 1 i=l for all for some 6 j = k, k+1, •••, n . n 6 . - nfi - (3-a) =0 1 (PAQ)1" for a l l j = k, k+1, (3) •> n . or 6 . = 6 + -(3-a) = 6 ' 3 n Consequently, PAQ or takes the form: (B-a)+A +5 A+6 A+5 (3-a)+A +5 n A+5 A+5 (3~a)+A +6 n X +5 ' n A+6 n A +5 ' n For convenience, put and (2) 1 (1) , (2) and (3) , for some 6' (1) J 6i=60-=*--=61 , = 6 1 2 k-1 Hence . z = A + 61 . • • • A+5 ' A+5 * A+5 ' A+S ' x=(3~a)+An + 6 Then PAQ or x A+5 (PAQ)fc , -» (k-l)th row y=A+6 > y' = A + 5' , becomes y -» (k-l)th row y" z Clearly, this matrix has two distinct diagonal sums values: there are (k-1)(n-1)! diagonals passing through some x + (k-2)y + (n-k+l)z y' and (n-k+1)(n-1)! with sum y' + (n-k)z + (k-l)y . precisely (n-1)(n-1)! k-1 = n-1 or PAQ or Since diagonals passing through some Since, by assumption, there are diagonals with the same sum, we have either n-k+1 = n-1 . (PAQ)t x with sum Hence k = n or k = 2 . For k = n , becomes A e ft , we have n x y y x y y x y y ••• y y' z z ••• z x = z and hence after permuting the rows, the matrix becomes y x x y x y Since this matrix is symmetric, we can conclude that for some permutation matrices P' and Q' , P'AQ' = A(y', x, y) . For k = 2 , PAQ = (PAQ)*" becomes Since A e ft^ , we have x y ••• y y' z ••• z • • y' z y = y' . • •• • zJ Therefore, PAQ = A(x, y, z) As an application of the above theorem, we have: Corollary 1.21: If A e ft has precisely with the common sum a 4 1 , then Conversely, given an}' exists a matrix 41 a 1- , with . diagonals \ < a < 1 + —,—\s? n-1 — — (n-l) z 1- ±_ a <_ 1 + A e ftn that has precisely the common sum a (n-1) (n-1) ! (3j_)2 n- (n-1)(n-1)! > there diagonals with This matrix is unique up to permutation of rows and columns. If A e Q has precisely (n-1)(n-1)! diagonals with the n common sum a ^ 1 , then by Theorem 1.20, there exist permutation matrices Proof: P and Q such that PAQ = A(x, y, z) = for some y = 1-x " n^I ' ( n x, y, Z = and z . 1-y n^l x y y z Since _x + (n-l)y = y + (n-l)z = 1 , we have n+x-2 Tn^lp- " „ H e n C £ a „ ,, =? ^ 2 + _ ^ C 2 ( l - x ) (n-1) + (n-2) (n+x-2)} = 1 a ( attains i t s maximum 1 + ( _"jj2 6 precisely a n c n ^-r when x = 0 and x = 1 respectively. n-1 be given with „v = [n2-2n+2-nx> = 1 + * ~ " * ) 2 Consequently, z 1 < a < 1 + —\TT . n-1 — (n-1)(n-1)! — * t s . minimum Conversely, let a ^ 1 A matrix A E8 (n-l) z that has n diagonals with a common sum a of Theorem 1.20, equivalent to A(x, y, z) l 2 for some must be, i n view x, y, and z via x + (n-l)y = 1 , (4) y + (n-l)z = 1 , (5) 2y + (n-2)z = a . (6) 2 - a From (5) and (6), we get into (5), we get y = z = a < 2 . since Substitute this (n-l)a >_ n-2 . x = 1 - (n-l) + 2 ( n ~ 1 ) 2 a(n-l) 2 < (n-l) 2 + 1 . n A(x, y, z) since { (2-n) + (n-l)a) >_ 0 Substitute this into (4), we get > 2 - n + ^n — = 0 since — n > 0 " a(n-l) 2 ^ Hence the matrix — where x = (2-n) + ( n - l ) 2 ( 2 ~ a ) , y = ^ {(2-n) + (n-l)a> , 2 - a and z = —-— is d.s. and has precisely the common sum a . (n-l)(n-l)! diagonals with This proves both the existence and uniqueness up to permutation of rows and columns. Remark 1.22: (i) Corollary 1.21 above shows that the bound given in Theorem 1.3, though best possible in general, is not uniform in the sense that i f the value a ^ 1 of the common diagonal sum does not belong to the interval n—2 1 [—r- , 1 + -,—7-rrr] z n-l (n-l) be attained. Consequently, a better (smaller) bound depending on the value of a should be expected. , then the bound (n-l) (n-l) ! can not To get an explicit formula for such a bound, however, seems to be d i f f i c u l t . For instance, i t is intuively clear (though a simple and rigorous proof using the Konig-Frobenius theorem [6, 8] can be given) that for zero diagonals is e.g. value [20], p. 22). D n for AE , the maximum number of - the number of derangements of n object. (cf. An explicit formula, i f i t exists, must then give the a = 0 . (ii) Theorem 1.20 and Corollary 1.21 above do not hold for a = 1 . In fact, the example given in Remark 1.7.(i) is not valid for since 2y + (n-2)z = 1 implies x=y=z are equal to one. or a = 1 together with y + (n-l)z = 1 = x + (n-l)y A = Jn A= . For Hence, excluding , clearly a l l diagonal sums , we can ask the question: is the maximum number of diagonals with sum one?" The bound "What (n-l)(n-l)! s t i l l holds in general, but we are unable to construct examples to show that this bound is attained for a l l n = 3 , the matrix attained. For n . (cf. Proposition 1.8) For B given in Remark 1 . 7 . ( i i i ) shows that this bound is n = 4 , the best example we can get is the one given in Remark 1.17 which gives 16, rather than 18, diagonals with sum one. We close this chapter by giving a proposition that answers partially the problem mentioned in Remark 1.22.(i) above. Proposition 1.23: such that 1 < a <^ n . Let A e ft^ and let Then at most have diagonal sums >_ a , where Proof: sums >_ a be a given real number (m-1)(n-l)! diagonals of A can m = [^] + 1 . Suppose more than . a (m-1)(n-l)! diagonals of A have Then by Theorem 1.12, we can select from them m mutually disjoint ones with total sum > ma = a([—1 + 1) > a(—) = n , a — a a ' contradiction. CHAPTER II MAXIMUM AND MINIMUM DIAGONAL SUM OF d.s. MATRICES The purpose of this chapter is to carry out a combinatorial investigation of the diagonals with maximum diagonal sum h diagonals with minimum diagonal sum k . and the First, we obtain the best possible upper and lower bounds for entries on these diagonals. Secondly, we obtain the best possible upper and lower bounds for various kinds of functions of h and k . The key w i l l be a covering theorem that enables us to analyze the cases when these bounds are attained. lower bound for itself. given. When studying the h+k , an interesting combinatorial question presents Concerning this question, a conjecture and partial solutions are Finally, we obtain the bounds for h and k when the d.s. matrices under consideration have properties discussed in Chapter I. Throughout, we shall use matrix case for A >_ 0 to mean that a l l the entries of the A are non-negative, and we shall assume that n = 1 Definition 2.1: n ^ 2 , since the is always a t r i v i a l i t y . Let Aeft n . A diagonal a of A is called a maximum diagonal i f its sum is a maximum among a l l diagonal sums of A, and a minimum diagonal i f its sum is a minimum among a l l diagonal sums of A. The f i r s t result gives the upper bound for entries on a minimum diagonal. Proposition diagonal. 2.2: Let Then max a. £ some i and =0 , n> — and l e t a be a minimum with equality i f f n+1 for a l l 3 a. i s the main d i a g o n a l , 2 —-r for n+1 j ^ i . the s e t o f d i a g o n a l sums, we may a . = ICJ(I) J N S i n c e permuting the rows and columns o f affect that io" ( l ) ~ a. Proof: A e 9, n 2 ... < — — A does n o t assume, w i t h o u t l o s e o f g e n e r a l i t y , and t h a t max a ^ = a ^ . By assumption, a.,.. + a.. < a.. + a.-, f o r a l l i = l , 2, • • • , n . Summing over i , we 11 ix — l i i l ° n n get (n+l)a + 7 a. . < 7 ( a - . + a...) = 2 . Hence a... < - ^ r - w i t h ° 11 i i— l i i l 11 — n+1 i=2 i=l n 1 e q u a l i t y i f f a.. 11 i n+1 , ' a.. = 0 i i and a . + a li i l n n+1 for a l l = 2, 3, • • • , n . Remark 2.3: (i) If (ii) For a l l A n = 2 , the upper bound i s and a 11 and i s a t t a i n e d iff n > 3 , the upper bound i s the b e s t p o s s i b l e . n+1 n+1 1 n+1 0 A = Consider n+1 (n+1)(n-2) = n (n+1)(n-2) n+1 where 1/2 n+1 ' a.. . = a .., il l i n a.. = ij (n+1)(n-2) minimum d i a g o n a l , =—rr , n+1 otherwise. a. . = 0 i i f o r a l l i = 2, 3, n, C l e a r l y , the main d i a g o n a l i s a and i t s maximum e n t r y is ^-_rr . Incidentally, this example also shows that in general the maximum entry of a d.s. matrix can l i e on a minimum diagonal. If we were to apply the argument used in the proof of Proposition 2.2 to a maximum diagonal CT , we should get the lower bound n max a. . . . > 1/n which is t r i v i a l since Y a. . . . > 1 by CorollaryJ 1.5, I lo ( i ; — ^ lo (l) — However, the upper bound for min a. i ,., 10(1) max a. , . . and the lower bound for i can be obtained in terms of the diagonal sum h and the bounds are non-trivial when h <_ 2 . have n-max a. ± i.e., ,. > h > 10(1) - 2-h N 2-h max a. , > i — n and , and 10(1) Since h >_ 1 by Corollary 1.5, we n'min a. i . . . -1 < h-1 10(1) - . (n-l)(h-1) mm a. , < £ — n 10(1) < (n-l) (h-1) , +1 . However, the following stronger results hold. Proposition 2.4: sum h . Then Let (i) A e £2 and let min a. ± ... > 10(1) — .... (11) (i) max a. ... < — Suppose ^r a = min a.. 11 i 11. for a l l i=l, 2, Suppose a ^ = max a ^ . 0 is the main diagonal. By assumption, r ' J n . 1=1 . n As before, assume that nn — 10(1) - n a,, + h > Y (an . + a.,) 11 —.L, li ii (ii) 2—h n (n-l)(h-1) + 1 ± Proof: 0 be a maximum diagonal with Summing over = 2 , or a..., + a.. > a n . + a., 11 — li ii 11 i , we get a,, > —— . 11 — n By assumption, for each fixed j = 1, 2, • • • , n . y ( a . . +a..) Summing o v e r a l l j ^ 1, i , 7 < (n-2)a.. + a.. 2 - a,. - a.. - 2a.. < ( n - 2 ) a . . + 7 1i i l ii i i fi jrl,i 7 2 - a,. - a... < ( n - 1 ) a . . + li il i i we get n £ (a i=2 2(n-1) - JJ . Summing o v e r a l l i ^ 1 1 1 <_ 2 ( n - l ) ( h - a.^) u a^ a.. X <_ ^ { (n-1) (h-1) + 1} . or JJ + a. ) <_ 2(n-1) £ j£L 1 1 2 ( n - l ) - (2 - 2 a ) J get , or a.. ; n we . a.. , or 2 2 S i m p l i f y i n g , we get T h i s completes the p r o o f . I f we c o n s i d e r a minimum d i a g o n a l a i n s t e a d , the same argument as above y i e l d s : P r o p o s i t i o n 2.5: sum k . Let A e ft^ , and l e t a • ( l ) mm Then ± a. ... > ia (l) - (ii) max i aa..... ,.. ^< ia(i) — Since 1 U d A and 0 1 ~ 2-k n be a minimum d i a g o n a l w i (n-D(l-k) n . a r e the upper and l o w e r bound, 2 h — r e s p e c t i v e l y , f o r any e n t r y o f a d.s. m a t r i x , and s i n c e h < 2 — i f f ( n 1 ) ( 1) n n + i < ^ — P r o p o s i t i o n 2.4 >_ 0 i f f can be r e s t a t e d as follows: Proposition w i t h sum 2.6: h . Then Let A e ft , and l e t a n be a maximum d i a g o n a l (1) mm ± 10(1) a. ,.. > 2 _ h if h < 2 0 if h > 2 - ( h (ix) 10(1) max a. ... i S i m i l a r l y , since and 2-k 2 < —-rn — n+1 < - - 1 } + 1 if h < 2 1 if h > 2 - { 1 - (n-l)(1-k)} > 0 n — . i f f k> — n—1 2 i f f — — < k , Propositions 2.2 and 2.4 can be put n+1 — together and restated i n : Proposition 2.7: sum k . Let A e ft , and l e t 0 n be a minimum diagonal with 0 Then 1 (i) (ii) 10(1) - - fa"1) ^ i f k>2-2 _ 0 ._ , n—2 i f k < —-— n-l n min a. ... > i 10(1) < — 2-k n — n-l ... 2 if k > - n+1 max a. ,.. ± n+1 if 2 k < - n+1 Clearly, ( i i ) above i s a refinement of Proposition 2.2. In the following examples, we discuss the case of equality f o r the bounds given i n Propositions 2.6 and 2.7 f o r a r b i t r a r i l y preassigned h and k . values of Example 2.8: Let h be a given number such that Consider the d.s. matrix y = J 2-h n and z = j A = A(x, y, z) n + h- 2 -,—-r n(n-l) with 1 <_ h <_ 2 . x = fa-1)(h-1) + 1 ^ ; i.e., ' ' (n-1)(h-l)+l n 2-h n 2-h n 2-h n n+h-2 n(n-l) n+h-2 n(n-l) 2-h n n+h-2 n(n-l) n+h-2 n(n-l) A = Then n £ a_„ = h , and any diagonal missing i=l 2 (2-h) J (n-2) (n+h-2) n-h 1 ;— = —~- < 1 < h . n n(n-l) n-1 — — maximum diagonal with sum h . a^ . . Hence the mam diagonal is a TT Finally, (n-1)(h-1) + 1 _ (n-1)2(h-1) + (n-1) (h-1) + (n-1) _ n + h n(n-l) n(n-l) n(n-l) max a.. = a,, _ (n-1)(h-1) + 1 i ii 11 n . I f matrices are examples for which has sum implies that h > 2 , then the permutation max a. , = 1 . Hence the upper bound ia(i) ± in Proposition 2.6 is always attainable. Remark 2.9: two cases: If we consider the lower bound in Proposition 2.7 we have (i) 0 < k< n-2 n-1 provide examples for which r r In this case, permutation matrices min a. . . . =0 i io(l) this case, Example 2.8 above with change from h > 1 to k < 1 h . n— 2 (ii) — r < k < 1 . n-1 replaced by k In suffices since a merely reverses a l l the inequalities therein and consequently the main diagonal becomes a minimum diagonal and mm a. . = a,, 11 11 is always 1 - (n-l) q-k.) Hence the lower bound in Proposition 2.7 n attainable. Example 2.10: Let n 3 and let k be a given number such that o n+1 <- k < 1 . where a Consider the d.s. matrix 2-k n n+k-2 n(n-l) n+k-2 n(n-l) n+k-2 n(n-l) (n+l)k-2 n(n-l) (n2-2n+4)-(n+2)k n(n-l)(n-2) n+k-2 nCn-1) (n2-2h+4)-(n+2)k n(n-l) (n-2) (n+l)k-2 n(n-l) 11 2-k n „ o i = 2, 3, • • • , n , > a ,--- = ii „ and a.. = ij (n+l)k - 2 >_ 0 , and since n2-2n+4>n+2> (n+l)k - 2 n(n-l) (n2-2n+4) - (n+2)k fc, —-^r-,— — otherwise. n(n-l)(n-2) n 2 - 3n + 2 = (n-l) (n-2) >_ 0 (n+2)k , we have computations show that indeed 2 - k ^ (n+l)k - 2 = + . n + k n(n-l) a.. . = a. 1 li ii A> 0 . Aeft 2-k . for a l l Since implies that Straightforward ][ a. . = i=l , (n+l)k - 2 _ 2(n+k-2) , - K. , Furthermore, -,—TT T - T rr— , ana n n n n(n-l) n(n-l) (n2-2n+4) - (n+2)k (n+l)k - 2 n(l-k) _ „ . ,. . 2 -, k> 0 (n+l)k - 2the _ 2(l-k) -. -4—. ^ / ,. = T . Hence mam diagonal is a minimum diagonal. Finally, since n(n-l) n-l n(n-l)(n-2) n(n-l) (n-l)(n-2) n — 2-k we have max a.. = a n 1 The case for n = 2 is easy since ^ ii 11 1 l ll 2-k —-— . . . ^, ^ implies that a^ 2-k —^— W 0 , and a 1 2 = a^ k = ^ . , If T — - — <_ — , then equality holds k >_ 1 . Hence i f f k = 1 . k = 1 that Therefore, the A = H e n c e t h e u p p e r b o u n d i n P r o p o s i t i o n 2.7 i s always a t t a i n a b l e f o r a l l n , provided however, t h e f a c t or max a ia(i) that < k < n+1 2 k >_ --_j^r clearly . 2 I f k < ^-_rr , shows t h a t t h e u p p e r bound i s n o t a t t a i n a b l e . The is equality somewhat c o m p l i c a t e d . case B e f o r e m a k i n g a c o m p l e t e a n a l y s i s , we n e e d a lemma w h i c h g i v e s a n o n - t r i v i a l with "comparatively Let Lemma 2 . 1 1 : Then f o r a l l f o r t h e l o w e r b o u n d i n P r o p o s i t i o n 2.6 lower bound f o r any e n t r y on a d i a g o n a l l a r g e " d i a g o n a l sum A e ft n a and l e t i = 1, 2. a. 1 0 there e x i s t permutation matrices P a b e a d i a g o n a l w i t h sum n + 2 ,.* > (l) - and Q form: n a 2 l - a 2 1-a where Y a. = 1 i-1 1 such that a > n-2 — with equality i f f PAQ takes the Proof: Permuting the rows and columns of may assume that considered. a is the main diagonal and a ^ Let R. and C. 1 1 respectively. is the entry being denote the i t h row sum and column sum n n 2n - 2 = £ (R. + C.) = 2( £ a..) + 1 1=2 1 i=2 1 1 n +2 I a = 2Ox - a ) + (n - a) + 3 irj i,j=2 Then n £ (au + a ) i=2 n 8 = T a.. > 0 . . k „ iJ i — i,J=2 irj + A , i f necessary, we ±1 Therefore 2 a 1 1 = a 11 n + 2 + s _ where , and thus n, I 2 a^^ >_ with equality i f f i f j > i » j = 2, 3, i = 2, 3, • • * , n . described form where n . 3 =0 ; i . e . , i f f Since A is d.s., Therefore, i f we write n 7 a. = 1 . 1=1 1 a. 1 a „ = 0 for a l l a^ = a^ for l a, . , i for a l l A takes the This completes the proof. Now we are in a position to analyze the equality case for the lower bound in Proposition 2.6. Case I: by 1 <_ h <_ 2 . There are two cases to be considered: In this case, Example 2.10 with h suffices provided that n >_ 4 k replaced since then (n2 - 2n + 4) - (n + 2)h >_ (n2 - 2n + 4) - 2(n + 2) = n 2 - 4n >_ 0 and hence A >_ 0 . Furthermore, a change from reverses a l l the inequalities therein. k <_ 1 to h >_ 1 merely Consequently, the main diagonal becomes a maximum diagonal and a^^ becomes a minimum entry thereon. 2—h The case for n = 2 is again easy since h = 1 and hence equality is attained i f f a ^ = ——— implies that h = 1 , i.e., iff The case for n = 3 calls for separate consideration. Since A= • (rg - 2n + 4). - (n + 2)h = 7 - 5h for replaced by h h) s t i l l stands for claim that the equality can not hold. n = 3 , Example 2.10 (with k y . If h > y , however, we Assume the contrary, and let A e ft be such that the main diagonal is a maximum diagonal with sum h, -=• < h < 2 , and that 5 — an .. = min a. . = 11 i ii Proposition 2.4. ( i ) , we see that a 2-h 3 Examining the proof of + a^ = a^ + a^ . Hence A takes the form: 1+h 3 -x 2-h 2-h A = x-y+ But £ a^ = h i=l 1+h x-2y + 3 - x+y 2h-l implies that 1-x-y 3y + l = h this into the matrix, we find that 1+h ~3 1 + x - h > 0 , we get y = 2h-l 2h-l 3 -x 1+x-h 2h-l x >_ h - 1 > - x >_ 0 => x <_ -j (4 - 2h) < — (4 - 2*j) = j On the other hand, , a contradiction. this case, however, Lemma 2.11 gives the lower bound Since Substituting 1+h 3 - x 4-2h Since or l-2h A takes the form: 2-h 3 A= 2y + a ^ >_ n ^ . 7 . h 2 ~* h h > — => —— 1 — > — - — , this bound is a better one. In • (Note that since there is a "gap" between is not even approachable.) , the lower bound n z ^ < ^ ^ ^ h-1 2 3-h 4 3-h 4 3-h 4 h+1 4 0 3-h 4 0 h+1 4 (*•" h <_ 2) . h > 2 . In this case, we claim that the lower bound 0 i t is not attainable for a. 30 ( l ) n = 1, 2, 3, 4.) h — n + 2 > ^ > 0 2 diagonal and hence the lower bound consider the d.s. A = matrix: 0 1 n-1 n-1 , 7X h > -) , h — 1 —^— . in Proposition 2.6.(i) is attainable i f f Lemma 2.11, .. . ( . Hence the main diagonal is a maximum diagonal on which the minimum entry is Case II: —^p- matrix v i- h - 1 , h + 1 3h-l „.3-h. I a.. = h , — — + — r — = — > 2(—-) i=l on. Then and and Furthermore, this new lower bound is the d.s. A= —^ h <_ n-2 . Suppose (Hence in particular, h > n-2 . Then by for a l l entries on this maximum 0 n-1 h n-1 n-h-2 (n-1)(n-2) is not attainable. For n-1 n-h-2 (n-1)(n-2) n-1 h <_ n-2 , where and a... = 0 , a... = a... = —\r , a. . = — ^ r 11 li ii n-l ' n n-l a. . = „ - , w o \ ij (n-l) (n-2) n otherwise. 2 Since straightforward computations show that h n-h-2 n^l ~ (n-l)(n-2) = h(n-l) - (n-2) —(n-l)(n-2)— diagonal with minimum entry n > ' for a l l i = 2, 3, • • • , n , n-h-2 > 0 - , A > 0 and - • A E ft . n . m a i n h 2 —— > —— and n-l n-l Since J . d i a § o n a l 1 S a maximum 0 . Now we can summarize and state the equality case for the lower bound given in Proposition 2.6 in the following: Proposition 2.12: (I) If Let h be a given number such that 1 <_ h < n . 1 <_ h <_ 2 , then there exists a d.s. matrix with maximum diagonal sum h and such that the minimum entry on the diagonal 2—h is (II) iff (i) n = 2 and h = 1 or (ii) n = 3 and h < y or ( i i i ) n >_ 4 . If 2 < h <_ n , then there exists a d.s. matrix with maximum diagonal sum h is 0 iff and such that the minimum entry on the diagonal h <_ n-2 . In what follows, we shall obtain the best possible upper and lower bounds for various kinds of functions of discuss the cases for equality. w i l l be constructed. h and k and When the bounds are attained, examples The key w i l l be Theorem 2.13 referred to as the "Covering Theorem", the proof of which depends on a well-known combinatorial theorem of P. Hall on SDR (systems of distinct tives). A conjecture is given. representa- Theorem 2.13: (The Covering Theorem) Let be p n><n matrix, and let a^, o^, • given mutually disjoint diagonals of can select that A be a given {a i ; n-p mutually disjoint diagonals i = 1, 2, • • • , n} Proof: If cover each diagonal of 2, o"p+-^» o^ 2' '"> A exactly. for a l l a^, a2> " • , a i = 1, 2, • • • , p . 1 P S„ = S ^ U {a. (2)} , n A exactly 1 <_ p <_ n-1 . Since on S such that P S = S ^ U {a . (1)} , Let 1=1 . 1=1 1 < m< n . We claim that I S 1 {co} U S co-, M 1 2 co„ M 1 Let m be an integer U • • • U S I > m co /i\ m 1 l < c o - , < c o „ < * * " < co < n . — 1 2 m — i / j , i , j = 1, 2, • • • » P » a ^ O a j = d) , we have | Sj| = n-p for a l l such that j = 1, 2, S u S CO •« m(n-p) . On the other hand, each index from times in n p \J \J {a .(i)} i=l j=l 3 1 S ,hence appears exactly each index from Since n , and hence (I) the number of elements, counting repetitions, in the set and hence (II) c on S , 1 <_ p <_ n-1 , P S = S % U { a . (n)} 1=1 for a l l u (Definition 1.10.) Hence assume that one can always exhibit another permutation -a for a l l sequences s n , the assertion is equivalent to saying that given p mutually disjoint permutations such that 0 " + A corresponds to a permutation on the set n} a H a . = <> j Then one p = n , the given diagonals already cover and there is nothing to prove. S={1, A , 1 <_ p <_ n . ii ••• M CO « 2 appears exactly n-p times in S appears at most S is CO m p n \J S. , i=l 1 n-p times in Su i |S 1 1 US to •, 1 U ••• U S . tom L u S to 2 The two statements (I) and (II) u '*' II S 1 | > m • to — m By a well-known theorem of P. Hall on KJ o SDR [20, p. 48], there exists an SDR for exist d. e S. , i = 1, 2, permutation a on S n S2, S. that p . n . It is for a l l a f\ a . = <>f 3 there Define the i = 1, 2, i j = 1, 2, ; i.e., that form an SDR. by a (i) = d_^ for a l l clear from the construction of imply that Y This completes the proof. As an immediate consequence, we get: Corollary 2.14: (i) Let A e fiR . h + (n-l)k <^ n with equality i f f for any set of 0 1* a 2' '"' n CT (ii) cover t n a t diagonal, we have n V n A exactly where a. = k for a l l l' T 2' * " " ' Tn t n a t diagonal, we have Proof: (i) Theorem, let j = 2, 3, 2 j-2 i=l i a j j = 2, 3, • • • j n . ( l ) n A exactly where x^ i x . (i) = n ' a 1 1 , J = cover ^e n _ 1 •••,n. diagonals is a minimum > 3, 2 be any maximum diagonal. ***' °n o > cr^s n 7 a. a Let (a^; i = 1, 2, • • • , n} n <h+y n £ cover diagonals is a maximum (n-l)h + k >_ n with equality i f f for any set of T ~ Then n . By the Covering diagonals such that A exactly. Then = n , with equality i f f n y i=l The proof of (ii) is similar. h + (n-l)k <^ a. i a j ... = k ( l ) for (i) The equalities in the above corollary are always attainable. example, i f h + (n-l)k A is a permutation matrix = n , and i f A= J (n-l)h + k = n . (ii) n or or A= J n Y b . . < n , e.g., ji , jL = l , then n A = —^r-(nJ - I) , then n-1 n The above corollary i s , in fact, true for any with For n*n matrix B substochastic matrices, X Proposition 2.16: n = 2 or For and Then h+k = 2 h+k <_ n with equality i f f always holds. h+k <_ h+(n-l)k <_ n . Hence k = (n-l)k A is a permutation matrix. Proposition 2.17: n = 2 n = 2 , By Corollary 2.14, h+k = h+(n-l)k = n . h = n A e ftn . A is a permutation matrix. Proof: n >_ 3 . Let Let A e ft . n and so n-1 If h+k = n , then k = 0 . Therefore The converse is obvious. Then or there exist permutation matrices PAQ = -^r(nJ - I) = n-1 n We assume that h+k > — — n-1 P and with equality i f f Q such that n-1 n-1 0 1 n-1 Proof: For n >_ 3 . h+k = 2 By Corollary 2.14, h+k > —2— . — n-l Hence n = 2 , h = n If ^ . always holds. (n-l) (h+k) >_ (n-l)h + k >_ n . h+k = — , n-l then Furthermore, let n-2 diagonals {x, a . ; i = 2, 3, • • • , n} x . Then the Covering Theorem implies a^, a^, such that cover 10^ diagonal n . x In other words, i f Since n , . n-1 tion matrices x = n , h+k = , then there is a zero is a maximum diagonal We claim that this implies the existence of permuta- P and a zero diagonal (n-l)h + k = h = —r- for a l l (l) n-l such that any diagonal disjoint from x with sum h = k = 0 . be any minimum (zero) diagonal and A exactly. n we get from Corollary 2.14. (ii) that Y a. j = 2, 3, Hence (n-l)k = k , from which be any diagonal disjoint from x the existence of We assume that Q such that PAQ = —^r(nJ n-l n and a l l entries off x - I) ; i . e . , are equal to A has -^y . The proof of this which turns out to be an interesting combinatorial argument must be s p l i t into several steps and w i l l follow from the subsidiary results contained in Lemma 2.18, Theorem 2.19, and Theorem 2.20. Lemma 2.18: If an certain diagonal x nxn matrix such that every diagonal disjoint from constant sum, then every from x A has the property that there is a 2x2 x has a submatrix that does not contain any entry must have both diagonal sums equal. Proof: main diagonal. Without loss of generality, we may assume that For n = 2 or n = 3 , there is no does not contain any entry from the main diagonal. 2x2 x is the submatrix that We assume that n >_ 4. Consider any 2x2 submatrix A[i,j | i ' , j ' ] entry from the main diagonal. that does not contain any Interchanging the 1st row with the i t h row, the 2nd row with the i ' t h row, the 1st column with the jth column, and the 2nd column with the j ' t h column, we can bring to the upper left corner. On the 1st and 2nd row, there is an entry from the original main diagonal at the k >_ 2 , I >_ 2 . (1, k) and (2, &) positions, say, Interchanging the 3rd column with the kth column, the 4th column with the j£th column, we can bring a , and a „ IK submatrix A[l,2 | 3,4] . a.. into the Zx, Similarly, we can bring the two main diagonal entries on the 1st and 2nd column into the submatrix Consequently, A[i,j | i ' , j ' ] A[3,4 | 1,2] . the matrix takes the form: a.., * * * a * 6 B where a in the * denotes an entry form the original main diagonal of (n-4)x(n-4) any diagonal submatrix o such that B) are disjoint. B = A(l,2,3,4 a "and T | 1,2,3,4) , we can chose (to be precise, Consider the diagonals A . Now, x restricted to a U {a, 3, a . . , a.,.,} and a U {a , 3 > hence »> a i ' j ^ ' B assumption, they have the same sum, and y a . . + a . , . , = a . . , + a. . . . Theorem 2.19: If an nxn matrix certain diagonal x any entry from x P and such that every 2x2 submatrix that does not contain has both diagonal sums equal, then for some permutation Q, PAQ takes the form: * a +3 2 B = PAQ = 3 £ a 3 +3 1 _an*l 3 •• •a 2 ^ n * 2 • • a n + 3z * 2 a, 2*^3 ^ a +3 = a . + 3 • for a l l i i J = 0 , and a 3 * x • convenience A has the property that there is a • an+3., 3 9 * f j , i , j = 1, 2, n denotes an entry from x We prove this by induction on n . Proof: For n = 2 or n = 3, there i s no 2x2 submatrix satisfying the assumed condition and hence the assertion is "vacuously true". We start with the case Without loss of generality, we may assume that If we put a 4 = and a a ; L 41 ~ a 21 + a24 " a 14 ' 3 1 = a u , is the main diagonal. a3 = a31 - 21 " a24 + a 14 ' 3 2 + a 2 4 - a^ , = a 12 » 3 3 = a 13 3^ = a ^ , then from the assumption, one can verify easily that a.. = a. + 3 . for = 0 , a2 = a24 - a x n= 4 . n> 4 . for a l l i ? i . Now assume that the assertion is true Let A be an (n-l)x(n-l) matrix with the described property. nxn As usual, assume that T submatrix A (n+1 | n+1) 3 * a +3 3 takes the form: A e 3 a +3 2 3 ft 2 Since the also has the described property, the induction hypothesis implies that * is the main diagonal. n a l n+1 n+1 a 2^n a 2 a 3^n a 3 n+1 a n-2 A= • n-2 K a n-2+ 3 n n-1 0 * °n+*l 3 Let 3 n = n+l 1 n+1 3 the a = n+l 2 l n+1 " a 2x2 3 submatrix a. + M8 , , . l n+1 a " a n-2 n+1 a n-2 n+l = + p a + a For n n+l n + + P a n-1 n+l 3 • For each a. a ,, + 3 . . n+1 j = n+1 X n+l n - l » a • F n d h e n C 6 = ° a r n e a G h + 3 3 a Finally, for J n - l n+1 a n n+1 ft n+l n n - l , consider a. l n+1 = a. + an ,. l 1 n+1 2x2 submatrix ~ + 3 i + a ,. = n-l n n+1 n-2 n n+1 " n+l,j = & n-2 n+1 S i m i l a r l > A[n,n+1 | l , j ] a + Mg . + a J 1 1 n j n+1 1 a By assumption, a n+l a , 1 = 2, 3, > and hence By assumption, n * n-l a , consider the n n+1 ' 2x2 submatrix + MB. + a . l n+1 j a A [ l , i | n,n+l] . n " an-2 n+l 1 " h consider the a a n + a. = a-i ,-, + a . + 3 x n+1 1 n+1 i n A[n-2,n 1I n-l,n+1] . = a n +B,j n+e2 n-l n+1 j . = y> 2 ' + % " an-2 = d e f l n e 3 ' " • ' n _ 1 ' By assumption, , and hence a .., , consi der the n+1 n a ,.. . n+1 j = g. + a 1 j n+1 2x2 submatrix A[n-2,n+l I n-l,n] . By assumption, a _ + B . . + a ,, n-2 n-1 n+1 n a,. = a ,.. . + S - 8 . n+1 n n+1 n-1 n *n-1 1 = a o+6o n-2 2 + = a ,i + 8 n+1 H n a , i i > n+1 n-1 • and hence Therefore i , j = 1, 2, n+1 a.. = a . + 8 . lj i *j i f we set a-^ = 0 for a l l i ^ j , for notational convenience. This completes the proof of Theorem 2.19. Theorem 2.20: If A c fi^ has a zero diagonal T such that every diagonal disjoint from T has a constant sum, then a l l entries off x are equal to 1 n-1 For Proof: n = 2 and n = 3 , this is clear. As usual, assume that Theorem 2.19, x is the main diagonal. We assume n>4 By Lemma 2.18 and A takes the form: 0 a +3 2 a 3 0 x 3+3l 3 2 a +3 3 ct + 3 2 2 3 3 3 0 A = n ' a 2^n ' a 3^n • a n+S-, p l a n*2 0 a n +3 F 3o Clearly, any diagonal disjoint from x has the constant sum J (a. + i=l 1 n n Let a = J a. > 3 £ 3 • • Since 1 i=l 1 i=l 1 by the Covering Theorem, we can always select n-1 diagonals such that where we set together with a, = 0 as before. x , they cover = A exactly, we have (n-l)a + ( n - l ) 3 = n . a + 3 = ~^ or (1) Since the 1st row sum and the 1st column sum are one, we have B -6 and X = 1 (2) a + (n-1)^ = 1 . (3) a + (n-l)3 = n . (4) From (2) and (3), we get From (1) and (4), we get and from (2), 3-^ 3 - 1 = column sum are one, = (n-2)a = 0 from which a = 0 . Hence B = ~ y . Since the ith row sum and the i t h i = 2, 3, • • • , n , we get a - a. + (n-l)B. = 1 . l l (n-l)a^ +3 - 6 ^ = 1 M i = 0 1 n-l (5) a. - (n-l)3. = a - 1 = -1 . l i From (5) and (6), we get which for a l l for a l l and Hence (n-l)a. - 3. = 1 " 3 = ^ and n-l n i=2, [(n-l) 2 - l]a^ =0 i = 2, 3, 3, • • • , n . n . or (6) n(n-2)cu = 0 , from Therefore, from (5), This completes the proof. The proof of Proposition 2.17 is thus also completed. Theorem 2.20 has a generalized from which we shall state as a conjecture since we have not been able to prove i t completely. Conjecture 2.21: * Let A e 0, , and let n mutually disjoint zero diagonals of disjoint from each constant sum is A , T 1 T 2 T 1 <_ m <_ n-l . m be m If every diagonal T ^ , i = 1, 2, • • • , m has a constant sum (this —— by the Covering Theorem), then a l l entries off the n-m m zero diagonals are equal to n-m We m = n-1 since remark t h a t t h i s c o n j e c t u r e i s c l e a r l y A i s then a p e r m u t a t i o n the s p e c i a l case where m = 1 . p r o o f o f Lemma 2.18 Theorem 2.19 2.21 and since for arbitrary t h a t does not c o n t a i n any n matrix. Furthermore, and Let c m mutually disjoint from each o f f the x^ n-2 ft n the g i v e n n-2 A e n t r i e s o f f every we such e n t r y a " s t a r " . c a l l any i n the h y p o t h e s i s must be x^ p o s i t i o n , then we 2x2 1/2 T „ n-2 be The also. n-2 disjoint then a l l e n t r i e s . and each column, t h e r e a r e n-2 . For convenience, By the C o v e r i n g Theorem, the . Permuting get a d i r e c t sum. submatrix m = n - 2 every d i a g o n a l the rows and Otherwise, i s a t the by permuting constant columns, (1, l ) t h , (1, 2 ) t h , and I f the o t h e r s t a r on the 2nd row can assume t h a t i t i s a t the rows, we If , i = 1, 2, y is i n the zero d i a g o n a l s . , has a c o n s t a n t sum, can assume'that t h e r e a r e s t a r s a t the (2, 2 ) t h p o s i t i o n s . m T , ,T „ , 1 2 I t i s c l e a r t h a t i n each row e x a c t l y two we . not be any i s true f o r let zero d i a g o n a l s a r e e q u a l to Proof: sum and zero d i a g o n a l s o f , i = 1, 2, the arguments used , t h e r e may e n t r y from A e A l s o , Theorem 2.20 do not y i e l d an answer f o r C o n j e c t u r e next p r o p o s i t i o n shows t h a t C o n j e c t u r e 2.21 P r o p o s i t i o n 2.22: true f o r we the (2, l ) t h the columns, (2, 3 ) t h p o s i t i o n , and by permuting the can assume t h a t the o t h e r s t a r on the 3rd column i s a t the (3, 3 ) t h p o s i t i o n . a d i r e c t sum, Repeat t h i s p r o c e s s . E v e n t u a l l y , we can w r i t e A as r r n , each n. ^ 2 ; A = © Y A. , where A. e ft 1=1 and each A_^ d i a g o n a l and as two 1 d i a g o n a l s c o n s i s t i n g o f s t a r s o n l y - the main the d i a g o n a l c o r r e s p o n d i n g to the permutation (1,2,•••,n.). Since each A. is d.s., we can write 1 diagonal and i = 1, 2, l~x^ ^or r a x x for a l l entries on the main entries on the other diagonal. For each , we have, by assumption, that xn + n„x„ + • • • + n. x. + • • • + n x 1 1 2 2 i i r n. x., + n 0 x 0 + • • • + n.(1-x.) + • • • + 1 1 2 2 i i x. = -ij- . x. i = and r 2 n x = ~ . r r 2 Hence x. = 1 - x. l i or This completes the proof. In view of Theorem 2.20 and Proposition 2.22, Conjecture 2.21 is true for n = 2, 3, 4. Since h+k 2 hk <_ ( —— 2 ;) that n2 = 4 . hk < ^- g(n)-n 2 — H Proposition 2.23: iff h+k <_ n by Proposition 2.16, we get Hence there exists a smallest constant . We claim that Let Aeft n . g (n) such g (n) = —^-r . n—1 n2 hk < - 7 - 7 — - T T — 4 (n-l) Then with equality n J h = I" and any diagonal disjoint from a maximum diagonal is a n minimum diagonal with sum k = 2(n-l) Proof: Since n 2 - 4nh + 4h2 = (n-2h)2 >_ 0 , we get 2 h(n-h) = hn - h <_ ^ 2 . (7) Also, from Corollary 2.14.(i), we get (n-l)k <_ n-h . (8) n2 From (7) and (8), we get (n-l)hk <_-^- holds, i t must hold in both (7) and (8). n2 or hk <_ ^TJ^Zjy Hence h = y • i f equality and the equality case in Corollary 2.14.(i) implies that any diagonal from a maximum n 2(n.-l) diagonal is a minimum diagonal with sum obvious. The converse is This completes the proof. The next examples show that the above bound is always attainable and is not unique for n >_ 3 . Example 2.24: (i) Let A be the d.s. matrix: 1 2 2(n-1) 2(n-1) 1 2 1 2(n-1) 2(n-1) 1 2 2(n-1) A= 2(n-1) where a.. = ii 2 Clearly, h = for a l l i = 1, 2, n £ a. . = -ri=l 1 1 n and a.. = „ , ^ , > otherwise, IJ 2(n-1) and any diagonal disjoint from the main diagonal is a minimum diagonal with sum k = ^ (ri-1) ' (ii) For n > 3 , let n+1 2n A= 1 2n 1 2n A be the d.s. matrix: _1_ 2n n2-n-l 2n(n-l) n2-2n+2 2n(n-l)(n-2) 2n n2-2n+2 2n(n-l)(n-2) n2-n-l 2n(n-l) , where n+1 a-, = -z— 11 2n 1 = 2, 3, , n , and n2-n-l 2n(n-l) a. . = -r-7—TT~ xi ,, for a l l r a.. = — 7 — ? ? > " W\ otherwise. It is readily xj 2n(n-l)(n-2) A • J J , n2-2n+2 ' n 2 - n - l „ n+1 A xs d.s. and -r— < -r—,—rv?—oT o~7—TT o — • 2n 2n(n-l)(n-2) 2n(n-l) 2n j ^ verxfxed that Hence 1 a.. . = a... = 77— lx ii 2n , 2 1 < < h = £ a^ = i=l +" ^ Y = 2 a n ^ a n ^ diagonal disjoint from the main diagonal is a minimum diagonal with sum , 2 , n -2n+2 k = h 2n 2n(n-l) n 2(n-l) For any equality i f f A = Jn ' A e ftn , since h >_ 1 (Corollary 1.5), we have h+k-hk >^ 1 with equality i f f A= . equality i f f Let h = n-l Aeft n . k <_ 1 with either (h-1)(1-k) ^ 0 or The next proposition gives the upper bound for the corresponding quantity Proposition 2.25: c and Then h+k+hk . h+k+hk < n + -Kr — n-l with and any diagonal disjoint from a maximum diagonal 1 is a minimum diagonal with sum k = n-l Proof: Let B = -^(A + J ) . 2 n diagonals and minimum diagonals of Then A and Be ft n and the maximum B correspond to each other. h+1 An application of Proposition 2.23 to or n2 h+k+hk < —=— 1 — n-l h+1 n 2.23, —— = "2 or B gives k+1 2 (——) (—-— j ) <^ 4( n -l) ' 1 = n H h = n-l 7- . n-l If equality holds, then by Proposition and any diagonal disjoint from a maximum diagonal is a minimum diagonal with sum k such that = 2 (n-l) k = \ . The converse is obvious. This completes the proof, n-l ° r We close this chapter by obtaining bounds for h+k h, k and when the d.s. matrices under consideration have properties discussed in Chapter I. Proposition 2.26: If A e ft^ has precisely with common sum a f 1 > then 2 •—, - N oz (n-l) n 2 < h+k — Proof: Q < 2 + \ — n-1 By Theorem 1.20, such that PAQ is a / I N n - (n-l)a = These bounds are always attainable. 1 there exist permutation matrices (x, y, z)-matrix. i 1-nx 1 - ~j~ , a n d . „ a + 3 • Hence g = x + (n-l)z = „ (1-nx)(n-2) 2 ( n -i)2 = denotes the only other diagonal sum (Lemma 1.19). its maximum 1 + , \ N 0 (n-l)2 and s H x = 0 . when x = 0 attains its maximum Finally, its minimum 2 a + 3 n 2 (n-l) — 7 — r - r - 5z~ Clearly, and its minimum ^ — 7 n-1 2 when x = 1 2 — , n 2 N 9z < h+k < 2 + ^ — 7 (n-l) — — n-1 . , where 3 a attains when x = 1; and its minimum ^—\ when n-1 attains its maximum 2 + when x = 0 . P and Examining the proof of l~nx a = 1 + ( n _]jz Corollary 1.21 shows that = . diagonals n—2 k >_ --^j- and h <_ 2 , n (n-1)(n-1)! Therefore, ^ when x = 1 h < 2 , — n2 k > — r - and — n-1 It is clear from the proof that these bounds are always attainable. Proposition 2.27: diagonals with sum If Ae (n >_ 3) has precisely (n-1)(n-1)! (i) greater than one, then h + k < 2 , (ii) smaller than one, than h + k > 2 . This bound is not attainable but best possible in the sense that can become arbitrarily close to 2 in either case. and h+k Proof: Let E = ja : ; £ i a (i) * a ' T h e ' ' n E Cn-1)(n-1)! . = (n-1)! Let D= [J D. be a decomposition of the set described in Theorem 1.11. |E H D | = n-1 for a l l Then we have seen (cf. Proposition 1.18) that j = 1, 2,. (n-1)! . be a maximum diagonal with sum h where O e •*•» 2 > where g < 1 _^> a n P and ou > 1 , i = 2, 3, i=2 e , say. Let of each diagonal in Since D.. covers n-1 . T q 2 where a > 1 A has only 2 - ^"^n-l)^2^ as h+0 < 2 . be the diagonal sum and 0^ < 1 , i = 2, 3, n-1 . n-1 £ 0 . < k + a + n-2 and i=2 1 n = k + a+ Finally, to see that this bound is approachable, consider a d.s. (x, y, z)-matrix „-o a + 0 —2 h+k Furthermore, i t is clear from the proof that this bound is not attainable. a + 0 = covers A be a minimum diagonal with sum k k , 0 , $y *•*> ^n_]_> 0 1 A exactly, h+k >_ ct+k > 2 . seen before, Let Since and hence 1 hence Q 1 Similarly, in case ( i i ) , let where t O be the diagonal sum of each diagonal in n-1 n = h + g + £ a. > h + 0 + n-2 exactly, In case ( i ) , let , say. Q h, c t D of a l l diagonals as A with x ^~ ( s o that 2 distinct diagonal sums " ^ c f 'P r ° P ° s i t i o n 2.26.) l-o j . „ „+o x —*• — , and a + 0 —>- 2 as a A ^ J^) . As and 0 with It is clear that 1+o x —*• — CHAPTER H I PROPERTIES OF THE h-FUNCTION AND THE k-FUNCTION OF d.s. MATRICES The main prupose of this chapter is to study the properties of the h-function and the k-function, the functions that associate with each d.s. matrix its maximum and minimum diagonal sums, respectively. In particular, we investigate the behaviour of these functions on the Kronecker product of d.s. matrices. very similar to the rank function We w i l l show that the h-function is in many respects. p Furthermore, we h(A))% h(A) < p(A) and per(A) < n — — In which improves a result of Marcus and Mine [11]. A conjecture is given. shall prove that, for Aeft , We mention f i r s t that the functions fact, defined for any nxn matrices. h and k are, in It is when restricted to d.s. matrices that they have interesting properties. We shall denote the set of a l l non-negative entries by Lemma 3.1: Let with equality i f f (ii) nxn matrices with H^ . A,B be in A and H . n Then (i) h(A+B) < h(A) + h(B) — B have a corresponding maximum diagonal, k(A + B) >_ k(A) + k(B) with equality i f f A and B have a corresponding minimum diagonal. Proof: and (i) Let a ,x A + B rest jpectively. Then and y be any maximum diagonals of A, B n h(A + B) = Y (a. . . . + b. ,..) = i = 1 n n n n Y a. . . . + Y b. . . . < Y a. . . . + Y b. . . . ^ iy(i) £ ip(i) ~ i la (i) i± IT(I) i 1 ± ± ± ipd) iyd) = h(A) + h(B) . If n equality holds, then rt Y- a. % ± X ... = Y a. ... and IU ^ CO ^ Ci) Hence u is a maximum diagonal for both obvious. The proof of (ii) is similar. A and n n Y b. ... = Y b. . . . iy Ci) B . ^ IT Ci) The converse is The above lemma can be generalized immediately to: Corollary 3.2: (i) Let A^ e m m h( I A.) <_ I h(A.) 1=1 H n , where i = 1 , 2, • • • , m . with equality i f f a l l Then A.'s have a A.'s have a 1=1 corresponding maximum diagonal, (ii) m m k( £ A.) >_ £ k(A.) 1=1 1 1=1 with equality i f f a l l 1 1 corresponding minimum diagonal. Proof: By Lemma 3 . 1 and induction on m . Corollary 3.3: k The function h is convex on H^ , and the function is concave on H n Proof: Let A,B be in H n and A e [ 0 , 1] . Then h{XA + (l-A)B} ^ h(AA) +h((l-A)B) = Ah (A) + (l-A)h(B) k{AA + (l-A)B} > k(AA) + k((l-A)B) = Ak(A) + (l-A)k(B) . Theorem 3.4: Let A,B be in Q . n Then (i) h(AB) <_ min (h(A), h(B)} (ii) k(AB) > max{k(A), k(B)} and Proof: (i) By the well-known theorem of Birkhoff [1], every d.s. matrix can be expressed as a convex combination of permutation m m matrices. Hence B = Y A.P. , where A. > 0 such that J X. = 1 , and i=l 1=1 is a permutation matrix, for a l l i = 1, 2, — , m . i , Corollary 3.3 gives that Since m m h(AB) = h( £ A.AP.) <_ £ A.h(AP.) = - X 1=1 a m = ( £ A.)(h(A)) = h(A) . i=l 1 Similarly, h(AB) <_ min {h(A), h(B)} . hCAP^) = h(A) h(AB) <_ h(B) . X . — X 1=1 X Therefore, The proof of ( i i ) is similar. The next two corollaries are immediate consequences of Theorem 3.4. Corollary 3.5: Let matrix i f f both Proof: hence and h(A) >_ n (ii) Proof: m = 1, 2, Remark 3.7: Then AB is a permutation B are permutation matrices. AB is a permutation matrix, then and h(B) >_ n by Theorem 3.4. Let A e ftn . Then for a l l h(AB) = n , and Therefore B are both permutation matrices. Corollary 3.6: and A and If A and A,B be in ftn . h(A) = h(B) = n, The converse is obvious. m , (i) h(Am) < h(A) ; k(Am) >_ k(A) . Since Ae ft n implies that i t suffices to put m—1 B= A Am e ft n for a l l in Theorem 3.4. To determine when equality holds in Theorem 3.4 seems to be quite d i f f i c u l t . permutation matrix or i f For example, h(AB) = h(A) PAQ = J ©J © ... ®J n„ n 2 r n. 1 w i l l hold i f where B is a r / n. = n , . I i=l u and P and when both Q are permutation matrices. A and B are fully indecomposable. 0 let For example, 1_ 4 -=- A= B= 0 1 £ Hence The equality can hold, however, £2 Then 1 0 4 h(AB) = — = h(A) = h(B) . equality as follows. 1 2 AB = Let g(B) matrices necessary to represent We also observe another condition for denote the minimum number of permutation B as a convex combination [15]. in view of Corollary 3.2 and the proof of Theorem 3.4, least g(B) maximum diagonals in order that hold. This condition, however, is rather weak since compared with Let (i) A,B be in h(AB) < h(A)h(B) — k(AB) > k(A)k(B) (ii) (i) Proof: that ft h(AB) = h(B) g(B) can possibly is small Then with equality i f f with equality i f f For any d.s. matrix h(X) > 1 with equality i f f X= J 1 or of (ii) is similar. A= B= J A= B = J . n A= B = J n X , we have, by Corollary 1.5, n h(AB) < min {h(A), h(B)} <_ h(A)h(B) h(A) = h(B) A must have at n! , the number of diagonals of a matrix. Corollary 3.8: that Then, Hence Theorem 3.4 implies with equality only i f The converse is obvious. The proof Let i t follows that A,B be i n ft^ . Since 1 < h(A) +• hCB) - h(AB) — hCA) >_ 1 and hCAB) ^ h C B ) , with equality i f f A = B = J . * n The problem of determining the corresponding best possible upper bound for h(A) + h(B) - h(AB) an upper bound. seems to be a d i f f i c u l t one. Clearly, 2n is The following conjecture which seems p l a u s i b l e i s exactly the analogue of Sylvester's law f o r rank of two matrices: p (A) + p (B) - p(AB) <_ n Conjecture 3.9: Remark 3.10: be true f o r Let A,B be i n Q,^ . With l i t t l e computation, n = 2 . Then h(A) + h(B) - h(AB) <_ n. Conjecture 3.9 can be v e r i f i e d to However, even f o r too involved to give any answer. [14, p. 28]. n = 3 , the manipulations get The d i f f i c u l t y of this problem can perhaps be seen from the fact that the equality w i l l not be attained uniquely. I t i s clear that i s a permutation matrix. h(A) + h(B) - h(AB) = n i f either This i s , however, not the only case when equality can hold; e.g., consider the 4x4 d.s. matrices: — I A 0 0 2 = B 0 J 2 J h(A) = h(B) = 3 , and AB — 0 2 = Jo 2 Jo 2 = _ Then A 0 I2 0 _ or B Hence h(AB) = 2 and h(A) + h(B) - hCAB) = 4 = n . For arbitrary h(A) + h(B) - h(A + B) and though zero is the lower A and A,B in H^ , i t is easy to see that k(A + B) - k(A) - k(B) have no upper bound bound in both cases by Lemma 3.1. If, however, B are d.s. matrices, then i t is readily seen that the upper bounds exist as indicated in the next proposition. Proposition 3.11: — (i) Let A,B be in ft . n Then h(A) + h(B) - h(A + B) <_ n with equality i f f A and B are permutation matrices corresponding to disjoint permutations. (ii) k(A + B) - k(A) - k(B) <_ 2 with equality i f f both a zero diagonal and 2 a.. .+ b . . = — for a l l A and B have i , j = 1, 2, n . Proof: (i) Since h(A) <_ n , h(B) <_ h(A + B) , i t is clear that h(A) + h(B) - h(A + B) <_ n . n = h(A) = h(B) = h(A + B) If equality holds, then and hence A and B matrices corresponding to disjoint permutations. are permutation The converse is obvious. (ii) Since -|(A + B) e ftR , we have, - | k(A + B) = M^y^-) <_ 1 k(A + B) <_ 2 , and hence holds, then B k(A + B) - k(A) - k(B) <_ 2 . k(A) = k(B) = 0 have a zero diagonal and A+B k(—^—) = 1 . and A+B ^ = or If equality Hence both , which implies that 2 a.. + b. . = — for a l l i , j = 1, 2, • • • , n . ij ij n obvious. This completes the proof. The converse is A and Next, we study the behaviour of the h-function and the k-function on the Kronecker product (or direct product) [9] of d.s. matrices. The fact that consideration of Lemma 3.12: (i) (ii) h(A x B) A,B e ft implies that A * B e ft ? makes the n n^ and k(A x B) quite natural. For any n-square matrices h(A x B) = h(B x A) and h(PAQ x P BQ^) = h(A x B) A and B , k(A x B) = k(B x A) . and for any permutation matrices k(PAQ x PjBO^) = k(A x B) P, Q, P^, and Q^ . Proof: (i) Since i t is known [2] that there exists a permutation matrix such that (ii) P Pfc(A x B)P = B x A , the assertions are clear, Since the Kronecker product satisfies the property that AC x BD = (Ax B)(C x D) , we have (P x P 1 )(A x B)(Q x Q1) = (PAQ) x (P^BQ^ ; i . e . , permuting the rows and columns of of Ax B . A and B only permutes the rows and columns Hence the assertions follows. This completes the proof. We remark that the above lemma can be of practical use sometimes when one of the matrices A x B or B x A has a form easily handled (e.g. Proposition 3.18 below). The next proposition presents a strong contrast between the Kronecker product and the ordinary product of d.s. matrices Corollary 3.8). (cf. Proposition 3.13: and (ii) A,B be in tt^ . (i) Let a CD be a maximum diagonal of A x B , consider the blocks at the i=l, Then h(A x B) h(A)h(B) k(A x B) <_ k(A)k(B) . Proof: In Let 2, • • • , n . block) with sum ( i , cr(i))th A with sum h(A) . position, where In each of these blocks, there is a diagonal (of that a. ...-hCB) , i = 1, 2, • • • n . The union of these xa ix) diagonals clearly forms a diagonal for Hence h(A x B) >_ h(A)h(B) . A x B with sum h(A)*h(B) . The proof of ( i i ) is similar. As an immediate consequence, we have: Corollary 3.14: A = B = J Let A,B be in fl . n Then Ax B = J ? rr iff . n Proof: If A x B = J2 > then h(A)h(B) <_ 1 by Proposition 3.13. Corollary 1.5. But Hence h(A) = h(B) = 1 h(A x B) = 1 and hence h(A) >_ 1 , and or A= B= J r h(B) >1 . by The sufficiency is clear. Remark 3.15: interest. The case for equality in Proposition 3.13 is of some It can be verified directly that for holds in both cases. for equality. For n = 2 , equality always In general, we are unable to determine the conditions n >_ 3 , however, there exist matrices such that the inequality is strict as shown by the next example. Then h(A) = h(B) = JL_ AxB = 16 0 2 B = =- 2 1 2 1 and e ft. h(A)h(B) = 2 5 . Now, -z-T 16 0 0 0 0 0 0 0 0 0 0 4 4 4 2 2 4 2 2 0 4 4 4 2 2 _4 2 2 0 4 4 4 2 2 4 2 2 0 2 2 2 1 1 2 1 1 0 2 2 2 2 1 1 1 A 0 4 4 4 2 2 4 2 2 0 2 2 2 1 1 2 1 1 0 2 2 2 1 1 If we consider the diagonal of entries, we see that AxB 2 1 1 consisting of the underlined h(A x B) > ^(24 + 3) = TT" > h(A)h(B) . lb — lo The next two propositions show that we have equality in both cases in Proposition 3.13 i f one of A and B is some special d.s, matrix. Let Proposition 3.17: Then (i) (ii) of P be any permutation matrix. h(A x P) = h(P x A) = h(P)h(A) = nh(A) kCA x P) = k(P x A) = k(P)k(A) = 0 Proof: Let A e ft^ and let In view of Lemma 3.12.(i), i t suffices to consider a be the permutation corresponding to A in the . ( i , a(i))th block, where other blocks are 0 . P . Then i = 1, 2, Hence h(P x A) = nh(A) and P x P x A. A has a copy n , and a l l the k(P * A ) =0 . Let k(A x J ) = k(J x A) = k(A) . n n In view of Lemma 3.12.(i) and Proposition 3.13, h(J x A) < h(A) . n — A A A A A A We have n x A . indices (mod n) taken from the set Consider the following sets of {1, 2, n} : = {a(kn + 1) , (mod n) ; k = 0, 1, • • • , n-l} % T 2 = {o-(kn + 2) , (mod n) ; k = 0, 1, T n = ^ C In other words, of it I be any diagonal of T Then (ii) J x A n a . h(A x J ) = hCJ x A) = h(A) . n n suffices to show that Let n (i) (i) Proof: Aeft a k n + n ) » (mod n) j k = 0, 1, n-l} • • •, n-l} T^ consists of the 2nd indices (mod n) a which l i e on the ith row of each block, where of a l l entries i=l, Note that the elements in each 2, n . T. are not necessarily distinct. We l • . claim that there is an SDR for the sets T, , T~ , • • • , T . Let m be 1 2 n an integer such that 1 <_ m <_ n . Let w be an increasing sequence of m terms, 1 < to, < to0 < • • • < to < n . We claim that — 1 2 m — |T U T U ••• U T I > m . to-, toto ' — 1 2 m Since each T , where to. l i = 1, 2,. • • • , m , has n T u T U' • • • U T con co0 to 1 2 m elements counting repetition, has mn elements counting repetition. Furthermore, i t is clear from the definition of diagonal that each index n (mod n) occurs precisely n times in \J T. and hence occurs at most n m U T . . _ •, to . i=l l times in Therefore, 1 T 0), U T U • • • U T 1 > m . Now, co 0 co — 1 2 m the theorem of P. Hall [20, p. 48] implies the existence of an SDR for the sets T.. , T „ , 1 2 0 < k. < n-1 — l— . T ; n Consider the set We identifyJ the rows of columns of J n k_^n+i ^ k j n + J a(k.n + i) e T. l I J n say, where x A that are the same rows of A . (mod n) , and a (k^n + i) ^ a (k^n + j) n , the elements of even under the identification. 2, S (mod n) for i ^ j, l i e on distinct rows and columns Hence they constitute a diagonal for 1 = 1, 2, Since these two rows are the same row under the A. identification, this permutation w i l l not affect the block structure of n x A . = {1 on 2 Furthermore, since •••> n} {a(k.n + i ) , (mod n); i = 1, 2, • • • , n} = a(k^.n + j) = i permuting the ith column with the i = 1, 2, ' I > there exists, for each i) such that i , a unique (mod n) , i = l , 2, a(k^n + j)th j (depending n . Hence (mod n) column, where n , w i l l not affect the block structure of J n xA . In this manner, we can bring the above found diagonal into the (1, l)th block of J n xA . ' Since (k^n + i)th row with the ith row, where J n, A .and the ' Now we permute the n . ' S = {a. ,. „ , .N : i = 1, 2, • • • , n} . k^n+ijo- (k^n+i) ' ' ' x A that are the same columns of i , j = 1, 2, i=l, J Since there are no entries of a left on the first n rows and columns, we can consider the (n2-n)-square matrix by deleting the first n2 - n entries of n rows and columns of x A , and the remaining cr w i l l form a diagonal for H. the above process and eventually bring the entries of (2, 2)th, from a and (n, n)th E obtained Now, we can repeat o into the (1,1)th, block such that each block has n entries that form a diagonal for that block (namely, A), and such that the block structure of x A remains unchanged. h(J R x A) <_i{nh(A)} = h(A) . Hence The proof of ( i i ) is similar. The Birkhoff theorem can be used to yield an upper bound for h(A x B) in terms of h(A) and h(B) . Proposition 3.19: Let A,B be in Q,^ . Then <_ min (nh(A), nh(B)} with equality i f either h(A x B) <_ A or B is a permutation matrix. Proof: such that i = 1, 2, By Birkhoffs theorem, let m B = Y A.P. , where x=l A. > 0 m £ A. =1 , and each P. is a permutation matrix, i=l m . Since the Kronecker product is distributive over the summation [9, p. 82], we get, by Corollary 3.2.(i) and Proposition 3.17.(i), m m m h(A x B) = h(A x \ A.P.) = h( £ A . (A x P.)) <_ £ A .h(A x P.) = 1 1 1=1 1 1 1=1 1 1=1 1 m = nh(A) £ A. = nh(A) . Similarly, h(A x B) <_ nh(B) . The assertion for i=l 1 that equality is obvious from Proposition 3.17. (i) . In the rest of this chapter, we shall study the relation between h(A) and per (A) , the permanent function of A , where A E 9, . First, however, in order to increase, understanding of the function hCA) , we l i s t the similarities between hCA) and t h e rank function p(A). (1) If A M , then 1 <_ p (A) <_ n . (1) ' If A e ftn , then (2) p (A) = p (AC) . (2) ' h(A) = h(A t ) . (3) p (A + B) <_ p (A) + p (B) . (3) ' (4) h(A + B) < h(A) + h(B) for — p(AB) <_ min {p (A), p(B)} . (4) ' h(AB) <_ min (h(A), h(B)} 1 <_ h(A) <_ n . (Corollary 1.5) (Trivial) m A = © I A. , then i=l 1 m A = €> I A. , then 1=1.1 A,B in D . (Lemma 3.1.(i)) n for A,B in R m p (A) = 7 p (A) . i=l m h(A) = £ h(A.) . 1 i=l . (Theorem 3.4. (i)) (5) If (5) * If (6) If P and Q are non-singular, then p(A) = p(PAQ) . (6)' If P and Q are permutation matrices, then h(A) = h(PAQ) . (Trivial) (Trivial) The similarities would be even more striking i f Conjecture 3.9 and i t s generalization (Conjecture 3.20 below) are true since they are exactly the analogue of Sylvester's law and Frobenius' inequality for the rank function, respectively [14, pp. 27-28]. Conjecture 3.20: Let A,B, and C be in ft^ . h(AB) + h(BC) <_ h(B) + h(ABC) . for B = I .) Then (Conjecture 3.9 is a special case of this In fact, i t was the above listed similarities together with some observations and experiments that tempted us to make the Conjectures 3.9 and 3.20. In [11], Marcus and Mine proved the following theorem. Theorem 3.21: A If A£ is normal, then matrix or n = 2 , then per(A) <_ j per(A) <_ P ^ and A= and in addition, i f " ^ ^ 2 with equality i f f A is a permutation • Our main result concerning this w i l l be to show that this theorem s t i l l holds i f we replace p ( A ) by bound is an improvement on the old one. inequality between per(A) Proposition 3.22: equality i f f Proof: If A= J and h(A) and that the new upper But first of a l l , a simple h(A) : A e ft , then . per (A) <_ — -jh(A)t n n ' This is immediate from the definition of with, per(A) and the arithmetic - geometric mean inequality. Theorem 3.23: A If A e ft^ , then is a permutation matrix. with equality i f f Proof: If per (A) <_ j^p-j^ A is also normal, then A is a permutation matrix or Assume first that proved [11, Theorem 1] that denote the eigenvalues of with equality i f f A is normal. n = 2 and A= • Then Marcus and Mine 1n n per(A) < — V |A.I , where — n>, 1 l 1 r=l A . per(A) < n ( A ) A , , A„, 1 2 Since i t is well known that each A n eigenvalue of a d.s. matrix does not exceed one in modulus, we have n I A . I < I A'. I 1 n per CA) <, —•• J U.l . Since A —n .u, i i=l n n normal, the classical Schur's inequality gives £ |X.|2 = £ |a..|2 = 1 i=l i,j=l 1 J n n 1 = £ a..2 and hence perCA) <_ —- £ a..2 . Furthermore, by a 1 J n 1 J i,j=l i,j=l ' 1' •1 2 for a l l i , and hence 2 f result of Marcus and Ree [18], there exists a diagonal n n V a..2< y a. i j=l 1 3 ~ i=l such that a 1 n and consequently, per (A) < — y n i=i .... If equality holds, then, for a l l n >_ 3 , this implies that i = 1, 2, | A ^ | =1 n , for a l l |A.J a. 1 0 N i = 1, 2, ... < ^ ~ = |A.J n . 2 h(A) n . If Hence by a result of Mirsky and Perfect [19, Theorem 5], we conclude that A is a permutation matrix. If n = 2 , then A= Hence per(A) = ~ ~ depending on whether x = 1 or Hence A= For general x = -| . or x 1-x 1-x X would imply that x2 + (1-x)2 = x x >_ . If or x <_ y If A , we apply the inequality x = 0 (per(A)) 2 <_ per(AA ) or x = -|- . The converse is obvious. (per(AB))2 <_ per (AA1") per (BfcB) of Marcus and Newman [17, Theorem 5] to get, by putting t 1-x x2 + (1-x)2 = x , we get x2 + (1-x)2 = 1-x , we get A is a permutation matrix. or B= I , t . Since AA e ftn is normal, the above result o r and Theorem 3.4. (i) together imply that (per(A))2 <_ ^ <_ per(A) <_ | n j * ^ equality holds, i t must also hold in the h,(A)te inequality (per(AB))2 <_ per(AA t )per(B t B) . Equality implies that either is (i) a row of where A or a column of B consists of zeros or D is a diagonal matrix and case, since D = A ? 1 1 B= I and since and hence E 0, n permutation matrix. (ii) A = BDP P is a permutation matrix. (i) is impossible, we get D= I . n Therefore Afc = P or In our A*" = DP or A = P1" is a The converse is again obvious. As an immediate consequence, we obtain the following well known upper bound for Corollary 3.24: per(A) If Ae ^ [16, Lemma 1]. , then per(A) <_ 1 with equality i f f A is a permutation matrix. Proof: This follows from Theorem 3.23 since equality i f f A is a permutation matrix. Theorem 3.25: If Proof: Let A^, A p (A) >_ r . Since Then Hence Ae , then b = 0 = trace(B) <_ p(B) t n e r r non-zero eigenvalues of | A.J <_ 1 | A 1 1 + |A | <^ r <_ p (A) . Q such that maximum diagonals. e A is d.s., trace ( A ) = A - , + A + * " + A <_ |AjJ + IA2I + and h(A) <_ p (A) . "*'» ^ r 2 > 1 2 P h(A) <_ n , with 1 + A „ + for a l l i = l , 2, -"+A|< 2 r1 — Now choose permutation matrices B = PAQ has the main diagonal as one of its Then, since B e ft,^ , we have h(A) = h(B) = = p (A) . In view of Theorem 3.25 and the fact that a l l non-singular A. p(A) = n for nxn matrices whence Theorem 3.21 yields the t r i v i a l r. bound perCA) <_ 1 , we see that the. bounds obtained in Theorem 3.23 are indeed improvements on those in Theorem 3.21. Concerning Theorem 3.23, we do not know whether the square root can be removed in general. The following propositions answer this question partially. Proposition 3.26: Let A e ft^ . r PAQ = # Y A. , where •tli i and Q, and Y n. = n , and i f , -. I i=l r > 1 , h. per(A.) < — i — n. U = h(A_^) , then If for some permutation matrices A. e ft i n . for a l l P , i = 1, 2, * • • , r , i=l, 2, • • • r , where I per(A) <_ with equality i f f A is a permutation matrix. r y n. Proof: S i n c e —— nr —^—= n. r i=l I h. i=l = Yj <_ Jr , Y n • • • n±. - - n < i=l h • • • h . , , , h i=l .1 I r 1 I r 1 1 , where h. " denotes the deletion of that factor, we have .' ', i r r i=l r per(A) = per(PAQ) = " J J p e r ^ ) <_ " J f ~ - - i - _ i _ i=l i=l i y =- then f o r a l l i = 1, 2, ' Hence r[ n. = ' i=l i=l, 2, so is A . I r h. . J ' i i=l r . Since Hence each ***, ' . T f equality n i=l holds, h 1 1 r , n.. ••• n. ••• n =h- ••• 1 i r l ( h. < n. , we get l — i h. = n. i i h . ••• I for a l l A^ is a permutation matrix and therefore The converse is obvious. h. r Proposition 3.27: such that . Let per(A) <_ per(B) equality i f f Since and .If there is a normal matrix h(B) h(A) , then n = 2 per(A) <; per(B) < < — — n — inequality is clear. (ii) h(A) = n n = 2 , and and hence 1 per(B) = — and hence conjecture is true for B= and A= n = 2 , • B is a In case ( i ) , A is a permutation matrix. 1 per(A) <_ — . with by Theorem 3.23, the n . B e ft n, per'(A) 5, If equality holds, then either (i) permutation matrix or implies that n A is a permutation matrix or Proof: (ii) , Aeft h(B) = n In case Since the van de Waerden per(A) = — , and therefore A= . The converse is obvious. It was once conjectured that for per(A) >_ max {per(AA t ), per(AtA)} (e.g. Aeft [12], Conjecture 2). given examples to show that this is false in general. if , n Newman has It turns out that A e ftn is such that the above inequality is reversed, then the square root can be removed from Theorem 3.23. Corollary 3.28: then n = 2 Proof: If per (A) <_ and A e ft^ satisfies , with equality i f f A= A is a permutation matrix or . We may assume that normal, and since per(A) <_ max (per(AA t ), per(A t A)}, h(AAt) < h(A) follows from Proposition 3.27, per(AAt) >_ per(AfcA) . Since AAC by Theorem 3.4.(i), the assertion is Corollary 3.29: per(A) <_ or n = 2 } and Proof: h( A * Lf satisfies with equality i f f A= Since A Ae A + A^ perC—2~~^ ' per(A) t n e n A is a symmetric permutation matrix . A + A*" — is symmetric and hence normal, and since ) = y h ( A + A*") <_-|{h(A) + hCAt)} = h(A) by Lemma 3.1.(i), the assertion except "symmetric" follows from Proposition 3.27. But i f A + A*" — for some a , is a permutation matrix, then 2 where a. 10(1) r i=l, ,.N + a ,.v .=2 2, ' ' * , n . Hence a (i) i A is a symmetric permutation matrix. The converse is obvious. We close this chapter by giving some upper bounds for per (A x B) in terms of h(A) In [2], the upper bound for Proposition 3.30: <^ min " | ( ~ ~ " ) ^ » Let (~~~)^ • and per(A h(B) , where x B) per(A x B) <_ min | ~ ~ ~ » ^ ^ ^ j A and Then £2^. per(A x B) <_ B are also normal, then with equality i f f - B are in was studied by Brualdi. A,B be in ft^ . If A and A and B are both permutation matrices. Proof: imply that Since A x B e tt^z » Theorem 3.23 and Proposition 3.19 per(A x B) <_ | • • ^ = min I ^ rf ^ ^ ' ^r^^ ^} " ^ -y A a n <_ j ^ - min[nh(A) , nh(B)] ^ B a r £ A x B , and hence, by the same argument, we get a ^ s o normal, then so is per(A x B) <_ h since n2 ^ 2 , ( A I 1 min {^~, B ) AxB . In [2], Brualdi proved that for r m and If equality holds, then n . Hence A and B The converse is obvious. per(A x B) < K (per A) n (per B) m r — mn depending on \ must be a permutation matrix. are both permutation matrices. Remark 3.31: ^ where K mn Ae H n and is a certain constant He conjectured that K = (™lL: (m!) we restrict A and Be H , m B to be d.s. matrices and put ^ jf (n!) n = m , then i t is natural to compare the bound given by this conjecture and that given in Proposition 3.30. For example, i f yields A and ^n \ * (n!)2n n = 1 [2, § 3 . 7 ] . , and i t is known that per(A x B) <_ ^ ^ n \.' >_ 1 (nir with equality i f f n On the other hand, i f A= B= , then Proposition 3.30 while Brualdi's conjecture yields (n 2 )! , n! . n , — ) v( — , ,.2n n ' (n!) n per v(A x B) < — — ( ^ B are permutation matrices, then Proposition 3.30 per(A x B) <^ 1 while Brualdi's conjecture yields per(A x B) <_ yields We remark that in general, they are not comparable. n! . n (n 2 )! = ——ir~ n / n.2n n (n ) — ) Cn ) ' per(A x B) = per(J x J ) = per(J 2 ) = ~— rr n n n ( n 2 ) n = , (n 2 )! —~T 0z \ (n ) n 2 > clearly • _. Since (n2) ! 1 ~z < 2 ) n . BIBLIOGRAPHY G. Birkhoff, Tres observaciones sobre el algebra l i n e a l , Univ. Nac. de Tucuman, Rev. Ser. A 5 (1946), 147-151. R. A. Brualdi, Permanent of the Direct Product of Matrices, J. of Math., Vol. 16, No. 3 (1966), 471-482. Pacific R. A. Brualdi and H. W. Wielandt, A Spectral Characterization of Stochastic Matrices, Linear Algebra and Its Application, Vol. 1, No. 1 (1968), 65-71. P. J. Eberlein, Remarks on the van der Waerden Conjecture, Linear Algebra and Its Application, 2 (1969), 311-320. II, P. J. Eberlein and G. S. Mudholkar, Some Remarks on the van der Waerden Conjecture, J. Comb. Theory (1968), 386-396. II G. Frobenius, Uber Matrizen aus nicht negativen Elementen, Kgl. Preuss Akad. Wiss. (1912), 456-477. S.-B. J. Kapoor, Matrices which, Under Row Permutations, Give Specified Values of Certain Matrix Functions, University of British Columbia Ph.D. thesis, June 1970. D. Konig, Theorie der endlichen und unendlichen Graphen, Chelsea, New York, 1950. C. C. MacDuffee, 1946. The Theory of Matrices, rev. ed. New York, Chelsea M. Marcus and H. Mine, Some Results on Doubly Stochastic Matrices, Proc. of Amer. Math. Soc. 13, No. 4 (1962), 571-579. Math. Soc , Inequalities for General Matrix Functions, Bull, of Amer. , Permanent, Amer. Math. Monthly 72 (1965), 577-591. , On a conjecture of B. L. van der Waerden, Proc. Comb. P h i l . Soc . 63 (1967), 305-309. Weber and , A Survey of Matrix Theory and Matrix Inequalities, Prindle, M. Marcus, H. Mine, and B. Moyls, Some Results on Non-Negative Matrices, J. of Research of the National Bureau of Standards, Vol. 65B, No. 3, July-Sept. 1961, 205-209. M. Marcus and M. Newman, On the inimum of the Permanent of a Doubly Stochastic Matrix, Duke Math. J . , Vol. 26, No. 1 (1959), 61-72. [17] M. Marcus and M. Newman, Inequalities for the permanent function, Ann. of Math. (2) 75 Q962), 47-62. [18] M. Marcus and R. Ree, Diagonals of Doubly Stochastic Matrices, Quart. J. of Math. Oxford 10, Q959), 296-302. [19] H. Perfect and L. Mirsky, Spectral Properties of Doubly Stochastic Matrices, Monat. fur Math. 69 (1965), 35-57. [20] H. J. Ryser, Combinatorial Mathematics, Carus Monograph 14, Wiley, New York, 1963. [21] R. Sinkhorn and P. Knopp, Problems Involving Diagonal Products in Non-Negative Matrices, Trans, of Amer. Math. Soc. 136 (1969), 67-75. [22] van der Waerden, B. L . , Aufgabe 45, Jber. Deutsch. Math. Verein., 35 (1926), 117.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Some combinatorial properties of the diagonal sums...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Some combinatorial properties of the diagonal sums of doubly stochastic matrices Wang, Edward Tzu-Hsia 1971
pdf
Page Metadata
Item Metadata
Title | Some combinatorial properties of the diagonal sums of doubly stochastic matrices |
Creator |
Wang, Edward Tzu-Hsia |
Publisher | University of British Columbia |
Date Issued | 1971 |
Description | Let Ωn denote the convex polyhedron of all nxn d.s. (doubly stochastic) matrices. The main purpose of this thesis is to study some combinatorial properties of the diagonal sums of matrices in Ωn. In Chapter I, we determine, for all d.s. matrices unequal to Jn ; the maximum number of diagonals that can have a common diagonal sum. The key will be a Decomposition Theorem that enables us to characterize completely the structure of a d.s. matrix when this maximum number is attained, provided that the common sum is not one. When the common sum is one, the question is more difficult and remains open. Several applications of the Decomposition Theorem are also given. In Chapter II, we concentrate on the diagonals with maximum diagonal sum h and the diagonals with minimum diagonal sum k. We obtain the best possible bounds for entries on these diagonals and for various kinds of functions of h and k. The key will be a Covering Theorem that enables us to analyze the cases when those bounds are attained. A conjecture is given. In Chapter III, we study the properties of the h-function and the k-function, the functions that associate with each d.s. matrix its maximum and minimum diagonal sums respectively. In particular, we investigate the behavior of these functions on the Kronecker product of d.s. matrices. Furthermore, we show that the h-function is very similar to the rank function ƿ in many respects. We also prove that for A ε Ωn, h(A) ≤ ƿ(A) and per (A) ≤ [formula omitted] which improves a result by M. Marcus and H. Mine. A conjecture is given. |
Subject |
Matrices |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-04-27 |
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.0080535 |
URI | http://hdl.handle.net/2429/34043 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1971_A1 W35.pdf [ 3.56MB ]
- Metadata
- JSON: 831-1.0080535.json
- JSON-LD: 831-1.0080535-ld.json
- RDF/XML (Pretty): 831-1.0080535-rdf.xml
- RDF/JSON: 831-1.0080535-rdf.json
- Turtle: 831-1.0080535-turtle.txt
- N-Triples: 831-1.0080535-rdf-ntriples.txt
- Original Record: 831-1.0080535-source.json
- Full Text
- 831-1.0080535-fulltext.txt
- Citation
- 831-1.0080535.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-0080535/manifest