UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Some inequalities with combinatorial applications Gordon, William Robert


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.

Item Media

Item Citations and Data


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.

Usage Statistics