Semigroups of rectangular matrices under a sandwich operation
Igor Dolinka
Department of Mathematics and Informatics
University of Novi Sad, Trg Dositeja Obradovića 4, 21101 Novi Sad, Serbia
dockie @ dmi.uns.ac.rs

James East
Centre for Research in Mathematics; School of Computing, Engineering and Mathematics

arXiv:1503.03139v2 [] 15 Aug 2016

Western Sydney University, Locked Bag 1797, Penrith NSW 2751, Australia
J.East @ WesternSydney.edu.au

August 16, 2016

Abstract
Let Mmn = Mmn (F) denote the set of all m × n matrices over a field F, and fix some n × m
matrix A ∈ Mnm . An associative operation ? may be defined on Mmn by X ? Y = XAY for all
A
X, Y ∈ Mmn , and the resulting sandwich semigroup is denoted MA
mn = Mmn (F). These semigroups
are closely related to Munn rings, which are fundamental tools in the representation theory of finite
A
A
semigroups. In this article, we study MA
mn as well as its subsemigroups Reg(Mmn ) and Emn (consisting
of all regular elements and products of idempotents, respectively), as well as the ideals of Reg(MA
mn ).
Among other results, we: characterise the regular elements; determine Green’s relations and preorders;
calculate the minimal number of matrices (or idempotent matrices, if applicable) required to generate each
semigroup we consider; and classify the isomorphisms between finite sandwich semigroups MA
mn (F1 ) and
MB
(F
).
Along
the
way,
we
develop
a
general
theory
of
sandwich
semigroups
in
a
suitably
defined
class
2
kl
of partial semigroups related to Ehresmann-style “arrows only” categories; we hope this framework will be
useful in studies of sandwich semigroups in other categories. We note that all our results have applications
to the variants MA
n of the full linear monoid Mn (in the case m = n), and to certain semigroups of linear
transformations of restricted range or kernel (in the case that rank(A) is equal to one of m, n).
Keywords: Matrix semigroups, sandwich semigroups, variant semigroups, idempotents, generators,
rank, idempotent rank, Munn rings, generalised matrix algebras.
MSC: 15A30; 20M20; 20M10; 20M17.

1

Introduction

In the classical representation theory of finite semigroups, a key role is played by the so-called Munn rings.
These are rings of m×n matrices (where m and n need not be equal) with the familiar addition operation but
with a sandwich multiplication defined by X ?Y = XAY , where A is a fixed n×m matrix. These rings are so
named, because of Douglas Munn’s 1955 paper [68], in which it was shown that: (1) the representation theory
of a finite semigroup is determined by the representations of certain completely 0-simple semigroups arising
from its ideal structure, and (2) the semigroup algebra of such a finite completely 0-simple semigroup is
isomorphic to an appropriate Munn ring over the group algebra of a naturally associated maximal subgroup;
conditions were also given for such a Munn ring to be semisimple. (Here, the sandwich matrix A arises from
the celebrated Rees structure theorem [81] for completely 0-simple semigroups.) Since their introduction
in [68], Munn rings have been studied by numerous authors, and continue to heavily inflence the theory of
semigroup representations: for classical studies, see [12–14,37,54,62–64,68–70,76]; for modern accounts, see
for example [1, 29, 47, 75, 78, 79, 85, 86], and especially the monographs [73, 74, 77, 82, 87].
In the same year as Munn’s article [68] was published, William Brown introduced the so-called generalised
matrix algebras [5], motivated by a connection with classical groups [3, 6, 95]. These generalised matrix
1

algebras are again rings of m × n matrices over a field, with multiplication determined by a fixed n × m
sandwich matrix. Whereas the sandwich matrix in a Munn ring is taken to be the structure matrix of a
completely 0-simple semigroup (and so has a certain prescribed form), Brown considered arbitrary sandwich
matrices. As with Munn rings, these generalised matrix algebras have influenced representation theory to
this day, and have been studied by numerous authors; see for example [21, 30, 35, 51, 52, 55, 92, 96, 97].
Shortly after the Munn and Brown articles [5, 68] appeared, Evgeny Lyapin’s early monograph on semigroups [57] was published. In [57, Chapter VII], we find a number of interesting semigroup constructions,
including the following. Let V and W be arbitrary non-empty sets, and let θ : W → V be an arbitrary (but
fixed) function. Then the set T (V, W ) of all functions V → W forms a semigroup, denoted T θ (V, W ), under
the operation ?θ defined by f ?θ g = f ◦ θ ◦ g. If it is assumed that V and W are vector spaces (over the
same field) and θ a linear transformation, then the subset L(V, W ) ⊆ T (V, W ) of all linear transformations
V → W is a subsemigroup of T θ (V, W ). This subsemigroup, denoted Lθ (V, W ) and referred to as a linear
sandwich semigroup, is clearly isomorphic to the underlying multiplicative semigroup of an associated generalised matrix algebra [5]. As noted above, the addition on a generalised matrix algebra is just the usual
operation, so these linear sandwich semigroups capture and isolate (in a sense) the more complex of the
operations on the algebras.
The sandwich semigroups T θ (V, W ) were first investigated in a series of articles by Magill and Subbiah
[58–60], and more recent studies may be found in [7, 65, 90, 93]; most of these address structural concerns
such as (von Neumann) regularity, Green’s relations, ideals, classification up to isomorphism, and so on.
The linear sandwich semigroups Lθ (V, W ) have received less attention, though they have also been studied
by a number of authors [9, 48, 49, 66], with studies again focusing on basic structural properties. This is
regrettable, because these semigroups display a great deal of algebraic and combinatorial charm, as we
hope to show in the current article. It is therefore our purpose to carry out a systematic investigation of
the linear sandwich semigroups, bringing their study up to date, and focusing on modern themes, especially
combinatorial invariant theory. As does Brown [5], we focus on the case that V and W are finite dimensional;
A
in fact, we study the equivalent sandwich semigroups MA
mn = Mmn (F) consisting of all m × n matrices over
the field F under the operation ?A defined by X ?A Y = XAY , where A is a fixed n × m matrix.
We speculate that the difficulty (until now) of systematically investigating the linear sandwich semigroups
may be due to the lack of a consistent theoretical framework for studying sandwich semigroups in more
generality. In the case that V = W , the sets T (V, W ) and L(V, W ) are themselves semigroups (under
composition); these are the full transformation semigroup TV [23, 28, 32, 34, 42, 43, 45, 65] and the general
linear monoid LV [2, 15, 16, 18, 20, 25, 33, 53, 74, 80, 94], respectively. In turn, the semigroups T θ (V, V ) and
Lθ (V, V ) are special cases of the semigroup variant construction. The variant of a semigroup S with respect
to an element a ∈ S is the semigroup S a = (S, ?a ), with operation defined by x ?a y = xay. Variants
were first explicitly studied by Hickey in the 1980s [38, 39], though (as noted above) the idea goes back to
Lyapin’s monograph [57]; a more recent study may be found in [50]. The current authors developed the
general theory of variants further in [19], and then used this as a starting point to explore the variants of
the finite full transformation semigroups, obtaining a great deal of algebraic and combinatorial information
about these semigroups. Unfortunately, the theory of semigroup variants does not help with studying
the more general sandwich semigroups T θ (V, W ) and Lθ (V, W ), since the underlying sets T (V, W ) and
L(V, W ) are not even semigroups if V 6= W . One of the main goals of the current article, therefore, is to
develop an appropriate general framework for working with arbitrary sandwich semigroups. Namely, if V
and W are objects in a (locally) small category C , and if θ ∈ Hom(W, V ) is some fixed morphism, then
the set Hom(V, W ) becomes a semigroup under the sandwich operation defined by f ?θ g = f ◦ θ ◦ g, for
f, g ∈ Hom(V, W ). (In the case that V = W and θ is the identity morphism, this construction reduces to
the usual endomorphism monoid End(V ).) The semigroups T θ (V, W ) and Lθ (V, W ) arise when C is the
category of sets (and mappings) or vector spaces (and linear transformations), respectively. In order to
develop a general theory of sandwich semigroups in such categories, we first explain how many important
semigroup theoretical techniques extend to the more general categorical setting; we note that there is only a
little overlap with the theory of Green’s relations in categories developed in [56], which focuses on issues more
relevant to representation theory. In order to avoid any confusion arising from terminology conflicts between
semigroup and category theory, rather than speak of (locally small) categories, we focus on the equivalently
defined class of partial semigroups, which are related to Ehresmann-style “arrows only” categories [24]. We
hope that the general theory we develop will prove to be a useful starting point for future studies of sandwich
2

