2021

[1]George Fikioris

[1]School of Electrical and Computer Engineering, National Technical
University of Athens, Zografou, Athens, GR 15773, Attica, Greece

2]Department of Computer Science, Cornell University, Hoy Rd, Ithaca, NY
14853, New York, USA

# A subsemigroup of the rook monoid

<EMAIL_ADDRESS>Giannis Fikioris<EMAIL_ADDRESS>*  [

###### Abstract

We define a subsemigroup $S_{n}$ of the rook monoid $R_{n}$ and investigate
its properties. To do this, we represent the nonzero elements of $S_{n}$
(which are $n\times n$ matrices) via certain triplets of integers, and develop
a closed-form expression representing the product of two elements; these tools
facilitate straightforward deductions of a great number of properties. For
example, we show that $S_{n}$ consists solely of idempotents and nilpotents,
find the numbers of idempotents and nilpotents, and compute nilpotency
indexes. Furthermore, we give a necessary and sufficient condition for the
$j$th root of a nonzero element to exist in $S_{n}$, show that existence
implies uniqueness, and compute the said root explicitly. We also point to
several combinatorial aspects; describe a number of subsemigroups of $S_{n}$;
and, using rook $n$-diagrams, graphically interpret many of our results.

###### keywords:

rook monoid, symmetric inverse semigroup, rook $n$-diagrams, inverse
semigroups, orthodox semigroups

##  1 Introduction

For $n=2,3,4,\ldots$, the rook monoid $R_{n}$, also known as the symmetric
inverse semigroup $\mathcal{IS}_{n}$, consists of all partial injective
transformations of $\\{1,2,\ldots,n\\}$. Any such transformation can be
represented as an $n\times n$ matrix whose entries are $0$ or $1$, and with at
most one $1$ in every row and every column. If we think of the matrix as an
$n\times n$ chessboard with rooks placed at the the nonzero matrix entries,
then no rook attacks any other rook; hence the name rook monoid, coined in
2002 by Solomon Solomon (2002); Li et al (2008).

This paper introduces a subsemigroup $S_{n}$ of $R_{n}$ and studies its
properties (note that the symbol $S_{n}$ does not denote the permutation
group). Our $S_{n}$ is also a subsemigroup of $\mathcal{POI}_{n}$, i.e., the
set of all partial order-preserving injective transformations Fernandes
(2001); East (2006, 2010), which is itself a subsemigroup of $R_{n}$. Besides
$S_{n}$, we discuss two closely related semigroups, namely the monoid
$M_{n}=S_{n}\cup\\{\mathbf{1}\\}$ (where $\mathbf{1}$ is the monoid identity,
represented by the $n\times n$ identity matrix), as well as a semigroup of
countably infinite order to be denoted by $S_{\infty}$.

We refer to a number of well-known properties of $R_{n}$. They are summarized
in the lemma that follows.

######  Lemma 1.

Ganyushkin and Mazorchuk (2008)

  * •

The order of $R_{n}$ is given by $\lvert
R_{n}\rvert=\sum_{k=0}^{n}k!\binom{n}{k}^{2}$.

  * •

$R_{n}$ contains $2^{n}$ idempotents, namely the diagonal matrices belonging
to $R_{n}$.

  * •

$R_{n}$ contains $\sum_{k=1}^{n}\frac{n!}{k!}\binom{n-1}{k-1}$ nilpotents.

  * •

$R_{n}$ is an inverse semigroup, i.e., any $x\in R_{n}$ has a unique inverse
$y\in R_{n}$. The matrices representing $x$ and $y$ are transposes of one
another.

  * •

The element $x\in R_{n}$ has an inverse in the sense of groups (i.e., there
exists a $y\in R_{n}$ such that $xy=yx=\mathbf{1}$) iff $x$ is a bijection, so
that it is represented by a permutation matrix.

######  Example 1.

For $n=2$, the elements of $R_{n}=R_{2}$ can be represented by the following
$7=\lvert R_{2}\rvert$ matrices,

$\displaystyle\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},$
$\displaystyle\begin{pmatrix}1&0\\\
0&1\end{pmatrix}=\mathbf{1},\begin{pmatrix}1&0\\\
0&0\end{pmatrix}=e,\begin{pmatrix}0&0\\\ 0&1\end{pmatrix}=f,$
$\displaystyle\begin{pmatrix}0&0\\\
0&0\end{pmatrix}=\mathbf{0},\begin{pmatrix}0&1\\\
0&0\end{pmatrix}=a,\begin{pmatrix}0&0\\\ 1&0\end{pmatrix}=b$

(see Proposition 8 for the meaning of the symbols $e$, $f$, $a$, and $b$). The
group of permutations of $\\{1,2\\}$ is represented by the first two matrices
in our list, which are permutation matrices and represent the only two
elements that have an inverse in the sense of groups. The first matrix in our
list—to which we assigned no symbol—is a square root of $\mathbf{1}$ ($j$th
roots in $R_{n}$ are discussed in Annin et al (2012); York (2017)). The next
$4=2^{2}$ matrices are idempotent, and the last three are nilpotent with
indexes 1, 2, and 2, respectively.

In Section 9, we use the usual maps—called rook $n$-diagrams Xiao (2016)—to
give graphical interpretations of some of the properties of $M_{n}$ and
$S_{n}$. The rook $n$-diagram of any element in the rook monoid $R_{n}$ is a
graph with two rows. Each row has $n$ vertices labeled $1$, $2$, …, $n$. The
graph’s edges start from the top row and end in the bottom one; an edge from
$i$ to $j$ means that the element maps $i$ to $j$, so that the matrix entry
$x_{ij}$ equals $1$. Each vertex—whether in the top or bottom row—must belong
to at most one edge, with the zero matrix having no edges. See the example in
Figure 1.

Figure 1: Rook $n$-diagram of an element of $R_{n}$. We specifically depict
the rook $6$-diagram of the matrix of $R_{6}$ whose nonzero entries are
$x_{12}=x_{31}=x_{44}=x_{63}=1.$

In particular, a rook $n$-diagram corresponds to an element of the submonoid
$\mathcal{POI}_{n}$ iff its edges do not intersect, such as the example in
Figure 2.

Figure 2: When no edges intersect, a rook $n$-diagram corresponds to an
element of $\mathcal{POI}_{n}$. Here we specifically depict the matrix of
$\mathcal{POI}_{6}$ whose nonzero entries are $x_{12}=x_{33}=x_{54}=x_{66}=1$.

Concatenation of rook $n$-diagrams corresponds to multiplication, as we will
further discuss (for the case of $M_{n}$) in Section 9.

##  2 Notation and conventions

Throughout, $\mathbf{0}$ denotes semigroup zeros and $\mathbf{1}$ denotes
monoid identities, as in Example 1. The symbol $\lvert S\rvert$ denotes the
order of the semigroup $S$, i.e., the cardinal number of its set of elements.
All our semigroups have at least two elements, so that
$\mathbf{0}\neq\mathbf{1}$. A $j$th root of $x\in S$ is a $y\in S$ such that
$x^{j}=y$ ($j\in\mathbb{N}$). We use $\sqsubseteq$ in place of “is a
subsemigroup of.” If $\mathbf{1}$ is the identity of $M_{b}$ and
$\mathbf{1}\in M_{a}\sqsubseteq M_{b}$, we say that $M_{a}$ is a submonoid of
$M_{b}$ (in Section 8, we encounter monoid subsemigroups that are not
submonoids because the identities differ). The term inverse element has its
familiar meaning within the context of semigroups; we also use the term
inverse in the sense of groups, which we defined in Lemma 1.

The elements of our semigroups are matrices whose entries are $0$ and $1$,
called zero and one, respectively. $\mathbb{Z}$ is the set of integers,
$\mathbb{N}$ is the set of positive integers, and $\mathbb{N}_{0}$ is the set
of nonnegative integers. An infinite matrix is one whose entries are $x_{i,j}$
with $i,j\in\mathbb{N}$. We use $\delta_{ij}$ ($i,j\in\mathbb{N}_{0}$) to
denote the Kronecker delta. $\lceil x\rceil$ stands for the ceiling of
$x\in\mathbb{R}$.

We often assume that elements of isomorphic semigroups coincide. For example,
our $M_{n}$ is a monoid of $n\times n$ matrices. After establishing a
multiplication-preserving, one-to-one correspondence between the nonzero
matrices of $M_{n}$ and certain triplets of integers, we make no distinction
between a matrix and its representing triplet. As another example, any
multiplicative semigroup consisting of $n\times n$ matrices is isomorphic to a
semigroup consisting of square matrices whose dimension is larger than $n$,
including infinite matrices: We can regard each $n\times n$ matrix as being a
submatrix of the larger one, with the remaining entries of the larger matrix
all equal to zero. It is in this sense that—in Section 4—we define $M_{n}$ as
a subsemigroup of a certain semigroup $S_{\infty}$, whose elements are
infinite matrices.

