Posets of finite functions (Q907250)

Summary: The symmetric group \(S(n)\) is partially ordered by Bruhat order. This order is extended by \textit{L. E. Renner} [Linear algebraic monoids. Berlin: Springer (2005; Zbl 1085.20041)] to the set of partial injective functions of \( \{ 1, 2, \ldots, n \} \). This poset is investigated by \textit{M. Fortin} in [Electron. J. Comb. 15, No. 1, Research Paper R62, 30 p. (2008; Zbl 1192.06004)]. In this paper we show that Renner order can be also defined for sets of all functions, partial functions, injective and partial injective functions from \( \{ 1, 2, \ldots, n \} \) to \( \{ 1, 2, \ldots, m \} \). Next, we generalize Fortin's results on these posets, and also, using simple facts and methods of linear algebra, we give simpler and shorter proofs of some fundamental Fortin's results. We first show that these four posets can be order embedded in the set of \( n \times m \)-matrices with non-negative integer entries and with the natural componentwise order. Second, matrix representations of the Dedekind-MacNeille completions of our posets are given. Third, we find join- and meet-irreducible elements for every finite sublattice of the lattice of all \( n \times m \)-matrices with integer entries. In particular, we obtain join- and meet-irreducible elements of these Dedekind-MacNeille completions. Hence and by general results concerning Dedekind-MacNeille completions, join- and meet-irreducible elements of our four posets of functions are also found. Moreover, subposets induced by these irreducible elements are precisely described.