 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Some combinatorial properties of matrices
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Some combinatorial properties of matrices Wales, David Bertram
Abstract
Three combinatorial problems in matrix theory are considered in this thesis. In the first problem the structure of 01 matrices with permanent 1, 2, or 3, is analysed. It is shown that a 01 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 01 matrix with permanent p. The structure of fully indecomposable 01 matrices with permanent 1, 2, or 3, is then determined. It is found that the only fully indecomposable 01 matrix with permanent 1 is the 1square matrix (1); and fully indecomposable 01 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 01 matrices with permanent 3 is also described. In the second problem relationships are considered between two 01 matrices given certain connections between their corresponding principal submatrices. The matrices considered are 01 nsquare 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 nsquare matrices A such that for any nsquare permutation matrix P there exists a doubly stochastic matrix B such that PA = AB. It is shown that for nonsingular matrices in G, the doubly stochastic matrix B must be a permutation matrix. The set of nonsingular 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 nsquare matrix with all entries 1, and α, β are scalars.
Item Metadata
Title 
Some combinatorial properties of matrices

Creator  
Publisher 
University of British Columbia

Date Issued 
1962

Description 
Three combinatorial problems in matrix theory are considered in this thesis.
In the first problem the structure of 01 matrices with permanent 1, 2, or 3, is analysed. It is shown that a 01 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 01 matrix with permanent p. The structure of fully indecomposable 01 matrices with permanent 1, 2, or 3, is then determined. It is found that the only fully indecomposable 01 matrix with permanent 1 is the 1square matrix (1); and fully indecomposable 01 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 01 matrices with permanent 3 is also described.
In the second problem relationships are considered between two 01 matrices given certain connections between their corresponding principal submatrices. The matrices considered are 01 nsquare 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 nsquare matrices A such that for any nsquare permutation matrix P there exists a doubly stochastic matrix B such that PA = AB. It is shown that for nonsingular matrices in G, the doubly stochastic matrix B must be a permutation matrix. The set of nonsingular 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 nsquare matrix with all entries 1, and α, β are scalars.

Genre  
Type  
Language 
eng

Date Available 
20111121

Provider 
Vancouver : University of British Columbia Library

Rights 
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

DOI 
10.14288/1.0302298

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Campus  
Scholarly Level 
Graduate

Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.