Mathematics Faculty Articles
Pattern-avoiding (0,1)-matrices and bases of permutation matrices
Document Type
Article
Publication Date
8-4-2021
Publication Title
Discrete Applied Mathematics
Keywords
Permutation, Pattern-avoiding, pqr-avoiding, (0, 1)-matrices, Permutation bases
ISSN
0166-218X
Volume
304
First Page
196
Last Page
211
Abstract
We investigate pattern-avoiding n × n (0, 1)-matrices with emphasis on patterns of length 3: pqr-avoiding where {p, q, r} ⊆ {1, 2, . . . , n}. We show that all such maximal (0, 1)-matrices contain the same number of 1’s, and their structure is determined. We then show that the set of pqr-avoiding n × n permutation matrices span the linear space of dimension (n − 1)2 + 1 generated by the n × n permutation matrices and determine a corresponding basis for each p, q, r.
NSUWorks Citation
Brualdi, Richard A. and Cao, Lei, "Pattern-avoiding (0,1)-matrices and bases of permutation matrices" (2021). Mathematics Faculty Articles. 342.
https://nsuworks.nova.edu/math_facarticles/342
ORCID ID
0000-0001-7613-7191
ResearcherID
G-7341-2019
DOI
10.1016/j.dam.2021.07.039