While we discuss $M_{n}$ and $S_{n}$ primarily via the aforementioned triplets
(not the corresponding matrices), our proof of Theorem 1 makes use of
infinite-length row and column vectors whose entries are all $0$ except for at
most one entry, which equals $1$. In the said proof, the relevant notation is
as follows. $V_{q}$ ($q\in\mathbb{N}_{0}$) is the infinite column vector whose
entries $V_{qj}$ are

$V_{qj}=\delta_{qj},\quad q\in\mathbb{N}_{0},\quad j\in\mathbb{N}$ (1)

and $V^{T}_{q}$ is the transpose of $V_{q}$. Therefore, $V^{T}_{q}$ is an
infinite row vector and $V_{0}$ and $V_{0}^{T}$ are the infinite zero vectors.
Furthermore, the inner product $V^{T}_{q}V_{p}$ is well defined (there is a
finite number of nonzero terms, so there are no convergence issues associated
with the infinite summation) and is given by

$V^{T}_{q}V_{p}=\begin{cases}0,\quad p=q=0\quad\mathrm{or}\quad p\neq q,\\\
1,\quad p=q\in\mathbb{N}.\end{cases}$ (2)

##  3 Semigroup $S_{\infty}$ of countably infinite order

The elements $x$ of $S_{\infty}$ are infinite matrices, see the example in
Fig. 3. Element $\mathbf{0}\in S_{\infty}$ is the zero matrix. The nonzero
matrices of $S_{\infty}$ are those for which

  * (i)

Each matrix entry is zero ($0$) or one ($1$).

  * (ii)

There is a finite and nonzero number of ones, with all ones lying on a single
diagonal.

  * (iii)

Within this diagonal, the ones form an uninterrupted block, i.e., there is no
zero between any two ones.

Figure 3: The infinite matrix corresponding to $\langle d,k,m\rangle$.

For any $x\in S_{\infty}\setminus\\{\mathbf{0}\\}$, let $k\in\mathbb{N}$ be
the row of the northwestern one; let $m\in\mathbb{N}$ be the row of the
southeastern one; and let $d\in\mathbb{Z}$ be the diagonal on which the ones
lie, with $d=0$ corresponding to the main diagonal, and $d>0$ ($d<0$) to
diagonals above (below) the main one. Then the matrix entries $x_{ij}$ of $x$
are given by

$x_{ij}=\begin{rcases}\begin{dcases}1,\quad k\leq i\leq
m\quad\mathrm{and}\quad j-i=d,\\\
0,\quad\mathrm{otherwise,}\end{dcases}\end{rcases},\quad i,j\in\mathbb{N}.$
(3)

Conversely, as long as

$1-\min(0,d)\leq k\leq m,$

we can use a triplet of integers $d,k,m$ to represent each $x\in
S_{\infty}\setminus\\{\mathbf{0}\\}$. We do this by letting $\langle
d,k,m\rangle$ stand for the matrix $x\in S_{\infty}\setminus\\{\mathbf{0}\\}$
whose entries $x_{ij}$ are given by (3). We can thus consider the set of
elements of $S_{\infty}$ to be

$S_{\infty}=\\{\mathbf{0}\\}\cup\\{\langle d,k,m\rangle:\
d\in\mathbb{Z}\mathchar 24635\relax\;\ k,m\in\mathbb{N}\mathchar
24635\relax\;\ 1-\min(0,d)\leq k\leq m\\}.$ (4)

Note that the number of ones in the nonzero matrix $\langle d,k,m\rangle$ is
$m-k+1>0$.

The operation in $S_{\infty}$ is matrix multiplication, which is well-defined
(in the sense that there are no convergence issues) and associative. The
theorem that follows shows that this operation is also closed in $S_{\infty}$
and, whenever the result is nonzero, gives the triplet representing the
product.

######  Theorem 1.

$S_{\infty}$ is a noncommutative semigroup of countably infinite order with
$x\mathbf{0}=\mathbf{0}x=\mathbf{0}$ for every $x\in S_{\infty}$. The product
of any two nonzero elements $\langle d,k,m\rangle$ and $\langle
d^{\prime},k^{\prime},m^{\prime}\rangle$ is given by

$\langle d,k,m\rangle\langle
d^{\prime},k^{\prime},m^{\prime}\rangle=\begin{cases}\langle
d^{\prime\prime},k^{\prime\prime},m^{\prime\prime}\rangle,\quad
k^{\prime\prime}\leq m^{\prime\prime},\\\ \ \mathbf{0},\quad
k^{\prime\prime}>m^{\prime\prime},\end{cases}$ (5)

in which the parameters $d^{\prime\prime}$, $k^{\prime\prime}$, and
$m^{\prime\prime}$ are

$d^{\prime\prime}=d+d^{\prime},$ (6) $k^{\prime\prime}=\max(k,k^{\prime}-d),$
(7) $m^{\prime\prime}=\min(m,m^{\prime}-d).$ (8)

Irrespective of whether $k^{\prime\prime}\leq m^{\prime\prime}$ or not, the
parameters $d^{\prime\prime}$ and $k^{\prime\prime}$ satisfy

$1-\min(0,d^{\prime\prime})\leq k^{\prime\prime}.$ (9)

Proof: The equality $x\mathbf{0}=\mathbf{0}x=\mathbf{0}$ is obvious. As
$\langle d,k,m\rangle$ and $\langle d^{\prime},k^{\prime},m^{\prime}\rangle$
both belong to $S_{\infty}\setminus\\{\mathbf{0}\\}$, (4) gives

$1-\min(0,d)\leq k\quad\mathrm{and}\quad 1-\min(0,d^{\prime})\leq k^{\prime},$

from which it is easy to show (e.g. by distinguishing cases depending on the
signs of $d$, $d^{\prime}$, and $d^{\prime\prime}$) that the
$d^{\prime\prime}$ and $k^{\prime\prime}$ defined in (6) and (7) satisfy the
similar relation (9).

Each entry $x_{ij}$ of the matrix $x=\langle d,k,m\rangle\langle
d^{\prime},k^{\prime},m^{\prime}\rangle$ is given by the inner product

$x_{ij}=\langle d,k,m\rangle_{i*}\langle
d^{\prime},k^{\prime},m^{\prime}\rangle_{*j},\quad i,j\in\mathbb{N},$ (10)

where $\langle d,k,m\rangle_{i*}$ and $\langle d,k,m\rangle_{*j}$ denote the
$i$’th row and $j$’th column of $\langle d,k,m\rangle$, respectively (our
notation for rows and columns is reminiscent of the one in Meyer (2000)). In
terms of the vectors $V_{q}$ introduced in Section 2, it is apparent from (3)
that

$\langle d,k,m\rangle_{i*}=\begin{cases}V^{T}_{0},\quad i<k\mathrm{\ or\
}i>m,\\\ V^{T}_{i+d},\quad k\leq i\leq m,\end{cases}$ (11)

and

$\langle d^{\prime},k^{\prime},m^{\prime}\rangle_{*j}=\begin{cases}V_{0},\quad
j<k^{\prime}+d^{\prime}\mathrm{\ or\ }j>m^{\prime}+d^{\prime},\\\
V_{j-d^{\prime}},\quad k^{\prime}+d^{\prime}\leq j\leq
m^{\prime}+d^{\prime}.\end{cases}$ (12)

We can thus use (2) to find the inner product in (10). Specifically, (2) and
(10)–(12) tell us that $x_{ij}=1$ iff

$i+d=j-d^{\prime}\in\mathbb{N}\quad\mathrm{and}\quad k\leq i\leq
m\quad\mathrm{and}\quad k^{\prime}+d^{\prime}\leq j\leq
m^{\prime}+d^{\prime},$ (13)

while $x_{ij}=0$ in any other case. The set of conditions in (13) is
equivalent to

$k^{\prime\prime}\leq i\leq m^{\prime\prime}\quad\mathrm{and}\quad
j=i+d^{\prime\prime}\quad\mathrm{and}\quad i+d\in\mathbb{N},$ (14)

where $d^{\prime\prime}$, $k^{\prime\prime}$, and $m^{\prime\prime}$ are
defined in (6)–(8); further, it is easy to show that the condition
$i+d\in\mathbb{N}$ in (14) is superfluous. We have thus arrived at

$x_{ij}=\begin{cases}1,\quad k^{\prime\prime}\leq i\leq
m^{\prime\prime}\mathrm{\ and\ }j=i+d^{\prime\prime},\\\
0,\quad\mathrm{otherwise.}\end{cases}$ (15)

When $k^{\prime\prime}>m^{\prime\prime}$, (15) gives $x_{ij}=0$ for all
$i,j\in\mathbb{N}$, so that $x=\mathbf{0}$ and we have proved the bottom
equality in (5). On the other hand, when $k^{\prime\prime}\leq
m^{\prime\prime}$ we have $x\neq\mathbf{0}$; furthermore, comparison of (15)
and (9) to (3) and (4) gives the top equality, completing our proof of (5) and
of closure in $S_{\infty}$.

