Back to search

University of British Columbia

Some inequalities with combinatorial applications

Abstract

dc: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.

Degree

thesis:*
Name thesis:degree_name
Master of Arts - MA
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
1961

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gordon, William Robert

Rights

dc:rights
Statement dc: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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/40300

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Gordon, William Robert. Some inequalities with combinatorial applications. master's thesis, University of British Columbia, 1961. http://hdl.handle.net/2429/40300