CaltechTHESIS
A Caltech Library Service

# Permutation decomposition of (0,1)-matrices and decomposition transversals

## Citation

Henderson, John Robert (1971) Permutation decomposition of (0,1)-matrices and decomposition transversals. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/J1Z1-SK19. https://resolver.caltech.edu/CaltechTHESIS:04212010-092257716

## Abstract

The central problem of this thesis is the study of sums of disjoint partial permutation matrices ("permutation decompositions"). This problem has as its origin the result of G. Birkoff that an ordern (0,1)-matrix having k l's in every row and column can be written as a sum of k permutation matrices (partial permutation matrices of "size" and order n). The thesis divides into two main parts. In the first part (Chapters II, III) we first deal with the existence of permutation decompositions of a given (0, 1)-matrix where each of the summands has a specified size and secondly, with some applications consisting of reformulating certain identification problems of Combinatorics in terms of permutation decompositions. The general existence problem remains unsolved. For more than two distinct sizes in the proposed permutation decomposition of a (0, 1)-matrix A, a more subtle invarient than numbers of l's in submatrices of A is required. The second part of this thesis is concerned with "transversals" of permutation decompositions. The specific goal is to make some contribution toward resolving the conjecture of H. J. Ryser that every odd order latin square has a "transversal". Chapter IV is preliminary, and deals with "generalized traces" of 3-dimensional (0, 1)-matrices. A more fruitful approach is considered in Chapter V. There the conjecture of Ryser is generalized and the apparently central concept of a "square" n-tuple of positive integers is introduced. Such square "lists" are characterized in terms of tournament score vectors. A weaker structure than a latin square, that of a "pair configuration", is also introduced and for such structures the concept of a square list is more intimately connected with the existence of a "transversal". The generalized conjecture is proven only in special cases.

Item Type: Thesis (Dissertation (Ph.D.)) Mathematics California Institute of Technology Physics, Mathematics and Astronomy Mathematics Public (worldwide access) Ryser, H. J. Unknown, Unknown 24 August 1970 CaltechTHESIS:04212010-092257716 https://resolver.caltech.edu/CaltechTHESIS:04212010-092257716 10.7907/J1Z1-SK19 No commercial reproduction, distribution, display or performance rights in this work are provided. 5726 CaltechTHESIS Tony Diaz 21 Apr 2010 21:33 20 Dec 2019 19:32

## Thesis Files  Preview
PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page