Let us now use Theorem 1 to verify that $S_{\infty}$ is not a monoid.

######  Proposition 2.

The semigroup $S_{\infty}$ has no $\mathbf{1}$.

Proof: Suppose that $\mathbf{1}=\langle d,k,m\rangle$. Then (6) and
$\mathbf{1}\langle d^{\prime},k^{\prime},m^{\prime}\rangle=\langle
d^{\prime},k^{\prime},m^{\prime}\rangle$ implies $d=0$, so that
$\mathbf{1}=\langle 0,k,m\rangle$. Thus, by Theorem 1,

$\mathbf{1}\langle 0,k,m+1\rangle=\langle 0,k,m\rangle\langle
0,k,m+1\rangle=\langle 0,k,m\rangle,$

but on the other hand,

$\mathbf{1}\langle 0,k,m+1\rangle=\langle 0,k,m+1\rangle,$

implying the contradiction $m+1=m$.

(It is tempting to say that $\mathbf{1}$ is the diagonal matrix with all
entries equal to $1$ but the said matrix does not belong to $S_{\infty}$ by
definition.)

Theorem 1 can yield further properties of $S_{\infty}$. Our main focus,
however, is a similar semigroup $M_{n}$ of finite order, which we now proceed
to deal with.

##  4 Monoid $M_{n}$ and semigroup $S_{n}$

Although it is possible to discuss $M_{n}$ directly, we avoid calculations by
introducing $M_{n}$ as a subsemigroup of $S_{\infty}$. Specifically, for any
fixed $n$ with $n=2,3,\ldots$ we define

$M_{n}=\\{\mathbf{0}\\}\cup\\{x\in S_{\infty}\setminus\\{\mathbf{0}\\}:m\leq
n-\max(0,d)\\}.$ (16)

Thus $M_{n}$ can be regarded as a semigroup of $n\times n$ matrices, in the
sense explained in Section 2; that is to say, any element of $M_{n}$ is an
$n\times n$ submatrix (on the top left) of the infinite matrix in Figure 3.

For any $x\in M_{n}\setminus\\{\mathbf{0}\\}$, properties (i)–(iii) of Section
3 continue to hold. Any nonzero $x\in M_{n}$ has matrix entries $x_{ij}$ that
are given by (3), but with $i,j\in\\{1,2,\ldots,n\\}$, and with the meaning of
the integers $d$, $k$, $m$ remaining the same. Clearly, $M_{n}$ is a
subsemigroup of the rook monoid $R_{n}$.

In terms of triplets, the set of elements of $M_{n}$ is

$\begin{split}M_{n}&=\\{\mathbf{0}\\}\\\ &\cup\\{\langle d,k,m\rangle:\
d\in\mathbb{Z}\mathchar 24635\relax\;\ k,m\in\mathbb{N}\mathchar
24635\relax\;\ 1-\min(0,d)\leq k\leq m\leq n-\max(0,d)\\}.\end{split}$ (17)

In addition to $k,m\in\\{1,2,\ldots,n\\}$, the restrictions written in (17)
imply

$-(n-1)\leq d\leq n-1,$ (18)

for any $\langle d,k,m\rangle\in M_{n}\setminus\\{\mathbf{0}\\}$; (18) is the
range of the diagonal $d$, as expected.

The multiplication formula (5) remains unaltered, but $M_{n}$ is associated
with an additional restriction on $d^{\prime\prime}$ and $m^{\prime\prime}$.
Furthermore—and even if the underlying semigroup $S_{\infty}$ is not a monoid
(Proposition 2)—we now have a $\mathbf{1}$ :

######  Theorem 3.

$M_{n}$ is a noncommutative monoid with $\mathbf{1}=\langle 0,1,n\rangle$. The
product of two nonzero monoid elements $\langle d,k,m\rangle$ and $\langle
d^{\prime},k^{\prime},m^{\prime}\rangle$—see (17)—is given by

$\langle d,k,m\rangle\langle
d^{\prime},k^{\prime},m^{\prime}\rangle=\begin{cases}\langle
d^{\prime\prime},k^{\prime\prime},m^{\prime\prime}\rangle,\quad
k^{\prime\prime}\leq m^{\prime\prime},\\\ \ \mathbf{0},\quad
k^{\prime\prime}>m^{\prime\prime},\end{cases}$ (19)

in which the parameters $d^{\prime\prime}$, $k^{\prime\prime}$, and
$m^{\prime\prime}$ are

$d^{\prime\prime}=d+d^{\prime},$ (20) $k^{\prime\prime}=\max(k,k^{\prime}-d),$
(21) $m^{\prime\prime}=\min(m,m^{\prime}-d).$ (22)

Irrespective of whether $k^{\prime\prime}\leq m^{\prime\prime}$ or not, we
have

$1-\min(0,d^{\prime\prime})\leq k^{\prime\prime}\quad\mathrm{and}\quad
m^{\prime\prime}\leq n-\max(0,d^{\prime\prime}).$ (23)

Proof: As $\langle d,k,m\rangle$ and $\langle
d^{\prime},k^{\prime},m^{\prime}\rangle$ belong to
$M_{n}\setminus\\{\mathbf{0}\\}$, (17) gives

$m\leq n-\max(0,d)\quad\mathrm{and}\quad m^{\prime}\leq n-\max(0,d^{\prime}),$

from which it is easy to show (e.g. by distinguishing cases depending on the
signs of $d$, $d^{\prime}$, and $d^{\prime\prime}$) that $d^{\prime\prime}$
and $m^{\prime\prime}$ satisfy the second inequality in (23). Since $M_{n}$ is
a subsemigroup of $S_{\infty}$, (19)–(22) follow immediately from Theorem 1,
as does the first inequality in (23). Since $\langle 0,1,n\rangle$ represents
the $n\times n$ identity matrix, the equality $\mathbf{1}=\langle
0,1,n\rangle$ is obvious. (Alternatively, we can use (19)–(22) and the
restrictions in (17) to show that $x\langle 0,1,n\rangle=\langle 0,1,n\rangle
x=x$ for every $x=\langle d,k,m\rangle\in M_{n}\setminus\\{\mathbf{0}\\}$.)

######  Remark 1.

Since the number of ones in the matrix $\langle
d^{\prime\prime},k^{\prime\prime},m^{\prime\prime}\rangle$ equals
$m^{\prime\prime}-k^{\prime\prime}+1$, the condition $k^{\prime\prime}\leq
m^{\prime\prime}$ in (19) assures that the number of ones (in any matrix which
corresponds to a nonzero product) is positive.

Reformulating the inequality $k^{\prime\prime}\leq m^{\prime\prime}$, we
obtain alternative conditions for a product to be zero/nonzero.

######  Corollary 1.

Let $x=\langle d,k,m\rangle\in M_{n}\setminus\\{\mathbf{0}\\}$ and $y=\langle
d^{\prime},k^{\prime},m^{\prime}\rangle\in M_{n}\setminus\\{\mathbf{0}\\}$,
and let $d^{\prime\prime}$, $k^{\prime\prime}$, and $m^{\prime\prime}$ be
given by (20)–(22). Then

$xy\neq\mathbf{0}\iff k^{\prime\prime}\leq m^{\prime\prime}\iff
k^{\prime}-m\leq d\leq m^{\prime}-k.$ (24)

Proof: By (21) and (22), the $k^{\prime\prime}\leq m^{\prime\prime}$ in (19)
is equivalent to the four inequalities

$k\leq m\quad\mathrm{and}\quad k\leq m^{\prime}-d\quad\mathrm{and}\quad
k^{\prime}-d\leq m\quad\mathrm{and}\quad k^{\prime}-d\leq m^{\prime}-d.$

The first and last of the four were known beforehand from (17). The second and
third give the last condition in (24).

A formula for powers, to be used many times in this paper, can be verified
using Theorem 3, Remark 1, and induction:

######  Corollary 2.

For $x=\langle d,k,m\rangle\in M_{n}\setminus\\{\mathbf{0}\\}$ and
$j\in\mathbb{N}$ we have

$x^{j}=\begin{cases}\left\langle
d^{(j)},k^{(j)},m^{(j)}\right\rangle,\quad\textrm{if}\quad k^{(j)}\leq
m^{(j)},\\\ \mathbf{0},\quad\textrm{if}\quad k^{(j)}>m^{(j)},\end{cases}$ (25)

where

$d^{(j)}=jd,\quad k^{(j)}=k-(j-1)\min(0,d),\quad m^{(j)}=m-(j-1)\max(0,d).$
(26)

Furthermore, as long as $x^{j}\neq\mathbf{0}$, the number of ones in the
matrix representing $x^{j}$ equals $m-k+1-(j-1)\lvert d\rvert$.

The elements of $M_{n}$ are idempotent or nilpotent. This is shown in the
theorem that follows, which further gives the nilpotency index.

######  Theorem 4.

