Back to search

University of British Columbia

Some combinatorial properties of matrices

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Arts - MA
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
1962

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wales, David Bertram

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/39205

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wales, David Bertram. Some combinatorial properties of matrices. master's thesis, University of British Columbia, 1962. http://hdl.handle.net/2429/39205