Open Collections

Some combinatorial properties of the diagonal sums of doubly stochastic matrices

University of British Columbia

Let Ωn denote the convex polyhedron of all nxn d.s. (doubly stochastic) matrices. The main purpose of this thesis is to study some combinatorial properties of the diagonal sums of matrices in Ωn. In Chapter I, we determine, for all d.s. matrices unequal to Jn ; the maximum number of diagonals that can have a common diagonal sum. The key will be a Decomposition Theorem that enables us to characterize completely the structure of a d.s. matrix when this maximum number is attained, provided that the common sum is not one. When the common sum is one, the question is more difficult and remains open. Several applications of the Decomposition Theorem are also given. In Chapter II, we concentrate on the diagonals with maximum diagonal sum h and the diagonals with minimum diagonal sum k. We obtain the best possible bounds for entries on these diagonals and for various kinds of functions of h and k. The key will be a Covering Theorem that enables us to analyze the cases when those bounds are attained. A conjecture is given. In Chapter III, we study the properties of the h-function and the k-function, the functions that associate with each d.s. matrix its maximum and minimum diagonal sums respectively. In particular, we investigate the behavior of these functions on the Kronecker product of d.s. matrices. Furthermore, we show that the h-function is very similar to the rank function ƿ in many respects. We also prove that for A ε Ωn, h(A) ≤ ƿ(A) and per (A) ≤ [formula omitted] which improves a result by M. Marcus and H. Mine. A conjecture is given.

Text

2011-04-27

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/34043

Mathematics

University of British Columbia

Graduate