An element $\langle d,k,m\rangle\in M_{n}\setminus\\{\mathbf{0}\\}$ is
idempotent if $d=0$ and nilpotent if $d\neq 0$. In the latter case, the index
$\ell$ of the nilpotent is given (in terms of $\lvert d\rvert$ and the number
$m-k+1$ of ones in the matrix $\langle d,k,m\rangle$) by

$\ell=1+\left\lceil\frac{m-k+1}{\lvert d\rvert}\right\rceil,$ (27)

where $\lceil x\rceil$ denotes the ceiling of $x\in\mathbb{R}$. This index
satisfies $2\leq\ell\leq n$.

Proof: For $d=0$ and $j=2$, Corollary 2 gives $\langle
0,k,m\rangle^{2}=\langle 0,k,m\rangle$ so that $\langle 0,k,m\rangle$ is
idempotent. Assume that $d<0$. Then the $k^{(j)}=k+\lvert d\rvert(j-1)$ in
(26) increases with $j$ and will thus surpass the constant $m^{(j)}=m$. By
(25), this means that $\langle 0,k,m\rangle^{j}=\mathbf{0}$ for sufficiently
large $j$, so that $\langle d,k,m\rangle$ is nilpotent. The index $\ell$,
which is the smallest $j$ for which $k^{(j)}>m$, is then given by (27). As
$\langle d,k,m\rangle$ is not a diagonal matrix, the numerator and denominator
of $\frac{m-k+1}{\lvert d\rvert}$ both lie between $1$ and $n-1$. Thus
$2\leq\ell\leq n$. (More generally, the nilpotency index of any nonzero
nilpotent $n\times n$ matrix satisfies this relation, see p. 190 of Horn and
Johnson (2012).) The proof for $d>0$ is similar. As expected, $\ell$ is
independent of $n$. Eqn. (27) further shows that moving the block of ones
along the underlying diagonal leaves the nilpotency index unaltered.

$\mathbf{1}$ is the only permutation matrix in $M_{n}$, which is a submonoid
of $R_{n}$. It thus follows from Lemma 1 that $\mathbf{1}$ is the only element
of $M_{n}$ which has an inverse in the sense of groups. We can strengthen this
statement by the proposition that follows, which is not true for $x,y\in
R_{n}$ (but is true for any monoid consisting solely of nilpotents and
idempotents).

######  Proposition 5.

Let $x,y\in M_{n}$. We have $xy=\mathbf{1}$ iff $x=y=\mathbf{1}$.

Proof: Let $xy=\mathbf{1}$, so that $x\neq\mathbf{0}$. If $x$ is nilpotent
with index $\ell$, then $\ell\geq 2$, so left-multiplication of
$xy=\mathbf{1}$ by $x^{\ell-1}$ gives $x^{\ell}y=x^{\ell-1}$, implying
$\mathbf{0}=x^{\ell-1}$ and contradicting the definition of the index. Thus
$x$ is not nilpotent. By Theorem 4, $x$ is idempotent, so $xy=\mathbf{1}$
gives $xy=x$. Thus $x=xy=\mathbf{1}$ and $\mathbf{1}=xy=\mathbf{1}y=y$.
Multiplication is thus closed within $M_{n}\setminus\\{\mathbf{1}\\}$.
Consequently,

######  Corollary 3.

$S_{n}=M_{n}\setminus\\{\mathbf{1}\\}$ is a semigroup and is a subsemigroup of
$R_{n}$.

Let us note that there is some risk of confusion between four closely related
entities dealt with herein; namely, the monoid
$M_{n}=S_{n}\cup\\{\mathbf{1}\\}$, the semigroup
$S_{n}=M_{n}\setminus\\{\mathbf{1}\\}$, the set
$M_{n}\setminus\\{\mathbf{0}\\}$, and the set
$S_{n}\setminus\\{\mathbf{0}\\}$. While sets (consisting of the elements that
can be represented by triplets), the last two entities are not semigroups.

We close this section by providing an example that views a familiar semigroup
as a subsemigroup of $S_{n}$.

######  Example 2.

Let us specialize our multiplication formula to elements of the set $B_{n}$
defined by

$B_{n}=\\{\mathbf{0}\\}\cup\\{\langle d,k,m\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}:m=k\\}.$ (28)

With the aid of Corollary 1 (take $m=k$ and $m^{\prime}=k^{\prime}$), we see
that (19)–(22) reduce to

$\langle d,k,k\rangle\langle
d^{\prime},k^{\prime},k^{\prime}\rangle=\begin{cases}\langle
d+d^{\prime},k,k\rangle,\quad k^{\prime}=k+d,\\\
\mathbf{0},\quad\mathrm{otherwise}.\end{cases}$ (29)

Thus multiplication is closed and $B_{n}$ is a subsemigroup of $S_{n}$. Now
set $(k,p)=\langle p-k,k,k\rangle$; in this new notation, (29) becomes

$\big{(}k,p\big{)}\big{(}k^{\prime},p^{\prime}\big{)}=\begin{cases}\big{(}k,p^{\prime}\big{)},\quad
k^{\prime}=p,\\\ \mathbf{0},\quad\mathrm{otherwise}.\end{cases}$ (30)

For $1\leq k,p\leq n$, the matrix $(k,p)$ is, by definition, the $n\times n$
matrix $x$ with all elements zero except for element $x_{kp}$, which equals 1.
Therefore (30) is self-evident and $B_{n}$ is the well-known combinatorial,
$0$-bisimple inverse semigroup associated with Brandt semigroups, see Chapter
3 of Lawson (1998). Theorem 4 corroborates that the nonzero elements of
$B_{n}$ are idempotent if $d=0$ ($p=k$) and nilpotent with index $\ell=2$ if
$d\neq 0$ ($p\neq k$). We further note that $(k,p)$, which is sometimes called
the single-entry matrix, arises in ring theory Lawson (1998), as well as other
applications Shimizu et al (2006).

##  5 $j$th roots

As mentioned in our Introduction, Annin et al (2012) and York (2017) discuss
$j$th roots in the monoid $R_{n}$. In its submonoid $M_{n}$, the triplet
representation renders the problem of finding roots more straightforward:
Firstly, the roots of $\mathbf{0}$ can be computed via Theorem 4. Secondly,
any nonzero idempotent $x$ has a unique $j$th root, namely $x$ itself (as all
$y\in M_{n}$ are idempotent or nilpotent, showing uniqueness is trivial).
Thirdly, the roots of any nonzero nilpotent $x$ can be found from the theorem
that follows (the theorem actually holds for any $x\in M_{n}$, as long as
$x\neq\mathbf{0}$). As it turns out, if a root $y$ of a nonzero $x$ does
exist, it is unique.

######  Theorem 6.

Let $j\in\mathbb{N}$ and let $x=\langle d,k,m\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}$. Then a $j$th root of $x$ exists in $M_{n}$
iff $d$ is an integer multiple of $j$. In this case, the $j$th root is unique
in $M_{n}$ and given by $y=\langle d^{\prime},k^{\prime},m^{\prime}\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}$, where

$d^{\prime}=\frac{d}{j},\quad k^{\prime}=k+(j-1)\min(0,d^{\prime}),\quad
m^{\prime}=m+(j-1)\max(0,d^{\prime}).$ (31)

Proof: We take $d\geq 0$. Then (17) and $x=\langle d,k,m\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}$ yield

$1\leq k\leq m\leq n-d.$ (32)

We seek $y\in M_{n}$ such that $x=y^{j}$. Since $y\neq\mathbf{0}$, we can set
$y=\langle d^{\prime},k^{\prime},m^{\prime}\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}$. By Corollary 2, $y$ exists iff there exist
integers $d^{\prime}$, $k^{\prime}$, and $m^{\prime}$ satisfying

$d=jd^{\prime},\quad k=k^{\prime},\quad m=m^{\prime}-(j-1)d^{\prime},$ (33)

which, because of (17), must also satisfy

$1\leq k^{\prime}\leq m^{\prime}\leq n-d^{\prime}.$ (34)

In (33) and (34), we took $d^{\prime}\geq 0$ because no negative $d^{\prime}$
can satisfy the first equality (33). If $d$ is not an integer multiple of $j$,
then the first equality (33) cannot be satisfied, so no root $y$ exists. If
$d$ is an integer multiple of $j$, we can uniquely solve (33) for
$d^{\prime}$, $k^{\prime}$, $m^{\prime}$; the solution thus obtained is given
by (31) (when (31) is specialized to $d>0$). Using (32), it is then easy to
show that the aforementioned $d^{\prime}$, $k^{\prime}$, $m^{\prime}$ further
satisfy (34). Accordingly, in this case there is a unique root $y$, whose
triplet parameters are given by (31). The proof for $d<0$ is similar.

######  Remark 2.

