123-avoiding doubly stochastic matrices

Richard A. Brualdi; Lei Cao

doi:10.1016/j.laa.2023.07.021

123-avoiding doubly stochastic matrices

Richard A. Brualdi
, Lei Cao

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We investigate the convex polytope Ω_n(123‾) of doubly stochastic matrices spanned by the n×n permutation matrices that avoid an increasing pattern of length 3, the 123‾-permutation matrices. We determine some of its facets and other faces, including faces of small dimension, and their connection to facets and faces of the polytope Ω_n of all n×n doubly stochastic matrices. The paper concludes with some relations concerning the frequencies of the positions of the 1's in n×n 123‾-permutation matrices, and the vertex-edge graph of Ω_n(123‾).

Original language	English
Pages (from-to)	49-81
Number of pages	33
Journal	Linear Algebra and its Applications
Volume	697
DOIs	https://doi.org/10.1016/j.laa.2023.07.021
State	Published - Sep 15 2024

Bibliographical note

Publisher Copyright:
© 2023 Elsevier Inc.

ASJC Scopus Subject Areas

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

123-avoiding
Doubly stochastic matrix
Facet
Permutation matrix
Polytope

Access to Document

10.1016/j.laa.2023.07.021

Cite this

@article{6a58d24ed5d643aea23d7b1602596161,

title = "123-avoiding doubly stochastic matrices",

abstract = "We investigate the convex polytope Ωn(123‾) of doubly stochastic matrices spanned by the n×n permutation matrices that avoid an increasing pattern of length 3, the 123‾-permutation matrices. We determine some of its facets and other faces, including faces of small dimension, and their connection to facets and faces of the polytope Ωn of all n×n doubly stochastic matrices. The paper concludes with some relations concerning the frequencies of the positions of the 1's in n×n 123‾-permutation matrices, and the vertex-edge graph of Ωn(123‾).",

keywords = "123-avoiding, Doubly stochastic matrix, Facet, Permutation matrix, Polytope",

author = "Brualdi, \{Richard A.\} and Lei Cao",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Inc.",

year = "2024",

month = sep,

day = "15",

doi = "10.1016/j.laa.2023.07.021",

language = "English",

volume = "697",

pages = "49--81",

journal = "Linear Algebra and its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - 123-avoiding doubly stochastic matrices

AU - Brualdi, Richard A.

AU - Cao, Lei

PY - 2024/9/15

Y1 - 2024/9/15

N2 - We investigate the convex polytope Ωn(123‾) of doubly stochastic matrices spanned by the n×n permutation matrices that avoid an increasing pattern of length 3, the 123‾-permutation matrices. We determine some of its facets and other faces, including faces of small dimension, and their connection to facets and faces of the polytope Ωn of all n×n doubly stochastic matrices. The paper concludes with some relations concerning the frequencies of the positions of the 1's in n×n 123‾-permutation matrices, and the vertex-edge graph of Ωn(123‾).

AB - We investigate the convex polytope Ωn(123‾) of doubly stochastic matrices spanned by the n×n permutation matrices that avoid an increasing pattern of length 3, the 123‾-permutation matrices. We determine some of its facets and other faces, including faces of small dimension, and their connection to facets and faces of the polytope Ωn of all n×n doubly stochastic matrices. The paper concludes with some relations concerning the frequencies of the positions of the 1's in n×n 123‾-permutation matrices, and the vertex-edge graph of Ωn(123‾).

KW - 123-avoiding

KW - Doubly stochastic matrix

KW - Facet

KW - Permutation matrix

KW - Polytope

UR - https://www.scopus.com/pages/publications/85166357626

UR - https://www.scopus.com/pages/publications/85166357626#tab=citedBy

U2 - 10.1016/j.laa.2023.07.021

DO - 10.1016/j.laa.2023.07.021

M3 - Article

AN - SCOPUS:85166357626

SN - 0024-3795

VL - 697

SP - 49

EP - 81

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

ER -

123-avoiding doubly stochastic matrices

Abstract

Bibliographical note

ASJC Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this