Open Collections

Some inequalities with combinatorial applications

University of British Columbia

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.

Text

2012-01-26

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.

http://hdl.handle.net/2429/40300

Mathematics

University of British Columbia

Graduate