For $d=0$, Theorem 6 recovers the above-stated result for nonzero idempotents.
For nonzero nilpotents and for $j\geq 2$, the theorem and (18) (or,
alternatively, the inequality $\ell\leq n$ of Theorem 4) imply that a $j$th
root can exist only if $j\leq n-1$. For example, $\mathbf{0}$ is the only
nilpotent of $M_{2}$ that possesses a square root in $M_{2}$ (in fact,
$\mathbf{0}$ has three square roots in $M_{2}$, namely the nilpotents of
$M_{2}$, see Example 1 or Proposition 8). Needless to say, Theorem 6 does not
pertain to roots in $R_{n}\setminus M_{n}$, such as the additional square root
of $\mathbf{1}\in M_{2}$ that we noted in Example 1.

##  6 Further properties of $M_{n}$ and $S_{n}$

The triplet representation and simple combinatorics allow us to find the
number of elements in $S_{n}$ and $M_{n}$. As expected, $\lvert M_{n}\rvert$
is much smaller than $\lvert R_{n}\rvert$ (see Lemma 1) when $n$ is large:

######  Proposition 7.

The order $\lvert S_{n}\rvert$ of $S_{n}$ equals the square pyramidal number
Sloane (2021b), while $\lvert M_{n}\rvert=\lvert S_{n}\rvert+1$. In other
words,

$\lvert S_{n}\rvert=\lvert
M_{n}\rvert-1=\frac{n^{3}}{3}+\frac{n^{2}}{2}+\frac{n}{6}.$ (35)

Proof: Each nonzero element of $M_{n}$ uniquely defines the
northwest/southeast diagonal of a square and vice versa. Therefore $\lvert
S_{n}\rvert=\lvert M_{n}\rvert-1$ equals the number of squares within an
$n\times n$ square grid, which is Sloane (2021b) the square pyramidal number
written in the right-hand side of (35). Alternatively, (18) and (17) give

$\lvert
M_{n}\rvert-1=\sum_{d=-(n-1)}^{n-1}\,\sum_{k=1-\min(0,d)}^{n-\max(0,d)}\,\sum_{m=k}^{n-\max(0,d)}1,$

from which (35) follows by direct summation.

######  Example 3.

For $n=2$, $M_{n}=M_{2}$ consists of all matrices in Example 1 with the
exception of the first matrix $\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$ (to
which we assigned no symbol), so that $\lvert M_{2}\rvert=6$ and $\lvert
S_{2}\rvert=5$, as given by (35).

The semigroup $S_{2}$ has in fact been well studied Howie (1995); Ciric and
Bogdanovic (2000):

######  Proposition 8.

The Cayley table of $S_{2}$ is

| $\mathbf{0}$ | $a$ | $b$ | $e$ | $f$
---|---|---|---|---|---
$\mathbf{0}$ | $\mathbf{0}$ | $\mathbf{0}$ | $\mathbf{0}$ | $\mathbf{0}$ | $\mathbf{0}$
$a$ | $\mathbf{0}$ | $\mathbf{0}$ | $e$ | $\mathbf{0}$ | $a$
$b$ | $\mathbf{0}$ | $f$ | $\mathbf{0}$ | $b$ | $\mathbf{0}$
$e$ | $\mathbf{0}$ | $a$ | $\mathbf{0}$ | $e$ | $\mathbf{0}$
$f$ | $\mathbf{0}$ | $\mathbf{0}$ | $b$ | $\mathbf{0}$ | $f$

and $S_{2}$ is isomorphic to $B_{2}$, where $B_{2}$ is the five-element Brandt
semigroup.

Proof: For $n=2$, set $e=\langle 0,1,1\rangle$, $f=\langle 0,2,2\rangle$,
$a=\langle 1,1,1\rangle$, and $b=\langle-1,2,2\rangle$ (the symbols $e$, $f$,
$a$, $b$ are those used in Example 1). The table given above can then be
verified using Theorem 3 (or by multiplying the corresponding matrices), and
coincides with the table of $B_{2}$ in p. 32 of Howie (1995). The isomorphism
is also apparent from our description of $B_{n}$ in Example 2.

As seen from its Cayley table, $S_{2}$ has 3 idempotents (namely,
$\mathbf{0}$, $e$, and $f$) and 3 nilpotents ($\mathbf{0}$, $a$, and $b$).
More generally, the number of idempotents is the frequently-arising East
(2010); Sloane (2021a) triangular number $\frac{n(n+1)}{2}$:

######  Proposition 9.

$S_{n}=M_{n}\setminus\\{\mathbf{1}\\}$ has $\frac{n(n+1)}{2}$ idempotents and
$\frac{n^{3}}{3}-\frac{n}{3}+1$ nilpotents.

Proof: Let $N$ be the number of idempotents in
$S_{n}=M_{n}\setminus\\{\mathbf{1}\\}$. Then $N$ equals the number of
idempotents in $M_{n}\setminus\\{\mathbf{0}\\}$, which is in turn equal to the
number of elements $\langle 0,k,m\rangle$. By Theorem 4, this number is

$N=\sum_{k=1}^{n}\,\sum_{m=k}^{n}1=\frac{n(n+1)}{2},$

a result which can also be found using elementary combinatorics. The number of
nilpotents, which is $\lvert S_{n}\rvert-N+1$, then follows from Proposition
7.

Proposition 9 tells us that $R_{n}$ contains more idempotents than does
$M_{n}$, see Lemma 1. As for nilpotents, all those of $R_{2}$ belong to
$M_{2}$, but this is no longer true when $n\neq 2$.

In $R_{n}$, any two inverse elements are transposes of one another (in the
usual sense of matrix transposition), and this must also be true of the
subsemigroup $M_{n}$. With the obvious expression for $\langle
d,k,m\rangle^{T}$, we have arrived at the following proposition.

######  Proposition 10.

Let $x\in M_{n}$. The transpose $x^{T}$ of $x$ is

$x^{T}=\begin{cases}\mathbf{0},\quad x=\mathbf{0},\\\
\langle-d,k+d,m+d\rangle,\quad x=\langle d,k,m\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}.\end{cases}$ (36)

$x^{T}$ is the unique inverse of $x$. Therefore $M_{n}$ is an inverse monoid
and $S_{n}$ is an inverse semigroup.

While $R_{n}$ and $S_{n}$ are not abelian semigroups, some nonzero elements do
commute, e.g., $e$ and $f$ of $S_{2}$, see Proposition 8. What follows is a
necessary and sufficient condition for two nonzero $x,y\in M_{n}$ to commute
($xy=yx$).

######  Proposition 11.

Let $x,y\in M_{n}\setminus\\{\mathbf{0}\\}$ with $x=\langle d,k,m\rangle$ and
$y=\langle d^{\prime},k^{\prime},m^{\prime}\rangle$. Then

  * •

Case 1: $xy=yx\neq\mathbf{0}$ iff

$\max(k,k^{\prime}-d)=\max(k^{\prime},k-d^{\prime})\leq\min(m,m^{\prime}-d)=\min(m^{\prime},m-d^{\prime}).$
(37)

  * •

Case 2: $xy=yx=\mathbf{0}$ iff

$\max(k,k^{\prime}-d)>\min(m,m^{\prime}-d)\quad\mathrm{and}\quad\max(k^{\prime},k-d^{\prime})>\min(m^{\prime},m-d^{\prime}).$
(38)

Proof: Apply Corollary 1, interchange the roles of $x$ and $y$, and apply
again. In the special case $d=d^{\prime}=0$, the conditions of either Case 1
or Case 2 are satisfied for all $k,m,k^{\prime},m^{\prime}$ (as expected,
because diagonal matrices commute, see also Section 8.1). Thus the idempotents
of $M_{n}$ and $S_{n}$ commute, which is tantamount to saying that $M_{n}$ and
$S_{n}$ are orthodox semigroups. This was known beforehand, because all
inverse semigroups are orthodox.

##  7 On the numbers of zero and nonzero products

The set $S_{2}\setminus\\{\mathbf{0}\\}$, which has $4$ elements, gives rise
to $4^{2}=16$ possible products. The last four rows and columns of the table
in Proposition 8 tell us that $8$ of these products are zero and $8$ are
nonzero. This case ($n=2$) seems to be the only one in which the numbers of
zero and nonzero products are equal; e.g. $S_{3}\setminus\\{\mathbf{0}\\}$,
which has 13 elements, gives rise to 91 nonzero products, about $r(3)=53.9\%$
of the total. We have investigated the more general ratio $r(n)$ in the
following manner.

Let $\psi(n)$ be the number of nonzero products arising from the set
$M_{n}\setminus\\{\mathbf{0}\\}$. By (17) and Corollary 1, $\psi(n)$ is given
by

$\begin{split}\psi(n)=\sum_{d=1-n}^{n-1}\,&\sum_{k=1-\min(0,d)}^{n-\max(0,d)}\,\sum_{m=k}^{n-\max(0,d)}\\\
&\sum_{d^{\prime}=1-n}^{n-1}\,\sum_{k^{\prime}=1-\min(0,d^{\prime})}^{\min\left(m+d,n-\max(0,d^{\prime})\right)}\,\sum_{m^{\prime}=\max(k^{\prime},k+d)}^{n-\max(0,d^{\prime})}1.\end{split}$
(39)

