Bruhat-Chevalley order on the rook monoid

2008/03/04 by Mahir Bilen Can, Can, Mahir Bilen, Lex E. Renner +1
Computer Science · Mathematics · #20H20 #20M07 #Algebraic Geometry (math.AG) #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Mathematical Dynamics and Fractals #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0803.0491

openalex publication_date 2008/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The rook monoid R_n is the finite monoid whose elements are the 0-1 matrices with at most one nonzero entry in each row and column. The group of invertible elements of R_n is isomorphic to the symmetric group S_n. The natural extension to R_n of the Bruhat-Chevalley ordering on the symmetric group is defined in \citeRenner86. In this paper, we find an efficient, combinatorial description of the Bruhat-Chevalley ordering on R_n. We also give a useful, combinatorial formula for the length function on R_n.

Related

• A subsemigroup of the rook monoid
• Bruhat intervals as rooks on skew Ferrers boards
• Elementary methods for splitting representations of Rook monoids: a gentle introduction to groupoids
• Lexicographic shellability of sects
• R-polynomials of finite monoids of Lie type