Pattern-avoiding (0,1)-matrices and bases of permutation matrices

Authors

Richard A. Brualdi, University of Wisconsin-Madison
Lei Cao, Nova Southeastern UniversityFollow

Document Type

Article

Publication Date

12-15-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)²+1 generated by the n×n permutation matrices and determine a corresponding basis for each p, q, r.

Comments

© 2021 Elsevier B.V. All rights reserved.

NSUWorks Citation

Brualdi, Richard A. and Cao, Lei, "Pattern-avoiding (0,1)-matrices and bases of permutation matrices" (2021). Mathematics Faculty Articles. 314.
https://nsuworks.nova.edu/math_facarticles/314

ORCID ID

0000-0001-7613-7191

ResearcherID

G-7341-2019

DOI

10.1016/j.dam.2021.07.039