SOME INEQUALITIES WITH COMBINATORIAL APPLICATIONS by WILLIAM ROBERT GORDON B.A., Univ e r s i t y of B r i t i s h Columbia, 1957 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF ARTS i n the Department of MATHEMATICS We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA August, 1961 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make i t freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of ray Department or by his representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. W. R. G O R D O N Department of 1 V 8 C T U WL Oil V, C. £ The University of British Columbia, Vancouver 8 , Canada. Date 13 ^ i ^ V e M x L ^ I ; 1 9 l ( ABSTRACT Some i n e q u a l i t i e s of H. J . Ryser with combinatorial applications are generalized. Let f be a non-negative concave symmetric function on v-tuples of non-negative r e a l s . I f f has the property that when 0a + (l-e)b <£ G f = f _ 1 ( ^ t : t > O J ) , 0 < 6 < 1, then f(6a + (l-6)b) .= 6f(a) + ( l - e ) f ( b ) , then we say that f i s s t r i c t l y concave. ( S i m i l a r l y , i f f i s convex and has the property j u s t mentioned, then we say that f i s s t r i c t l y convex). Let H be a non-negative hermitian matrix with eigenvalues . . . , ~K where > . . . > "K > ~K . , = • • • = A = 0. Let h be an integer, 1 < h, 1 — — e e+1 v such that e <g h ^ v and define k and ^ by k = trace (H)/h, X <, k + (h-l ) A <, A , . Define the matrix B of order h by B = (k -?Ol + M , h - 1 where I i s the i d e n t i t y matrix a l l of whose ent r i e s are l ' s . Let B = B + 0, where the matrix B of order v i s the d i r e c t sum of the o V o matrix B of order h and the (v-h)-order zero matrix. Let f(H) denote f ( A 1 » •••» Ay)* Then we prove theorems of the following nature. THEOREM: The matrices H and B s a t i s f y . o *-f(H).£ f ( B ) . — o If f i s s t r i c t l y concave and i f , ..., 7^) € G f then equality holds i f and only i f H and B q have the same eigenvalues. I f f i s s t r i c t l y concave and i f f o r some integer z, G f i s the set of non-negative vectors with at l e a s t z p o s i t i v e coordinates and i f k + (h-l»v ^ 0 and z ^ h or k + (h-l ) A = 0 and z < h, then f(H) = f ( B Q ) i f and only i f H and B Q have the same eigenvalues. If f Is convex a similar theorem with the inequality reversed can be proved. We discuss various choices of the function f and indicate some applications of the results to some combinatorial problems. TABLE OF CONTENTS I Statement of Results i II Proofs of the Results 5 III Applications 14 Acknowledgments I wish to acknowledge the assistance of and express my gratitude to Dr. Marvin Marcus who not only suggested the problem but who a l s o contributed the major ideas i n i t s s o l u t i o n . I wish a l s o to thank the National Research Council of Canada and the United States National Bureau of Standards f o r f i n a n c i a l assistance rendered to me during the preparation of t h i s t h e s i s . I STATEMENT OF THE RESULTS In a recent paper H. J . Ryser obtained the following r e s u l t s [1]. Let H be a non-negative hermitian matrix of rank e and order v with eigenvalues 7^, where ^ > ^ \ > \»+l = *** = \ ~ °* Let h be an integer, h > 1, such that e <g h ^ v, and define k and \ by trace (H) = kh, A h < k + (h-l)A < \ v Define the matrix B of order h by B = (k-A)I + 7\J, where I i s the i d e n t i t y matrix and J i s the matrix a l l of whose entries are l ' s . Let B = B + 0, o where the matrix B of order v i s the d i r e c t sum of the matrix B of order o h and the zero matrix of order (v-h). Let k* = trace (H)/v, V v i = l j=l 1 J A* = ((M A ) - k * ) / ( v - l ) . Define the matrix B* of order v by B* = (k* - A*) I + A*J. - 1 -- 2 -til F i n a l l y l e t C r(A) denote the r — compound matrix of A, and P r(A) denote the r ^ 1 induced power matrix of A (for d e f i n i t i o n s of C and P see [1]). Then r r THEOREM 1: The matrices H and B s a t i s f y . O i. trace (C (H)) < trace (C (B )) (1 g r < v ) . r r o Equality holds f o r r = 1, h + 1, ..., v. If k + (h-l)A 4 0 and equality holds f o r an r, 1 < r ^ h, or k + (h-l)A = 0 and equ a l i t y holds f o r an r, 1 < r < h, then there e x i s t s a unitary U such that H = U *B U. THEOREM 2: The matrices H and B* s a t i s f y trace (C (H)) £ trace (C (B*)) (1 £ r £ v ) . ,r r Equality holds f o r r = 1. If k* + (v-l)A* ^ 0 and equality holds f o r 1 < r v, or i f k* + (v-l)A* = 0 and equality holds f o r an r, 1 < r < v, then H = B*. THEOREM 3: The matrices H and B s a t i s f y o -trace (i»r(H)) ^ trace (P^ (B Q)) (1 ^ r ^ v) . Equa l i t y holds f o r r = 1. If equality holds f o r "an r > 1, then there e x i s t s a unitary U such that H = U ^^^U. THEOREM 4 : The matrices H and B* s a t i s f y trace (P (H)) ^ trace (P (B*)) (1 < r < v ) . r — r Equa l i t y holds f o r r = 1. If equality holds f o r an r > 1, then H = B*. - 3 -Ryser applied some of these r e s u l t s to c e r t a i n combinatorial problems such as the determination of necessary and s u f f i c i e n t conditions f o r both the existence of complete f i n i t e oriented graphs and the existence of solutions to the v, k, A problem. That h i s r e s u l t s are applicable to such combinatorial problems i s due to two f a c t s : one, i n such problems there a r i s e s a matrix A which contains the combinatorial information of the problem and while, i n general, A i s -T not non-negative hermitian, the matrix A A i s non-negative hermitian; two, -T i f B = PAQ, where P and Q are permutation matrices, then trace (C ( B B ) ) = - r -T trace (C (A A ) ) , i . e . simultaneous permutation of the rows and columns of r -T -T A A leave i n v a r i a n t trace (C (A A ) ) . r In what follows we state and prove generalizations of Ryser's r e s u l t s . Our proofs w i l l depend only on the properties of concave and convex functions and not, as Ryser's proofs do, on the properties of majorizing sequences. Throughout the remainder of t h i s work we s h a l l always assume that a l l vectors mentioned have non-negative coordinates. Let f be a non-negative concave symmetric function on v-tuples of non-negative r e a l s . I f f i s such that i f 9a + (l-8)b £ Gf = f 1 ( [ t : t > o]), 0 < 8 < 1, then f(6a + (l-6)b) = 6f(a) + ( l - 6 ) f ( b ) i f and only i f a and b are proportional ( a ^ b ) , then f i s c a l l e d s t r i c t l y concave. S i m i l a r l y , i f f i s convex and s a t i s f i e s t h i s l a s t condition then f i s c a l l e d s t r i c t l y convex. If A; i s a matrix with eigenvalues JJ^ ^ 0, ..., jj. ^ 0 l e t f(A) denote f ( j j ^ 1 , . ). Then THEOREM 5: The matrices H and B q s a t i s f y f(H) £ f ( B D ) . - 4 -I f f i s s t r i c t l y concave and i f (7^, .... 7\y) € G f then equality holds i f and only i f H and B q have the same eigenvalues. If f i s s t r i c t l y concave and i f f o r some integer z, G f i s the set of (non-negative) vectors with at l e a s t z p o s i t i v e coordinates and i f k + (h-l)Tv 0 and z <, h or k + ( h - l ) A = 0 and z < h, then f (H) = f.(B ) i f and only i f H and B q have the same eigenvalues. THEOREM 6: The matrices H and B * s a t i s f y f(H) £ f ( B * ) If f i s s t r i c t l y concave and i f (7^, ..., 7^) € G f, then equality holds i f and only i f H = B * . If f i s s t r i c t l y concave and i f f o r some integer z,G f i s the set of (non-negative) vectors with at l e a s t z p o s i t i v e coordinates and i f k* + ( v - l ) A * ¥ 0 and z g v o r k* + (v-l)Tv* = 0 and z < v then f(H) = f ( B * ) i f and only i f H = B * . If f i s assumed to be convex instead of concave then we have THEOREM 7: The matrices H and B s a t i s f y ^ , ._ 0 i-f(H) ^ f ( B Q ) . I f f i s s t r i c t l y convex and i f (7^ , . . . , A y ) 6 G f then e q u a l i t y holds i f and only i f H and B q have the same eigenvalues. I f f i s s t r i c t l y convex and i f f o r some integer z>G f i s the set of (non-negative) vectors with at l e a s t z p o s i t i v e coordinates and i f k + (h-l)Tv 4 0 and z $; h or k + ( h - D A = 0 and z < h, then f (H) = f (B q ) i f and only i f H and B q have the same eigenvalues. THEOREM 8: The matrices H and B * s a t i s f y f(H) ^ f ( B * ) . If, f Is s t r i c t l y convex and i f O^, •••, A y ) € G^ , then equality holds i f and only i f H = B*. If f i s s t r i c t l y convex and i f there e x i s t s an integer z such that G f i s the set of (non-negative) vectors with at l e a s t z p o s i t i v e coordinates and i f k* + (v-l)?v* 4 0 and z ^ h or k* + (v-l )A* = 0 and z < h, then f(H) = f(B*) i f and only i f H = B*. II PROOFS OF THE RESULTS F i r s t we mention some known r e s u l t s which we s h a l l need l a t e r . I f A i s an n-square matrix, then a diagonal of A i s a set of the form l a . . , a , a , ]. where a i s a permutation on the set 1 10(1) 2tf(<i) na(n) l [ l , 2, n] . The main diagonal of A i s the set { &n> &22' & n n l * THEOREM (Frobenius-Konig): Let A be an n-square matrix and l e t S be a set of e n t r i e s of A. Then every diagonal of A contains an element of S i f and only i f S contains a set of elements c o n s t i t u t i n g an s b_£ t submatrix of A with s + t = n + 1. For a proof of t h i s r e s u l t see [2]. An n-square matrix A i s doubly stochastic i f the elements of A are n n non-negative and £ a . = 1 ( j = 1, ..., n) and 2 a ( i = 1, ..., n) . i = l J J=l 1 J THEOREM ( B i r k h o f f ) : ^ f A i s an n-square doubly stochastic matrix,then A 2 i£ i n the convex h u l l of at most n - n + 1 permutation matrices. In the proof of t h i s theorem the Frobenius-Konig theorem i s used to show that A must have a diagonal a l l of whose elements are p o s i t i v e [3]. If d i s a p o s i t i v e diagonal of A and t i s the l e a s t element of d (we may as well assume that t < 1, f o r i f t = 1 then c l e a r l y A i s a permutation matrix) and i f P i s a permutation matrix with l ' s i n the positions - 6 -corresponding to the positions of the elements of d, then the matrix A—tP A^ = ^ i s a doubly stochastic matrix with one more zero element than A. The proof i s completed by an induction on p, the number of po s i t i v e e n t r i e s i n A. LEMMA 0: Let A be a non-negative hermitian matrix of order n with eigenvalues A, » •••> ~h • Suppose that A, ^ ••• J> A and l e t l n 1 — — n u. , ..., u be. an orthonormal set of eigenvectors of A corresponding l n to A-^> • • •» AQ r e s p e c t i v e l y . Let h be an integer, 1 £ h £ n. If u i s a number such that Afl <C |A <^ 7^, then there e x i s t s a unit vector X q i n the space spanned by u^, ..., u^ such that (HX O,X q) = H . Proof: Since Afa ^ M ^ A1 there ex i s t s 0, O ^ B ^ l , such that (1-8) A. + &\ = p . Let a = 6 ^ , a = (1-8)^, and define x = a u + a u . Jul J. J. & O X X A H Then (Hx o, X q ) = ( H ^ + a ^ ) , ( a ^ + a ^ ) ) = + | a a | \ = 6A X + d-e)A h = u • Let f be the concave function defined on page 3 . LEMMA 1: Let a ^ \ a^ P^ be non-zero v-tuples of non-negative r e a l s . P If 2 8 . = 1 and 0 < 6 (j=l, .... p) then j=l J J P (J) P (J) f ( 2 B ayj') ^ 2 6 f ( a V J ' ) . j=l 3 j = l J P (j) If f i s s t r i c t l y concave and i f 2 8 . a V J / t G then equality holds i f and i - l ^ (1) (p) J only i f a *v .. P (j) P (j) Proof: C l e a r l y f ( 2 8.a V J /) £ 2 6 f ( a V J ' ) . j=l J j=l J P (J) Suppose that f i s s t r i c t l y concave, that 2 8 a & G , and that j=l J P (J) P (J) f ( 2 8.a V J ) = 2 8 . f ( a ^ J ' ) . j= l J j = l J - 7 -Now f ( 2 6.a ( J )) = f ( 6 J a ( i ) + (1 -e . ) 2 T - ~ a ( J ) ) > e . f ( a ( i ) ) + ( l - 6 . ) f ( 2 -r-4- a ( J ) ) Jjti i £ 6 f ( a ( i ) ) + (1-6,) 2 T-4- f ( a ( J ) ) " 1 1 J * l 1 _ 6 i P (J) = 2 6.f ( a V J ' ) ( i = 1, p). j=l 3 Therefore, since we are assuming equality, we have that 0 0 f ( 6 . a ( l ) + (1-6.) 2 T - * r a ( J > ) = 6 f ( a ( l ) ) + ( l - 9 . ) f ( 2 T~4- a ( J ) ) J * i i J5*i i fo r (1 s 1, p), and so,since f i s s t r i c t l y concave, ~m 1 _ e i ( i = l f " " p ) -Thus there e x i s t non-zero numbers )s ( i = 1, ..., n) such that 0 M , a ( l ) = 2 a ( J ) ( i = 1, ..., n). Therefore 1 j * i 1 " 6 i M (1-6 ) a ( i ) = 2 6 . a ( J ) j ^ i J yx (1-6 ) a ( i ) + 9 a ( 1 ) = 2 6 . a ( J ) ( i = 1, n). j=l J Hence a ^ / ^ / 2 6 . a ^ ( i = 1, ..., n) and so a ^ 1 ^ .. • r^, a^P\ j=l J LEMMA 2 : Tf H i s a non-negative hermitian matrix with eigenvalues A , , A and i f Ix,, .... x ) i s an orthonormal set of vectors then 1 n i l n i \ ) £ f ( ( H x ^ X ; L ) , (Hx n, x n ) ) . If f i s s t r i c t l y concave and i f ( A - , . . . , A ) £ G~ then equality holds — X n f i f and only i f ((Hx^, X j ) ) i s a diagonal matrix. \ - 8 -Proof: If H = 0 the r e s u l t i s t r i v i a l l y true, hence assume H ^ 0. Let K = ((Hx , x . ) ) . Then K = XHXT, where X i s the unitary matrix whose row vectors are, i n order, x, , x . Thus H and K have the i ' 1' ' n same eigenvalues S Let u ^ ..., be an orthonormal set of eigenvectors of H corresponding to A , . . . , 7^ r e s p e c t i v e l y . Let A = (7, , . . . , X ) and l e t a. , . . . , a be the main diagonal elements 1 V 1 TI of K. Then a = (Hx., x.) i x i n n = (H 2 (x, , u )u , 2 (x , u )u ) . i s s ^ n i t t s=l t=l n n = ( 2 ( X i, u s ) A s V 2 ( X i, u t ) u t ) s=l t=l n 2 = 2 I (x , u )| 7vi ( i = 1, n). j=l J 1 i2 Let S = (s ) = (|(x , u )| ). Then c l e a r l y S i s doubly stochastic and a = (S.^, A) where i s the i — row of S,(i = 1, ..., n). By Birkhoff's theorem there e x i s t permutation matrices P ^ , P^p^ P ( i ) P such that S = 2 6 .P , where 2 6. = 1 and 0 < 9. < 1 ( j = 1, p). j=l 3 j=l 3 3 P ( i ) Thus a± = (S t , A) = (( 2 6 P V J ' ) i , A). Therefore f ( ( H x 1 , x±), (Hx n > x n>) 1 j=l P (J) = f(SA) = f ( 2 6 .P A)• But f i s concave and so, by lemma 1, P J = 1 J p f ( 2 e.P^^A) ^ 2 0 f ( P ( J ) A ) . But P^ J ) i s a permutation matrix and j=l J ' " j = l J f i s a symmetric function and therefore f ( P ^ ^ A ) = P = If •••> P>-Thus f ( ( H x 1 , X ; L ) , (Hx n, x n ) ) ^ f ( A 1 , . . . A Q ) . - 9 -Suppose now that f i s s t r i c t l y concave, that (7^, 7^) 6 G f, and that f ((Hx. , x,), (Hx , x )) = f(A,, V ) . This means 1 1 n n 1 ,n that f ( 2 e.P ( J )A) = 2 6 . f ( P < J > A ) and so, by lemma 1, 6 P ( 1 \ ^ .,.^.B P ( p )7 i=l J i=l J 1 P (1) ( i ) Thus, s e t t i n g P = P,we have that 9 ^ A = d^P)\ f o r some number d. ( i = 1, p). No d. can be zero otherwise a l l the d J would i i i P (j) be zero and hence 2 9 .P A would be zero. This would imply that j=l 3 Ck^t •••» 7^) = 0 which would contradict the assumption that H j£ 0. P (j) ' P Thus 2 9 . P A = SA = dPA , where d = 2 d . . But JSA = JA = JdPA - dJA j=l J i = l 1 and so d = 1. Therefore SA = PA. Thus a. = ( i = 1, n) i O A I ) where (J i s the permutation corresponding to the permutation matrix P. n 2 n 2 -T n 2 * n 2 Since 2 a. = 2 A. = trace (KK ) = 2 C2. + 2 2 |k. .1 , i t . f o l l o w s i = l 1 i = l 1 1=1 1 i=l ,4=1 1 J that K = diag (0^, ..., C O , i . e . K = ((Hx^ x^)) i s a diagonal matrix. LEMMA 3: Let a = (a^, ...., a^) and l e t n be an integer 1 ^ n ^ v. Then 1 n 1 n f ( a ) ^ f ( - ^ a . , - Z*y a n + 1 , a^. If f i s s t r i c t l y concave and i f a € Gj,then equality holds i f and only i f S_ — • • • = 3 . • 1 n Proof: The r e s u l t i s t r i v i a l l y true i f a = 0, so assume henceforth that a ^ 0. Let P = P + I , where P i s the permutation matrix corresponding n v _ n n to the f u l l n-cycle and I i s the (v-n)-order i d e n t i t y matrix. v-n n n Since f i s symmetric f(a) = f(Pa) = - 2 f ( P J a ) £ f ( - 2 P Ja) n . , ~ n . , J=l J=l 1 n 1 n ~ f ( n ; Z , V n 4 Z , a j ' V l ' V * 3=1 ° j=l d Suppose now that f i s s t r i c t l y concave, that a 6 G^, and that 1 n i n f (a) = f (—• 2 a ., ..., — .2 a . , a ,, , ..., a ). Then by leimna 1 n j=i J n j s i J n" K L v P a ... r*j Paa - a > Thus Pla = a f o r some number p. . Now u ^ 0 = a = n - 10 -otherwise then P^a =0, a = 0, co n t r a d i c t i n g the hypothesis that a £ 0. Hence we may assume u ^ 0 and so a^ = p- a t _ i ( m o , j ny (t = 1» ..., n). Therefore a.^ = l ^ a ^ . . If a_L = 0 then a2 = P a i = °' a 3 = ^ a 2 = °» a n = y a n - i = 0 i , e * a i = * S i m i l a r l y we can show that i f a ± = 0 (1 < i ^ n) then a 1 = ... = » n = 0. Therefore suppose that no a i = 0 f o r 1 g i ^ n. Then ]xn = 1 and, since P 1a ^ 0, a ^ 0, and neither i s zero, i t follows that p- = 1. Therefore a, = ... = a . 1 n We s h a l l now prove theorems 5 and 6. Proof of theorem 5: Let u,, .... u be an orthonormal set of eigenvectors . • 1 v of H corresponding to A , 7^ r e s p e c t i v e l y . Since 7^ g k + (h^l)X £ 7^ there i s (by lemma 0) a un i t vector x^ i n the space spanned by u^, ..., such that (Hx , x ) = k + ( h - l ) ^ . Choose orthonormal x , ..., x i n the 1 1 & ii i n t e r s e c t i o n of the space spanned by u , u and the orthogonal complement of x1; l e t x ^ ^ = u ^ ^ , ..., x^ = . Then by lemma 2 f(H) = f ( A r . . . . 7^) ^ f ( ( H x 1 , X ; L ) , (Hx v,x v)) = f ( k + (h-l)Tv, (Hx 2, x 2 ) , (Hx v, x y ) ) = f ( k + (h-l)Tv, (Hx 2, x 2 ) , {Hxh, x h ) , 0, 0). By lemma 3 f ( k + (h-l )A, (Hk 2, x 2 ) , (Hx h, x h ) , 0, 0) h h ^ f(k + (h-l )A , — 2 (Hx , x ) , . . . , . — 2 (Hx , x ), 0, ..., 0). a _ x j=2 j=2 J J - 11 Now (k-A) = trace (H)/h - A 1 v - ( 2 (Hx., x.)) - A h j=l 3 3 Therefore and so 1 h - (k + (h-l)A + 2 (Hx., x.) - Ah) h j=2 3 3 1 h - (k - A * 2 (Hx., x.)). h j=2 J J (k - A) = ~ 2 (Hx., x.) h h j=2 J J t — f 2 (Hx., x ) = k - A-h - 1 j=2 J J Thus f(H) > f(k + (h-l)A, k - A, .... k - A, 0, ..., 0) But B = ((k-A)I.+ AJ) + 0 and so k + (h-l)A, k - A, k - A, 0, o are the eigenvalues of B Q . Thus f(H),< f ( B ) . — o Suppose now that f i s s t r i c t l y concave, that 0\ , A y) 6. G f and that f(H) = f ( B ) . Then o fOvj, \ ) = f((Hx 1, X ; L ) , (Hxv, x v)) and so by lemma 2, ((Hx., x.)) is a diagonal matrix. Since we are as (A »^ . . . , . Ay) € i t follows (in the case of equality) that 1 h i h (k + (h-l)A, r - r 2 (Hx., x ), ..., — - 2 (Hx , x ), 0, 0) 6 G h - l j = 2 j j h-1 j_2 J J f Since in the case of equality h h f (k + (h-l)A, r-rr 2 (Hx., x ), ..., — 2 (Hx , x.), 0, 0) h-1 J = 2 j j h-1 j = 2 j j = f(k + (h-l)A, (Hx2, x 2 ) , (Hx2, x 2 ) , 0, 0) - 12 -i t follows by lemma 3 that W2i x 2 ) = ... = (Hx h, x h ) = k - A-Thus ((Hx., x.)) and B have the same eigenvalues, and therefore, since H i j o and ((Hx,, , x.)) are u n i t a r i l y s i m i l a r , i t follows that H and B have the i J o same eigenvalues. Suppose now that f i s s t r i c t l y concave, that there e x i s t s an integer z such that i s the set of x with at l e a s t z p o s i t i v e coordinates, and suppose that f(H) = f ( B Q ) . We have j u s t discussed the case i n which (7^, A y ) € G^. Therefore l e t us assume that Q^> • • • i A y ) £ G^. This means that f(7v1» A y ) = f (k + (h-l) A , k - A, k - A, 0, 0) = 0 If k + (h - l ) A 4 0 and z ^ h then k - A = 0: otherwise (k + (h - l ) A , k - A. • • • f k - A. 0, ...» 0) would have h ^ z p o s i t i v e coordinates. This would mean that (k + (h - l ) A , k - A> k - At 0, ..., .0) would belong to G f, which i s a co n t r a d i c t i o n . Therefore A = k = trace (H)/h. v Now \ k + ( h - l ) A = kh £ A, • But kh = trace (H) = 2 A,. Thus h " ' " 1 j - 1 J v A,. < 2 T\. <, A,- But A. ^ 0 ( j = 1, v) and therefore i t follows that h ~ . = 1 j - 1 J " A 0 = ... =7, = 0 and k + (h - l ) A = A, • Therefore ((Hx , x )) and B have /t v 1 . i j o the same eigenvalues, and consequently H and B q have the same eigenvalues. I f k + (h - l ) A = 0 and h > z then i t follows that (k - A) = 0 and hence A^ =-.•.. = A^ = 0, i . e. H and B q are both the zero matrix. Proof of theorem 6: Theorem 5 with h = v implies that f(H) g f ( B * ) . Suppose now that f i s s t r i c t l y concave, that (A^> •••> A y ) € G^, and that f(H) = f ( B * ) . Let x1 = (l/\fv, l / / v ) . Then (x , = 1 and - 13 -(Hx^, x^) = /v = k* + (v-l ) A * . Complete x^ to an orthonormal basis (x^» x^| . Then, by the argument i n the proof of theorem 5, (Hx , x.) i s a diagonal matrix whose eigenvalues are k* + (v-l)A*» k* - A* , k* - A* , and i n f a c t ((Hx , x )) = diag (k* + (v-l ) A * , k* - A*» .... k* - A * ) -Now (B*x l t a: ) = (k* - A*) + A*(Jx x, x 1 ) = k* + (v-l ) A * . and (B* x ±, X j ) = (k* - A * ) & i j + A*(Jx ±, Xj) ,k* - A* i f i = j / 1* = I (Here 6 . i s the well-known 10 If i * j i J Kronecker d e l t a ) . Thus ((B*x , x.)) = diag (k* + (v-l ) A * , k* - A* k*~A*) = ((Hx , x . ) ) . Therefore H = B*. 1 J Suppose now that f i s s t r i c t l y concave, that there e x i s t s an integer z such that i s the set of x with at l e a s t z p o s i t i v e coordinates, and suppose that f(H) = f ( B * ) . We have j u s t considered the case i n which (A-^ > • Ay) 6 G^. Therefore l e t us assume that (A^, . . . » Ay) ^ G f. This means that fO^ , A y ) = f ( k * + (v-l ) A * . k* - A*, • k* - A*) = 0. If k* + (v-l ) A * t 0 and z£ v then k* - A* = 0, otherwise (k* + (v-l ) A * , k* - A*» •••» k* - A*) would have v j> z p o s i t i v e coordinates and would therefore belong to G^, which i s a c o n t r a d i c t i o n . Thus k* = A*. v Now c l e a r l y trace (H) = trace (B*) = k* + (v-l ) A * = 2 A, = H /v. I t i = l follows, since H i s non-negative hermitian, that Ay H /v ^ Thus v Ay ^ Aj• Once again \^ ^ 0 f o r i = 1, ..., v. Consequently A x = k* + (v-l ) A * and A 2 = . . . = A v = 0. Thus ((Hx ±, X j ) ) = ((B*x ±, x..)) and so H = B*. I f k* + (v-l ) A * = 0 and z < v then c l e a r l y k* - A* = 0. Thus H and B* are both equal to the zero matrix. This completes the proof. - 14 -If f i s assumed to be convex and, where necessary, s t r i c t l y convex then Lemmas 1, 2, and 3 with the i n e q u a l i t i e s reversed hold. Thus, except f o r the obvious modifications, the proofs of theorems 7 and 8 are the same as those of theorems 5 and 6 r e s p e c t i v e l y . I l l A pplications In t h i s section we describe the region G f f o r various choices of f, in d i c a t e how Ryser's r e s u l t s follow from ours, and i n d i c a t e two a p p l i c a -tions of the r e s u l t s . Let f (a) = (E (a)/E ( a ) ) 1 / / p f o r 0 < p <, r , where E (a) i s the r r-p ~ r th r — elementary symmetric function i l 1 i . e . E (a) = S a ... a V r i,+ ... + i = r V 1 v 0 ^ 1 j * 1 If a has fewer than r p o s i t i v e coordinates then c l e a r l y E (a) = 0 and so r f ( a ) =0. If a has at l e a s t r p o s i t i v e coordinates then E (a) > 0 and r c e r t a i n l y E (a) > 0. Thus i n t h i s case G^ , i s the set of non-negative r-p f vectors with at l e a s t r p o s i t i v e coordinates. It has been shown [4] that f i s concave f o r non-negative vectors a and s t r i c t l y concave. Since trace (C (H)) = E (A,, ... A ) theorems 5 and 6 with f(a) = (E (a)/E (a)) r r J. v r r-p where p = r imply Ryser's r e s u l t s , theorems 1 and 2, r e s p e c t i v e l y . 1/r Now l e t f(a) = (h (a)) where h (a) i s the completely symmetric function r h \ of degree r, i . e . h (a) s 2 a, ... a If a has at l e a s t r . . . . 1 v i,+ ... + l *» r. one p o s i t i v e coordinate then c l e a r l y f(a) > 0 and i f a = 0 then f ( a ) = 0. 1/P - 15 -Thus i n t h i s case i s the set of non-negative vectors with at l e a s t one 1/r p o s i t i v e coordinate. I t has been shown [5] that h (a) i s convex f o r non-r negative a and i s s t r i c t l y convex. Since trace (P (H)) = ^ 0 ^ * •••> 7^)« 1/r theorems 7 and 8 with f ( a ) = (h (a)) imply Ryser's r e s u l t s , theorems r 3 and 4 r e s p e c t i v e l y . 1/ i l 1 Let f ( a ) = T (a) where T (a) = 2 &. ... 6., a, ... a V n n i,+ ... + i = n x l Av 1 V O ^ i . V ' (*) i f k > 0 J and k i s any number, provided that i f where 6^ = ( - l ) 1 ^ ) i f k < 0 i f k i s p o s i t i v e and not an integer then n < k + 1. Suppose k i s a p o s i t i v e integer and l e t m = < j ^ j i f k divides n Jj^j + 1 i f k does not d i v i d e n (Here [x] denotes the greatest integer i n x ) . If 5. = ( i ) i s to be j J defined then i . can not be greater than k. This means that no exponent i n 1 v a term 8, ... 6, a, ... a can be greater than k. On the other hand i , i 1 v 1 v i , , i must sum to n. Thus i f k divides n, then the minimum number 1 v of the exponents which must be p o s i t i v e i s jj^ j , and these exponents w i l l each be k. If k does not d i v i d e n then the minimum number of the exponents which must be p o s i t i v e i s + 1, and of these j^j w i l l be k and one w i l l be between 0 and k. Thus i f k i s a p o s i t i v e integer,then f ( a ) = 0 i f a has fewer than m p o s i t i v e coordinates and f(a) > 0 i f a has at l e a s t m p o s i t i v e coordinates. Therefore i f k i s a p o s i t i v e integer then G f i s the set of non-negative vectors with at l e a s t m p o s i t i v e coordinates. Suppose now that k i s p o s i t i v e but not an integer. R e c a l l that i n t h i s case we - 16 -r e s t r i c t n to being l e s s than k + 1. Thus i f a has at l e a s t one p o s i t i v e coordinate, say a,, then T (a) w i l l be p o s i t i v e since the choice t n ( i , i , i ) = (0, 0, n, 0, 0) assures us that there i s at l e a s t one p o s i t i v e term i n the summation. So i n the case k p o s i t i v e and k not an integer,G^.is the set of non-negative vectors with at l e a s t one p o s i t i v e coordinate. Suppose now that k i s negative. k t k Then < ) i s defined f o r a l l non-negative integers t. C l e a r l y (-1) ( ) i s p o s i t i v e f o r a l l non-negative t . Thus i f a has at l e a s t one p o s i t i v e coordinate, say a^, then T n ( a ) i s p o s i t i v e since, as before, the choice ( i , i ^ , i y ) = (0, 0, n, 0, 0) assures us that at l e a s t one of the terms i n T (a) i s p o s i t i v e . Thus i n the case that k i s negative> n G f i s the set of vectors with at l e a s t one p o s i t i v e coordinate. I t has been shown [6] that T ^ n i s convex f o r k < 0 and concave f o r k > 0. 1 J n C l e a r l y T ^ n i s symmetric. I t can be shown [7] that T 1^ 1 1 i s s t r i c t l y convex • n n f o r k < 0 and s t r i c t l y concave f o r k > 0. I t i s i n t e r e s t i n g to note that f o r k = 1 T (a) = E (a), and for k = -1 T (a) = h (a). n n n n Ryser applies theorem 2 to the problem of determining whether or not a f i n i t e oriented graph i s complete. A graph consists of a non-null set V of objects c a l l e d points and a set W of objects c a l l e d l i n e s , the two sets having no elements i n common. With each l i n e there are associated j u s t two d i s t i n c t points, c a l l e d i t s endpoints. The l i n e i s s a i d to j o i n i t s endpoints. Isolated points, i . e . points having no l i n e s associated with them, are permitted and two or more l i n e s may j o i n the same endpoints. If the number of l i n e s j o i n i n g d i s t i n c t point p a i r s i s the same f o r each such p a i r , then G i s complete. G i s f i n i t e i f both V and W are f i n i t e . - 17 -G i s oriented i f each l i n e i s assigned a d i r e c t i o n i n one of the two possible ways. Let G be a f i n i t e oriented graph. Let P , .. ., P be the points and.let L,, .... L be the l i n e s of G. Let p.. = 1 i f P, i s 1 w i j i the i n i t i a l point of the d i r e c t e d l i n e L.; l e t p J . = -1 i f P. i s the terminal J i j i point of the d i r e c t e d l i n e L,; and l e t p. , = 0 i f P, i s not an end point of j i j i L.. Then P = ( p , J defines a matrix of s i z e v by w. This matrix i s c a l l e d J i j T the incidence matrix of G. The matrix PP=His non-negative symmetric. As before l e t Then trace (H) .=, k*v JHJ = JJ. J >i a (k* + <v-l)A*)v k* = 2w/v A* = -2w/v(v-l). If B = (k* - A*)I + A*J i s of order v,then trace (C r(B)) = C ) (r^) (^fj) T (r = 1, v ) . Note that G i s complete i f and only i f PP = B. Ryser applies theorem 2 to obtain THEOREM: The incidence matrix P of an oriented graph G of v points and w l i n e s s a t i s f i e s trace (C r<PP T)) £ (*) ( ^ ) ( ^ - ) r (r = 1, .... v ) . Equality holds f o r r = 1 and r = v. Equality holds f o r an r, 1 < r < v, i f and only i f G i s complete. Let f be a non-negative symmetric concave function. Let f(A) denote f(A^, • • •» A^) > where ^ , ..., A Y a*"e the eigenvalues of the matrix A. Then the preceeding theorem may be generalised as follows. - 18 -THEOREM: The incidence matrix P of an oriented graph G of v points and w l i n e s s a t i s f i e s f ( P P T ) ^ f(B) If f i s s t r i c t l y concave and i f (A.^ Ay), the vector of eigenvalues T of PP , belongs to G f then equality holds i f and only i f G i s complete. This r e s u l t follows as a consequence of theorem 6. Let v elements x,, .... x be arranged i n t o v sets s,, .... s 1 v 1 v such that every set contains exactly k d i s t i n c t elements and such that •every p a i r of sets has exactly A elements i n common, 0 < A < k < v. Such an arrangement i s c a l l e d a v, k, A configuration. I t turns out k ( k _ l ) that every v, k, A configuration s a t i s f i e s A = ^ — . For such a configuration, l e t a. . = 1 i f x J i s an element of S, , and l e t a. . = 0 i j j i ' i j i f x. i s not an element of S . The v by v matrix A = (a ) of O's and l ' s i s the incidence matrix of the v, k, A configuration. Define the matrix B of order v by B = (k -A)I £ AJ. I t i s c l e a r that i f 0 < A < k < v, then a v, k, A configuration e x i s t s i f and T " • • • only i f there e x i s t s a 0, 1 matrix A of order v such that AA = B. Thus Ryser i s able to state THEOREM: Let Q be a 0, 1 matrix of order v, containing exactly kv l ' s . Let A = k ( k - l ) / ( v - l ) and B = (k -A)I + AJ, where, 0 < A < k < v. Then trace (C (QQ T)) g trace (C (B)) (r = 1, v ) . r r Equa l i t y holds f o r r = 1. Equality holds f o r an r > 1 i f and only i f Q i s the incidence matrix of a v, k, A configuration. - 19 -Let f be a non-negative symmetric concave function and l e t f(A) denote f ( A 1 > •••> Ay) where Aj , . . . , Ay a r e the eigenvalues of A. Then we may generalise Ryser's r e s u l t s . THEOREM: Let Q be a 0, 1 matrix of order v, containing exactly kv l ' s . Let A = k ( k - l ) / ( v - l ) and B = (k -A)I .+ AJ, where 0 < A < k < v. Then f(QQ T) £ f ( B ) . If f i s s t r i c t l y concave and i f (A^, •••, Ay)> the vector of eigenvalues T of QQ , belongs to then equality holds i f and only i f Q i s the incidence matrix of a v, k, A configuration. - 20 -BIBLIOGRAPHY H. J . Ryser, Compound and Induced Matrices i n Combinatorial A n a l y s i s , Proceedings of Symposia i n Applied Mathematics, X (1960, 149. L. Dulmage and I. Halperin, On a theorem of Frobenius-Konig and J. von Neuman's game of hide and seek, Trans. Roy. Soc. Canada Sect. I l l , v o l . 49, 1955, pp 23-29. Marvin Marcus, Some Properties and A p p l i c a t i o n of Doubly Stochastic Matrices, American Mathematical Monthly, v o l . 67, 1960, pp 215-221. Peter Bullen and Marvin Marcus, Symmetric Means and Matrix I n e q u a l i t i e s , Proc. American Math. S o c , v o l . 12, 1961, pp 285-290. J . N.Whiteley, Some Inequalities Concerning Symmetric Forms, Mathe-matika, 5 (1958), 49-57. J. N. Whiteley, l o c . c i t . Marvin Marcus, private communication.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Some inequalities with combinatorial applications
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Some inequalities with combinatorial applications Gordon, William Robert 1961
pdf
Page Metadata
Item Metadata
Title | Some inequalities with combinatorial applications |
Creator |
Gordon, William Robert |
Publisher | University of British Columbia |
Date Issued | 1961 |
Description | Some inequalities of H. J. Ryser with combinatorial applications are generalized. Let f be a non-negative concave symmetric function on v-tuples of non-negative reals. If f has the property that when θa + (1- θ)b ∈ G[subscript f] = f[power -1] ({t:t > 0}), 0 < θ < 1, then f(θa + (1- θ)b) = θf(a) + (1-θ)f(b), then we say that f is strictly concave. (Similarly, if f is convex and has the property just mentioned, then we say that f is strictly convex). Let H be a non-negative hermitian matrix with eigenvalues λ₁, ..., λ[subscript v], where λ₁ ≧ ... ≧λ[subscript e] > λ[subscript e+1] = … = λ[subscript v] = 0. Let h be an integer, 1 < h, such that e ≦h ≦ v and define k and λ by k = trace (H)/h, λ[subscript h] ≦k + (h-1) λ ≦λ₁. Define the matrix B of order h by B = (k- λ)I + λJ, where I is the identity matrix all of whose entries are 1's. Let B₀ = B ∔ 0, where the matrix B₀ of order v is the direct sum of the matrix B of order h and the (v-h)-order zero matrix. Let f(H) denote f(λ₁, … , λ[subscript v]). Then we prove theorems of the following nature. THEOREM: The matrices H and B₀ satisfy f(H) ≦ f(B₀). If f is strictly concave and if (λ₁, ..., λ[subscript v]) ∈ G[subscript f] then equality holds if and only if H and B₀ have the same eigenvalues. If f is strictly concave and if for some integer z, G[subscript f] is the set of non-negative vectors with at least z positive coordinates and if k + (h-1) λ ≠ 0 and z ≦ h or k + (h-1)λ = 0 and z < h, then f(H) = f(B₀) if and only if H and B₀ have the same eigenvalues. If f is convex a similar theorem with the inequality reversed can be proved. We discuss various choices of the function f and indicate some applications of the results to some combinatorial problems. |
Subject |
Inequalities (Mathematics) Combinations |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-01-26 |
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.0080653 |
URI | http://hdl.handle.net/2429/40300 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1961_A8 G67 S6.pdf [ 1.66MB ]
- Metadata
- JSON: 831-1.0080653.json
- JSON-LD: 831-1.0080653-ld.json
- RDF/XML (Pretty): 831-1.0080653-rdf.xml
- RDF/JSON: 831-1.0080653-rdf.json
- Turtle: 831-1.0080653-turtle.txt
- N-Triples: 831-1.0080653-rdf-ntriples.txt
- Original Record: 831-1.0080653-source.json
- Full Text
- 831-1.0080653-fulltext.txt
- Citation
- 831-1.0080653.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-0080653/manifest