semigroups in other categories.
The article is organised as follows. In Section 2, we develop a general theory of sandwich semigroups in partial
semigroups (i.e., locally finite categories), extending certain important semigroup theoretic notions (such as
Green’s relations, regularity and stability, the definitions of which are given in Section 2) to the more general
context. In Section 3, we gather results on the partial semigroup M = M(F) of all (finite dimensional)
matrices over the field F, mainly focusing on regularity, stability and Green’s relations, and we state some
well-known results on (idempotent) generation and ideals of the general linear monoids Mn . We begin our
investigation of the linear sandwich semigroups MA
mn in Section 4, the main results of this section being: a
characterisation of the regular elements (Proposition 4.3); a description of Green’s relations (Theorem 4.5)
and the ordering on D-classes (Propositions 4.6, 4.7 and 4.10); a classification of the isomorphism classes
of sandwich semigroups over Mmn (Corollary 4.8); and the calculation of rank(MA
mn ) (Theorems 4.12
and 4.14). (Recall that the rank of a semigroup S, denoted rank(S), is the minimum size of a generating
set for S.) Section 5 explores the relationship between a sandwich semigroup MA
mn and various (nonsandwich) matrix semigroups, the main structural results being Theorem 5.7 and Propositions 5.8 and 5.11.
We then focus on the regular subsemigroup P = Reg(MA
mn ) in Section 6, where we: calculate the size
of P and various Green’s classes (Proposition 6.2 and Theorem 6.4); classify the isomorphism classes of
finite linear sandwich semigroups (Theorem 6.5); and calculate rank(P ) (Theorem 6.10). In Section 7, we
A of MA , where we: enumerate the idempotents
investigate the idempotent generated subsemigroup Emn
mn
A
A
of Mmn (Proposition 7.2); show that Emn consists of P \ D and the idempotents from D, where D is
A ) and idrank(E A ), showing in particular that
the maximal D-class (Theorem 7.3); and calculate rank(Emn
mn
these are equal (Theorem 7.5). (The idempotent rank of an idempotent generated semigroup S, denoted
idrank(S), is defined similarly to the rank, but with respect to idempotent generating sets for S.) Finally, in
Section 8, we classify the proper ideals of P , showing that these are idempotent generated, and calculating
their ranks and idempotent ranks, which are again equal (Theorem 8.1). We note that all our results have
applications to the variants MA
n of the full linear monoid Mn (in the case m = n), and to certain semigroups
of linear transformations of restricted range or kernel (in the case that rank(A) is equal to one of m, n; see
Remarks 4.2 and 5.3).

2

Sandwich semigroups from partial semigroups

A
Recall that our main interest is in the linear sandwich semigroups MA
mn = Mmn (F). The underlying set of
A
Mmn is Mmn , the set of all m × n matrices over the field F, which is not itself a semigroup (unless m = n).
However, Mmn is contained in M, the set of all (finite dimensional) matrices over F. While M is still not a
semigroup, it does have the structure of a (small) category. As we will see, in order to understand the linear
sandwich semigroups MA
mn , we need to move beyond just m × n (and n × m) matrices, and gain a fuller
understanding of the whole category M. Some (but not all) of what we need to know about M is true in a
larger class of categories, and more general structures we call partial semigroups, so we devote this section
to the development of the general theory of these structures. We begin with the definitions.

Definition 2.1. A partial semigroup is a 5-tuple (S, ·, I, λ, ρ) consisting of a set S, a partial binary operation
(x, y) 7→ x · y (defined on some subset of S × S), a set I, and functions λ, ρ : S → I, such that, for all
x, y, z ∈ S,
(i) x · y is defined if and only if ρ(x) = λ(y),
(ii) if x · y is defined, then λ(x · y) = λ(x) and ρ(x · y) = ρ(y),
(iii) if x · y and y · z are defined, then (x · y) · z = x · (y · z).
We say that a partial semigroup (S, ·, I, λ, ρ) is monoidal if in addition to (i–iii),
(iv) there exists a function I → S : i 7→ ei such that, for all x ∈ S, x · eρ(x) = x = eλ(x) · x.
We say that a partial semigroup (S, ·, I, λ, ρ) is regular if in addition to (i–iii),
(v) for all x ∈ S, there exists y ∈ S such that x = x · y · x and y = y · x · y.
3

Remark 2.2. We note that conditions (i–iv) amount to one of several equivalent ways to define (small)
categories in an “arrows only” fashion. See for example Ehresmann’s monograph [24], and also [41] for a
historical discussion of the connections between category theory and (inverse) semigroup theory.
For a partial semigroup (S, ·, I, λ, ρ), and for i, j ∈ I, we write
Sij = {x ∈ S : λ(x) = i, ρ(x) = j}

and

Si = Sii .

S
So S = i,j∈I Sij . Note that if x ∈ S, then x · x is defined if and only if λ(x) = ρ(x). It follows that Si
is a semigroup with respect to the induced binary operation (the restriction of · to Si × Si ) for each i ∈ I,
but that Sij is not if i 6= j. We will often slightly abuse notation and refer to “the partial semigroup S” if
the rest of the data (S, ·, I, λ, ρ) is clear from context. We also note that in what follows, we could allow S
and I to be classes (rather than insist on them being sets); but we would still require Sij to be a set for
each i, j ∈ I.
Note that, as is the case with semigroups, condition (v) is equivalent to the (ostensibly) weaker condition:
(v)0 for all x ∈ S, there exists z ∈ S such that x = x · z · x.
Indeed, with z as in (v)0 , one easily checks that y = z · x · z satisfies the condition of (v).
If S is monoidal, then Si is a monoid with identity ei ∈ Si for each i. If S is not monoidal, then S may be
embedded in a monoidal partial semigroup S (1) as follows: for each i ∈ I we adjoin an element ei to Si and
declare that x · ei = x and ei · y = y for all x, y ∈ S with ρ(x) = i and λ(y) = i, if such an element ei ∈ Si
does not already exist. In particular, if S is monoidal, then S = S (1) .
Obviously any semigroup is a partial semigroup (with |I| = 1); in particular, all results we prove in this
section concerning partial semigroups hold for semigroups. A great number of non-semigroup examples
exist, but we will limit ourselves to describing just a few.
Example
2.3. As a trivial example, let {Si : i ∈ I} be any set of pairwise disjoint semigroups. Then
S
S = i∈I Si is a partial semigroup where we define λ, ρ : S → I by λ(x) = ρ(x) = i for each i ∈ I and
x ∈ Si , and x · y is defined if and only if x, y ∈ Si for some i, in which case x · y is just the product of x, y
in Si . Note that this S is regular (resp., monoidal) if and only if each Si is regular (resp., a monoid).
Example 2.4. Let X be some set, and P(X ) = {A : A ⊆ X } the power set of X . The set TX =
{(B, f, A) : A, B ⊆ X , f is a function A → B} is a regular monoidal partial semigroup. We define I =
P(X ), and λ(B, f, A) = B and ρ(B, f, A) = A, with (D, g, C) · (B, f, A) defined if and only if B = C, in
which case (D, g, C) · (B, f, A) = (D, g ◦ f, A).
The previous example may be extended in a number of ways, by replacing functions f : A → B by other
objects such as binary relations [8, 91], partial functions [11, 88], partial bijections [10], block bijections [26],
partial braids [22], partitions [61], Brauer diagrams [3], etc., or by assuming the functions f : A → B preserve
some kind of algebraic or geometric structure on the sets A, B. The main example we will concentrate on
in this article is as follows.
Example 2.5. Let F be a field, and write M = M(F) for the set of all (finite dimensional, non-empty)
matrices over F. Then M has the structure of a regular monoidal partial semigroup. We take I = N =
{1, 2, 3, . . .} to be the set of all natural numbers and, for X ∈ M, we define λ(X) (resp., ρ(X)) to be the
number of rows (resp., columns) of X. For m, n ∈ N, Mmn = Mmn (F) denotes the set of all m × n matrices
over F, and forms a semigroup if and only if m = n. (Of course, M is isomorphic to a certain partial
semigroup of linear transformations; we will have more to say about this later.)
For the remainder of this section, we fix a partial semigroup (S, ·, I, λ, ρ), and we write xy for the product
x · y (whenever it is defined). Note that we may define a second partial binary operation • on S by
x•y =y·x

for each x, y ∈ S with ρ(y) = λ(x).
4

We see then that (S, •, I, ρ, λ) is a partial semigroup (note the swapping of λ and ρ), and we call this the
dual partial semigroup to (S, ·, I, λ, ρ). As is frequently the case in semigroup theory, this duality will allow
us to shorten several proofs.
Green’s relations and preorders are crucial tools in semigroup theory (for general background on semigroups,
see [40, 44]), and we will need to extend these to the partial semigroup setting. If x, y ∈ S, then we say
• x ≤R y if x = ya for some a ∈ S (1) ,
• x ≤L y if x = ay for some a ∈ S (1) ,
• x ≤J y if x = ayb for some a, b ∈ S (1) .
Note that if x ≤R y (resp., x ≤L y), then λ(x) = λ(y) (resp., ρ(x) = ρ(y)). Note also that if x ≤R y, then
ux ≤R uy for any u ∈ S with ρ(u) = λ(x); a dual statement holds for the ≤L relation. Finally, note that
the use of S (1) is merely for convenience since, for example, x ≤R y means that x = y or x = ya for some
a ∈ S. All three of the above relations are preorders (i.e., they are reflexive and transitive). If K is one
of R, L , J , we write K = ≤K ∩ ≥K for the equivalence relation on S induced by K . So, for example,
xRy if and only if x = ya and y = xb for some a, b ∈ S (1) . We also define equivalence relations
H =R∩L

and

D = R ∨L.

(The join ε ∨ η of two equivalences ε and η is the transitive closure of ε ∪ η, and is itself an equivalence.) It
is easy to see that D ⊆ J . The duality mentioned above means that x ≤R y in (S, ·, I, λ, ρ) if and only if
x ≤L y in (S, •, I, ρ, λ), and so on.
Analogously to the definition for semigroups [83, Definition A.2.1], we say that the partial semigroup S is
stable if for all x, y ∈ S,
xJ xy ⇔ xRxy
and
xJ yx ⇔ xL yx.
The following simple but crucial observation is proved in analogous fashion to the corresponding results for
semigroups; see for example [44, Proposition 2.1.3] and [83, Corollary A.2.5].
Lemma 2.6. We have D = R ◦ L = L ◦ R. If S is stable, then D = J .

2

If x ∈ Sij and K is one of R, L , J , D, H , we write
[x]K = {y ∈ S : xK y}

and

Kx = [x]K ∩ Sij = {y ∈ Sij : xK y}.

We call [x]K (resp., Kx ) the K -class of x in S (resp., in Sij ). The next result is reminiscent of Green’s
Lemma, and may be proved in virtually identical fashion to [44, Lemma 2.2.1].
Lemma 2.7. Let x, y ∈ S.
(i) Suppose xRy, and that x = ya and y = xb where a, b ∈ S (1) . Then the maps [x]L → [y]L : w 7→ wb
and [y]L → [x]L : w 7→ wa are mutually inverse bijections. These maps restrict to mutually inverse
bijections [x]H → [y]H and [y]H → [x]H .
(ii) Suppose xL y, and that x = ay and y = bx where a, b ∈ S (1) . Then the maps [x]R → [y]R : w 7→ bw
and [y]R → [x]R : w 7→ aw are mutually inverse bijections. These maps restrict to mutually inverse
bijections [x]H → [y]H and [y]H → [x]H .
(iii) If xDy, then [x]R = [y]R , [x]L = [y]L and [x]H = [y]H .

2

Note that if x, y ∈ S are such that xH y, then λ(x) = λ(y) and ρ(x) = ρ(y). It follows that [x]H = Hx for
all x ∈ S.
Lemma 2.8. Let x, y ∈ Sij .
(i) Suppose xRy, and that x = ya and y = xb where a, b ∈ S (1) . Then the maps Lx → Ly : w 7→ wb and
Ly → Lx : w 7→ wa are mutually inverse bijections. These maps restrict to mutually inverse bijections
Hx → Hy and Hy → Hx .
5

(ii) Suppose xL y, and that x = ay and y = bx where a, b ∈ S (1) . Then the maps Rx → Ry : w 7→ bw and
Ry → Rx : w 7→ aw are mutually inverse bijections. These maps restrict to mutually inverse bijections
Hx → Hy and Hy → Hx .
(iii) If xDy, then |Rx | = |Ry |, |Lx | = |Ly | and |Hx | = |Hy |.
Proof. Suppose xRy, and that x = ya and y = xb where a, b ∈ S (1) . We first show that the map
f : Lx → S : w 7→ wb does indeed map Lx into Ly . With this in mind, let w ∈ Lx . We already know that
wb ∈ [y]L , by Lemma 2.7(i). Also, w = ux for some u ∈ S (1) , since wL x. Now, λ(wb) = λ(w) = i, and
also ρ(wb) = ρ(uxb) = ρ(uy) = ρ(y) = j, showing that wb ∈ [y]L ∩ Sij = Ly , as required. By symmetry, it
follows that g : Ly → S : w 7→ wa maps Ly into Lx . By Lemma 2.7(i), we see that f ◦ g and g ◦ f are the
identity maps on their respective domains. This completes the proof of (i).
Next, note that (ii) follows from (i) by duality. Now suppose xDy. So xRzL y for some z ∈ S. Since xRz,
it follows that λ(z) = λ(x) = i; similarly, ρ(z) = j, so in fact, z ∈ Sij . In particular, Rx = Rz and Ly = Lz .
The statement about cardinalities then follows from parts (i) and (ii).
2
As is the case for semigroups [40, 44], Lemma 2.6 means that the elements of a D-class D of S or Sij may
be grouped together in a rectangular array of cells, which (for continuity with semigroup theory) we call an
eggbox. We place all elements from D in a box in such a way that R-related (resp., L -related) elements are
in the same row (resp., column), and H -related elements in the same cell. An example is given in Figure 2
below for a D-class of the linear partial semigroup M(Z3 ).
We now come to the definition of the main objects of our study, the sandwich semigroups.
Definition 2.9. Let (S, ·, I, λ, ρ) be a partial semigroup. Fix some a ∈ Sji , where i, j ∈ I. Define a binary
operation ?a on Sij by x ?a y = xay for each x, y ∈ Sij . It is easily checked that ?a is associative. We
a = (S , ? ) the semigroup obtained in this way, and call S a the sandwich semigroup of S
denote by Sij
ij
ij a
ij
a = S a is the well-known variant [38, 39, 50] of S with respect
with respect to a. (Note that when i = j, Sij
i
i
to a ∈ Si .)
Recall that an element x of a semigroup T is regular if x = xyx and y = yxy for some y ∈ T (or, equivalently,
if x = xzx for some z ∈ T ). The set of all regular elements of T is denoted by Reg(T ), and we say T is
regular if T = Reg(T ). (In general, Reg(T ) need not even be a subsemigroup of T .) Of crucial importance is
that if any element of a D-class D of a semigroup T is regular, then every element of D is regular, in which
case every element of D is L -related to at least one idempotent (and also R-related to a possibly different
idempotent); the H -class He of an idempotent e ∈ E(T ) = {x ∈ T : x = x2 } is a group, and He ∼
= Hf for
any two D-related idempotents e, f ∈ E(T ). When drawing eggbox diagrams, group H -classes are usually
shaded grey (see for example Figure 3). See [40, 44] for more details.
a need not be regular themselves (alIf S is a regular partial semigroup, then the sandwich semigroups Sij
a
a forms a subsemigroup,
though all of the semigroups Si are), but the set Reg(Sij ) of all regular elements of Sij
as we now show.
a ) is a subsemigroup of S a
Proposition 2.10. Let (S, ·, I, λ, ρ) be a regular partial semigroup. Then Reg(Sij
ij
for all i, j ∈ I and a ∈ Sji .
a ), so x = xauax and y = yavay for some u, v ∈ S . Since S is regular, there
Proof. Let x, y ∈ Reg(Sij
ij
exists w ∈ S such that (auaxayava)w(auaxayava) = (auaxayava). Then

(xay)a(vawau)a(xay) = (xauaxay)a(vawau)a(xayavay)
= x(auaxayava)w(auaxayava)y = x(auaxayava)y = xay,
a ).
showing that (x ?a y) ? (v ?a w ?a u) ?a (x ?a y) = x ?a y, and x ?a y ∈ Reg(Sij

2

a , we
In order to say more about the regular elements and Green’s relations of the sandwich semigroup Sij
define the sets

P1a = {x ∈ Sij : xaRx},

P2a = {x ∈ Sij : axL x},
6

P3a = {x ∈ Sij : axaJ x},

P a = P1a ∩ P2a .

The next result explains the relationships that hold between these sets; the various inclusions are pictured
in Figure 1.

P1a

P2a

P1a

P2a

R

R

Pa

P a = P3a

P3a

Figure 1: Venn diagrams illustrating the various relationships between the sets P1a , P2a , P3a , P a = P1a ∩ P2a
a ) in the general case (left) and the stable case (right); for clarity, we have written R = Reg(S a ).
and Reg(Sij
ij

Proposition 2.11. Let (S, ·, I, λ, ρ) be a partial semigroup, and fix i, j ∈ I and a ∈ Sji . Then
a ) ⊆ P a ⊆ P a,
(i) Reg(Sij
3

(ii) P a = P3a if S is stable.

a ), then x = xayax for some y ∈ S , giving xRxa and xL ax, so that x ∈ P a ∩P a = P a .
Proof. If x ∈ Reg(Sij
ij
1
2
a
a
a
Next, suppose x ∈ P = P1 ∩ P2 , so x = xav = uax for some u, v ∈ S (1) . It follows that x = uaxav, so
xJ axa and x ∈ P3a . This completes the proof of (i).

Now suppose S is stable, and let x ∈ P3a . So x = uaxav for some u, v ∈ S (1) . It then follows that xJ xa
and xJ ax. By stability, it follows that xRxa and xL ax, so that x ∈ P1a ∩ P2a = P a , completing the proof
of (ii).
2
Remark 2.12. The assumption of regularity (resp., stability) could be greatly weakened in Proposition 2.10
(resp., Proposition 2.11(ii)). However, because the linear partial semigroup M is regular and stable (see
Lemmas 3.1 and 3.2), we will not pursue this thought any further.
We now show how the sets P1a , P2a , P3a and P a = P1a ∩ P2a may be used to relate Green’s relations on the
a to the corresponding relations on S. To avoid confusion, if K is one of R, L , J ,
sandwich semigroups Sij
a
a . So, for example, if x, y ∈ S , then
D, H , we write K for the Green’s K -relation on Sij
ij
• xR a y if and only if [x = y] or [x = y ?a u = yau and y = x ?a v = xav for some u, v ∈ Sij ].
It is then clear that R a ⊆ R, and the analogous statement is true for all of the other Green’s relations. If
a . Since K a ⊆ K , it follows that
x ∈ Sij , we write Kxa = {y ∈ Sij : xK a y} for the K a -class of x in Sij
a
Kx ⊆ Kx for all x ∈ Sij .
Theorem 2.13. Let (S, ·, I, λ, ρ) be a partial semigroup, and let a ∈ Sji where i, j ∈ I. If x ∈ Sij , then
(
Rx ∩ P1a
(i)
=
{x}
(
Lx ∩ P2a
(ii) Lax =
{x}
(
Hx
(iii) Hxa =
{x}
Rxa

if x ∈ P1a
if x ∈ Sij \ P1a ,
if x ∈ P2a
if x ∈ Sij \ P2a ,
if x ∈ P a
if x ∈ Sij \ P a ,



Dx ∩ P a



La
x
(iv) Dxa =

Rxa



{x}
(
Jx ∩ P3a
(v) Jxa =
Dxa
7

if
if
if
if

x ∈ Pa
x ∈ P2a \ P1a
x ∈ P1a \ P2a
x ∈ Sij \ (P1a ∪ P2a ),

if x ∈ P3a
if x ∈ Sij \ P3a .

a.
Further, if x ∈ Sij \ P a , then Hxa = {x} is a non-group H a -class of Sij

Proof. The proof of [19, Proposition 3.2] may easily be adapted to prove (i–iv) and the final statement
about H a -classes. We now prove (v). Let x ∈ Sij .
Suppose y ∈ Jxa \ {x}. So one of (a–c) and one of (d–f) holds:
(a) y = sax for some s ∈ Sij ,

(d) x = uay for some u ∈ Sij ,

(b) y = xat for some t ∈ Sij ,

(e) x = yav for some v ∈ Sij ,

(c) y = saxat for some s, t ∈ Sij ,

(f) x = uayav for some u, v ∈ Sij .

Suppose first that (a) and (d) hold. Then xL a y. Since x 6= y, we deduce that x ∈ P2a by (ii). Since
Lax = Lay , we also have y ∈ P2a . Similarly, if (b) and (e) hold, then xR a y and x, y ∈ P1a . One may check that
any other combination of (a–c) and (d–f) implies x, y ∈ P3a . For example, if (a) and (e) hold, then
y = sax = s(aya)v

and

x = yav = s(axa)v.

In particular, we have shown that |Jxa | ≥ 2 implies x ∈ P1a ∪ P2a ∪ P3a . By the contrapositive of this last
statement, if z ∈ Sij \ (P1a ∪ P2a ∪ P3a ), then Jza = {z} = Dza , with the last equality following from (iv).
Next, suppose x ∈ P1a \ P3a . In particular, x 6∈ P2a since P1a ∩ P2a ⊆ P3a by Proposition 2.11(i). Since
D a ⊆ J a , we have Dxa ⊆ Jxa . Conversely, suppose y ∈ Jxa . We must show that y ∈ Dxa . If y = x, then
we are done, so suppose y 6= x. As above, one of (a–c) and one of (d–f) holds. If (b) and (e) hold, then
y ∈ Rxa = Dxa , the second equality holding by (iv). If any other combination of (a–c) and (d–f) holds then, as
explained in the previous paragraph, x (and y) would belong to P2a or P3a , a contradiction. This completes
the proof that Jxa ⊆ Dxa . A dual argument shows that Jxa = Dxa if x ∈ P2a \ P3a .
Finally, suppose x ∈ P3a . Let z ∈ Jx ∩ P3a . So we have
x = s0 axat0 ,

z = s00 azat00 ,

z = u0 xv 0 ,

x = u00 zv 00

for some s0 , s00 , t0 , t00 , u0 , u00 , v 0 , v 00 ∈ S (1) .

We then calculate z = u0 xv 0 = u0 s0 axat0 v 0 = u0 s0 a(s0 axat0 )at0 v 0 = (u0 s0 as0 ) ?a x ?a (t0 at0 v 0 ), and similarly
x = (u00 s00 as00 ) ?a z ?a (t00 at00 v 00 ), showing that zJ a x, and Jx ∩ P3a ⊆ Jxa . To prove the reverse inclusion, since
we have already observed that Jxa ⊆ Jx , it suffices to show that Jxa ⊆ P3a . So suppose y ∈ Jxa . If y = x, then
y ∈ P3a , so suppose y 6= x. Then one of (a–c) and one of (d–f) above holds. If (a) and (d) hold, then
y = sax = sas0 axat0 = sas0 auayat0 ,
showing that y ∈ P3a . A similar argument covers the case in which (b) and (e) hold. As we observed above,
any other combination of (a–c) and (d–f) implies that y ∈ P3a . This completes the proof.
2
For a pictorial understanding of Theorem 2.13, Figures 4 and 5 below give eggbox diagrams of various linear
a.
sandwich semigroups.Next, we show that stability of S entails stability of all sandwich semigroups Sij
a is stable for all i, j ∈ I and
Proposition 2.14. Let (S, ·, I, λ, ρ) be a stable partial semigroup. Then Sij
a ∈ Sji .

Proof. Let x, y ∈ Sij . We must show that
xJ a x ?a y ⇔ xR a x ?a y

and

xJ a y ?a x ⇔ xL a y ?a x.

By duality, it suffices to prove the first of these. Clearly, xR a x ?a y ⇒ xJ a x ?a y. Conversely, suppose
xJ a x ?a y. Then one of the following holds:
(i) x = xay,

(iii) x = uaxay for some u ∈ Sij ,

(ii) x = xayav for some v ∈ Sij ,

(iv) x = uaxayav for some u, v ∈ Sij .
8

Clearly, (i) or (ii) implies xR aaxay. Next, suppose (iv) holds. Then xJ xaya, so that xRxaya by stability.
Clearly, (i) or (ii) implies xR xay. Next, suppose (iv) holds. Then xJ xaya, so that xRxaya by stability.
In particular, (a) x = xaya or (b) x = xayaw for some w 2 Sij . If (a) holds, then x = (xaya)aya, so (b)
In particular, (a) x = xaya or (b) x = xayaw for some w ∈ Sij . If (a) holds, then x = (xaya)aya, so (b)
holds with w = aya. In particular, x = (x ?a y) ?a w, completing the proof that xR aax ?a y. Finally, if (iii)
holds with w = aya. In particular, x = (x ?a y) ?a w, completing the proof that xR x ?a y. Finally, if (iii)
holds, then x = ua(uaxay)ay, so that case (iii) reduces to case (iv). The proof is therefore complete.
2
holds, then x = ua(uaxay)ay, so that case (iii) reduces to case (iv). The proof is therefore complete.
2
We conclude this section with a result that shows how regularity of the sandwich element implies close
We conclude this section with a result that shows how
regularity
of the sandwich element implies close
a and
b and certain
relationships between certain sandwich semigroups Sij
subsemigroups
a and S
b and certain (non-sandwich)
relationships between certain sandwich semigroups Sij
Sji
(non-sandwich) subsemigroups
ji
of Si and Sj .
of Si and Sj .
Theorem 2.15. Let (S, ·, I, , ⇢) be a partial semigroup and let i, j 2 I. Let a 2 Sji and b 2 Sij be such
Theorem 2.15. Let (S, ·, I, λ, ρ) be a partial semigroup and let i, j ∈ I. Let a ∈ Sji and b ∈ Sij be such
that a = aba and b = bab. Then
that a = aba and b = bab. Then
(i) Sij a and aSij are subsemigroups of Si and Sj (respectively),
(i) Sij a and aSij are subsemigroups of Si and Sj (respectively),
(ii) (aSij a, ?b ) and (bSji b, ?a ) are monoids with identities b and a (respectively), and are subsemigroups of
(ii) (aS
a, ?b )a and (bSji b, ?a ) are monoids with identities b and a (respectively), and are subsemigroups of
b ij
Sji
S a (respectively),
b and
Sji
and Sijij
(respectively),
(iii) the maps aSij a ! bSji b : x 7! bxb and bSji b ! aSij a : x 7! axa define mutually inverse isomorphisms
(iii) the maps aSij a → bSji b : x 7→ bxb and bSji b → aSij a : x 7→ axa define mutually inverse isomorphisms
between (aSij a, ?b ) and (bSji b, ?a ),
between (aSij a, ?b ) and (bSji b, ?a ),
a )a is contained in Reg(S b ),
(iv) a Reg(Sij
a )a is contained in Reg(Sji
b
(iv) a Reg(Sij
ji ),

(v) the following diagrams commute, with all maps being homomorphisms:
(v) the following diagrams commute, with all maps being homomorphisms:
(Sij , ?a )
1 :x7!xa

2 :x7!ax

(Sij a, ·)
1 :y7!ay

Reg(Sij , ?a )
1 :x7!xa

(aSij , ·)
(aSij a, ?b )

2 :x7!ax

Reg(Sij a, ·)

2 :y7!ya

1 :y7!ay

Reg(aSij , ·)
Reg(aSij a, ?b )

2 :y7!ya

aa ), so x = xauax
∈ Reg(Sij
Proof. Part (i) is clear, and parts (ii) and (iii) are easily checked. Next, suppose x 2
ij
for some u 2
∈ Sijij . Then axa = axauaxa = axabauabaxa = (axa) ?bb (aua) ?bb (axa), giving (iv). Part (v) is
all mostly easy to check. That Φ11 is a homomorphism follows from Φ11((xa)(ya)) = axaya = axabaya =
aa ) into Reg(S a). It follows from (iv) that φ maps
Φ11 (xa) ?bb Φ11 (ya). It is clear that ψ11 maps Reg(Sij
ij
ij
ij
11
bb ).
Reg(Sijija) into Reg(Sji
2
ji

Remark 2.16. Other relationships exist, such as (baSijija, ·) = (bSji
jiba, ·), but these will not be explored any
further.

3

The linear partial semigroup

A
As noted earlier, to understand the linear sandwich semigroups MA
mn, it is crucial to first understand the
mn
partial semigroup M. So in this section, we gather the required material on M, showing how the general
framework of Section 2 applies in this case.

∈ N = {1, 2, 3, . . .}, we write
We fix a field F for the remainder of the article. For positive integers m, n 2
=M
Mmn
(F) for
forthe
theset
setofofallallmm
n matrices
(i.e.,
matrices
with
m rows
n columns)
F.
Mmn
⇥×
n matrices
(i.e.,
all all
matrices
with
m rows
andand
n columns)
overover
F. We
mn =
mn(F)
S S
We write
= M(F)
M
for
the
set
of
all
(finite
dimensional,
non-empty)
matrices
over
F.
So
write
M =MM(F)
= =
M
for
the
set
of
all
(finite
dimensional)
matrices
over
F.
So
M
is
a
partial
mn
m,n∈Nmn
m,n2N
M is a partial
semigroup,
as noted
Example
2.5. we
By consider
convention,
wetoconsider
theremto
a unique
m×0
semigroup,
as noted
in Example
2.5.inBy
convention,
there
be a unique
⇥ 0beand
0 ⇥ n matrix
andany
0 ×m,
n nmatrix
for anythe
m, empty
n ≥ 0, matrix,
namely which
the empty
matrix,
wemn
denote
So0 M
for
0, namely
we denote
by which
;. So M
= {;}byif ∅.
m=
or mn
n ==0.{∅}
Butif
m =is0 aormatter
n = 0.ofBut
this is a matter
do not
consider
theanempty
matrix
∅ to
an
this
convenience,
and weofdoconvenience,
not considerand
the we
empty
matrix
; to be
element
of M.
Webealso
element
of
M.
We
also
write
M
=
M
(F)
=
M
for
any
n,
and
denote
by
G
=
G
(F)
the
group
of
n
×
n
write Mn = Mn (F) = Mnn fornany n,n and denote
nn by Gn = Gn (F) the group nof n ⇥
n n invertible matrices
9
9

invertible matrices over F. So Mn and Gn are the full linear monoid and general linear group of degree n.
For background on the full linear monoids, the monograph [74] is highly recommended.
If V and W are vector spaces, we write Hom(V, W ) for the set of all linear transformations from V to W .
As usual, if α ∈ Hom(V, W ), we write im(α) = {α(v) : v ∈ V } and ker(α) = {v ∈ V : α(v) = 0} for the
image and kernel of α. We write End(V ) = Hom(V, V ) for the monoid of all endomorphisms of V (i.e.,
all linear transformations V → V ), and Aut(V ) for the group of all automorphisms of V (i.e., all invertible
endomorphisms of V ). For n ≥ 0, we write Vn = Fn for the vector space of all n×1 column vectors over F. We
will identify Mmn with Hom(Vn , Vm ) in the usual way. Namely, if X ∈ Mmn , we write λX ∈ Hom(Vn , Vm )
for the linear transformation λX : Vn → Vm defined by λX (v) = Xv for all v ∈ Vn . We will often prove
statements about Mmn by proving the equivalent statement about Hom(Vn , Vm ). When m = n, the map
X → λX determines an isomorphism of monoids Mn → End(Vn ), and its restriction to Gn ⊆ Mn determines
an isomorphism of groups Gn → Aut(Vn ). We write {en1 , . . . , enn } for the standard basis of Vn (eni has a 1
in position i and 0’s elsewhere). We also write Wns = span{en1 , . . . , ens } for each 0 ≤ s ≤ n. (We interpret
span ∅ = {0}, though the dimension of the ambient space must be understood from context.)
Our first aim is to characterise Green’s relations (R, L , J , D, H ) and preorders (≤R , ≤L , ≤J ) on M.
Because M is monoidal (see Definition 2.1), M = M(1) . So, for example, if X, Y ∈ M are two matrices
(not necessarily of the same size), then X ≤R Y if and only if X = Y A for some A ∈ M. Note that if
X ≤R Y (resp., X ≤L Y ), then X and Y must have the same number of rows (resp., columns).
Let X ∈ Mmn . For 1 ≤ i ≤ m and 1 ≤ j ≤ n, we write ri (X) and cj (X) for the ith row and jth column
of X, respectively. We write Row(X) = span{r1 (X), . . . , rm (X)} and Col(X) = span{c1 (X), . . . , cn (X)} for
the row space and column space of X, respectively, and we write rank(X) = dim(Row(X)) = dim(Col(X))
for the rank of X. Because of the transpose map M → M : A 7→ AT , which is a bijection and satisfies
(AB)T = B T AT , the linear partial semigroup M is self-dual (in the sense that it is anti-isomorphic to its own
dual). Since Row(X T ) = Col(X), any statement about row spaces implies a corresponding dual statement
about column spaces (and vice versa). (Without causing confusion, we will often blur the distinction between
row vectors and column vectors, and think of Row(X) and Col(X) as subspaces of Fn and Fm , respectively.)
The next result characterises Green’s relations and preorders on M in terms of the parameters introduced
above. An equivalent formulation in the special case of square matrices may be found in [74, Lemma 2.1].
Lemma 3.1. Let X, Y ∈ M. Then
(i) X ≤R Y ⇔ Col(X) ⊆ Col(Y ),

(iv) XRY ⇔ Col(X) = Col(Y ),

(ii) X ≤L Y ⇔ Row(X) ⊆ Row(Y ),

(v) XL Y ⇔ Row(X) = Row(Y ),

(iii) X ≤J Y ⇔ rank(X) ⊆ rank(Y ),

(vi) XJ Y ⇔ rank(X) = rank(Y ).

ßFurther, M is stable, so J = D.
Proof. Clearly, (iv–vi) follow from (i–iii). Note that (ii) is the dual of (i), which is true because
X ≤R Y ⇔ X = Y A for some A ∈ M

⇔ every column of X is a linear combination of the columns of Y

⇔ Col(X) ⊆ Col(Y ).

For (iii), if X ≤J Y , then X = AY B for some A, B ∈ M, giving rank(X) = rank(AY B) ≤ rank(Y ).
Conversely, suppose rank(X) ≤ rank(Y ), and say X ∈ Mmn and Y ∈ Mkl . It is sufficient to show
that λX = α ◦ λY ◦ β for some α ∈ Hom(Vk , Vm ) and β ∈ Hom(Vn , Vl ). Put r = rank(X) and s =
rank(Y ). Choose bases B1 = {u1 , . . . , un } and B2 = {v1 , . . . , vl } for Vn and Vl so that {ur+1 , . . . , un } and
{vs+1 , . . . , vl } are bases for ker(λX ) and ker(λY ), respectively. Extend (if necessary) the linearly independent
sets {λY (v1 ), . . . , λY (vr )} and {λX (u1 , . . . , λX (ur )} arbitrarily to bases
B3 = {λY (v1 ), . . . , λY (vr ), wr+1 , . . . , wk }

and

10

B4 = {λX (u1 ), . . . , λX (ur ), xr+1 , . . . , xm }

for Vk and Vm . Now let α ∈ Hom(Vk , Vm ) and β ∈ Hom(Vn , Vl ) be chosen arbitrarily so that
α(λY (vi )) = λX (ui ),
β(ui ) = vi ,

α(wj ) ∈ span{xr+1 , . . . , xm }
β(uj ) ∈ span{vs+1 , . . . , vl }

for all 1 ≤ i ≤ r and r + 1 ≤ j ≤ k,
for all 1 ≤ i ≤ r and r + 1 ≤ j ≤ n.

One easily checks that α ◦ λY ◦ β = λX , by checking the respective actions on the basis B1 of Vn .
To prove stability, we must show that for all X, Y ∈ M,
XJ XY ⇔ XRXY

and

XJ Y X ⇔ XL Y X.

By duality, it suffices to prove the first equivalence. Since R ⊆ J , it is enough to prove that XJ XY ⇒
XRXY . Now, Col(XY ) ⊆ Col(X). But also XJ XY gives dim(Col(X)) = rank(X) = rank(XY ) =
dim(Col(XY )), so that Col(X) = Col(XY ), whence XRXY .
2
As we saw in Section 2, stability and regularity are very useful properties for a partial semigroup to have.
Now that we know M is stable, let us show that M is also regular.
Lemma 3.2. The linear partial semigroup M is regular.
Proof. Let X ∈ Mmn . It suffices to show that there exists α ∈ Hom(Vm , Vn ) such that λX = λX ◦ α ◦ λX .
Let B = {v1 , . . . , vn } be a basis of Vn such that {vr+1 , . . . , vn } is a basis of ker(λX ). Extend (if necessary)
the linearly independent set {λX (v1 ), . . . , λX (vr )} to a basis {λX (v1 ), . . . , λX (vr ), wr+1 , . . . , wm } of Vm . Let
α ∈ Hom(Vm , Vn ) be any linear transformation for which α(λX (vi )) = vi for each 1 ≤ i ≤ r. Then one easily
checks that λX = λX ◦ α ◦ λX by calculating the action on the basis B.
2
As in Section 2, if X ∈ Mmn and K is one of R, L , J , D, H , we write KX = {Y ∈ Mmn : XK Y }, and
call KX the K -class of X in Mmn . Note that all matrices from KX have the same dimensions. (We will
have no need to consider the sets [X]K of all matrices K -related to X.) Recall that Gk denotes the group
of all invertible k × k matrices over F. The next result gives an alternative description of various Green’s
classes in M.
Lemma 3.3. Let X ∈ Mmn . Then
(i) RX = {Y ∈ Mmn : Col(X) = Col(Y )} = XGn ,
(ii) LX = {Y ∈ Mmn : Row(X) = Row(Y )} = Gm X,
(iii) DX = JX = {Y ∈ Mmn : rank(X) = rank(Y )} = Gm XGn .
Proof. For (i), note that clearly XGn ⊆ RX . By Lemma 3.1, it remains to show the reverse inclusion,
so suppose Y ∈ RX . In particular, XJ Y , so rank(X) = rank(Y ). Put r = rank(X). We show that
λY = λX ◦ α for some α ∈ Aut(Vn ). Since XRY , we already know that λY = λX ◦ β for some β ∈
End(Vn ). Let B1 = {u1 , . . . , un } be a basis of Vn such that {ur+1 , . . . , un } is a basis of ker(λY ). So
{λX (β(u1 )), . . . , λX (β(ur ))} = {λY (u1 ), . . . , λY (ur )} is a basis of im(λY ). It follows that {β(u1 ), . . . , β(ur )}
is linearly independent. We may therefore extend this set to a basis B2 = {β(u1 ), . . . , β(ur ), vr+1 , . . . , vn }
of Vn , where {vr+1 , . . . , vn } is a basis of ker(λX ). Now define α ∈ Aut(Vn ) by
(
β(ui ) if 1 ≤ i ≤ r
α(ui ) =
vi
if r < i ≤ n.
One easily checks that λY = λX ◦ α. This completes the proof of (i).
Part (ii) is dual to (i). For (iii), clearly Gm XGn ⊆ JX , and the converse follows quickly from (i) and (ii) and
the fact that J = D = L ◦ R. By Lemma 3.1, this completes the proof.
2
If K is one of R, L , D = J , then the set Mmn /K of all K -classes of Mmn inherits a partial order:
KX ≤K KY ⇔ X ≤K Y.
11

We typically write ≤ for the order ≤J on the D = J -classes. Of importance is the fact that these classes
form a chain:
D0 (Mmn ) < D1 (Mmn ) < · · · < Dl (Mmn ),
where Ds (Mmn ) = {X ∈ Mmn : rank(X) = s} for all 0 ≤ s ≤ l = min(m, n).
Figure 2 pictures an eggbox diagram (as explained in Section 2) of the D-class D1 (M23 (Z3 )) of all 2 × 3
matrices of rank 1 over the field F = Z3 = {0, 1, 2} (see Lemma 3.4 for an explanation of the number
and sizes of the R-, L - and H -classes). The reader need not yet worry about the subdivisions within
the eggbox; for now, it is enough to note that the matrices to the left (resp., top) of the vertical (resp.,
horizontal) divider satisfy the property that the first column (resp., row) spans the column space (resp., row
space) of the matrix.
6⊆ P1

⊆ P1

[ 10 00 00 ] [ 10 00 10 ] [ 10 00 20 ] [ 10 10 00 ] [ 10 10 10 ] [ 10 10 20 ] [ 10 20 00 ] [ 10 20 10 ] [ 10 20 20 ] [ 00 10 00 ] [ 00 10 10 ] [ 00 10 20 ] [ 00 00 10 ]
[ 20 00 00 ] [ 20 00 20 ] [ 20 00 10 ] [ 20 20 00 ] [ 20 20 20 ] [ 20 20 10 ] [ 20 10 00 ] [ 20 10 20 ] [ 20 10 10 ] [ 00 20 00 ] [ 00 20 20 ] [ 00 20 10 ] [ 00 00 20 ]

⊆ P2

[ 11 00 00 ] [ 11 00 11 ] [ 11 00 22 ] [ 11 11 00 ] [ 11 11 11 ] [ 11 11 22 ] [ 11 22 00 ] [ 11 22 11 ] [ 11 22 22 ] [ 00 11 00 ] [ 00 11 11 ] [ 00 11 22 ] [ 00 00 11 ]
[ 22 00 00 ] [ 22 00 22 ] [ 22 00 11 ] [ 22 22 00 ] [ 22 22 22 ] [ 22 22 11 ] [ 22 11 00 ] [ 22 11 22 ] [ 22 11 11 ] [ 00 22 00 ] [ 00 22 22 ] [ 00 22 11 ] [ 00 00 22 ]
[ 12 00 00 ] [ 12 00 12 ] [ 12 00 21 ] [ 12 12 00 ] [ 12 12 12 ] [ 12 12 21 ] [ 12 21 00 ] [ 12 21 12 ] [ 12 21 21 ] [ 00 12 00 ] [ 00 12 12 ] [ 00 12 21 ] [ 00 00 12 ]
[ 21 00 00 ] [ 21 00 21 ] [ 21 00 12 ] [ 21 21 00 ] [ 21 21 21 ] [ 21 21 12 ] [ 21 12 00 ] [ 21 12 21 ] [ 21 12 12 ] [ 00 21 00 ] [ 00 21 21 ] [ 00 21 12 ] [ 00 00 21 ]

6⊆ P2

[ 01 00 00 ] [ 01 00 01 ] [ 01 00 02 ] [ 01 01 00 ] [ 01 01 01 ] [ 01 01 02 ] [ 01 02 00 ] [ 01 02 01 ] [ 01 02 02 ] [ 00 01 00 ] [ 00 01 01 ] [ 00 01 02 ] [ 00 00 01 ]
[ 02 00 00 ] [ 02 00 02 ] [ 02 00 01 ] [ 02 02 00 ] [ 02 02 02 ] [ 02 02 01 ] [ 02 01 00 ] [ 02 01 02 ] [ 02 01 01 ] [ 00 02 00 ] [ 00 02 02 ] [ 00 02 01 ] [ 00 00 02 ]

Figure 2: An eggbox diagram of the D-class D1 (M23 (Z3 )).
So Mmn has min(m, n)+1 D-classes. It will also be convenient to have some more combinatorial information
about the number and size of certain K -classes. Recall that the q-factorials and q-binomial coefficients are
defined by
(q − 1)(q 2 − 1) · · · (q s − 1)
[s]q ! = 1 · (1 + q) · · · (1 + q + · · · + q s−1 ) =
(q − 1)s

and

 
[m]q !
(q m − 1)(q m − q) · · · (q m − q s−1 )
(q m − 1)(q m−1 − 1) · · · (q m−s+1 − 1)
m
=
=
=
.
s q
[s]q ![m − s]q !
(q s − 1)(q s − q) · · · (q s − q s−1 )
(q s − 1)(q s−1 − 1) · · · (q − 1)
It is easy to check (and well-known) that when |F| = q < ∞,
s

|Gs | = (q s − 1)(q s − q) · · · (q s − q s−1 ) = q (2) (q − 1)s [s]q !.
In what follows, a crucial role will be played by the matrices Jmns ∈ Mmn defined for s ≤ min(m, n) by


Is
Os,n−s
Jmns =
.
Om−s,s Om−s,n−s
Here and elsewhere, we write Is and Okl for the s × s identity matrix and k × l zero matrix (respectively). If
the dimensions are understood from context, we just write O = Okl . So Jmns is the m × n matrix with 1’s in
the first s positions on the leading diagonal and 0’s elsewhere. Note that if s = m ≤ n (resp., s = n ≤ m),
then the
i Om−s,s and Om−s,n−s (resp., Os,n−s and Om−s,n−s ) are empty, and Jmns = [Is Os,n−s ]
h matrices
(resp.,

Is
Om−s,s

).

Lemma 3.4. Suppose |F| = q < ∞, and let 0 ≤ s ≤ min(m, n). Then
(i) Ds (Mmn ) contains [ m
s ]q R-classes,
12

(ii) Ds (Mmn ) contains [ ns ]q L -classes,
s

n
s
()
(iii) Ds (Mmn ) contains [ m
s ]q [ s ]q H -classes, each of which has size |Gs | = q 2 (q − 1) [s]q !,
s

n
s
()
(iv) |Ds (Mmn )| = [ m
s ]q [ s ]q q 2 (q − 1) [s]q !.

Proof. Parts (i) and (ii) follow immediately from parts (i) and (ii) of Lemma 3.3 and the well-known fact
that [ m
s ]q is the number of s dimensional subspaces of an m dimensional vector space over F. The number of
H -classes follows immediately from (i) and (ii). By Lemma 2.8, all the
 H -classes in Ds (Mmn ) have the same
A
B
size, so it suffices to calculate the size of H = HJmns . Let X = C D ∈ H, where A ∈ Ms , B ∈ Ms,n−s , and
so on. Since Row(X) = Row(Jmns ), we see that B and
 AD
are zero matrices. Considering column spaces, we
O
see that C is also a zero matrix. It follows
that X = O O , and also rank(A) = rank(X) = rank(Jmns ) = s.

A O with rank(A) = s belongs to H. The condition that rank(A) = s is
Clearly every such matrix X = O
O
equivalent to A ∈ Gs , so it follows that |H| = |Gs |. Finally, (iv) follows from (iii).
2
Of course, by considering the size of Mmn when |F| = q < ∞, we obtain the identity
l    
X
s
m
n
mn
q
=
[s]q !(q − 1)s q (2) .
s q s q
s=0

We conclude this section by stating some well-known results on the full linear monoids Mn and their
ideals that we will require in what follows. The set E(Mn ) = {X ∈ Mn : X = X 2 } of idempotents
of Mn is not a subsemigroup (unless n ≤ 1), but the subsemigroup En = hE(Mn )i of Mn generated by
these idempotents has a neat description. Namely, it was shown by Erdos [25] that any singular (i.e.,
non-invertible) matrix over F is a product of idempotent matrices. This result has been reproved by a
number of authors [2, 15, 18, 27, 53]. The minimal number of (idempotent) matrices required to generate En
was determined by Dawlings [16]. Recall that the rank (resp., idempotent rank ) of a semigroup (resp.,
idempotent generated semigroup) S, denoted rank(S) (resp., idrank(S)), is the minimal size of a generating
set (resp., idempotent generating set) for S. (The rank of a semigroup should not be confused with the rank
of a matix.) If U is a subset of a semigroup S, we write E(U ) = E(S) ∩ U for the set of all idempotents
from U .
Theorem 3.5 (Erdos [25], Dawlings [15, 16]). We have
En = hE(Mn )i = (Mn \ Gn ) ∪ {In }

and

Mn \ Gn = hE(Dn−1 (Mn ))i.

Further, if |F| = q < ∞, then

rank(Mn \ Gn ) = idrank(Mn \ Gn ) = (q n − 1)/(q − 1).

2

The previous result has been extended by Gray [33] to arbitrary ideals of Mn .
Theorem 3.6 (Gray [33]). The ideals of Mn are precisely the sets
Is (Mn ) = D0 (Mn ) ∪ · · · ∪ Ds (Mn ) = {X ∈ Mn : rank(X) ≤ s}

for 0 ≤ s ≤ n,

and they form a chain: I0 (Mn ) ⊆ · · · ⊆ In (Mn ). If 0 ≤ s < n, then Is (Mn ) = hE(Ds (Mn ))i is generated
by the idempotents in its top D-class. Further, if |F| = q < ∞, then
 
n
rank(Is (Mn )) = idrank(Is (Mn )) =
.
2
s q
Note that In (Mn ) = Mn , Dn (Mn ) = Gn and In−1 (Mn ) = Mn \ Gn , so Theorem 3.5 is a special case of
n
Theorem 3.6 since [ n−1
]q = (q n − 1)/(q − 1).
On several occasions, we will need to make use of the fact that the general linear group Gn may be generated
by two matrices, as was originally proved by Waterhouse [94]; see also [31], where minimal generating sets
for Gn are explored in more detail. Probabilistic generation of matrix groups is considered in [4, 36], for
example, though the context is usually for classical groups.
13

Theorem 3.7 (Waterhouse [94]). If |F| < ∞, then
(i) rank(G1 ) = 1, and rank(Gn ) = 2 if n ≥ 2,
(ii) Mn = hGn ∪ {X}i for any X ∈ Dn−1 (Mn ),
(iii) rank(M1 ) = 2, and rank(Mn ) = 3 if n ≥ 2.

2

For convenience, eggbox diagrams are given for the full linear monoids Mn (Z2 ) for 0 ≤ n ≤ 3 in Figure 3
below. In the diagrams, group H -classes are shaded grey, and a label of k indicates that the group H -class
is isomorphic to Gk (Z2 ).
3

2

2
2

2

2
2

2
2

2
2
2

2

2

2

2

2

2

2

2

2

2

2

2

2

2
2

2

2

2
1

1
1

1

1

1

1
1

1
1

1

1

1

1

1

1

1
1

0

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1
1

1

1

0

Figure 3: Egg box diagrams of the full linear semigroups M0 , M1 , M2 , M3 , all over Z2 (left to right).

4

Linear sandwich semigroups

Now that we have gathered the required material on M, we may begin our study of the linear sandwich
semigroups. From now on, we fix integers m, n ≥ 1 and an n × m matrix A ∈ Mnm . As in Section 2, we
denote by
A
MA
mn = Mmn (F) = (Mmn , ?A )

the sandwich semigroup of Mmn under the operation ?A defined by

for X, Y ∈ Mmn .

X ?A Y = XAY

A
We note that if m = n, then MA
mn = Mn is a variant [38] of the full linear monoid Mn , so everything
we prove about linear sandwich semigroups holds for such linear variants also. We begin with a simple
observation.

Lemma 4.1.

∼ AT
(i) If A ∈ Mnm , then MA
mn = Mnm .

∼ B
(ii) If A, B ∈ Mnm are such that rank(A) = rank(B), then MA
mn = Mmn .
T

A
Proof. It clear that X 7→ X T defines an isomorphism MA
mn → Mnm , giving (i). Next, if rank(A) =
rank(B), Lemma 3.3 gives A = U BV for some U ∈ Gm and V ∈ Gn . But then one may check that
B
X 7→ V XU defines an isomorphism MA
2
mn → Mmn , giving (ii).

In particular, when studying the semigroup MA
mn where rank(A) = r, we may choose any A ∈ Mnm of
rank r. For the rest of the article, we will therefore study the semigroup MJmn , where


Ir
Or,m−r
J = Jnmr =
∈ Mnm .
On−r,r On−r,m−r
14

From now on, unless
specified, whenever a k × l matrix X (with k, l ∈ {m, n}) is written in 2 × 2
 A Botherwise

block form, X = C
,
we
will
be tacitly assuming that A ∈ Mr (from
D
 which the dimensions of B, C, D
I
O
may be deduced). So for example, we will usually just write J = O O . For simplicity, we will write ? for
the operation ?J on MJmn , throughout. One easily verifies the rule

 
 

A B
E F
AE AF
?
=
.
C D
G H
CE CF
A B
Also note that if X = C
D , then






A O
A B
A O
XJ =
∈ Mm , JX =
∈ Mn , JXJ =
∈ Mnm .
C O
O O
O O
Remark 4.2. In the special case that r = m ≤ n, we have J = [I O], and the product in MJmn satisfies
[A B] ? [E F ] = [AE AF ]. But we just view this as a special case of the above rule, with the bottom
rows — i.e., [C D], [G H], [CE CF ] — containing empty blocks. A dual statement holds in the case
r = n ≤ m. In only one place will we need to consider the case in which r = min(m, n) separately (see
Theorems 4.12 and 4.14). If r = m = n, then MJmn is precisely the full linear monoid Mn ; since all
the problems we investigate have already been solved for Mn , we will typically assume that r = m = n
does not hold, though our results are true for the case r < m = n (corresponding to variants of the full
linear monoids Mn ). See Remark 5.3, where the above observations are used to show that the sandwich
semigroups MJmn are isomorphic to certain well-known (non-sandwich) matrix semigroups in the case that
r = min(m, n).
Green’s relations and the regular elements of the sandwich semigroup MJmn were calculated in [9, 49]. We
now show how these results may be recovered (and given a cleaner presentation) using the general theory
developed in Section 2. In particular, a crucial role is played by the sets
P1J = {X ∈ Mmn : XJRX}, P2J = {X ∈ Mmn : JXL X}, P3J = {X ∈ Mmn : JXJJ X}, P J = P1J ∩P2J .
For simplicity, we denote these sets simply by P1 , P2 , P3 , and P = P1 ∩ P2 .
Certain special matrices from Mmn will be very important in what follows. With this in mind, if A ∈ Mr ,
M ∈ Mm−r,r and N ∈ Mr,n−r , we write


A
AN
∈ Mmn .
[M, A, N ] =
M A M AN
One may check that when matrices of this form are multiplied in MJmn , they obey the rule
[M, A, N ] ? [K, B, L] = [M, AB, L].
Proposition 4.3.


(i) P1 = {X ∈ Mmn : rank(XJ) = rank(X)} = X ∈ Mmn : Col(XJ) = Col(X) ,

(ii) P2 = {X ∈ Mmn : rank(JX) = rank(X)} = X ∈ Mmn : Row(JX) = Row(X) ,

(iii) P3 = P = {X ∈ Mmn : rank(JXJ) = rank(X)}

= [M, A, N ] : A ∈ Mr , M ∈ Mm−r,r , N ∈ Mr,n−r ,

(iv) P = Reg(MJmn ) is the set of all regular elements of MJmn , and is a subsemigroup of MJmn .

Proof. Parts (i) and (ii) follow quickly from Lemma 3.1 (making crucial use of stability). We now prove (iii).
Since M is stable,
 A B Proposition 2.11 and Lemma 3.3 give P3 = P = {X ∈ Mmn : rank(JXJ) = rank(X)}.
Now let X = C D ∈ Mmn . First, note that
A B
X ∈ P2 ⇔ Row(X) = Row(JX) = Row O
O
⇔ each row of [C D] is a linear combination of the rows of [A B]
⇔ [C D] = M [A B] = [M A M B] for some M ∈ Mm−r,r .
15

Similarly,
   


B
A
AN
X ∈ P1 ⇔
=
N=
for some N ∈ Mr,n−r .
D
C
CN


Putting these together, we see that X ∈ P = P1 ∩ P2 if and only if P = MAA MAN
AN = [M, A, N ], completing
the proof of (iii).
For (iv), Proposition 2.11 gives Reg(MJmn ) ⊆ P . Conversely, suppose X = [M, A, N ] ∈ P . If B ∈ Mr is
B C for any
such that A = ABA (see Lemma 3.2), then it is easy to check that X = X ? Y ? X where Y = D
E
(appropriately sized) C, D, E, completing the proof that P = Reg(MJmn ). The fact that P is a subsemigroup
follows immediately from Proposition 2.10 and Lemma 3.2 (or directly from the rule [M, A, N ] ? [K, B, L] =
[M, AB, L]).
2
Remark 4.4. Part (iv) of the previous proposition also follows from [9, Theorem 2.1], but the rest of
Proposition 4.3 appears to be new.
Now that we have described the sets P1 , P2 , P3 = P = P1 ∩ P2 , we may characterise Green’s relations
on MJmn . As in Section 2, if K is one of R, L , H , D, J , we will write K J for the Green’s K -relation
on MJmn . Since MJmn is not a monoid in general, these relations are defined, for X, Y ∈ Mmn , by
• XR J Y ⇔ [X = Y ] or [X = Y ? U and Y = X ? V for some U, V ∈ Mmn ],
and so on. Since M is stable, so too is MJmn , so we have J J = D J (see Proposition 2.14 and Lemmas 2.6
and 3.1). We will continue to write R, L , H , D, J for the relations on M defined in Section 3. As in
Section 2, if K is one of R, L , H , D = J , and if X ∈ Mmn , we will write
KX = {Y ∈ Mmn : XK Y }

and

J
KX
= {Y ∈ Mmn : XK J Y }

for the K -class and K J -class of X in Mmn , respectively. As noted in Section 2, K J ⊆ K for each K ,
J ⊆ K for each X. The next result follows immediately from Theorem 2.13. It also follows from
and so KX
X
Theorem 2.3, Lemma 2.4, and Corollaries 2.5–2.8 of [9], but we prefer the current succinct description.
Theorem 4.5. If X ∈ Mmn , then
(
RX ∩ P1 if X ∈ P1
J
(i) RX =
{X}
if X ∈ Mmn \ P1 ,

(ii) LJX

(
LX ∩ P2
=
{X}

if X ∈ P2
if X ∈ Mmn \ P2 ,

(iii)

J
HX

J
(iv) DX

(
HX
=
{X}


DX ∩ P



LJ
X
=
J

R

X


{X}

if X ∈ P
if X ∈ Mmn \ P ,
if
if
if
if

X
X
X
X

∈P
∈ P2 \ P1
∈ P1 \ P2
∈ Mmn \ (P1 ∪ P2 ).

The sets P1 , P2 are described in Proposition 4.3, and the sets RX , LX , HX , DX in Proposition 3.3. In
J = LJ = H J = D J = {X} if rank(X) > r. If X ∈ M
J
particular, RX
mn \ P , then HX = {X} is a non-group
X
X
X
J
J
H -class of Mmn .
2
Eggbox diagrams of some linear sandwich semigroups are given in Figures 4 and 5. As usual, grey boxes
indicate group H J -classes; a label of k on such a group H J -class indicates isomorphism to Gk . Note that
the bottom diagram from Figure 4 is of a variant of M3 (Z2 ) = M33 (Z2 ). The diagrams in the pdf version
of this article may be zoomed in a long way. The authors may be contacted for more such pictures.
Theorem 4.5 yields an intuitive picture of the internal structure of MJmn . Recall that the D-classes of Mmn
are the sets Ds (Mmn ) = {X ∈ Mmn : rank(X) = s} for 0 ≤ s ≤ l = min(m, n). If r < l, then each of
the D-classes Dr+1 (Mmn ), . . . , Dl (Mmn ) separates completely into singleton D J -classes in MJmn . (We will
study these classes in more detail shortly.) Next, note that D0 (Mmn ) = {O} ⊆ P (as the zero matrix
clearly belongs to both P1 and P2 ), so D0 (Mmn ) remains a (regular) D J -class of MJmn . Now fix some
16

1

1

1

1

1

1

1

1

0

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

Figure 4: Egg box diagrams of the linear sandwich semigroups MJ32231 (Z2 ) and MJ33332 (Z2 ) (top and bottom,
respectively).

1 ≤ s ≤ r. The D-class Ds (Mmn ) is split into a single regular D J -class, namely Ds (Mmn ) ∩ P , and a
number of non-regular D J -classes. Some of these non-regular D J -classes are singletons, namely those of the
J = {X} where X ∈ D (M
J
form DX
s
mn ) belongs to neither P1 nor P2 . Some of the non-regular D -classes
J
J
J
consist of one non-singleton L -class, namely those of the form DX = LX = LX ∩ P2 , where X ∈ Ds (Mmn )
belongs to P2 \ P1 ; the H J -classes contained in such a D J -class are all singletons. The remaining nonregular D J -classes contained in Ds (Mmn ) consist of one non-singleton R J -class, namely those of the form
J
J
J = RJ = R ∩ P , where X ∈ D (M
DX
1
s
mn ) belongs to P1 \ P2 ; the H -classes contained in such a D -class
X
X
are all singletons.
h 1 0 i This is all pictured in Figure 6 for the D-class D1 (M23 ) where F = Z3 = {0, 1, 2} and
J = J321 = 0 0 ; cf. Figure 2.
00

It will be important to have a description of the partial order ≤ on the D J -classes of MJmn .

J ≤ D J in MJ
Proposition 4.6. Let X, Y ∈ Mmn . Then DX
mn if and only if one of the following holds:
Y

(i) X = Y ,

(iii) Row(X) ⊆ Row(JY ),

(ii) rank(X) ≤ rank(JY J),

(iv) Col(X) ⊆ Col(Y J).

J ≤ D J if and only if one of the following holds:
Proof. Note that DX
Y

(a) X = Y ,

(c) X = U JY for some U ∈ Mmn ,

(b) X = U JY JV for some U, V ∈ Mmn ,

(d) X = Y JV for some V ∈ Mmn .

The equivalences (b) ⇔ (ii), (c) ⇔ (iii), and (d) ⇔ (iv) all follow from Lemma 3.1.

2

The description of the order on D J -classes of MJmn from Proposition 4.6 may be simplified in the case that
one of X, Y is regular.
17

2

2

2

2

2

2

2

1

1

1

1

1

1

1

1

2

2

2

2

1

1

1

1

1

1

1

1

2

2

2

2

1

1

1

1

1

1

1

1

2

2

2
2
2

1

1

1

1
1

1

1

1

1

1

1

1

0

0

Figure 5: Egg box diagrams of the linear sandwich semigroups MJ32232 (Z2 ) and MJ24422 (Z2 ) (left and right,
respectively).
6⊆ P1

⊆ P1

[ 02 01 01 ]

[ 01 02 02 ]

[ 02 01 02 ]

[ 01 02 01 ]

[ 02 01 00 ]

[ 01 02 00 ]

[ 02 02 01 ]

[ 00 21 00 ] [ 00 21 21 ] [ 00 21 12 ] [ 00 00 21 ]

[ 01 01 02 ]

[ 21 00 00 ] [ 21 00 21 ] [ 21 00 12 ] [ 21 21 00 ] [ 21 21 21 ] [ 21 21 12 ] [ 21 12 00 ] [ 21 12 21 ] [ 21 12 12 ]

[ 02 02 02 ]

[ 00 12 00 ] [ 00 12 12 ] [ 00 12 21 ] [ 00 00 12 ]

[ 01 01 01 ]

[ 12 00 00 ] [ 12 00 12 ] [ 12 00 21 ] [ 12 12 00 ] [ 12 12 12 ] [ 12 12 21 ] [ 12 21 00 ] [ 12 21 12 ] [ 12 21 21 ]

[ 02 02 00 ]

[ 00 22 00 ] [ 00 22 22 ] [ 00 22 11 ] [ 00 00 22 ]

[ 01 01 00 ]

[ 22 00 00 ] [ 22 00 22 ] [ 22 00 11 ] [ 22 22 00 ] [ 22 22 22 ] [ 22 22 11 ] [ 22 11 00 ] [ 22 11 22 ] [ 22 11 11 ]

[ 02 00 01 ]

[ 00 11 00 ] [ 00 11 11 ] [ 00 11 22 ] [ 00 00 11 ]

[ 01 00 02 ]

[ 11 00 00 ] [ 11 00 11 ] [ 11 00 22 ] [ 11 11 00 ] [ 11 11 11 ] [ 11 11 22 ] [ 11 22 00 ] [ 11 22 11 ] [ 11 22 22 ]

[ 02 00 02 ]

[ 00 20 00 ] [ 00 20 20 ] [ 00 20 10 ] [ 00 00 20 ]

[ 01 00 01 ]

[ 20 00 00 ] [ 20 00 20 ] [ 20 00 10 ] [ 20 20 00 ] [ 20 20 20 ] [ 20 20 10 ] [ 20 10 00 ] [ 20 10 20 ] [ 20 10 10 ]

[ 02 00 00 ]

6⊆ P2

[ 00 10 00 ] [ 00 10 10 ] [ 00 10 20 ] [ 00 00 10 ]

[ 01 00 00 ]

⊆ P2

[ 10 00 00 ] [ 10 00 10 ] [ 10 00 20 ] [ 10 10 00 ] [ 10 10 10 ] [ 10 10 20 ] [ 10 20 00 ] [ 10 20 10 ] [ 10 20 20 ]

[ 00 01 00 ] [ 00 01 01 ] [ 00 01 02 ] [ 00 00 01 ]
[ 00 02 00 ] [ 00 02 02 ] [ 00 02 01 ] [ 00 00 02 ]

Figure 6: A D-class D1 (M23 (Z3 )) breaks up into D J -classes in MJ23 (Z3 ), where J = J321 . Group H J -classes
are shaded grey; the idempotent of such a group is the upper of the two matrices. (cf. Figure 2.)

Proposition 4.7. Let X, Y ∈ Mmn .
J ≤ D J ⇔ rank(X) ≤ rank(JY J).
(i) If X ∈ P , then DX
Y
J ≤ D J ⇔ rank(X) ≤ rank(Y ).
(ii) If Y ∈ P , then DX
Y

The regular D J -classes of MJmn form a chain: D0J < · · · < DrJ , where
DsJ = Ds (Mmn ) ∩ P = {X ∈ P : rank(X) = s}

for each 0 ≤ s ≤ r.

J ≤ D J if and only if one of (a–d) holds. Suppose first
Proof. As in the proof of Proposition 4.6, DX
Y
that X ∈ P , so X = XJZJX for some Z ∈ Mmn . Then (a) implies X = XJZ(JY J)ZJX, (c) implies
X = U (JY J)ZJX, and (d) implies X = XJZ(JY J)V . So, in each of cases (a–d), we deduce that
J ≤ D J implies rank(X) ≤ rank(Y JY ). Proposition 4.6 gives the reverse
rank(X) ≤ rank(JY J). So DX
Y
implication.

Next, suppose Y ∈ P . Now, each of (a–d) implies rank(X) ≤ rank(Y ). Conversely, if rank(X) ≤ rank(Y ),
J ≤ D J , since rank(Y ) = rank(JY J). The statement about regular D J -classes
then Proposition 4.6 gives DX
Y
follows quickly from (ii).
2
The linear ordering on the regular D J -classes may be seen by inspecting Figures 4 and 5; see also Figure 8.
18

As an immediate consequence of Proposition 4.7, we may classify the isomorphism classes of sandwich
semigroups on the set Mmn ; the m = n case of the next result was proved in [48].
∼ B
Corollary 4.8. Let A, B ∈ Mnm . Then MA
mn = Mmn if and only if rank(A) = rank(B).
Jnmr and
∼
Proof. Put r = rank(A) and s = rank(B). By Proposition 4.7 and Lemma 4.1(ii), MA
mn = Mmn
Jnms
A
B
A ∼
B
∼
MB
mn = Mmn have r + 1 and s + 1 regular D - and D -classes, respectively. So Mmn = Mmn implies
r = s. The converse was proved in Lemma 4.1(ii).
2

B
∼
Remark 4.9. It is possible to have MA
mn = Mkl even if (m, n) 6= (k, l), although we would of course still
need rank(A) = rank(B) by Proposition 4.7. For example, if O = Onm is the n × m zero matrix, then MO
mn
O
is a zero semigroup (X ? Y = Omn for all X, Y ∈ Mmn ). Two such zero semigroups MO
mn and Mkl are
isomorphic if and only if they have the same cardinality; that is, if and only if F is infinite or F is finite and
B
mn = kl. We will return to the problem of distinguishing non-isomorphic MA
mn and Mkl in Theorem 6.5.
See Figure 7.

0

O12
22
Figure 7: Egg box diagram of the linear sandwich semigroup MO
22 (Z2 ) or, equivalently, M21 (F4 ). Both
are zero semigroups of size 16.

The next result describes the maximal D J -classes of MJmn . See also Figures 4 and 5.
Proposition 4.10. (i) If r = min(m, n), then DrJ = Dr ∩ P = {X ∈ P : rank(X) = r} is the unique
maximal D J -class of MJmn , and is a subsemigroup of MJmn .
J = {X} with
(ii) If r < min(m, n), then the maximal D J -classes of MJmn are those of the form DX
rank(X) > r.

Proof. Part (i) follows immediately from Proposition 4.7(ii), the rule [M, A, N ] ? [K, B, L] = [M, AB, L],
and the fact that Gr = Dr (Mr ) is a subgroup of Mr .
J ≤ D J . Then condition (ii) from
For (ii), let X ∈ Mmn . Suppose first that rank(X) > r and that DX
Y
Proposition 4.6 does not hold, since rank(JY J) ≤ rank(J) = r < rank(X). Similarly, rank(JY ) < rank(X)
and rank(Y J) < rank(X), so neither (iii) nor (iv) holds. Having eliminated (ii–iv), we deduce that (i)
J = {X} is indeed maximal. Conversely, suppose rank(X) ≤ r, and let
must hold; that is, X = Y , so DX
Ir O
Y = O D , where D 6= O. Then rank(Y ) > r, so DYJ = {Y } is maximal by the previous paragraph. But
J < D J = {Y }, whence
also JY J = J, and it follows that rank(X) ≤ r = rank(J) = rank(JY J), so that DX
Y
J
DX is not maximal.
2

The description of the maximal D J -classes from Proposition 4.10 allows us to obtain information about
generating sets for MJmn and, in the case of finite F, about rank(MJmn ). In order to avoid confusion when
discussing generation, if Ω ⊆ Mmn , we will write hΩiJ for the subsemigroup of MJmn generated by Ω, which
consists of all products X1 ? · · · ? Xk , with k ≥ 1 and X1 , . . . , Xk ∈ Ω. If Σ ⊆ Mk for some k, we will
continue to write hΣi for the subsemigroup of Mk generated by Σ. For convenience, we will state two
separate results, according to whether r = min(m, n) or r < min(m, n). The next lemma will be useful as
the inductive step in the proofs of both Theorems 4.12 and 4.14. Recall that {em1 , . . . , emm } is the standard
basis of Vm = Fm .
Lemma 4.11. Suppose X ∈ Ds (Mmn ), where 0 ≤ s ≤ l − 1 and l = min(m, n). Then X = Y ? Z for some
Y ∈ Dl (Mmn ) and Z ∈ Ds+1 (Mmn ).
19

Proof. Let B = {v1 , . . . , vn } be a basis of Vn such that {vs+1 , . . . , vn } is a basis of ker(λX ). Consider the
linear transformation β ∈ Hom(Vn , Vm ) defined by


emi if 1 ≤ i ≤ s
β(vi ) = 0
if s < i < n


emm if i = n,
noting that rank(β) = s + 1. The proof now breaks into two cases, depending on whether r < m or r = m.

Case 1. Suppose first that r < m. Let α ∈ Hom(Vn , Vm ) be any linear transformation of rank l that
extends the map eni 7→ λX (vi ) (1 ≤ i ≤ s). One easily checks that α ◦ λJ ◦ β = λX .
Case 2. Now suppose r = m. Recall that we are assuming that r = m = n does not hold, so r = m < n.
This time, define we let α be any linear transformation of rank m = l that extends the map eni 7→ λX (vi )
(1 ≤ i ≤ s), enr = enm 7→ 0. Then, again, one easily checks that α ◦ λJ ◦ β = λX .
2
Theorem 4.12. Suppose r < l = min(m, n). Then MJmn = hΩiJ , where Ω = {X ∈ Mmn : rank(X) > r}.
Further, any generating set for MJmn contains Ω. If |F| = q < ∞, then
   
l
X
s
m
n
rank(MJmn ) = |Ω| =
q (2) (q − 1)s [s]q !.
s q s q
s=r+1

Proof. For convenience, we will assume that l = m ≤ n. The other case will follow by duality. We will also
denote Ds (Mmn ) simply by Ds for each 0 ≤ s ≤ m. Consider the statement:
H(s):

hΩiJ contains Ds ∪ · · · ∪ Dm = {X ∈ Mmn : rank(X) ≥ s}.

Note that Ω = Dr+1 ∪ · · · ∪ Dm , so H(s) is clearly true for r + 1 ≤ s ≤ m. Lemma 4.11 shows that H(s + 1)
implies H(s) for all 0 ≤ s ≤ m − 1. So we conclude that H(s) is true for all 0 ≤ s ≤ m. In particular, H(0)
says that MJmn = hΩiJ .
Since {X} is a maximal D J -class for any X ∈ Ω, it follows that any generating set of MJmn must contain Ω.
Thus, Ω is the minimal generating set with respect to both size and containment, so rank(MJmn ) = |Ω|. The
formula for |Ω| with |F| finite follows from Lemma 3.4.
2
In order to consider the case in which r = min(m, n), we first prove an intermediate result. There is a dual
version of the following lemma (dealing with the case in which r = n < m), but we will not state it.
Lemma 4.13. If r = m < n, then
(i) P2 = MJmn ,

(ii) P = P1 is a left ideal of MJmn ,

(iii) L J = L in MJmn .

A B
Proof. Let X ∈ MJmn . As noted earlier, in the 2 × 2 block description, X = C
D (where A ∈ M
 rI ,and
so on), the matrices C and
D
are
empty
(since
r
=
m).
So
we
write
X
=
[A
B].
Note
that
J
=
O , so

A B . It follows that Row(JX) = Row(X) and, since X ∈ MJ
JX = OI [A B] = O
was
arbitrary,
this
mn
O
completes the proof of (i).
We immediately deduce P = P1 from (i). As in Proposition 4.3, the regular elements of MJmn are of the
form [A AN ] where A ∈ Mr and N ∈ Mr,n−r . We denote such a regular element by [A, N ]. The proof
of (ii) concludes with the easily checked observation that [A B] ? [C, N ] = [AC, N ].
Part (iii) follows quickly from (i) and Theorem 4.5(ii).
Theorem 4.14. Suppose r = min(m, n) where m 6= n. If |F| = q < ∞, then
 
L
J
rank(Mmn ) =
,
l q
where L = max(m, n) and l = min(m, n).
20

2

Proof. Again, it suffices to assume that r = m < n, so l = m and L = n. We keep the notation of the
previous proof.
Let Ω be an arbitrary generating set for MJmn . Let X ∈ Dm (Mmn ) be arbitrary. We claim that Ω must
contain some element of LJX = LX . Indeed, consider an expression X = Y1 ? · · · ? Yk , where Y1 , . . . , Yk ∈ Ω. If
k = 1, then Y1 = X ∈ LX and the claim is established, so suppose k ≥ 2. Since Dm (Mmn ) is a maximal D J class, we must have Yk ∈ Dm (Mmn ). So Yk D J X = (Y1 ?· · ·?Yk−1 )?Yk , whence Yk L J (Y1 ?· · ·?Yk−1 )?Yk = X,
by stability. By Lemma 4.13(iii), this completes the proof of the claim. In particular, |Ω| is bounded below
n
by the number of L -classes contained in Dm (Mmn ), which is equal to [ m
]q , by Lemma 3.4. Since Ω was


n
J
L
an arbitrary generating set, it follows that rank(Mmn ) ≥ [ m ]q = l q .

To complete the proof, it remains to check that there exists a generating set of the desired cardinality.
J
m)
XN =
[ANN, N∈] 2
is possible
= q m(n
rank(G}mgenerates
)  2 by Theorem
m | that
m . (This
For
each
MDm,n−m
, choose
some since
AN ∈|M
Grm,n
such
{AN : N2,∈and
Mm,n−m
Gm , and 3.7.)
put
J . Also, choose
J
m(n−m)
It
is
easy
to
see
that
⌦
=
{X
:
N
2
M
}
is
a
cross-section
of
the
L
-classes
in
D
1
m,n
m
N
m Theorem 3.7.)
XN = [AN , N ] ∈ Dm . (This is possible since |Mm,n−m | = q
≥ 2, and rank(Gm ) ≤ 2 by
J . Then
J.⌦
some
cross-section
⌦2Ω=1 =
{Yi{X
:N
i 2: I}
of M
the
L
-classes
contained
in
D
(M
)
\
D
= ⌦ 1 [ ⌦2
m
mn
m
It
is easy
to see that
N∈
}
is
a
cross-section
of
the
L
-classes
in
D
m,n−m
m Also, choose
n
is a cross-section
contained in Dm (M
|⌦| J= [ m ]q , the
mn ). Since,
some
cross-sectionofΩ2the
=L
{Y-classes
contained
in Dtherefore,
Ω =proof
Ω1 ∪will
Ω2
i : i ∈ I} of the L -classes
m (Mmn ) \ Dm . Then
J
n
be acomplete
if weofcan
that M
Lemma
4.11, ittherefore,
suffices to
that
h⌦iJproof
contains
is
cross-section
theshow
L -classes
contained
|Ω|show
= [m
]q , the
will
J . DBy
mn = h⌦iin
m (M
mn ). Since,
J , and write Z = [B, L], noting that
Dmcomplete
(Mmn ). So
suppose
Z 2that
Dm (M
first
that Z4.11,
2 Ditm
mn ).= Assume
be
if we
can show
MJmn
hΩiJ . By
Lemma
suffices to show that hΩiJ contains
1
J· ·, A
B m2(M
Grmn
. ).Choose
N1 , . . .Z, N∈k D
2mM
such
that
BA
=
A
·
ThenZone
easily
checks that
that
m,n
m
N
Nk . write
1
D
So suppose
(M
).
Assume
first
that
Z
∈
D
= [B,
L], noting
L
mn
m and
−1
Z=
? · · · ? X Nk 1?, .X
suppose Z is not regular. Choose i 2 I such that ZL Yi . By Lemma
3.3,
checks that
B
∈X
GN
. .L,.NNow,
r .1 Choose N
k ∈ Mm,n−m such that BAL = AN1 · · · ANk . Then one easily
Z
=
U
Y
for
some
U
2
G
.
But
then
Z
=
[U
V
]
?
Y
for
any
V
2
M
.
Since
rank(U
)
=
m,
we
have
i
m
i
m,n
m
Z = XN1 ? · · · ? XNk ? XL . Now, suppose Z is not regular. Choose i ∈ I such that ZL Yi . By Lemma 3.3,
J
[U =V U
] 2YiDfor
h⌦iJU, whence
Z 2 then
h⌦iJ ,Zcompleting
proof.
2
m ✓
Z
some
∈ Gm . But
= [U V ] ? the
Yi for
any V ∈ Mm,n−m . Since rank(U ) = m, we have

J ⊆ hΩi , whence Z ∈ hΩi , completing the proof.
[U V ] ∈ Dm
J
J

2

Remark 4.15. By inspecting Figures 4 and 5, the reader may use Theorems 4.12 and 4.14 to locate the
J the
Remark
4.15.a By
inspecting
Figures
and
reader may use Theorems 4.12 and 4.14 to locate the
elements from
minimal
generating
set4for
M5,
mn .
J
elements from a minimal generating set for Mmn .

5
5

Connection to (non-sandwich) matrix semigroups
Connection to (non-sandwich) matrix semigroups

h
i
h
i
I
Or,n r i
Ir
Or,m r i
T = J
h
Recall that J = Jnmr = h OmIrr r,r OO
2
M
.
Now
let
K
=
J
=
2 Mmn .
nm
mnr
OnIr r,r OO
mr,n−r
r,n r
n r,m−r
r,m r
T = J
Recall that J = Jnmr = Om−r,r
∈
M
.
Now
let
K
=
J
=
∈
Mmn .
nm
mnr
Om−r,n−rJ
On−r,r On−r,m−r
So Lemma 4.1 says that MK
nm and MJ
mn are anti-isomorphic. Also, since J = JKJ and K = KJK,
K
anti-isomorphic.
Also,
J = homomorphisms
JKJ and K = where,
KJK,
Mmn arecommutative
So
Lemma2.15
4.1says
saysthat
thatweM
nm and
Theorem
have
the following
diagrams
of since
semigroup
Theorem
2.15
says
that
we
have
the
following
commutative
diagrams
of
semigroup
homomorphisms
where,
for clarity, we write · for (non-sandwich) matrix multiplication:
for clarity, we write · for (non-sandwich) matrix multiplication:
(Mmn , ?J )

Reg(Mmn , ?J )

1 :X7!XJ

2 :X7!JX

(Mmn J, ·)
1 :Y

7!JY

(JMmn , ·)
2 :Y

(JMmn J, ?K )

7!Y J

1 :X7!XJ

2 :X7!JX

Reg(Mmn J, ·)
1 :Y

7!JY

Reg(JMmn , ·)
2 :Y

Reg(JMmn J, ?K )

7!Y J

In this section, we show that the various semigroups appearing in the above diagrams are all (equal to or
In this section, we show that the various semigroups appearing in the above diagrams are all (equal to or
isomorphic to) certain well-known (non-sandwich) matrix semigroups, and explore the consequences for the
isomorphic to) certain well-known (non-sandwich) matrix semigroups, and explore the consequences for the
structure of the sandwich semigroups MJmn
. First, we have a simple observation.
structure of the sandwich semigroups MJmn . First, we have a simple observation.
Lemma 5.1. We have (JMmn J, ?K ) = Reg(JMmn J, ?K ) ∼
= (Mr , ·).
Lemma 5.1. We have (JMmn J, ?K ) = Reg(JMmn J, ?K ) ⇠
= (Mr , ·).
A B
Proof.
or not, JXJ =
 A O  Let X = ⇥ C D ⇤ ∈ Mmn . We have already observed Athat,
 whether
 E O  X isAEregular

O ?
O .
A
B
∈
M
.
The
result
follows
quickly
from
the
fact
that
=
Proof.
Letnm
X = C D 2 Mmn . We have already observed⇥ Othat,
whether
or not, JXJ 2
=
O⇤
O⇤ K
O ⇤ X ⇥isOregular
O⇤
⇥O
⇥O
A O 2M
A
O
E
O
AE
O
.
The
result
follows
quickly
from
the
fact
that
?
=
.
2
nm
K O O
O O
O O
O O
For integers k ≥ 1 and 0 ≤ l ≤ k, we write
For integers k

1 and 0  l Ckk,
(l)we
= write
{X ∈ Mk : cl+1 (X) = · · · = ck (X) = O},

Rk (l) = {X ∈ Mk : rl+1 (X) = · · · = rk (X) = O}.
Ck (l) = {X 2 Mk : cl+1 (X) = · · · = ck (X) = O},
Rk (l) = {X 2 Mk : rl+1 (X) = · · · = rk (X) = O}.
21

(As before, without causing confusion, we write O for any zero matrix when the dimensions are clear from
context.) These matrix semigroups have been studied in a number of contexts (see for example [72, 89]),
along with their associated isomorphic semigroups of linear transformations

⊥
Kk (l) = α ∈ End(Vk ) : ker(α) ⊇ Wkl
,

Ik (l) = α ∈ End(Vk ) : im(α) ⊆ Wkl .

⊥ = span{e
Here we have written Wkl
k,l+1 , . . . , ekk }. Clearly, Ck (l) and Rk (l) are anti-isomorphic.

Lemma 5.2. We have Mmn J = Cm (r) and JMmn = Rn (r).
A B
A O
A B
Proof. Let X = C
D ∈ Mmn . We have already observed that XJ = C O ∈ Mm and JX = O O ,
and the result quickly follows.
2
A B
Remark 5.3. A typical element X ∈ Rk (l) may be written as X = O
, B ∈ Ml,k−l and
O , where A
 A∈BM
 l E

F = AE AF .
so on. One easily checks that multiplication of matrices in this form obeys the rule O O O O
O O
Comparing this to the discussion in Remark 4.2, we see that Rk (l) is isomorphic to the sandwich semigroup
MJlk where J = Jkll ∈ Mkl . (A dual statement holds for the matrix semigroups Ck (l).) Thus, every result
we obtain for linear sandwich semigroups leads to analogous results for the semigroups
Rk (l) and Ck (l). For
 
example, we deduce from Theorem 4.14 that rank(Ck (l)) = rank(Rk (l)) = kl q if |F| = q < ∞. Note that
the sandwich semigroups MJmn pictured in Figure 5 satisfy r = min(m, n), so Figure 5 essentially pictures
eggbox diagrams of C3 (2) and R4 (2).
Remark 5.4. Similarly, one may think of an arbitrary linear sandwich semigroup MJmn itself as a (nonsandwich) matrix semigroup, as noted by Thrall in [92] and slightly adapted as follows. Consider
h O O O i the set
M of all (m + n − r) × (m + n − r) matrices that may be written in 3 × 3 block form B A O , where
D C O
A ∈ Mr , D ∈ Mm−r,n−r (and from which the dimensions of the other sub-matrices
may
be
h
ih
i hderived). iOne
O O O

O O O

F E O =
easily checks that the matrices from M multiply according to the rule B A O
D C O
H GO
hO O Oi
A B
that C D 7→ B A O determines an isomorphism (Mmn , ?J ) → (M , ·). Note also that

O O O
AF AE O
CF CE O

, so

D C O

M = R∗m+n−r (m) ∩ Cm+n−r (n)

where
write R∗k (l) = {X ∈ Mk : r1 (X) = · · · = rk−l (X) = O}. (It is easily seen that the map
 A B  here
 Owe

J
∗
O
O O → B A determines an isomorphism Rk (l) → Rk (l).) Since using this isomorphic copy M of Mmn
does not appear to confer any obvious advantage, we will make no further reference to it.
The regular elements of Ck (l) and Rk (l) (and also of Ik (l) and Kk (l)) were classified in [72]. The next result,
which gives a much simpler description of these regular elements, may be deduced from [72, Theorems 3.4
and 3.8] (and vice versa), but we include a simple proof for convenience.
Proposition 5.5. The regular elements of the semigroups Cm (r) = Mmn J and Rn (r) = JMmn are given
by
Reg(Cm (r)) = Reg(Mmn J) = P J = {X ∈ Mmn J : rank(JX) = rank(X)}

Reg(Rn (r)) = Reg(JMmn ) = JP = {X ∈ JMmn : rank(XJ) = rank(X)}.
A B
Proof. We just prove the second statement
as
the
other
is
dual.
Let
X
=
∈ Mmn , and put
C D
A B
0
0
A
B
X = O O ∈ Mmn . Then JX = JX = O O ∈ Mn (where the zero matrices in the last expression
have n − r rows). Since X 0 clearly belongs to P2 (by Proposition 4.3), wehave JMmn ⊆ JP2 . Next, note
A B . Now suppose X ∈ M
that KJ = Jmmr , so that KJY = Y for all Y ∈ Mmn of the form Y = O
mn
O
A
B
is such that JX ∈ Reg(JMmn ). As above, we may assume that X = O O . So (JX) = (JX)(JY )(JX)
for some Y ∈ Mmn . But then X = K(JX) = K(JXJY JX) = XJY JX = X ? Y ? X, so that, in fact,
22

X ∈ Reg(MJmn ) = P . This completes the proof that Reg(JMmn ) ⊆ JP . The reverse inclusion is easily
checked.
 A AN 
 A AN 
Now suppose X = JY where Y = O
∈ P . Then X = JY = O
(with appropriately sized zero
O
O
matrices), so rank(X) = rank(JY ) = rank(Y ) = rank(JY J) = rank(XJ), where we have used Proposition 4.3. Conversely, suppose X ∈ JMmn is such that rank(XJ) = rank(X). As before, we may assume
that X = JY where Y ∈ P2 . Then rank(Y ) = rank(JY ) = rank(X) = rank(XJ) = rank(JY J), so that
Y ∈ P . This completes the proof.
2

Remark 5.6. As always, the condition rank(JX) = rank(X), for X 2 Mmn , is equivalent to saying that
Remark
5.6. .As
the condition
rank(JX)
X ∈ statement
Mmn , is equivalent
saying
that
rows rr+1 (X),
. . , always,
rm (X) belong
to span{r
rrrank(X),
(X)}, withfora dual
holding fortothe
condition
1 (X), . . . ,=
rows
rr+1 (X),
. . . , rm (X)The
belong
to span{r
(X),
.
.
.
,
r
(X)},
with
a
dual
statement
holding
for
the
condition
rank(XJ)
= rank(X).
regular
elements
of
the
corresponding
semigroups
of
linear
transformations
are
1
r
rank(XJ)
given by = rank(X). The regular elements of the corresponding semigroups of linear transformations are
given by
?
Reg(Km (r)) = {↵ 2 Km (r) : im(↵) \ Wmr
= {0}},
⊥
Reg(K
(r))
=
{α
∈
K
(r)
:
im(α)
∩
W
=
{0}},
m
m
mr
Reg(I (r)) = {↵ 2 I (r) : im(↵) = ↵(W )}.
n

n

nr

Reg(In (r)) = {α ∈ In (r) : im(α) = α(Wnr )}.

Putting together all the above, we have proved the following. (In the following statement, we slightly abuse
Putting
all the above,
we have
proved
theJfollowing.
notationtogether
by still denoting
the map
Cm (r)
= Mmn
! Mr by(In1 the
andfollowing
so on.) statement, we slightly abuse
notation by still denoting the map Cm (r) = Mmn J → Mr by Φ1 and so on.)
Theorem 5.7. We have the following commutative diagrams of semigroup epimorphisms:
Theorem 5.7. We have the following commutative diagrams of semigroup epimorphisms:
1:

[

A B
C D

]7![

A O
C O

]

MJmn

Cm (r)
[ A O ]7!A

Reg(MJmn )
2:

[

A B
C D

]7![

A B
O O

Rn (r)

1: C O

[ A B ]7!A

2: O O

Mr

]

1:

[

A B
C D

]7![

A O
C O

]

[ A B ]7![ OA BO ]

2: C D

Reg(Cm (r))
[ A O ]7!A

1: C O

Reg(Rn (r))

Mr

[ A B ]7!A

2: O O

2
2
JJ ). From now on, we
The
The remaining
remaining results
results of
of this
this section
section concern
concern the
the regular
regular subsemigroup
subsemigroup PP =
= Reg(M
Reg(Mmn
From
mn
⇥).
⇤ now on, we
A
AB
B ∈
denote
P , we write
denote by
by φ =
= φ11◦ ψ11 =
= φ22◦ ψ22 the
the induced
induced epimorphism
epimorphism φ :: PP →
!M
Mrr.. Also,
Also, for
for X
X=
= C
D
C D 2 P , we write
X
X=
= φ(X)
(X) =
= A.
A. The
The next
next result
result shows
shows how
how the
the second
second commutative
commutative diagram
diagram from
from Theorem
Theorem 5.7
5.7 may
may be
be
JJ ) as a special kind of subdirect product of Reg(C (r)) and Reg(R (r)).
used
to
identify
Reg(M
used to identify Reg(Mmn
m (r)) and Reg(Rnn (r)).
mn ) as a special kind of subdirect product of Reg(Cm

Proposition
Proposition 5.8.
5.8. There
There is
is an
an embedding
embedding
) → Reg(C (r)) × Reg(R (r)) : X 7→ (ψ (X), ψ (X)) = (XJ, JX).
ψ : Reg(MJmn
: Reg(MJmn ) ! Reg(Cmm (r)) ⇥ Reg(Rnn (r)) : X 7! ( 11 (X), 22 (X)) = (XJ, JX).
As such, P = Reg(MJmn
) is (isomorphic to) a pullback product of P J = Reg(Cm (r)) and JP = Reg(Rn (r)).
As such, P = Reg(MJmn ) is (isomorphic to) a pullback product of P J = Reg(Cm (r)) and JP = Reg(Rn (r)).
Namely,
Namely,


P ∼
= im(ψ) = (ψ1 (X), ψ2 (X)) : X ∈ P = (Y, Z) ∈ P J × JP : φ1 (Y ) = φ2 (Z) .
P ⇠
= im( ) = ( 1 (X), 2 (X)) : X 2 P = (Y, Z) 2 P J ⇥ JP : 1 (Y ) = 2 (Z) .

Proof. Clearly, ψ is a homomorphism. Now let X = [M, A, N ] and Y = [K, B, L] be elements of P with
Proof.
Clearly,
ψ(X)
= ψ(Y
). Thenis a homomorphism. Now let X = [M, A, N ] and Y = [K, B, L] be elements of P with
(X) = (Y ). Then
 A O   A AN 
 B O   B BL 
O ⇤ = ψ(X) = ψ(Y ) = ⇥KB O ⇤, ⇥O O ⇤ .
⇥MAA OO ⇤, ⇥OA AN
B O , B BL
= (X) = (Y ) = KB
.


MA O , O O
O
O O
Comparing
various
coordinates,
we
deduce
A
=
B,
M
A
=
KB
and
AN = BL, giving X = MAA MAN
AN ⇤ =
 B BL 
⇥ A AN
Y , completing
the proof
that ψAis=injective.
Comparing
coordinates,
we deduce
B, M A = KB and AN = BL, giving X = M A M AN =
KBL ⇤ =various
⇥KB
B BL
is injective.
KBL = Y , completing the proof that
ToKB
prove
the statement about im(ψ), let X ∈ P and put Y = ψ1 (X) = XJ and Z = ψ2 (X) = JX. Then
φTo
) = JY
JXJ = about
ZJ =im(
φ2 (Z).
× and
JP satisfies
JY ==JX.
ZJ.Then
Say
the =
statement
), letConversely,
X 2 P andsuppose
put Y =(Y, 1Z)
(X)∈ =P J
XJ
Z = 2 (X)
1 (Yprove
A
O
Y 1=
JV
A, N
] and V = [K,
B, L] (Y,
belong
Then
= JUJY
J == OZJ.
and
(YU) J=and
JY Z==JXJ
= ZJ U== [M,
Conversely,
suppose
Z) 2toPPJ. ⇥
JP JY
satisfies
2 (Z).
 , where
⇥ A OO ⇤ Say
O , giving A = B. But then (Y, Z) = ψ(X), where X = [M, A, L] ∈ P .
ZJ
J = ZB
2
Y ==UJV
J and
=
JV
,
where
U
=
[M,
A,
N
]
and
V
=
[K,
B,
L]
belong
to
P
.
Then
JY
=
JU
J
=
O O and
⇥O OO ⇤
ZJ = JV J = B
,
giving
A
=
B.
But
then
(Y,
Z)
=
(X),
where
X
=
[M,
A,
L]
2
P
.
2
O O
Remark 5.9. We note that the previous result does23
not lift to a similar identification of MJmn as a pullback

Remark 5.9. We note that the previous result does not lift to a similar identification of MJmn as a pullback
product of Cm (r) and Rn (r) because the induced map
Ψ : MJmn → Cm (r) × Rn (r) : X 7→ (Ψ1 (X), Ψ2 (X)) = (XJ, JX)
A B
 A O   A B 
A B
is not injective. Indeed, if X = C
D ∈ Mmn , then Ψ(X) =
C O , O O , with C E mapping to the
same pair for any other E ∈ Mm−r,n−r .
Remark 5.10. More generally, given a partial semigroup (S, ·, I, λ, ρ), the epimorphisms Ψ1 and Ψ2 from
Theorem 2.15(v) allow for the definition of a map
Ψ : (Sij , ?a ) → (Sij a, ·) × (aSij , ·) : x 7→ (xa, ax).
To say that Ψ is injective is to say that, for all x, y ∈ Sij , xa = ya and ax = ay together imply x = y.
Compare this to the notion of a weakly reductive semigroup S, in which, for every x, y ∈ S, the assumption
that xa = ya and ax = ay for all a ∈ S implies x = y. See for example [71, Definition 1.42].
We conclude this section with a simple but important observation that shows that P = Reg(MJmn ) is a homomorphic image of the direct product of a rectangular band by the (non-sandwich) matrix semigroup Mr .
(Recall that a rectangular band is a semigroup of the form S × T with product (s1 , t1 )(s2 , t2 ) = (s1 , t2 ).)
Its proof is routine, relying on Proposition 4.3 and the rule [M, A, N ] ? [K, B, L] = [M, AB, L]. For the
statement, recall that the kernel of a semigroup homomorphism φ : S → T (not to be confused with the
kernel of a linear transformation) is the congruence ker(φ) = {(x, y) ∈ S × S : φ(x) = φ(y)}. (A congruence
on a semigroup S is an equivalence relation ∼ for which x1 ∼ y1 and x2 ∼ y2 together imply x1 x2 ∼ y1 y2
for all x1 , x2 , y1 , y2 ∈ S; the quotient S/∼ of all ∼-classes is a semigroup under the induced operation. The
first homomorphism theorem for semigroups states that any semigroup homomorphism φ : S → T induces
an isomorphism S/ ker(φ) ∼
= im(φ).)
Proposition 5.11. Consider the semigroup U = Mm−r,r × Mr × Mr,n−r under the operation  defined by
(M, A, N )  (K, B, L) = (M, AB, L).
Define an equivalence ∼ on U by
(M, A, N ) ∼ (K, B, L) ⇔ A = B, M A = KB and AN = BL.
Then ∼ is a congruence on U , and the map
ξ:U →P =

Reg(MJmn )



A
AN
: (M, A, N ) 7→ [M, A, N ] =
M A M AN

is an epimorphism with ker(ξ) = ∼. In particular, P ∼
= U/∼.

6


2

The regular subsemigroup

In this section, we continue to study the subsemigroup P = Reg(MJmn ) consisting of all regular elements
of MJmn . Eggbox diagrams of P = Reg(MJ43 (Z2 )) are given in Figure 8 for values of 0 ≤ rank(J) ≤ 3;
more examples can be seen by inspecting the regular D J -classes in Figures 4 and 5. Comparing Figure 8
with Figure 3, which pictures the full linear monoids Mr (Z2 ) for 0 ≤ r ≤ 3, an interesting pattern seems
to emerge: namely, that P = Reg(MJ43 (Z2 )) appears to be a kind of “inflation” of Mr , where r = rank(J).
One of the goals of this section is to explain this phenomenon, and we do so by further exploring the map
φ : P → Mr : X = [M, A, N ] 7→ X = A
defined after Theorem 5.7. We also calculate |P |, rank(P
and sizes of various Green’s
 ), and the number
J
classes. As before, we assume that J = Jnmr = IOr O
∈
M
.
Since
M
nm
mn is just a zero semigroup if
O
r = 0, we generally assume that r ≥ 1.
24

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0
1
1

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1

2

1

1

2

1

1

1

2

1

1

1

1

2

1

1

1

2

1

1
1

1

1

0
2

1

1

2

1

1

1

1

3

3

3

2

3

2

3

2

2

3

2

2

2

3

2

2

2

3

2

2

2

2

2

2
2

2

2

2

2

2
2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2
2

2
2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1

2

1

2

1

2

1

2

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1
1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1
1

1

0

Figure 8: Egg box diagrams (drawn sideways) of the regular linear sandwich semigroups P = Reg(MJ43 (Z2 )),
where rank(J) = 0, 1, 2, 3 (top to bottom).

Now, Theorem 4.5 enables us to immediately describe Green’s relations on P = Reg(MJmn ). Since P is a
regular subsemigroup of MJmn , the R, L , H relations on P are just the restrictions of the corresponding
relations on MJmn (see for example [40, 44]), and it is easy to check that this is also true for the D = J
relation in this case. So if X ∈ P and K is one of R, L , H , D, we will continue to write K J for
J for the K J -class of X in P . Parts (i–iv) of the next result also appear
the K relation on P , and KX
in [9, Theorem 2.3].
Corollary 6.1. If X ∈ P , then
J = R ∩ P = {Y ∈ P : Col(X) = Col(Y )},
(i) RX
X

(ii) LJX = LX ∩ P = {Y ∈ P : Row(X) = Row(Y )},
J = H ∩ P = H = {Y ∈ P : Col(X) = Col(Y ) and Row(X) = Row(Y )},
(iii) HX
X
X
J = D ∩ P = {Y ∈ P : rank(X) = rank(Y )}.
(iv) DX
X

The D J -classes of P form a chain: D0J < · · · < DrJ , where DsJ = {X ∈ P : rank(X) = s} for each
0 ≤ s ≤ r.
2
Also, the regularity of P means that P inherits the stability property from MJmn . The next result gives
some combinatorial information about the size of P , and of various Green’s classes in P , in the case that F
is finite. Recall that {ek1 , . . . , ekk } is the standard basis of Vk = Fk and that Wks = span{ek1 , . . . , eks } for
each 0 ≤ s ≤ k.
Proposition 6.2. Suppose |F| = q < ∞. Let X ∈ P with rank(X) = s. Then
s

J | = q s(n−r) q (2) (q − 1)s [s] ! [ r ] ,
(i) |RX
q s q
s

(ii) |LJX | = q s(m−r) q (2) (q − 1)s [s]q ! [ rs ]q ,
s

J | = |G | = q (2) (q − 1)s [s] !,
(iii) |HX
s
q
J = D J is the union of:
(iv) DX
s

25

(a) q s(m−r) [ rs ]q R J -classes,

(b) q s(n−r) [ rs ]q L J -classes,

(c) q s(m+n−2r) [ rs ]2q H J -classes,

s

J | = |D J | = q s(m+n−2r) q (2) (q − 1)s [s] ! [ r ]2 .
(v) |DX
q s q
s

Consequently, |P | =

| Reg(MJmn )|

=

r
X
s=0

s

q s(m+n−2r) q (2) (q − 1)s [s]q ! [ rs ]2q .

J | = |RJ | for all Y ∈ D J = D J , we may assume X = J
Proof. We start with (i). Since |RX
mns . Now,
s
Y
X
Col(X) = Wms . By Proposition 4.3 and Corollary 6.1, we have
J
RX
= {Y ∈ P : Y R J X}

= {Y ∈ Mmn : Col(X) = Col(Y ), Col(Y ) = Col(Y J), Row(Y ) = Row(JY )}

= {Y ∈ Mmn : Col(Y ) = Col(Y J) = Wms },
i
h
A
B
since if Col(Y ) = Wms , then Y is of the form Y = Om−s,r
Om−s,n−r for some A ∈ Msr and B ∈ Ms,n−r ,
i
h
A
B
in which case JY = On−s,r
On−s,n−r automatically has the same row space as Y .



J . As noted above, we must have Y = A B for some A ∈ M and B ∈ M
Now considersome Y ∈ RX
sr
s,n−r .
O O
A O , the condition Col(Y J) = W
Since Y J = O
is
equivalent
to
Col(A)
=
V
.
In
particular,
there
is
ms
s
O
s(n−r)
no restriction on the entries of B, so B may be chosen (arbitrarily, and independently of A) in q
ways. Also, dim(Row(A)) = dim(Col(A)) = s. So A may be specified by listing its rows (in order),
which are s linearly independent row vectors from Fr . The number of possible choices for A is therefore
s
(q r − 1)(q r − q) · · · (q r − q s−1 ) = q (2) (q − 1)s [s]q ! [ rs ]q . Multiplying these two values gives (i).
Part (ii) is dual to (i). Part (iii) follows directly from Corollary 6.1(iii) and Lemma 3.4(iii). Parts (a)
J | by |H J |, respectively. Part (c) follows from (a) and (b).
and (b) of (iv) follow by dividing |LJX | and |RX
X
Part (v) follows from (iii) and part (c) of (iv). The formula for |P | is obtained by adding the sizes of the
D J -classes.
2
Recall that, for X = [M, A, N ] ∈ P , we write X = φ(X) = A ∈ Mr . We extend this notation to subsets
of P , so if Ω ⊆ P , we write Ω = {X : X ∈ Ω}. We now show how the epimorphism φ : P → Mr may be
used to relate Green’s relations on the semigroups P and Mr . If X, Y ∈ P and K is one of R, L , H , D,
b J = φ−1 (K ) = {Y ∈ P : X KbJ Y } the KbJ -class of X
we say X KbJ Y if XK Y (in Mr ). Denote by K
X
X
in P . We first need a technical result.
b J Y , then |R
b J | = |L
b J |.
bJ | = |R
bJ | and |L
Lemma 6.3. Let X, Y ∈ P . If X D
X
Y
X
Y

b J Y means that X LbJ W RbJ Y
Proof. By duality, it suffices to prove the statement about RbJ -classes. Now, X D
J
J
b = R
b , we may assume without loss of generality that X LbJ Y . Write
for some W ∈ P . Since R
Y
W
X = [M, A, N ] and Y = [K, B, L]. By definition X LbJ Y , means that AL B in Mr , so A = U B for some
bJ , and define α(Z) = [M 0 U, U −1 A0 , N 0 ]. It is easy to
U ∈ Gr by Lemma 3.3. Now let Z = [M 0 , A0 , N 0 ] ∈ R
X
00
00
check that for any other representation Z = [M , A , N 00 ], we have [M 00 U, U −1 A00 , N 00 ] = [M 0 U, U −1 A0 , N 0 ],
so that α(Z) is well-defined. Also,
Z RbJ X ⇒ A0 RA ⇒ U −1 A0 RU −1 A = B ⇒ α(Z)RbJ Y.

bJ . It is easy to check that R
bJ → R
bJ : [M 0 , A0 , N 0 ] 7→ [M 0 U −1 , U A0 , N 0 ] is the
bJ → R
Thus α is a map α : R
X
Y
Y
X
J
J
b | = |R
b |.
inverse mapping of α. We conclude that |R
2
X
Y

For the proof of the next result, we note that stability of M implies that A2 DA ⇔ A2 H A for all A ∈ Mr .
We also use the fact that an H -class H of a semigroup S is a group if and only if x2 ∈ H for some (and
hence for all) x ∈ H [44, Theorem 2.2.5]. Recall that a k × l rectangular band is a semigroup of the form
S × T with product (s1 , t1 )(s2 , t2 ) = (s1 , t2 ), where |S| = k and |T | = l. A k × l rectangular group with
respect to a group G is a direct product of a k × l rectangular band with G.
26

For the proof of the next result (and elsewhere), it will be convenient to define a number of equivalence
relations. For A ∈ Mr , we define equivalences ∼A and ≈A on Mm−r,r and Mr,n−r (respectively) by
M1 ∼A M2 ⇔ M1 A = M2 A

and

N1 ≈A N2 ⇔ AN1 = AN2 .

Theorem 6.4. Suppose |F| = q < ∞. Let X ∈ P = Reg(MJmn ) and put s = rank(X).
bJ is the union of q s(m−r) R J -classes of P .
(i) R
X

b J is the union of q s(n−r) L J -classes of P .
(ii) L
X

s
b J is the union of q s(m+n−2r) H J -classes of P , each of which has size |Gs | = q (2) (q − 1)s [s]q !. The
(iii) H
X
map φ : P → Mr is injective when restricted to any H J -class of P .

b J is a non-group.
(iv) If HX is a non-group H -class of Mr , then each H J -class of P contained in H
X

b J is a group isomorphic
(v) If HX is a group H -class of Mr , then each H J -class of P contained in H
X
b J is a q s(m−r) × q s(n−r) rectangular group with respect to Gs .
to Gs ; further, H
X

b J = D J and D
b J = DJ = DsJ = {Y ∈ P : rank(Y ) = s} is the union of:
(vi) D
X
X
(a) [ rs ]q RbJ -classes (and the same number of LbJ -classes) of P ,

(b) q s(m−r) [ rs ]q R J -classes of P ,
(b) q s(n−r) [ rs ]q L J -classes of P ,
(d) [ rs ]2q HbJ -classes of P ,

(e) q s(m+n−2r) [ rs ]2q H J -classes of P .

Proof. First observe that if ρ : S → T is an epimorphism of semigroups, and if K is a K -class of T where
K is one of R, L , H , then ρ−1 (K) is a union of K -classes of S. Throughout the proof, we write


A
AN
,
X = [M, A, N ] =
M A M AN
b J = D J immediately follows.
so A ∈ Mr satisfies rank(A) = rank(JXJ) = rank(X) = s. We note that D

bJ . Since |R
bJ | =
(i) By the first observation, it suffices to count the number of R J -classes contained in R
X
X
bJ | for all Y ∈ DsJ by Lemma 6.3, it follows that each RbJ -class of DsJ contains the same number
|R
Y
of R J -classes. By Lemma 3.4, Ds (Mr ) is the union of [ rs ]q R-classes (and the same number of L classes), so it follows that DsJ is the union of [ rs ]q RbJ -classes (and the same number of LbJ -classes).
By Proposition 6.2, DsJ is the union of q s(m−r) [ rs ]q R J -classes. Dividing these, it follows that each
RbJ -class of DsJ is the union of q s(m−r) R J -classes.

(ii) This is dual to (i).

b J follows immediately from (i)
(iii) The statement concerning the number of H J -classes contained in H
X
and (ii), and the size of these H J -classes was given in Proposition 6.2. Next, for any B ∈ Mr with
BH A, it is easy to check that [M, B, N ]H J X. So the set Ω = {[M, B, N ] : B ∈ HA } is contained
J |, we see that H J = Ω. For any Z = [M, B, N ] ∈ Ω = H J , we
in HXJ . Since |Ω| = |HA | = |Gs | = |HX
X
X
have φ(Z) = B, so it follows that φ|H J is injective.
X

b J be arbitrary. Since
(iv) Suppose HA = HX is a non-group H -class of Mr , and let Y = [K, B, L] ∈ H
X
J
Y Hb X, it follows that B = Y H X = A. Since HB = HA is not a group, we have B 2 6∈ HB , whence
B 2 6∈ DB and rank(B 2 ) < rank(B) = rank(A) = s. But then Y 2 = [K, B 2 , L] 6∈ DsJ = DYJ , so that
Y 2 6∈ HYJ , and we conclude that HYJ is not a group.

27

2
b J , so rank(Y ? Y ) = rank(Y 2 ) = rank(Y ) =
(v) Suppose HX is a group. Then Y ∈ HX for any Y ∈ H
X
rank(Y ), giving Y ? Y D J Y , so that Y ? Y ∈ HYJ and HYJ is a group. By (iii), the restriction of φ to
HYJ yields an isomorphism onto HY ∼
= Gs .

Let E ∈ Mr be the identity element of the group HA . Let ME ⊆ Mm−r,r (resp., NE ⊆ Mr,n−r ) be
a cross-section of the ∼E -classes (resp., ≈E -classes) in Mm−r,r (resp., Mr,n−r ). It is easy to check
b J may be uniquely represented as Y = [K, B, L] for some K ∈ ME , B ∈ HA and
that every Y ∈ H
X
L ∈ NE . It follows that the map
b JA : (K, B, L) 7→ [K, B, L]
ME × HA × NE → H

is a well-defined isomorphism, where the (rectangular group) product on ME × HA × NE is defined
by (K1 , B1 , L1 ) · (K2 , B2 , L2 ) = (K1 , B1 B2 , L2 ). We have already observed that HA ∼
= Gs , and the
dimensions of the rectangular band ME × NE follow from parts (i–iii) together with the observation
b J for each K ∈ ME and L ∈ NE .
that {[K, B, L] : B ∈ HA } is an H J -class contained in H
X

b J = D J . We proved (a) while proving (i), above. Parts (b), (c) and (e)
(vi) We have already noted that D
were proved in Proposition 6.2. Part (d) follows from (a).
2
The previous result explains the “inflation” phenomenon discussed at the beginning of this section; see also
Figure 8. As an immediate corollary of Theorem 6.4, we may now completely classify the isomorphism
classes of finite linear sandwich semigroups.
Theorem 6.5. Let F1 and F2 be two finite fields with |F1 | = q1 and |F2 | = q2 , let m, n, k, l ≥ 1, and let
A ∈ Dr (Mnm ) and B ∈ Ds (Mlk ). The following are equivalent:
∼ B
(i) MA
mn (F1 ) = Mkl (F2 ),

(ii) one of the following holds:
(a) r = s = 0 and q1mn = q2kl , or
(b) r = s ≥ 1, (m, n) = (k, l), and q1 = q2 .

A
B
∼ B
∼
Further, if r ≥ 1, then MA
mn (F1 ) = Mkl (F2 ) if and only if Reg(Mmn (F1 )) = Reg(Mkl (F2 )).
B
∼
Proof. Again, if r 6= s, then counting the regular D A - and D B -classes shows that MA
mn (F1 ) 6= Mkl (F2 ).
For the remainder of the proof, we assume r = s. Suppose first that r = s = 0. Then MA
mn (F1 ) and
mn and q kl , are equal.
MB
(F
)
are
both
zero
semigroups
and
so
are
isomorphic
if
and
only
if
their
sizes,
q
2
1
2
kl
For the remainder of the proof, we assume r = s ≥ 1, and write DtA and DtB for the relevant regular D A B
and D B -classes in MA
mn (F1 ) and Mkl (F2 ) for each 0 ≤ t ≤ r = s.

∼ F× , the multiplicative
By Theorem 6.4(v), any group H A -class contained in D1A is isomorphic to G1 (F1 ) =
1
×
A
∼
6
group of F1 . Since |F×
1 | = q1 − 1 and |F2 | = q2 − 1, it follows that if q1 6= q2 , then Reg(Mmn (F1 )) =
B
A
B
∼
∼
Reg(Mkl (F2 )) and, hence, Mmn (F1 ) =
6 Mkl (F2 ). Now suppose q1 = q2 (so F1 = F2 ), and write q = q1 .
By Theorem 6.4(vi), D1A (resp., D1B ) contains q m−r [ 1r ]q R A -classes (resp., q k−r [ 1r ]q R B -classes). It follows
B
A
∼
∼ B
that if m 6= k (or, dually, if n 6= l), then Reg(MA
mn (F1 )) 6= Reg(Mkl (F2 )) and, hence, Mmn (F1 ) 6= Mkl (F2 ).
∼ B
Conversely, if (b) holds, then MA
mn (F1 ) = Mkl (F2 ) by Lemma 4.1(ii).
A
B
∼ B
∼
For the final statement, first note that MA
mn (F1 ) = Mkl (F2 ) clearly implies Reg(Mmn (F1 )) = Reg(Mkl (F2 )).
∼
In the previous paragraph, we showed that the negation of (b) implies Reg(MA
6 Reg(MB
mn (F1 )) =
kl (F2 )).
This completes the proof.
2
B
∼
Remark 6.6. Of course, if rank(A) = rank(B) = 0, then Reg(MA
mn (F1 )) = {Omn } = Reg(Mkl (F2 )) =
{Okl }, regardless of m, n, k, l, q1 , q2 . So the final clause of Theorem 6.5 does not hold for r = 0.

Remark 6.7. The infinite case is not as straight-forward, since |Mmn (F)| = |F| for all m, n ≥ 1, and
×
since it is possible for two non-isomorphic fields F1 , F2 to have isomorphic multiplicative groups F×
1 , F2 (for
example, Q and Z3 (x) both have multiplicative groups isomorphic to Z2 ⊕ F , where F is a free abelian group
of countably infinite rank). So we have the following isomorphisms:
28

B
∼
(i) MA
mn (F1 ) = Mkl (F2 ) if m, n, k, l ≥ 1, |F1 | = |F2 |, and rank(A) = rank(B) = 0 — indeed, both
sandwich semigroups are zero semigroups of size |F1 | = |F2 |;
I O
× ∼ ×
B
∼
1
(ii) MA
mn (F1 ) = Mmn (F2 ) if F1 = F2 and rank(A) = rank(B) = 1 — indeed, when J = Jnm1 = O O ,
sandwich products X ?J Y involve only field multiplication and no addition:

 
 

a11 a12 · · · a1n
b11 b12 · · · b1n
a11 b11 a11 b12 · · · a11 b1n
 a21 a22 · · · a2n   b21 b22 · · · b2n   a21 b11 a21 b12 · · · a21 b1n 


 
 
 ..
..
..
..
..  .
..  ?J  ..
..  =  ..
.
.
.
.
.
.
 .
.
.
.
.
.
.
. 
.   .
.   .
am1 b11 am1 b12 · · · am1 b1n
am1 am2 · · · amn
bm1 bm2 · · · bmn

We leave it as an open problem to completely classify the isomorphism classes of linear sandwich semigroups
over infinite fields. But we make two simple observations:
∼ B
(iii) as in the proof of Theorem 6.5, if MA
mn (F1 ) = Mkl (F2 ), then we must have rank(A) = rank(B);
B
∼
∼
(iv) if MA
mn (F1 ) = Mkl (F2 ) with rank(A) = rank(B) = r ≥ 2, we must have F1 = F2 (since the maximal
A
subgroups of Mmn (F1 ) are isomorphic to Gs (F1 ) for 0 ≤ s ≤ r, and since Gs (F1 ) ∼
= Gs (F2 ) implies
F1 ∼
= F2 for s ≥ 2 [17]).

In what follows, the top D J -class of P = Reg(MJmn ) plays a special role. We write D for this D J -class, so
D = DrJ = φ−1 (Gr ) = {X ∈ P : rank(X) = r}.
As a special case of Theorem 6.4(v), D is a q r(m−r) ×q r(n−r) rectangular group with respect to Gr . Since D is
the pre-image of Gr under the map φ : P → Mr , we may think of D as a kind of “inflation” of Gr , the group
of units of Mr . In fact, more can be said along these lines. Recall again that the variant of a semigroup S
with respect to an element a ∈ S is the semigroup S a with underlying set S and operation ?a defined by
x ?a y = xay for all x, y ∈ S. Recall also that an element a ∈ S of a (necessarily regular) semigroup S is
regularity preserving if the variant S a is regular. The set RP(S) of all regularity preserving elements of S
was studied in [38,50]; we will not go into the details here, but it was explained in [50] that RP(S) is a useful
alternative to the group of units in the case that S is not a monoid (as with P when r = m = n does not
hold). Because of this, it is significant that D is equal to RP(P ), the set of all regularity preserving elements
of P = Reg(MJmn ), as we will soon see. We now state a result from [50] concerning regularity preserving
elements. Recall that an element u of a semigroup S is a mididentity if xuy = xy for all x, y ∈ S [98]; of
course for such an element, ?u is just the original semigroup operation.
Proposition 6.8 (Khan and Lawson [50]). Let S be a regular semigroup.
(i) An element a ∈ S is regularity preserving if and only if aH e for some regularity preserving idempotent
e ∈ E(S). (In particular, RP(S) is a union of groups.)
(ii) An idempotent e ∈ E(S) is regularity preserving if and only if f eRf L ef for all idempotents f ∈ E(S).
(iii) Any mididentity is regularity preserving.

2

In order to avoid confusion when discussing idempotents, if Ω ⊆ Mmn , we will write
EJ (Ω) = {X ∈ Ω : X = X ? X}
for the set of idempotents from Ω with respect to the ? operation on MJmn . If Σ ⊆ Mk for some k, we will
continue to write E(Σ) = {A ∈ Σ : A = A2 } for the set of idempotents from Σ with respect to the usual
matrix multiplication.
Lemma 6.9.

(i) EJ (MJmn ) = EJ (P ) = {[M, A, N ] : A ∈ E(Mr ), M ∈ Mm−r,r , N ∈ Mr,n−r }.

(ii) EJ (D) = {[M, Ir , N ] : M ∈ Mm−r,r , N ∈ Mr,n−r } is a q r(m−r) × q r(n−r) rectangular band.
(iii) Each element from EJ (D) is a mididentity for both MJmn and P .
29

(iv) D = RP(P ) is the set of all regularity-preserving elements of P .
Proof. Note that all idempotents are regular. If X = [M, A, N ] ∈ P , then X ? X = [M, A2 , N ], so
X = X ? X if and only if A = A2 , giving (i). Part (ii) follows from (i), since Ir is the only idempotent
from the group Gr = Dr (Mr ). Using (ii), it is easy to check by direct computation that X ? Y ? Z = X ? Z
for all X, Z ∈ Mmn and Y ∈ EJ (D), giving (iii). Finally, to prove (iv), note that by Proposition 6.8(i), it
suffices to show that EJ (RP(P )) = EJ (D). By (iii) and Proposition 6.8(iii), we have EJ (D) ⊆ EJ (RP(P )).
Conversely, suppose X ∈ EJ (RP(P )). Let Y ∈ EJ (D). By Proposition 6.8(ii), and the fact that L J ⊆ D J ,
X ?Y D J Y . It follows that r = rank(Y ) = rank(XJY ) ≤ rank(X) ≤ r, giving rank(X) = r, and X ∈ EJ (D).
This shows that EJ (RP(P )) ⊆ EJ (D), and completes the proof.
2
We may now calculate the rank of P = Reg(MJmn ) in the case of finite F. For the following proof, recall
from [46] that the relative rank rank(S : U ) of a semigroup S with respect to a subset U ⊆ S is defined to
be the minimum cardinality of a subset V ⊆ S such that S = hU ∪ V i.
Theorem 6.10. Suppose |F| = q < ∞. If 1 ≤ r ≤ min(m, n) and we do not have r = m = n, then
rank(P ) = rank(Reg(MJmn )) = q r(L−r) + 1,
where L = max(m, n).
Proof. Since D is a subsemigroup of P and P \ D is an ideal, it quickly follows that rank(P ) =
rank(D) + rank(P
that a rectangular group R = (S × T ) × G satisfies
 : D). It is well-known [84]r(m−r)
rank(R) = max |S|, |T |, rank(G) . Since D is a q
× q r(n−r) rectangular group with respect to Gr , and
since rank(Gr ) ≤ 2 by Theorem 3.7, it immediately follows that rank(D) = q r(L−r) . Since hDiJ = D 6= P
(as r ≥ 1), we have rank(P : D) ≥ 1, so the proof will be complete if we can show that P = hD ∪ {X}iJ
J
for some X ∈ P . With this in mind, let X ∈ Dr−1
be arbitrary. Note that D = {Y : Y ∈ D} = Gr , and
X ∈ Dr−1 (Mr ). It follows from Theorem 3.7 that Mr = hD ∪ {X}i. Now let Y = [M, A, N ] ∈ P be arbitrary. Choose Z1 , . . . , Zk ∈ D ∪ {X} such that A = Z 1 · · · Z k . Then Y = [M, Ir , N ] ? Z1 ? · · · ? Zk ? [M, Ir , N ],
with [M, Ir , N ] ∈ D.
2
Remark 6.11. If r = 0, then P = {O}, while if r = m = n, then P = Mn . So rank(P ) is trivial
in the former case, and well-known in the latter (see Theorem 3.7). As in Remark 5.3, we deduce that
rank(Reg(Ck (l))) = rank(Reg(Rk (l))) = q l(k−l) + 1 for |F| = q < ∞.

7

The idempotent generated subsemigroup

J
In this section, we investigate the idempotent generated subsemigroup hEJ (MJmn )iJ of MJmn ; we write Emn
J = (P \ D) ∪ E (D)
for this idempotent generated subsemigroup. Our main results include a proof that Emn
J
J
J
and a calculation of rank(Emn ) and idrank(Emn ); in particular, we show that these two values are equal.
Since the solution to every problem we consider is trivial when r = 0, and well-known when r = m = n, we
will continue to assume that r ≥ 1 and that r = m = n does not hold. To simplify notation, we will write
J = hEi . We begin by calculating |E| in the case of finite F, for which
E = EJ (MJmn ) = EJ (P ), so Emn
J
we need the following formulae for |E(Ds (Mr ))|. Although the next result might already be known, we are
unaware of a reference and include a simple proof for convenience.

Lemma 7.1. Suppose |F| = q < ∞. If 0 ≤ s ≤ r, then |E(Ds (Mr ))| = q s(r−s) [ rs ]q . Consequently,
|E(Mr )| =

r
X
s=0

30

q

s(r−s)

 
r
.
s q

Proof. To specify an idempotent endomorphism α ∈ End(Vr ) of rank s, we first choose W = im(α), which
is a subspace of dimension s and may be chosen in [ rs ]q ways, and we note that α must map W identically.
If {v1 , . . . , vr } is an arbitrary basis for Vr , such that {v1 , . . . , vs } is a basis of W , then α may map each of
vs+1 , . . . , vr arbitrarily into W , and there are (q s )r−s ways to choose these images.
2
Proposition 7.2. Suppose |F| = q < ∞. If 0 ≤ s ≤ r, then |EJ (DsJ )| = q s(m+n−r−s) [ rs ]q . Consequently,
|EJ (MJmn )| =

r
X

q s(m+n−r−s)

s=0

 
r
.
s q

J ⊆ D J is a group (so contains an
Proof. Parts (iv) and (v) of Theorem 6.4 say that an H J -class HX
s
idempotent) if and only if HX is a group H -class of Mr , and that there are q s(m−r) × q s(n−r) idempotents
of DsJ corresponding to each rank s idempotent of Mr , of which there are q s(r−s) [ rs ]q by Lemma 7.1. The
result quickly follows.
2

We now describe the idempotent generated subsemigroup of MJmn .
J = hE (MJ )i = (P \ D) ∪ E (D).
Theorem 7.3. We have Emn
J
J
mn J

Proof. Suppose X1 , . . . , Xk ∈ E = EJ (MJmn ), and write Xi = [Mi , Ai , Ni ] for each i. So Ai ∈ E(Mr ) for
each i. Then X1 ? · · · ? Xk = [M1 , A1 · · · Ak , Nk ]. If any of A1 , . . . , Ak belongs to Mr \ Gr , then so too does
A1 · · · Ak , so that X1 ? · · · ? Xk ∈ P \ D. If all of A1 , . . . , Ak belong to Gr , then A1 = · · · = Ak = Ir , so
J ⊆ (P \ D) ∪ E (D). Conversely, it suffices to
X1 ? · · · ? Xk = [M1 , Ir , Nk ] ∈ EJ (D). This shows that Emn
J
J
show that P \ D ⊆ Emn , so suppose X ∈ P \ D, and write X = [M, A, N ]. Since X 6∈ D, we must have
rank(A) = rank(X) < r. But then A ∈ Mr \ Gr , so that A = B1 · · · Bl for some B1 , . . . , Bl ∈ E(Mr ) by
Theorem 3.5. It follows that X = [M, B1 , N ] ? · · · ? [M, Bl , N ], with all [M, Bi , N ] ∈ E.
2
Remark 7.4. Recall (see Theorem 3.5) that En = hE(Mn )i = (Mn \ Gn ) ∪ {In }. Theorem 7.3 is a pleasing
analogue of that result, since {In } = E(Gn ), where Gn is the top D-class of Mn . Also, Gn = G(Mn ) =
RP(Mn ) and, while P has no group of units as it is not a monoid, it is still the case that D = RP(P ).
J , the next natural task is to calculate its
Now that we have described the elements of the semigroup Emn
rank and idempotent rank.

Theorem 7.5. Suppose |F| = q < ∞. Then
J
J
rank(Emn
) = idrank(Emn
) = q r(L−r) + (q r − 1)/(q − 1),

where L = max(m, n).
J ) = rank(E (D)) + rank(E J
Proof. As in the proof of Theorem 6.10, we have rank(Emn
J
mn : EJ (D)).
r(m−r)
r(n−r)
Since EJ (D) is a q
×q
rectangular band (see Lemma 6.9(ii)), we again deduce from [84] that
rank(EJ (D)) = idrank(EJ (D)) = q r(L−r) . So it remains to show that:
J = hE (D) ∪ Ωi , and
(i) there exists a set Ω ⊆ E of size (q r − 1)/(q − 1) such that Emn
J
J
J = hE (D) ∪ Σi , then |Σ| ≥ (q r − 1)/(q − 1).
(ii) if Σ ⊆ P satisfies Emn
J
J

By Theorem 3.5, we may choose some set Γ ⊆ E(Mr ) with hΓi = Mr \ Gr and |Γ| = (q r − 1)/(q − 1).
For each A ∈ Γ, choose any MA ∈ Mm−r,r and NA ∈ Mr,n−r , and put Ω = {[MA , A, NA ] : A ∈ Γ}. Since
J = (P \ D) ∪ E (D), the proof of (i) will be complete if we can show that P \ D ⊆ hE (D) ∪ Ωi . So
Emn
J
J
J
let X = [K, B, L] ∈ P \ D, and write B = A1 · · · Ak where A1 , . . . , Ak ∈ Γ. Then
X = [K, Ir , L] ? [MA1 , A1 , NA1 ] ? · · · ? [MAk , Ak , NAk ] ? [K, Ir , L] ∈ hEJ (D) ∪ ΩiJ ,
31

J = hE (D) ∪ Σi , where Σ ⊆ E J \ E (D) = P \ D. We will show that Σ
as required. Next, suppose Emn
J
J
J
mn
generates Mr \ Gr . Indeed, let A ∈ Mr \ Gr be arbitrary, and choose any X ∈ P such that X = A. Since
J . Consider an expression X = Y ? · · · ? Y , where
rank(X) = rank(A) < r, it follows that X ∈ P \ D ⊆ Emn
1
k
Y1 , . . . , Yk ∈ EJ (D) ∪ Σ. Now, A = X = Y 1 · · · Y k . If any of the Yi belongs to EJ (D), then Y i = Ir , so
the factor Y i is not needed in the product A = Y 1 · · · Y k . After cancelling all such factors, we see that A
is a product of elements from Σ. Since A ∈ Mr \ Gr was arbitrary, we conclude that Mr \ Gr = hΣi. In
particular, |Σ| ≥ |Σ| ≥ rank(Mr \ Gr ) = (q r − 1)/(q − 1), giving (ii).
2

Remark 7.6. As in Remarks 5.3 and 6.11, we deduce from the results of this section that for |F| = q < ∞,
P
• Ck (l) (and Rk (l)) has ls=0 q s(k−s) [ sl ]q idempotents,

• the semigroup generated by E(Ck (l)) (and the semigroup generated by E(Rk (l))) has rank and idempotent rank equal to q l(k−l) + (q l − 1)/(q − 1).

8

Ideals

In this final section, we consider the ideals of P = Reg(MJmn ). In particular, we show that each of the
proper ideals is idempotent generated, and we calculate the rank and idempotent rank, showing that these
are equal. Although the next result is trivial if r = 0 and well-known if r = m = n (see Theorem 3.6), the
statement is valid for those parameters.
Theorem 8.1. The ideals of P = Reg(MJmn ) are precisely the sets
IsJ = D0J ∪ · · · ∪ DsJ = {X ∈ P : rank(X) ≤ s}

for 0 ≤ s ≤ r,

and they form a chain: I0J ⊆ · · · ⊆ IrJ . If 0 ≤ s < r, then IsJ = hEJ (DsJ )iJ is generated by the idempotents
in its top D J -class, and if |F| = q < ∞, then
 
J
J
s(L−r) r
rank(Is ) = idrank(Is ) = q
,
where L = max(m, n).
s q
Proof. For convenience, we will assume that m ≤ n throughout the proof, so that L = n. (The other case
will follow by duality.)
More generally, it may easily be checked that if the J -classes of a semigroup S form a chain, J0 < · · · < Jk ,
then the ideals of S are precisely the sets Ih = J0 ∪ · · · ∪ Jh for 0 ≤ h ≤ k (and these obviously form a chain).
Now suppose 0 ≤ s < r, let Γ ⊆ E(Ds (Mr )) be any idempotent generating set of Is (Mr ) (see Theorem 3.6),
and put ΩΓ = {[M, A, N ] : M ∈ Mm−r,r , A ∈ Γ, N ∈ Mr,n−r }. If X = [M, A, N ] ∈ IsJ is arbitrary, then
A = B1 · · · Bk for some B1 , . . . , Bk ∈ Γ, and it follows that X = [M, B1 , N ] ? · · · ? [M, Bk , N ] ∈ hΩΓ iJ . Since
ΩΓ ⊆ EJ (DsJ ), it follows that IsJ = hEJ (DsJ )iJ .
We now prove the statement about rank and idempotent rank. Suppose Ω is an arbitrary generating set
for IsJ where 0 ≤ s < r. Let X ∈ DsJ and consider an expression X = Y1 ? · · · ? Yk with Y1 , . . . , Yk ∈ Ω. Since
J
X = X ? Z ? X for some Z ∈ DsJ , we may assume that k ≥ 2. Since Is−1
is an ideal of IsJ (we interpret
J
J
J
Is−1 = ∅ if s = 0), each of Y1 , . . . , Yk must belong to Ds = DX . In particular, Yk D J X = (Y1 ? · · · ? Yk−1 ) ? Yk .
By stability, it then follows that Yk L J (Y1 ? · · · ? Yk−1 ) ? Yk = X. Since X ∈ DsJ was arbitrary, it follows
that Ω contains at least one element from each L J -class contained in DsJ , and there are q s(n−r) [ rs ]q such
L J -classes, by Theorem 6.4(vi). It follows that rank(IsJ ) ≥ q s(n−r) [ rs ]q = q s(L−r) [ rs ]q .
Since idrank(S) ≥ rank(S) for any idempotent generated semigroup S, the proof will be complete if we
can find an idempotent generating set of IsJ of the specified size. First, let Γ ⊆ E(Ds (Mr )) be such
that hΓi = Is (Mr ) and |Γ| = [ rs ]q . Fix some A ∈ Γ, and let ∼A and ≈A be the equivalence relations on
Mm−r,r and Mr,n−r defined before Theorem 6.4, and let MA and NA be cross-sections of the equivalence
classes of ∼A and ≈A . Let MA = {M1 , . . . , Mqs(m−r) } and NA = {N1 , . . . , Nqs(n−r) }. (We know MA and
32

NA have the specified sizes by Theorem 6.4.) Put Q = q s(n−r) = q s(L−r) . (Recall that we are assuming
m ≤ n.) Extend MA arbitrarily to MA0 = {M1 , . . . , MQ }. Now put ΩA = {[Mi , A, Ni ] : 1 ≤ i ≤ Q}. If
M ∈ Mm−r,r and N ∈ Mr,n−r are arbitrary, then M ∼ Mi and N ∼ Nj S
for some i, j, and we have
[M, A, N ] = [Mi , A, Nj ] = [Mi , A, Ni ] ? [Mj , A, Nj ] ∈ hΩA iJ . Now put Ω = A∈Γ ΩA . By the previous
discussion, we see that hΩiJ contains ΩΓ , which is a generating set for IsJ (by the first paragraph of this
proof), so IsJ = hΩiJ . Since |Ω| = Q|Γ| = q s(L−r) [ rs ]q , the proof is complete.
2
Remark 8.2. Again, we may deduce a corresponding statement for the ideals of the matrix semigroups
Reg(Ck (l)) and Reg(Rk (l)); the reader may supply the details if they wish.

Acknowledgements
The first named author gratefully acknowledges the support of Grant No. 174019 of the Ministry of Education, Science, and Technological Development of the Republic of Serbia, and Grant No. 1136/2014 of
the Secretariat of Science and Technological Development of the Autonomous Province of Vojvodina. The
authors wish to thank Dr Attila Egri-Nagy for constructing the GAP [67] code that enabled us to produce
the eggbox diagrams from Figures 4, 5, 7 and 8.

References
[1] Jorge Almeida, Stuart Margolis, Benjamin Steinberg, and Mikhail Volkov. Representation theory of finite semigroups,
semigroup radicals and formal language theory. Trans. Amer. Math. Soc., 361(3):1429–1461, 2009.
[2] J. Araújo and J. D. Mitchell. An elementary proof that every singular matrix is a product of idempotent matrices. Amer.
Math. Monthly, 112(7):641–645, 2005.
[3] Richard Brauer. On algebras which are connected with the semisimple continuous groups. Ann. of Math. (2), 38(4):857–872,
1937.
[4] Thomas Breuer, Robert M. Guralnick, and William M. Kantor. Probabilistic generation of finite simple groups. II. J.
Algebra, 320(2):443–494, 2008.
[5] W. P. Brown. Generalized matrix algebras. Canad. J. Math., 7:188–190, 1955.
[6] William P. Brown. The semisimplicity of ωfn . Ann. of Math. (2), 63:324–335, 1956.
[7] Phatsarapa Chanmuang and Ronnason Chinram. Some remarks on regularity of generalized transformation semigroups.
Int. J. Algebra, 2(9-12):581–584, 2008.
[8] Karen Chase. Sandwich semigroups of binary relations. Discrete Math., 28(3):231–236, 1979.
[9] R. Chinram. Green’s relations and regularity of generalized semigroups of linear transformations. Lobachevskii J. Math.,
30(4):253–256, 2009.
[10] Ronnason Chinram. Regularity and Green’s relations of generalized one-to-one partial transformation semigroups. Far
East J. Math. Sci., 30(3):513–521, 2008.
[11] Ronnason Chinram. Regularity and Green’s relations of generalized partial transformation semigroups. Asian-Eur. J.
Math., 1(3):295–302, 2008.
[12] A. H. Clifford. Matrix representations of completely simple semigroups. Amer. J. Math., 64:327–342, 1942.
[13] A. H. Clifford. Basic representations of completely simple semigroups. Amer. J. Math., 82:430–434, 1960.
[14] A. H. Clifford and G. B. Preston. The algebraic theory of semigroups. Vol. I. Mathematical Surveys, No. 7. American
Mathematical Society, Providence, R.I., 1961.
[15] R. J. H. Dawlings. Products of idempotents in the semigroup of singular endomorphisms of a finite-dimensional vector
space. Proc. Roy. Soc. Edinburgh Sect. A, 91(1-2):123–133, 1981/82.
[16] R. J. H. Dawlings. Sets of idempotents that generate the semigroup of singular endomorphisms of a finite-dimensional
vector space. Proc. Edinburgh Math. Soc. (2), 25(2):133–139, 1982.
[17] Jean A. Dieudonné. La géométrie des groupes classiques (in French). Springer-Verlag, Berlin-New York, 1971. Troisième
édition, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 5.
[18] D. Ž. Djoković. Note on a theorem on singular matrices. Canad. Math. Bull., 11:283–284, 1968.
[19] Igor Dolinka and James East. Variants of finite full transformation semigroups. Internat. J. Algebra Comput., 25(8):1187–
1222, 2015.
[20] Igor Dolinka and Robert D. Gray. Maximal subgroups of free idempotent generated semigroups over the full linear monoid.
Trans. Amer. Math. Soc., 366(1):419–455, 2014.
[21] Jie Du and Zongzhu Lin. Stratifying algebras with near-matrix algebras. J. Pure Appl. Algebra, 188(1-3):59–72, 2004.
[22] D. Easdown and T. G. Lavers. The inverse braid monoid. Adv. Math., 186(2):438–455, 2004.
[23] J. East, J. D. Mitchell, and Y. Péresse. Maximal subsemigroups of the semigroup of all mappings on an infinite set. Trans.
Amer. Math. Soc., 367(3):1911–1944, 2015.
[24] Charles Ehresmann. Catégories et structures (in French). Dunod, Paris, 1965.
[25] J. A. Erdos. On products of idempotent matrices. Glasgow Math. J., 8:118–122, 1967.

33

[26] D. G. FitzGerald and Jonathan Leech. Dual symmetric inverse monoids and representation theory. J. Austral. Math. Soc.
Ser. A, 64(3):345–367, 1998.
[27] John Fountain and Andrew Lewin. Products of idempotent endomorphisms of an independence algebra of finite rank.
Proc. Edinburgh Math. Soc. (2), 35(3):493–500, 1992.
[28] Olexandr Ganyushkin and Volodymyr Mazorchuk. Classical finite transformation semigroups, an introduction, volume 9
of Algebra and Applications. Springer-Verlag London, Ltd., London, 2009.
[29] Olexandr Ganyushkin, Volodymyr Mazorchuk, and Benjamin Steinberg. On the irreducible representations of a finite
semigroup. Proc. Amer. Math. Soc., 137(11):3585–3592, 2009.
[30] Fabio Gavarini. On the radical of Brauer algebras. Math. Z., 260(3):673–697, 2008.
[31] Nick Gill. On a conjecture of Degos. Preprint, 2015, arXiv:1502.03341.
[32] Gracinda Gomes and John M. Howie. On the ranks of certain finite semigroups of transformations. Math. Proc. Cambridge
Philos. Soc., 101(3):395–403, 1987.
[33] R. Gray. Hall’s condition and idempotent rank of ideals of endomorphism monoids. Proc. Edinb. Math. Soc. (2), 51(1):57–
72, 2008.
[34] R. Gray and N. Ruškuc. Maximal subgroups of free idempotent-generated semigroups over the full transformation monoid.
Proc. Lond. Math. Soc. (3), 104(5):997–1018, 2012.
[35] Nicolas Guay and Stewart Wilcox. Almost cellular algebras. J. Pure Appl. Algebra, 219(9):4105–4116, 2015.
[36] Robert M. Guralnick and William M. Kantor. Probabilistic generation of finite simple groups. J. Algebra, 234(2):743–792,
2000. Special issue in honor of Helmut Wielandt.
[37] T. E. Hall. The radical of the algebra of any finite semigroup over any field. J. Austral. Math. Soc., 11:350–352, 1970.
[38] J. B. Hickey. Semigroups under a sandwich operation. Proc. Edinburgh Math. Soc. (2), 26(3):371–382, 1983.
[39] J. B. Hickey. On variants of a semigroup. Bull. Austral. Math. Soc., 34(3):447–459, 1986.
[40] Peter M. Higgins. Techniques of semigroup theory. Oxford Science Publications. The Clarendon Press, Oxford University
Press, New York, 1992.
[41] Christopher Hollings. The Ehresmann-Schein-Nambooripad theorem and its successors. Eur. J. Pure Appl. Math., 5(4):414–
450, 2012.
[42] J. M. Howie. The subsemigroup generated by the idempotents of a full transformation semigroup. J. London Math. Soc.,
41:707–716, 1966.
[43] J. M. Howie. Idempotent generators in finite full transformation semigroups. Proc. Roy. Soc. Edinburgh Sect. A, 81(34):317–323, 1978.
[44] John M. Howie. Fundamentals of semigroup theory, volume 12 of London Mathematical Society Monographs. New Series.
The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications.
[45] John M. Howie and Robert B. McFadden. Idempotent rank in finite full transformation semigroups. Proc. Roy. Soc.
Edinburgh Sect. A, 114(3-4):161–167, 1990.
[46] John M. Howie, N. Ruškuc, and P. M. Higgins. On relative ranks of full transformation semigroups. Comm. Algebra,
26(3):733–748, 1998.
[47] Zur Izhakian, John Rhodes, and Benjamin Steinberg. Representation theory of finite semigroups over semirings. J. Algebra,
336:139–157, 2011.
[48] R. Jongchotinon, S. Chaopraknoi, and Y. Kemprasit. Isomorphism theorems for variants of semigroups of linear transformations. Int. J. Algebra, 4(25-28):1407–1412, 2010.
[49] Yupaporn Kemprasit. Regularity and unit-regularity of generalized semigroups of linear transformations. Southeast Asian
Bull. Math., 25(4):617–622, 2002.
[50] T. A. Khan and M. V. Lawson. Variants of regular semigroups. Semigroup Forum, 62(3):358–374, 2001.
[51] Steffen König and Changchang Xi. On the structure of cellular algebras. In Algebras and modules, II (Geiranger, 1996),
volume 24 of CMS Conf. Proc., pages 365–386. Amer. Math. Soc., Providence, RI, 1998.
[52] Steffen König and Changchang Xi. A characteristic free approach to Brauer algebras. Trans. Amer. Math. Soc., 353(4):1489–
1505, 2001.
[53] Thomas J. Laffey. Products of idempotent matrices. Linear and Multilinear Algebra, 14(4):309–314, 1983.
[54] Gérard Lallement and Mario Petrich. Irreducible matrix representations of finite semigroups. Trans. Amer. Math. Soc.,
139:393–412, 1969.
[55] Yanbo Li and Feng Wei. Semi-centralizing maps of generalized matrix algebras. Linear Algebra Appl., 436(5):1122–1153,
2012.
[56] Markus Linckelmann and Michal Stolorz. On simple modules over twisted finite category algebras. Proc. Amer. Math.
Soc., 140(11):3725–3737, 2012.
[57] E. S. Lyapin. Semigroups (in Russian). Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow, 1960.
[58] K. D. Magill, Jr. and S. Subbiah. Green’s relations for regular elements of sandwich semigroups. I. General results. Proc.
London Math. Soc. (3), 31(2):194–210, 1975.
[59] K. D. Magill, Jr. and S. Subbiah. Green’s relations for regular elements of sandwich semigroups. II. Semigroups of continuous
functions. J. Austral. Math. Soc. Ser. A, 25(1):45–65, 1978.
[60] Kenneth D. Magill, Jr. Semigroup structures for families of functions. I. Some homomorphism theorems. J. Austral. Math.
Soc., 7:81–94, 1967.
[61] Paul Martin. Temperley-Lieb algebras for nonplanar statistical mechanics—the partition algebra construction. J. Knot
Theory Ramifications, 3(1):51–82, 1994.
[62] D. B. McAlister. The category of representations of a completely 0-simple semigroup. J. Austral. Math. Soc., 12:193–210,
1971.
[63] D. B. McAlister. Rings related to completely 0-simple semigroups. J. Austral. Math. Soc., 12:257–274, 1971.

34

[64] Donald B. McAlister. Representations of semigroups by linear transformations. I, II. Semigroup Forum 2 (1971), no. 3,
189–263; ibid., 2(4):283–320, 1971.
[65] Suzana Mendes-Gonçalves and R. P. Sullivan. Regular elements and Green’s relations in generalized transformation
semigroups. Asian-Eur. J. Math., 6(1):1350006, 11, 2013.
[66] Suzana Mendes-Gonçalves and R. P. Sullivan. Regular elements and Green’s relations in generalised linear transformation
semigroups. Southeast Asian Bull. Math., 38(1):73–82, 2014.
[67] J. D. Mitchell. The Semigroups package for GAP, Version 2.1. http://tinyurl.com/semigroups, 2014.
[68] W. D. Munn. On semigroup algebras. Proc. Cambridge Philos. Soc., 51:1–15, 1955.
[69] W. D. Munn. Matrix representations of semigroups. Proc. Cambrdige Philos. Soc., 53:5–12, 1957.
[70] W. D. Munn. Irreducible matrix representations of semigroups. Quart. J. Math. Oxford Ser. (2), 11:295–309, 1960.
[71] Attila Nagy. Special classes of semigroups, volume 1 of Advances in Mathematics (Dordrecht). Kluwer Academic Publishers,
Dordrecht, 2001.
[72] S. Nenthein and Y. Kemprasit. Regular elements of some semigroups of linear transformations and matrices. Int. Math.
Forum, 2(1-4):155–166, 2007.
[73] Jan Okniński. Semigroup algebras, volume 138 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel
Dekker, Inc., New York, 1991.
[74] Jan Okniński. Semigroups of matrices, volume 6 of Series in Algebra. World Scientific Publishing Co., Inc., River Edge,
NJ, 1998.
[75] Jan Okniński and Mohan S. Putcha. Complex representations of matrix semigroups. Trans. Amer. Math. Soc., 323(2):563–
581, 1991.
[76] I. S. Ponizovskiı̆. On matrix representations of associative systems. Mat. Sb. N.S., 38(80):241–260, 1956.
[77] Mohan S. Putcha. Linear algebraic monoids, volume 133 of London Mathematical Society Lecture Note Series. Cambridge
University Press, Cambridge, 1988.
[78] Mohan S. Putcha. Complex representations of finite monoids. Proc. London Math. Soc. (3), 73(3):623–641, 1996.
[79] Mohan S. Putcha. Complex representations of finite monoids. II. Highest weight categories and quivers. J. Algebra,
205(1):53–76, 1998.
[80] Mohan S. Putcha. Products of idempotents in algebraic monoids. J. Aust. Math. Soc., 80(2):193–203, 2006.
[81] D. Rees. On semi-groups. Proc. Cambridge Philos. Soc., 36:387–400, 1940.
[82] Lex E. Renner. Linear algebraic monoids, volume 134 of Encyclopaedia of Mathematical Sciences. Springer-Verlag, Berlin,
2005. Invariant Theory and Algebraic Transformation Groups, V.
[83] John Rhodes and Benjamin Steinberg. The q-theory of finite semigroups. Springer Monographs in Mathematics. Springer,
New York, 2009.
[84] N. Ruškuc. On the rank of completely 0-simple semigroups. Math. Proc. Cambridge Philos. Soc., 116(2):325–338, 1994.
[85] Benjamin Steinberg. Möbius functions and semigroup representation theory. J. Combin. Theory Ser. A, 113(5):866–881,
2006.
[86] Benjamin Steinberg. Möbius functions and semigroup representation theory. II. Character formulas and multiplicities. Adv.
Math., 217(4):1521–1557, 2008.
[87] Benjamin Steinberg. The representation theory of finite monoids. Universitext. Springer, In press.
[88] R. P. Sullivan. Generalised partial transformation semigroups. J. Austral. Math. Soc., 19(part 4):470–473, 1975.
[89] R. P. Sullivan. Semigroups of linear transformations with restricted range. Bull. Aust. Math. Soc., 77(3):441–453, 2008.
[90] R. P. Sullivan. Generalised transformation semigroups. Preprint, 2013.
[91] Melvin C. Thornton. Regular elements in sandwich semigroups of binary relations. Discrete Math., 41(3):303–307, 1982.
[92] R. M. Thrall. A class of algebras without unity element. Canad. J. Math., 7:382–390, 1955.
[93] Amorn Wasanawichit and Yupaporn Kemprasit. Dense subsemigroups of generalised transformation semigroups. J. Aust.
Math. Soc., 73(3):433–445, 2002.
[94] William C. Waterhouse. Two generators for the general linear groups over finite fields. Linear and Multilinear Algebra,
24(4):227–230, 1989.
[95] Hermann Weyl. The Classical Groups. Their Invariants and Representations. Princeton University Press, Princeton, N.J.,
1939.
[96] Zhankui Xiao and Feng Wei. Commuting mappings of generalized matrix algebras. Linear Algebra Appl., 433(11-12):2178–
2197, 2010.
[97] Zhankui Xiao and Feng Wei. Commuting traces and Lie isomorphisms on generalized matrix algebras. Oper. Matrices,
8(3):821–847, 2014.
[98] Miyuki Yamada. A note on middle unitary semigroups. Kōdai Math. Sem. Rep., 7:49–52, 1955.

35

