 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Some inequalities with combinatorial applications
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Some inequalities with combinatorial applications Gordon, William Robert
Abstract
Some inequalities of H. J. Ryser with combinatorial applications are generalized. Let f be a nonnegative concave symmetric function on vtuples of nonnegative 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 nonnegative 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 + (h1) λ ≦λ₁. 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 (vh)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 nonnegative vectors with at least z positive coordinates and if k + (h1) λ ≠ 0 and z ≦ h or k + (h1)λ = 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.
Item Metadata
Title 
Some inequalities with combinatorial applications

Creator  
Publisher 
University of British Columbia

Date Issued 
1961

Description 
Some inequalities of H. J. Ryser with combinatorial applications are generalized.
Let f be a nonnegative concave symmetric function on vtuples of nonnegative 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 nonnegative 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 + (h1) λ ≦λ₁. 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 (vh)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 nonnegative vectors with at least z positive coordinates and if k + (h1) λ ≠ 0 and z ≦ h or k + (h1)λ = 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  
Genre  
Type  
Language 
eng

Date Available 
20120126

Provider 
Vancouver : University of British Columbia Library

Rights 
For noncommercial 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  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Campus  
Scholarly Level 
Graduate

Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.