A Caltech Library Service

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


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.


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.))
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):
  • Ryser, H. J.
Thesis Committee:
  • Unknown, Unknown
Defense Date:24 August 1970
Record Number:CaltechTHESIS:04212010-092257716
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5726
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.


Repository Staff Only: item control page