Now $2\lvert S_{n}\rvert-1$ of these nonzero products involve $\mathbf{1}$, so
that
$S_{n}\setminus\\{\mathbf{0}\\}=M_{n}\setminus\\{\mathbf{0},\mathbf{1}\\}$
gives rise to $\psi(n)-2\lvert S_{n}\rvert+1$ nonzero products. As the total
number of products is $(\lvert S_{n}\rvert-1)^{2}$, the ratio $r(n)$ is

$r(n)=\frac{\psi(n)-2\lvert S_{n}\rvert+1}{(\lvert S_{n}\rvert-1)^{2}}.$ (40)

Although were not able to analytically evaluate the sextuple sum giving
$\psi(n)$, numerical evaluation and use of the On-Line Encyclopedia of Integer
Sequences (OEIS) suggested a connection to the so-called Polynexus numbers
Sloane (2021c), as stated in the following conjecture.

######  Conjecture 1.

For $n\in\mathbb{N}$, $\psi(n)$ equals the $(n+1)$th Polynexus number of order
$7$ Sloane (2021c), so that

$\psi(n)=\frac{(n+1)^{7}-n^{7}-(n+1)^{3}+n^{3}}{120}.$ (41)

This conjecture was verified for all $n\leq 70$. Provided that it is true,
(40), (35), and (41) give a closed-form expression for $r(n)$:

######  Conditional Proposition 1.

If Conjecture 1 is true, then the ratio $r(n)$ of nonzero products in
$S_{n}\setminus\\{\mathbf{0}\\}$ to the total number of products in
$S_{n}\setminus\\{\mathbf{0}\\}$ is given by

$r(n)=\frac{3(7n^{5}+28n^{4}+63n^{3}+18n^{2}-84n-120)}{10(n-1)(2n^{2}+5n+6)^{2}}.$
(42)

Accordingly, as $n\to\infty$,

$r(n)=\frac{21}{40}+\frac{147}{160}\,\frac{1}{n^{2}}+O\left(\frac{1}{n^{3}}\right).$
(43)

Thus when $n$ is large, $r(n)$ approaches $52.5\%=\frac{21}{40}$ monotonically
from above. Numerical results are given in Figure 4, where we observe a peak
at $n=4$.

Figure 4: The ratio $r(n)$ for $n=2,3,\ldots,70$.

######  Remark 3.

The three sums in the second line of (39) form a triple sum which depends on
$n$, $d$, $k$, and $m$. Given an $x=\langle d,k,m\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}$, the triple sum is the number of $y=\langle
d^{\prime},k^{\prime},m^{\prime}\rangle\in M_{n}\setminus\\{\mathbf{0}\\}$ for
which $xy\neq\mathbf{0}$. Conversely, if we are given a $y$, it is easy to
formulate a similar triple sum yielding the number of $x$ for which
$xy\neq\mathbf{0}$.

##  8 Submonoids and Subsemigroups

This section examines certain subsemigroups of $M_{n}$. To begin with, it can
be verified from Theorem 3 that, for $n\geq 3$, the following subset of
$M_{n}$

$\\{\mathbf{0}\\}\cup\\{\langle d,k,m\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}:m<n-\max(0,d)\\}$

is closed under multiplication. This set consists of $n\times n$ matrices
whose elements in the $n$’th row and the $n$’th column are all zero. Thus
closure alternatively follows from the general discussions in Section 2 and
amounts to

$M_{j}\sqsubseteq M_{n},\quad 2\leq j<n,$ (44)

where $\sqsubseteq$ means “is a subsemigroup of”. Note that the $\mathbf{1}$
of $M_{n}$ does not belong to $M_{j}$ ($M_{j}$ has a different $\mathbf{1}$
than does $M_{n}$) so that the monoids $M_{2},\ldots,M_{n-1}$ are not
submonoids of $M_{n}$.

Next, consider the subsets of $M_{n}$ described in the following table,

symbol for | matrices of $M_{n}$ representing | restrictions on
---|---|---
subset of $M_{n}$ | nonzero elements |  $d$, $k$, $m$
$UT_{n}$ | upper triangular | $d\geq 0$
$SUT_{n}$ | strictly upper triangular | $d>0$
$UF_{n}$ | upper full |  $d\geq 0$, $k=1$, and $m=n-d$
$SUF_{n}$ | strictly upper full |  $d>0$, $k=1$, and $m=n-d$
$LT_{n}$ | lower triangular | $d\leq 0$
$SLT_{n}$ | strictly lower triangular | $d<0$
$LF_{n}$ | lower full |  $d\leq 0$, $k=1-d$, and $m=n$
$SLF_{n}$ | strictly lower full |  $d<0$, $k=1-d$, and $m=n$
$D_{n}$ | diagonal | $d=0$

Each subset named in our table’s first column consists of $\mathbf{0}$
together with the elements $\langle d,k,m\rangle$ of
$M_{n}\setminus\\{\mathbf{0}\\}$ that satisfy the restrictions in the third
column. As an example,

$\begin{split}SUT_{n}&=\\{\mathbf{0}\\}\cup\\{\langle d,k,m\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}:d\geq 1\\}\\\ &=\\{\mathbf{0}\\}\cup\\{\langle
d,k,m\rangle:\ d,k,m\in\mathbb{N}\mathchar 24635\relax\;\ k\leq m\leq
n-d\\},\end{split}$ (45)

where the second expression follows from (17). As another example,

$SLF_{n}=\\{\mathbf{0}\\}\cup\\{\langle d,1-d,n\rangle\in
M_{n}\setminus\\{\mathbf{0}\\}:d<0\\}.$ (46)

Any nonzero element of $M_{n}$ corresponds to a matrix with only one nonzero
diagonal. The term “full” appearing in the table means that all entries of
this diagonal are nonzero (and equal to $1$). The terms upper/lower
triangular, strictly triangular, etc. are used in the usual sense of matrix
analysis.

######  Theorem 12.

All nine sets written in the above table are subsemigroups of $M_{n}$. The
semigroups $UT_{n}$, $UF_{n}$, $LT_{n}$, $LF_{n}$, and $D_{n}$ contain
$\mathbf{1}$ and are submonoids of $M_{n}$; removing $\mathbf{1}$ from any of
these five sets gives a subsemigroup of
$S_{n}=M_{n}\setminus\\{\mathbf{1}\\}$. Finally, $SUT_{n}$, $SUF_{n}$,
$SLT_{n}$, and $SLF_{n}$ consist solely of nilpotents, whose indexes are given
by (27).

Proof: The first statement is evident from Theorem 3 and the table’s third
column, or from elementary matrix theory and the second column. The second
statement follows from $\mathbf{1}=\langle 0,1,n\rangle$ and Corollary 3. The
third is a consequence of the table’s third column and Theorem 4. Further
properties are given in the proposition that follows, in which $A^{T}$ denotes
the set of transposes (see Proposition 10) of the subsemigroup $A$, viz.,

$A^{T}=\\{x^{T}:x\in A\sqsubseteq M_{n}\\}.$ (47)

######  Proposition 13.

The table below gives the transposes $A^{T}$ of semigroups $A$, states whether
$A$ and $A^{T}$ are commutative or not, and gives semigroup orders.

subsemigroup $A$ |  transpose $A^{T}$ |  $A$ and $A^{T}$ |  order of $A$ and $A^{T}$
---|---|---|---
of $M_{n}$ |  of $A$ is | are |
$UT_{n}$ | $LT_{n}$ | noncommutative | $1+\frac{1}{6}n(n+1)(n+2)$
$SUT_{n}$ | $SLT_{n}$ | noncommutative | $1+\frac{1}{6}(n-1)n(n+1)$
$UF_{n}$ | $LF_{n}$ | commutative | $1+n$
$SUF_{n}$ | $SLF_{n}$ | commutative | $n$
$D_{n}$ | $D_{n}$ | commutative | $1+\frac{1}{2}n(n+1)$

Proof: The orders can be found by direct summation, similarly to the proofs of
Propositions 7 and 9.

It is evident that

$SUF_{n}\sqsubseteq UF_{n}\sqsubseteq UT_{n}\sqsubseteq M_{n},\quad
SUT_{n}\sqsubseteq UT_{n}\sqsubseteq M_{n},$ (48)

and that the same relations hold when $U$ is replaced by $L$. It is also
evident that

$D_{n}=UT_{n}\cap LT_{n}=UF_{n}\cap LF_{n}.$ (49)

We proceed to give some additional properties of $D_{n}$, $SUF_{n}$,
$SLF_{n}$, and $SUT_{n}$.

###  8.1 Idempotents of $M_{n}$; diagonal matrices

