Permutation decomposition of (0,1)-matrices and decomposition transversals
Permutation decomposition of (0,1)-matrices and decomposition transversals
复制标题
(0,1)-矩阵的排列分解和分解横截面
DOI：
10.7907/j1z1-sk19
复制
发表时间：
1971
期刊：
影响因子：
--
通讯作者：
J. R. Henderson
中科院分区：
文献类型：
--
作者：
J. R. Henderson
本文的中心问题是研究不交部分置换矩阵的和（置换分解）。这个问题的根源是G. Birkoff指出，在每行和每列中具有k个l的阶n（0，1）-矩阵可以被写为k个置换矩阵（“大小”和阶n的部分置换矩阵）的和。
论文分为两大部分。在第一部分（第二章，第三章），我们首先处理的存在性置换分解的一个给定的（0，1）-矩阵，其中每个被加数有一个指定的大小，其次，与一些应用组成的重新制定某些识别问题的组合数学置换分解。普遍存在的问题仍然没有解决。对于（0，1）-矩阵A的置换分解中的两个以上不同的尺寸，需要比A的子矩阵中的l的数目更微妙的不变量。
本文的第二部分是关于置换分解的“断面”。具体目标是为解决H. J. Ryser证明了每一个奇数阶拉丁方都有一个“横截”。第四章是初步的，并处理的“广义迹”的三维（0，1）-矩阵。一个更富有成效的方法被认为是在第五章中的猜想Ryser是广义的，显然是中央的概念，一个“平方”n元组的正整数。这样的正方形“列表”的特征在于比赛得分向量。一个较弱的结构比拉丁方，一个“对配置”，也介绍了这样的结构，一个正方形列表的概念是更密切地与“横截”的存在。广义猜想仅在特殊情况下得到证明。
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.