Length of the inverse symmetric semigroup
The length of the lattice of subsemigroups of the inverse symmetric semigroup ISn is calculated.
Gespeichert in:
| Datum: | 2011 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2011
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/154767 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Length of the inverse symmetric semigroup / O. Ganyushkin, I. Livinsky // Algebra and Discrete Mathematics. — 2011. — Vol. 12, № 2. — С. 64–71. — Бібліогр.: 4 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154767 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1547672019-06-16T01:31:51Z Length of the inverse symmetric semigroup Ganyushkin, O. Livinsky, I. The length of the lattice of subsemigroups of the inverse symmetric semigroup ISn is calculated. 2011 Article Length of the inverse symmetric semigroup / O. Ganyushkin, I. Livinsky // Algebra and Discrete Mathematics. — 2011. — Vol. 12, № 2. — С. 64–71. — Бібліогр.: 4 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:20M18, 20M10. http://dspace.nbuv.gov.ua/handle/123456789/154767 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The length of the lattice of subsemigroups of the inverse symmetric
semigroup ISn is calculated. |
| format |
Article |
| author |
Ganyushkin, O. Livinsky, I. |
| spellingShingle |
Ganyushkin, O. Livinsky, I. Length of the inverse symmetric semigroup Algebra and Discrete Mathematics |
| author_facet |
Ganyushkin, O. Livinsky, I. |
| author_sort |
Ganyushkin, O. |
| title |
Length of the inverse symmetric semigroup |
| title_short |
Length of the inverse symmetric semigroup |
| title_full |
Length of the inverse symmetric semigroup |
| title_fullStr |
Length of the inverse symmetric semigroup |
| title_full_unstemmed |
Length of the inverse symmetric semigroup |
| title_sort |
length of the inverse symmetric semigroup |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2011 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154767 |
| citation_txt |
Length of the inverse symmetric semigroup / O. Ganyushkin, I. Livinsky // Algebra and Discrete Mathematics. — 2011. — Vol. 12, № 2. — С. 64–71. — Бібліогр.: 4 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT ganyushkino lengthoftheinversesymmetricsemigroup AT livinskyi lengthoftheinversesymmetricsemigroup |
| first_indexed |
2025-07-14T06:52:33Z |
| last_indexed |
2025-07-14T06:52:33Z |
| _version_ |
1837604225815674880 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 12 (2011). Number 2. pp. 64 – 71
c© Journal “Algebra and Discrete Mathematics”
Length of the inverse symmetric semigroup
Olexandr Ganyushkin and Ivan Livinsky
Communicated by V. Mazorchuk
Abstract. The length of the lattice of subsemigroups of the
inverse symmetric semigroup ISn is calculated.
1. Introduction
In the theory of inverse semigroups the inverse symmetric semigroup
IS(M) plays a role similar to the role of the symmetric group in group
theory. Especially interesting is the case |M | = n < ∞, since apart from
specific semigroup problems, a lot of combinatorial problems arise there.
A great number of papers, and even specialized monographs (see [1], [2]
and literature cited there) are dedicated to the study of the semigroup
ISn.
An essential question in the study of any semigroup is about the
structure of the lattice of its subsemigroups. Although such lattices were
studied actively (see e.g., [3]), not very much is known about the structure
of lattices of subsemigroups of particular semigroups. The main reason is
that lattices of subsemigroups have quite a complex structure. Even for
monogenic semigroups this question is nontrivial. For groups, it is hard
too: the paper [4] uses the classification of finite simple groups to calculate
the length of the lattice of subgroups of the symmetric group Sn.
In the case of ISn a little is known as well. Though the lattice of
two-sided ideals of ISn is quite simple (a chain of length n), the structure
of the lattice of left (right) ideals is considerably more complex (see [2,
2000 Mathematics Subject Classification: 20M18, 20M10.
Key words and phrases: length of a semigroup, inverse semigroup, semigroup,
Brandt semigroup.
O. Ganyushkin, I. Livinsky 65
Chapter 4.3]). Clearly, additional difficulties arise when considering the
lattice of all subsemigroups.
Recall that the length l(S) of a semigroup S is defined as the length
of its lattice of subsemigroups, i.e., the maximal integer n, for which there
exists a strictly increasing chain of subsemigroups
∅ 6= H0 ⊂ H1 ⊂ H2 ⊂ · · · ⊂ Hn = S. (1)
The objective of the present paper is the calculation of the length of
the inverse symmetric semigroup ISn (Theorem 8). As an auxiliary result,
a description of maximal subsemigroups of a finite Brandt semigroup is
obtained (Theorem 6).
In this paper only finite semigroups and groups are considered.
2. The main Lemma
Lemma 1. For every ideal I of a finite semigroup S the following equality
holds
l(S) = l(I) + l(S/I) , (2)
where S/I denotes the Rees quotient modulo the ideal I.
Proof. Let S be a finite semigroup and I an ideal of S. Assume that (1)
gives a longest chain of subsemigroups in S. First we prove that for every
extension Hk ⊂ Hk+1 the set Hk+1 rHk either is a subset of the ideal I
or is disjoint with it. Indeed, if this is not the case, we would have the
strict inclusions
Hk ⊂ Hk ∪ (Hk+1 ∩ I) ⊂ Hk+1 . (3)
The subsemigroup Hk+1 ∩ I is an ideal of Hk+1; therefore, the set Hk ∪
(Hk+1 ∩ I), being a union of an ideal and a subsemigroup, would be a
subsemigroup too. Then (3) would contradict the maximality of chain (1).
Extend chain (1) by the empty subsemigroup H−1 = ∅ and transform
the chain
H−1 = ∅ ⊂ H0 ⊂ H1 ⊂ H2 ⊂ · · · ⊂ Hn = S (4)
in the following way: if this chain contains a fragment Hk−1 ⊂ Hk ⊂ Hk+1,
where Hk rHk−1 * I and Hk+1 rHk ⊆ I, replace it by the fragment
Hk−1 ⊂ Hk−1 ∪ (Hk+1 ∩ I) ⊂ Hk+1
(strictness of the inclusions is obvious, and, similarly to the above, one
shows that the set Hk−1 ∪ (Hk+1 ∩ I) is a subsemigroup). By a finite
number of such transformations we get the chain
H−1 = ∅ ⊂ H ′
0 ⊂ H ′
1 ⊂ H ′
2 ⊂ · · · ⊂ H ′
n−1 ⊂ Hn = S , (5)
66 Length of the inverse symmetric semigroup
in which all extensions by the elements of ideal I come first, followed by
extensions by elements of S r I. From this property and maximality of
chain (5) it follows that for some m equality H ′
m = I must hold. Thus,
from (5) we get the chain
∅ ⊂ H ′
0 ⊂ H ′
1 ⊂ H ′
2 ⊂ · · · ⊂ H ′
m
of subsemigroups of I and the chain
0 = I/I = H ′
m/I ⊂ H ′
m+1/I ⊂ · · · ⊂ H ′
n−1/I ⊂ Hn/I = S/I
of subsemigroups of S/I. From the definition of Rees quotient it follows
that in the last chain all extensions are strict too. This gives us the
inequality l(S) ≤ l(I) + l(S/I).
The opposite inequality follows from the following fact: if
∅ 6= H0 ⊂ H1 ⊂ · · · ⊂ Hp = I and ∅ 6= K0 ⊂ K1 ⊂ · · · ⊂ Kq = S/I
are chains of subsemigroups for I and S/I correspondingly, and π : S →
S/I is the canonical epimorphism, then
∅ 6= H0 ⊂ H1 ⊂ · · · ⊂ Hp ⊆ π−1(K0) ⊂ π−1(K1) ⊂ · · · ⊂ π−1(Kq) = S
is a chain of subsemigroups for S.
3. The length of the Brandt semigroup
Recall that the Brandt semigroup B(n,G) over a group G is the
semigroup of all matrices of dimension n, all entries of which are zero,
except for at most one entry which is supposed to be an element of
G. The matrix, in which an element g ∈ G is in k-th row and l-th
column, is denoted by (g)kl. The zero matrix is the zero in B(n,G) and
the multiplication of nonzero elements from B(n,G) is the usual matrix
multiplication: (g)kl · (h)pq is equal to (gh)kq if l = p, and to 0 otherwise.
We will use the following notation: e is the unit of the group G; for
an arbitrary subset H ⊆ G denote by (H)kl the set {(h)kl | h ∈ H}; for
an arbitrary subset S ⊆ B(n,G) denote Skl = S ∩ (G)kl.
For an arbitrary subgroup H ≤ G and elements g1 = e, g2, . . . , gn of
G define S(H; g2, . . . , gn) by
S(H; g2, . . . , gn) =
(
⋃
k,l
(g−1
k Hgl)kl
)
∪ {0} . (6)
Lemma 2. For an arbitrary subgroup H ≤ G and elements g1 = e, g2,
. . . , gn of G the set S(H; g2, . . . , gn) is a subsemigroup of the semigroup
B(n,G).
O. Ganyushkin, I. Livinsky 67
Proof. That S(H; g2, . . . , gn) is closed under multiplication is verified by
a direct calculation.
Lemma 3. Let S be a subsemigroup of B(n,G) such that for every k
and l S ∩ (G)kl 6= ∅. Then S is equal to S(H; g2, . . . , gn) for some
g2, . . . , gn.
Proof. Let S be a subsemigroup of B(n,G) such that Skl 6= ∅ for arbitrary
k and l. In every Skl choose an element skl = (gkl)kl. Obviously, S11 is
a subgroup in B(n,G); thus, S11 is equal to (H)11, where H is some
subgroup of G. In particular, we can take g11 = e. From the inequalities
slk · Skk · skl ⊆ Sll, Skk · skl ⊆ Skl, Skl · slk ⊆ Skk (7)
it follows that all of the sets Skl are equinumerous. Hence, inclusions (7)
are equalities.
Since s1ksk1 ∈ S11, then g1kgk1 ∈ H . From the equality Sk1 = sk1 ·S11
it follows that, replacing gk1 by gk1 · (g1kgk1)
−1, we can assume gk1 = g−1
1k .
Then, from the equality Skl = sk1 ·S11 ·s1l it follows that Skl = (g−1
1k Hg1l)kl
and the subsemigroup S is equal to S(H; g2, . . . , gn), where gi = g1i,
2 ≤ i ≤ n.
Corollary 4. The semigroup S(H; g2, . . . , gn) is isomorphic to the semi-
group B(n,H).
Proof. The map (g−1
k hgl)kl 7→ (h)kl is an isomorphism between
S(H; g2, . . . , gn) and B(n,H).
For arbitrary subsets K,L ⊆ {1, 2, . . . , n} denote
S(K,L) = B(n,G) \
⋃
i∈K,j∈L
(G)ij . (8)
Lemma 5. If sets K and L form a covering of the set {1, 2, . . . , n}, then
S(K,L) is a subsemigroup of the semigroup B(n,G).
Proof. If S(K,L) is not a subsemigroup, then there exist non-zero elements
(g)pq, (h)rt ∈ S(K,L) such that (g)pq · (h)rt 6∈ S(K,L). But then p ∈ K,
q 6∈ L, t ∈ L, r 6∈ K and q = r, which is impossible.
Theorem 6. Let n > 1 and G be a finite group. A subsemigroup S of
a Brandt semigroup B(n,G) is maximal if and only if either it is equal
to the subsemigroup S(H; g2, . . . , gn), where H is a maximal subgroup of
the group G, or to the subsemigroup S(K,L), where sets K and L form a
partition of the set {1, 2, . . . , n}.
68 Length of the inverse symmetric semigroup
Proof. Let S be a subsemigroup of B(n,G). There are two possible cases.
I. For arbitrary k and l we have Skl 6= ∅. Then, by Lemma 3, S is
equal to some S(H; g2, . . . , gn). From the statement that all sets Skl are
equinumerous it follows that S(H; g2, . . . , gn) is a maximal subsemigroup
of B(n,G) if and only if H is a maximal subgroup of G.
II. There exist k and l such that Skl = ∅. Since from Sij 6= ∅ and
Sji 6= ∅ it follows that Sii ⊇ Sij · Sji 6= ∅, we can assume that k 6= l.
Denote
K = {p | Skp 6= ∅} ∪ {k}, L = {q | Sql 6= ∅} ∪ {l} .
Sets K and L do not intersect. Indeed, if i ∈ K ∩ L, then for arbitrary
(g)ki ∈ Ski and (h)il ∈ Sil we have (gh)kl ∈ Skl, which contradicts to the
condition Skl = ∅.
Note, that for arbitrary i ∈ K, j ∈ L we have Sij = ∅. Indeed, for Skj
and Sil this follows from the definition of the sets K and L. If i ∈ Kr{k},
j ∈ Lr {l}, this follows from the inclusion Ski · Sij · Sjl ⊆ Skl.
Show that if S is a maximal subsemigroup, then K ∪ L = {1, . . . , n}.
Indeed, let m ∈ {1, . . . , n} r (K ∪ L). Assume that there exists p ∈ K
such that Spm 6= ∅. Then S is a proper subset of the subsemigroup
S1 = 〈S, (G)km〉. On the other hand, from the inclusion Spm · Smq ⊆ Spq
it follows that Smq = ∅ for all q ∈ L. Thus, S1 does not contain elements
of (G)kl, i.e. it is a proper subsemigroup of B(n,G). If for all p ∈ K we
have Spm = ∅, then by the same argument it can be proved that S is a
proper subsemigroup of 〈S, (G)ml〉.
Therefore, if S is a maximal subsemigroup, then K and L form a
partition of the set {1, 2, . . . , n}. Since S is a subset of S(K,L), it must
be equal to the last one, i.e. S = S(K,L).
It is left to show that, if K and L form a partition, then the subsemi-
group S(K,L) is maximal. Indeed, S(K,L) cannot be a subset of any
other subsemigroup of this kind. Thus, if S∗ % S(K,L), then S∗
kl 6= ∅ for
arbitrary k and l, and by Lemma 3, S∗ is equal to some subsemigroup
S(H; g2, . . . , gn). But S∗
11 = (G)11, so H = G and S(H; g2, . . . , gn) =
B(n,G).
We denote by G0 the group G with a zero adjoint.
Theorem 7. For a finite group G
l(B(n,G)) = n · l(G0) +
n(n− 1)
2
|G|+ n− 1. (9)
Proof. We use induction on the parameter n. Since B(1, G) ≃ G0, then
for n = 1 equality (9) is true.
O. Ganyushkin, I. Livinsky 69
Now, assume that equality (9) is proved for all semigroups B(m,G),
where m < n. From Theorem 6 it follows that l(B(n,G)) is equal
to 1 + l(S(K,L)) for some partition K ∪ L = {1, 2, . . . , n}, or to 1 +
l(S(H; g2, . . . , gn)) for some maximal subgroup H < G.
Let us determine l(S(K,L)) for |K| = p, |L| = q, p+ q = n. To this
end, consider three subsets of S(K,L):
SK = {0} ∪
⋃
i,j∈K
(G)ij , SL = {0} ∪
⋃
i,j∈L
(G)ij , I = {0} ∪
⋃
i∈L,j∈K
(G)ij .
It is obvious that each of these subsets is a subsemigroup; in particular,
SK ≃ B(p,G), SL ≃ B(q,G), and I is a subsemigroup with zero multi-
plication. Moreover, S(K,L) = SK ∪ SL ∪ I. It is easy to check that I
is an ideal in S(K,L), and the Rees quotient S(K,L)/I is isomorphic to
SK ∪ SL. In turn, in the semigroup SK ∪ SL both subsemigroup SK and
SL are ideals with the following property: Rees quotient modulo SK is
isomorphic to SL and, vice versa, Rees quotient modulo SL is isomorphic
to SK . Therefore, by Lemma 1
l(S(K,L)) = l(I) + l(SK ∪ SL) = l(I) + l(SK) + l(SL) . (10)
Since for a semigroup T with zero multiplication we have l(T ) = |T | − 1,
by the inductive hypothesis we get:
l(S(K,L)) = pq|G|+
(
p · l(G0) +
p(p− 1)
2
|G|+ p− 1
)
+
+
(
q · l(G0) +
q(q − 1)
2
|G|+ q − 1
)
= n · l(G0) +
n(n− 1)
2
|G|+ n− 2.
In particular, l(S(K,L)) does not depend on the choice of K and L.
To complete the proof of the Theorem we need to show that
l(B(n,G)) = l(S(K,L)) + 1 . (11)
We will do this by induction on the order of the group G. Equality (11)
is obvious if |G| = 1, because in this case every maximal subsemigroup
of B(n,G) is isomorphic to S(K,L). Assume now that (11) holds for all
groups of order t. Let t < |G| ≤ 2t and H be a maximal subgroup of
G, then |H| ≤ |G|/2 ≤ t. Since S(H; g2, . . . , gn) ≃ B(n,H), then by the
inductive hypothesis
l(S(H; g2, . . . , gn)) = n · l(H0) +
n(n− 1)
2
|H|+ n− 1 ,
what clearly is less than l(S(K,L)). This completes the proof of the
equality (11).
70 Length of the inverse symmetric semigroup
4. Length of ISn
Theorem 8. The length of the inverse symmetric semigroup ISn is equal
to
l(ISn) =
n
∑
k=1
[(
n
k
)(⌈
3k
2
⌉
− b(k) + 1
)
+
(
n
k
)((
n
k
)
− 1
)
2
· k!− 1
]
,
where we denote by ⌈x⌉ the least integer, which is not less than x, and by
b(k) the number of nonzero digits in the binary expansion of k.
Proof. It is known that semigroup ISn has n + 1 ideals [2, Chapter 4],
which form the chain
{0} = I0 ⊂ I1 ⊂ I2 ⊂ · · · ⊂ In = ISn .
For every k, 1 ≤ k ≤ n, the Rees quotient Ik/Ik−1 is isomorphic to the
Brandt semigroup B
((
n
k
)
, Sk
)
, where Sk is the symmetric group of degree
k. Thus, from Lemma 1 and Theorem 7 it follows that the length of
semigroup ISn is equal to
l(ISn) =
n
∑
k=1
l(Ik/Ik−1) =
n
∑
k=1
l
(
B
((
n
k
)
, Sk
))
=
n
∑
k=1
[(
n
k
)
· l(S0
k) +
(
n
k
)
(
(
n
k
)
− 1)
2
|Sk|+
(
n
k
)
− 1
]
.
(12)
In the paper [4] it is proved that l(Sk) =
⌈
3k
2
⌉
− b(k) − 1. Therefore,
l(S0
k) = l(Sk)+ 1 =
⌈
3k
2
⌉
− b(k). Moreover, |Sk| = k!. Putting these values
into (12), we get the statement of the Theorem.
References
[1] Lipscomb S. Symmetric Inverse Semirgoups. Math. Surveys and Monographs, 46,
AMS, Providence, RI, 1996.
[2] Ganyushkin O., Mazorchuk V. Classical Finite Transformation semigroups. An
Introduction. Algebra and Applications, 9, Springer–Verlag, London, 2009.
[3] Shevrin L.N., Ovsyannikov A.Ya. Semigroups and their subsemigroup lattices.
Kluver Academic Publishers, 1996.
[4] Cameron P.I., Solomon R.G., Turul A. Chains of Subgroups in Symmetric Groups
// J. Algebra. — 1989. — Vol. 127. — P. 340–352
O. Ganyushkin, I. Livinsky 71
Contact information
O. Ganyushkin Department of Mechanics and Mathemat-
ics, Kyiv Taras Shevchenko University, 64,
Volodymyrska st. 01033, Kyiv, UKRAINE
E-Mail: ganiushk@univ.kiev.ua
I. Livinsky Department of Mathematics, University of Man-
itoba, 186 Dysart Road, R3T2N2, Winnipeg,
CANADA
E-Mail: umlivini@cc.umanitoba.ca
Received by the editors: 26.10.2011
and in final form 17.12.2011.
|