As already discussed, $D_{n}$ is the set of idempotents of $M_{n}$ and is an
submonoid of $M_{n}$ whose order is $\frac{n^{2}}{2}+\frac{n}{2}+1$. $D_{n}$
is a commutative, nonrectangular band and is a lower semilattice. Eqns.
(19)–(22) specialize to the expected equation

$\langle 0,k,m\rangle\langle
0,k^{\prime},m^{\prime}\rangle=\begin{cases}\left\langle
0,\max(k,k^{\prime}),\min(m,m^{\prime})\right\rangle,\quad\max(k,k^{\prime})\leq\min(m,m^{\prime}),\\\
\mathbf{0},\quad\max(k,k^{\prime})>\min(m,m^{\prime}).\end{cases}$ (50)

###  8.2 Shift matrices and subsemigroups they generate

The monoid elements $\langle 1,1,n-1\rangle$ and $\langle-1,2,n\rangle$
represent the usual backward and forward shift matrices Horn and Johnson
(2012), which are transposes of one another. Their products are given by

$\langle 1,1,n-1\rangle\langle-1,2,n\rangle=\langle 0,1,n-1\rangle\in D_{n}$
(51)

and

$\langle-1,2,n)\langle 1,1,n-1\rangle=\langle 0,2,n\rangle\in D_{n}.$ (52)

Corollary 2 gives the respective powers as

$\langle 1,1,n-1\rangle^{j}=\begin{cases}\langle j,1,n-j\rangle,\
j=1,2,\ldots,n-1,\\\ \mathbf{0},\ j=n,\end{cases}$ (53)

and

$\langle-1,2,n\rangle^{j}=\begin{cases}\langle-j,1+j,n\rangle,\
j=1,2,\ldots,n-1,\\\ \mathbf{0},\ j=n.\end{cases}$ (54)

The powers in (53) and (54) are precisely the elements of $SUF_{n}$ and
$SLF_{n}$, respectively; see the table in Theorem 12. We have thus reached the
following conclusion.

######  Proposition 14.

$SUF_{n}$ is the monogenic subsemigroup generated by $\langle 1,1,n-1\rangle$,
and $SLF_{n}=SUF_{n}^{T}$ is the monogenic subsemigroup generated by
$\langle-1,2,n\rangle=\langle 1,1,n-1\rangle^{T}$.

Proposition 14 and eqns. (53) and (54) can be recognized as well-known
properties of the two shift matrices; in fact, these properties make clear why
the set of upper (or lower) Toeplitz matrices of size $n$ form a commutative
algebra Horn and Johnson (2012).

###  8.3 Minimal generating set for $SUT_{n}$; rank of $SUT_{n}$

Let $S$ be a finite semigroup, let $A\subseteq S$ be a generating set of $S$,
and denote the cardinality of $A$ by $\lvert A\rvert$. Recall that $A$ is a
minimal generating set (texts such as Ganyushkin and Mazorchuk (2008) use
irreducible in place of minimal) if no proper subset of $A$ can generate $S$;
and that the rank of $S$, denoted here by $\mathrm{rank}(S)$, is defined by
Gray (2014)

$\mathrm{rank}(S)=\mathrm{min}\\{\lvert A\rvert:A\subseteq S\mathrm{\ and\
}A\mathrm{\ generates\ }S\\}.$ (55)

The semigroup $SUT_{n}$ was defined in (45). The theorem that follows provides
a minimal generating set (called $A_{n}$) for $SUT_{n}$, gives
$\mathrm{rank}(SUT_{n})$, and uses the triplet representation to find (non-
unique) closed-form expressions for all $x\in SUT_{n}$. The generating set
$A_{n}$ consists of all matrices of $SUT_{n}$ whose ones lie on the diagonal
$d=1$.

######  Theorem 15.

The subset $A_{n}$ of $SUT_{n}$ defined by

$A_{n}=\\{\langle 1,k,m\rangle:1\leq k\leq m\leq n-1\\}$ (56)

is a minimal generating set for $SUT_{n}$, with

$\mathrm{rank}\left(SUT_{n}\right)=\lvert A_{n}\rvert=\frac{1}{2}n(n-1).$ (57)

In fact, any $x\in SUT_{n}$ can be found explicitly as a power of some $y\in
A_{n}$ via

$x=\begin{cases}\langle 1,1,1\rangle^{2},\quad x=\mathbf{0},\\\ \langle
1,k,m+d-1\rangle^{d},\quad x=\langle d,k,m\rangle\in
SUT_{n}\setminus\\{\mathbf{0}\\}.\end{cases}$ (58)

Proof: By Theorem 4, $\langle 1,1,1\rangle$ is a square root of $\mathbf{0}$;
and by Theorem 6, $\langle 1,k,m+d-1\rangle$ is the (unique in $M_{n}$) $d$th
root of $x=\langle d,k,m\rangle\in SUT_{n}$. Therefore (58) holds. Since both
$\langle 1,1,1\rangle$ and $\langle 1,k,m+d-1\rangle$ belong to $A_{n}$, (58)
explicitly demonstrates that $A_{n}$ generates $SUT_{n}$.

We now turn to minimality and rank. If $x_{i}=\langle
d_{i},k_{i},m_{i}\rangle\in SUT_{n}\setminus\\{\mathbf{0}\\}$, then
$\sum_{i=1}^{p}d_{i}\geq p$ by (45); eqn. (56) and Theorem 3 then show that
the product $\prod_{i=1}^{p}x_{i}$ can belong to $A_{n}$ only if $p=1$ and
$x_{1}\in A_{n}$. In other words, any $y\in A_{n}$ can be written as a finite
product of elements of $SUT_{n}$ only in a trivial manner (i.e., the product
can only have one factor, equal to $y$), implying that any generating set must
contain this $y$. We have thus shown that

$(B_{n}\subseteq SUT_{n}\mathrm{\ and\ }B_{n}\mathrm{\ generates\
}SUT_{n})\implies A_{n}\subseteq B_{n}.$

It follows that no proper subset of $A_{n}$ can generate $SUT_{n}$, proving
minimality of the generating set $A_{n}$. It also follows that $\lvert
A_{n}\rvert\leq\lvert B_{n}\rvert$ for any $B_{n}$ generating $SUT_{n}$, so
that the rank of $SUT_{n}$ equals the cardinality of its generating set
$A_{n}$. Computing $\lvert A_{n}\rvert$ via (56), we arrive at (57). By taking
transposes, one can immediately re-state Theorem 15 so as to apply to
$SLT_{n}=SUT_{n}^{T}$.

###  8.4 More subsemigroups of $M_{n}$

We close Section 8 by listing some additional subsemigroups of $M_{n}$ that
can be studied by specializing the triplet representation developed in this
paper. The said subsemigroups are obtained by adjoining $\\{\mathbf{0}\\}$ to
any one of the following sets,

  * •

The matrices of $M_{n}$ with $d=$integer multiple of $d_{0}$, where $1\leq
d_{0}\leq n-1$.

  * •

The matrices of $M_{n}$ with $d\geq d_{0}$, where $1\leq d_{0}\leq n-1$.

  * •

The matrices of $M_{n}$ whose first row and first column are zero.

  * •

The matrices of $M_{n}$ whose first row and last column are zero.

  * •

The matrices of $M_{n}$ that have at most $j$ nonzero elements, where $2\leq
j\leq n$ (see Example 2 for the case $j=1$).

##  9 Graphical Interpretations

This section examines the rook $n$-diagrams associated with $M_{n}$. As we
already did in Figures 1 and 2, we assume that the two rows of vertices form
an $n\times 2$ orthogonal grid.

A rook $n$-diagram represents an element of $M_{n}$ iff its lines (edges) are
parallel, equispaced, and uninterrupted, as in Figure 5. Note that the said
requirements guarantee non-intersecting lines, so that
$M_{n}\sqsubseteq\mathcal{POI}_{n}$.

Figure 5: Rook $n$-diagram representation of the element $\langle
d,k,m\rangle$ belonging to $M_{n}\setminus\\{\mathbf{0}\\}$.

Multiplication of two elements in $M_{n}$ is done graphically in the usual
manner, as illustrated in Figure 6.

Figure 6: Graphical multiplication in $M_{n}$ via rook $n$-diagrams: Here, we
depict $\langle 1,1,3\rangle\langle 2,3,4\rangle=\langle 3,2,3\rangle$.

It is evident that many of our previous results (in Sections 4–8) can be
depicted and explained graphically, and that graphical methods can help one
discover further properties of $M_{n}$ and its subsemigroups. We thus proceed
to give some indicative graphical interpretations (there are many more). In
the discussion that follow, we conveniently refer to the parameter $d$ as the
(positive, negative, or zero) inclination of the rook $n$-diagram representing
$\langle d,k,m\rangle$.

  * •

