TY - JOUR
T1 - Pattern-avoiding (0,1)-matrices and bases of permutation matrices
AU - Brualdi, Richard A.
AU - Cao, Lei
PY - 2021/8/4
Y1 - 2021/8/4
N2 - 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.
AB - 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.
U2 - 10.1016/j.dam.2021.07.039
DO - 10.1016/j.dam.2021.07.039
M3 - Article
SN - 0166-218X
VL - 304
SP - 196
EP - 211
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -