Open Collections

Some combinatorial properties of matrices

University of British Columbia

Three combinatorial problems in matrix theory are considered in this thesis. In the first problem the structure of 0-1 matrices with permanent 1, 2, or 3, is analysed. It is shown that a 0-1 matrix whose permanent is a prime number p can be brought by permutations of rows and columns into a subdirect sum of 1 -square matrices (1) and a fully indecomposable 0-1 matrix with permanent p. The structure of fully indecomposable 0-1 matrices with permanent 1, 2, or 3, is then determined. It is found that the only fully indecomposable 0-1 matrix with permanent 1 is the 1-square matrix (1); and fully indecomposable 0-1 matrices with permanent 2 are I + K to within permutations of the rows and columns, where I is the identity matrix and K is the full cycle permutation matrix. The structure of fully indecomposable 0-1 matrices with permanent 3 is also described. In the second problem relationships are considered between two 0-1 matrices given certain connections between their corresponding principal submatrices. The matrices considered are 0-1 n-square symmetric matrices with zeros on the main diagonal. One of the theorems proved states that if two of these matrices have the same number of ones in corresponding (n - 2)-square principal submatrices, then the two matrices are identical. In the third problem the set of matrices G is determined. By definition G is the set of all n-square matrices A such that for any n-square permutation matrix P there exists a doubly stochastic matrix B such that PA = AB. It is shown that for non-singular matrices in G, the doubly stochastic matrix B must be a permutation matrix. The set of non-singular matrices in G is then determined by considering left multiplication of A by permutation matrices Pij. It is proved that G consists of the set of matrices with identical rows together with the set of matrices of the form αP + βJ where J is the n-square matrix with all entries 1, and α, β are scalars.

Text

2011-11-21

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

Mathematics

University of British Columbia

Graduate