Citation
Henderson, John Robert (1971) Permutation decomposition of (0,1)matrices and decomposition transversals. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/J1Z1SK19. https://resolver.caltech.edu/CaltechTHESIS:04212010092257716
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 3dimensional (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" ntuple 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.)) 

Subject Keywords:  Mathematics 
Degree Grantor:  California Institute of Technology 
Division:  Physics, Mathematics and Astronomy 
Major Option:  Mathematics 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  24 August 1970 
Record Number:  CaltechTHESIS:04212010092257716 
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:04212010092257716 
DOI:  10.7907/J1Z1SK19 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  5726 
Collection:  CaltechTHESIS 
Deposited By:  Tony Diaz 
Deposited On:  21 Apr 2010 21:33 
Last Modified:  20 Dec 2019 19:32 
Thesis Files

PDF
 Final Version
See Usage Policy. 1MB 
Repository Staff Only: item control page