It is apparent (e.g. from Figure 5) that $\mathbf{1}$ is the only element of
$M_{n}$ that has $n$ lines. This fact and the graphical interpretation of
multiplication make it easy to understand why the “if” part of Proposition 5
($xy=\mathbf{1}\implies x=y=\mathbf{1}$) is true: The number of lines in the
product of two elements is at most the minimum number of the two elements’
lines. Thus if $xy=\mathbf{1}$, then both $x$ and $y$ must have $n$ lines, so
that $x=y=\mathbf{1}$.

  * •

The subsets $D_{n}$ and $SUT_{n}$ correspond to a zero or positive
inclination, respectively. It is apparent that multiplication again leads to a
zero or positive inclination, explaining why $D_{n}$ and $SUT_{n}$ are
subsemigroups. It is also apparent why the elements of $D_{n}$ are the
idempotents of $M_{n}$.

  * •

The elements of the subset $UF_{n}$ are those whose first (leftmost) line
starts at vertex $1$ of the top row, and whose last (rightmost) line ends at
vertex $n$ of the bottom row. Evidently multiplication retains these
properties, so that $UF_{n}$ is a subsemigroup. The subsemigroup’s $n$
elements correspond to the $n$ possible inclinations $d=0,1,\ldots,n-1$.

  * •

Figure 6 helps one understand why multiplication adds inclinations and why
taking the $j$th power multiplies the inclination by $j$, as expressed by (20)
and (26). We can further understand formula (27) for the index of a nonzero
nilpotent: Let $x=\langle d,k,m\rangle$ with $d>0$. The first line of $x^{j}$
starts at (top) vertex $k$ and ends at (bottom) vertex $k+jd$. However, the
last line of $x^{j}$ cannot end after vertex $m+d$. This means that the index
$\ell$ of $x$ is the smallest $j$ such that $x^{j}$’s first line would have
been after $m+d$, i.e. the minimum $j$ for which $k+jd\geq m+d+1$. When $d<0$,
we can find the index in an analogous manner.

  * •

In a similar manner, we can perceive when the product of two elements is zero:
The first line of $\langle d,k,m\rangle\langle
d^{\prime},k^{\prime},m^{\prime}\rangle$ ends on vertex $k+d+d^{\prime}$ or to
the right of that vertex, but it cannot end to the right of vertex
$m^{\prime}+d^{\prime}$. Therefore $k+d+d^{\prime}>m^{\prime}+d^{\prime}$ is a
sufficient condition for the product to be $\mathbf{0}$, as asserted by
Corollary 1.

  * •

Much of Theorem 6 can be explained in the following manner. The inclination of
$\langle d^{\prime},k^{\prime},m^{\prime}\rangle^{j}$ is $jd^{\prime}$. Thus
$x=\langle d,k,m\rangle$ can have a $j$th root only if $d$ is a multiple of
$j$. Assume now that $d>0$. The first line of the $j$th root of $\langle
d,k,m\rangle$, must start at $k$ and its last line must end at $m+d$. This
means that $y=\langle d^{\prime},k^{\prime},m^{\prime}\rangle$ and $y^{j}=x$
imply $k^{\prime}=k$ and $m^{\prime}+d^{\prime}=m+d$, as illustrated in Figure
7.

Figure 7: Graphical interpretation of $\langle
d^{\prime},k^{\prime},m^{\prime}\rangle^{j}=\langle d,k,m\rangle$. Each row
shows $\langle d^{\prime},k^{\prime},m^{\prime}\rangle$, while the dashed
lines show $\langle d,k,m\rangle$.

##  10 Summary

In this paper, we defined a monoid $M_{n}$; showed that the nonzero elements
of $M_{n}$ can be represented as $\langle d,k,m\rangle$, where $d$, $k$, and
$m$ are properly defined integers; and used this “triplet representation” to
study numerous properties of $M_{n}$. Both $M_{n}$ and the set
$S_{n}=M_{n}\setminus\\{\mathbf{1}\\}$ (where $\mathbf{1}$ is the monoid
identity, corresponding to the $n\times n$ identity matrix) are subsemigroups
of the well-known rook monoid $R_{n}$, also known as the symmetric inverse
semigroup. The monoid $M_{n}$ consists of those elements of $R_{n}$ whose ones
lie on a single diagonal and form an uninterrupted block (i.e., no zero lies
between any two ones). Equivalently, the rook-$n$ diagram of any monoid
element has the form shown in Figure 5.

In Sections 3 and 4, we regarded $M_{n}$ as a subsemigroup of a certain
semigroup $S_{\infty}$ of countably infinite order; this helped us find the
triplet representation of the product of two monoid elements (Theorem 3). Our
results on $M_{n}$ include:

  * •

A simple formula for powers (Corollary 2).

  * •

A proof that any element is idempotent or nilpotent (Theorem 4). Proposition 9
further gives the numbers of idempotents and nilpotents.

  * •

A formula (in Theorem 4) for the index $\ell$ of any nonzero nilpotent in
terms of $d$, $k$, and $m$.

  * •

A proof that the $j$th root of any given nonzero element either does not
exist; or does exist, is unique, and has the triplet representation given
explicitly in Theorem 6.

  * •

An investigation of the ($n$-dependent) number of nonzero products in
$S_{n}~{}\setminus~{}\\{\mathbf{0}\\}$; this number is $50\%$ of the total
number of products when $n=2$, and appears to be slightly larger than $50\%$
for all other $n$ (Conditional Proposition 1 and Figure 4).

  * •

The use of rook-$n$ diagrams to give graphical interpretations of many of our
results (Section 9).

  * •

An investigation of some subsemigroups of $M_{n}$ (Section 8). Two of these
are the familiar monogenic subsemigroups generated by the well-known backward
and forward shift matrices (Proposition 14). For another subsemigroup—denoted
by $SUT_{n}$ and consisting of all strictly upper triangular matrices of
$M_{n}$—we found a minimal generating set $A_{n}$, gave a (non-unique)
explicit formula for any $x\in SUT_{n}$, and computed the rank of $SUT_{n}$
(Theorem 15).

  * •

Section 8.4, finally, lists more subsemigroups that can be investigated along
similar lines.

Acknowledgments

The work of Giannis Fikioris was supported in part by NSF grants CCF-1408673
and AFOSR grant FA9550-19-1-0183.

## References

  *   * Annin et al (2012) Annin S, Cannon T, Hernandez C, et al (2012) On kth roots in the symmetric inverse monoid. Pi Mu Epsilon Journal pp 321–331
  * Ciric and Bogdanovic (2000) Ciric M, Bogdanovic S (2000) The five-element Brandt semigroup as a forbidden divisor. Semigroup Forum 61(3):363–372
  * East (2006) East J (2006) A presentation of the singular part of the symmetric inverse monoid. Communications in Algebra 34(5):1671–1689. URL https://doi.org/10.1080/00927870500542689
  * East (2010) East J (2010) Presentations for singular subsemigroups of the partial transformation semigroup. Int J Algebra Comput 20(1):1–25. URL https://doi.org/10.1142/S0218196710005509
  * Fernandes (2001) Fernandes V (2001) The monoid of all injective order preserving partial transformations on a finite chain. Semigroup Forum 62:178–204. 10.1007/s002330010056
  * Ganyushkin and Mazorchuk (2008) Ganyushkin O, Mazorchuk V (2008) Classical finite transformation semigroups: an introduction. Springer Science & Business Media
  * Gray (2014) Gray RD (2014) The minimal number of generators of a finite semigroup. Semigroup Forum 89(1):135–154
  * Horn and Johnson (2012) Horn RA, Johnson CR (2012) Matrix analysis. Cambridge University Press
  * Howie (1995) Howie JM (1995) Fundamentals of semigroup theory. Oxford University Press
  * Lawson (1998) Lawson MV (1998) Inverse semigroups: The theory of partial symmetries. World Scientific
  * Li et al (2008) Li Z, Li Z, Cao Y (2008) Representations of the symplectic rook monoid. Int J Algebra Comput 18(5):837–852. URL https://doi.org/10.1142/S0218196708004640
  * Meyer (2000) Meyer CD (2000) Matrix analysis and applied linear algebra. SIAM
  * Shimizu et al (2006) Shimizu S, Hoyer PO, Hyvärinen A, et al (2006) A linear non-Gaussian acyclic model for causal discovery. J of Machine Learning Research 7:2003–2030
  * Sloane (2021a) Sloane N (2021a) Sequence A000217 (triangular numbers). URL https://oeis.org/A000217
  * Sloane (2021b) Sloane N (2021b) Sequence A000330 (square pyramidal numbers). URL https://oeis.org/A000330
  * Sloane (2021c) Sloane N (2021c) Sequence A083200 (Polynexus numbers of order 7). URL https://oeis.org/A083200
  * Solomon (2002) Solomon L (2002) Representations of the rook monoid. J of Algebra 256:309–342
  * Xiao (2016) Xiao Z (2016) On tensor spaces for rook monoid algebras. Acta Mathematica Sinica, English Series 32:607–620
  * York (2017) York C (2017) Enumerating kth roots in the symmetric inverse monoid. arXiv preprint arXiv:170903603