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. / Science, Faculty of / Mathematics, Department of / Graduate
| Identifer | oai:union.ndltd.org:UBC/oai:circle.library.ubc.ca:2429/40300 |
| Date | January 1961 |
| Creators | Gordon, William Robert |
| Publisher | University of British Columbia |
| Source Sets | University of British Columbia |
| Language | English |
| Detected Language | English |
| Type | Text, Thesis/Dissertation |
| 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. |
Page generated in 0.0024 seconds