<html><head><title>[ref] 49 Semigroups</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP048.htm">Previous</a>] [<a href ="CHAP050.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>49 Semigroups</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP049.htm#SECT001">Making transformation semigroups</a>
<li> <A HREF="CHAP049.htm#SECT002">Ideals of semigroups</a>
<li> <A HREF="CHAP049.htm#SECT003">Congruences for semigroups</a>
<li> <A HREF="CHAP049.htm#SECT004">Quotients</a>
<li> <A HREF="CHAP049.htm#SECT005">Green's Relations</a>
<li> <A HREF="CHAP049.htm#SECT006">Rees Matrix Semigroups</a>
</ol><p>
<p>
This chapter describes functions for creating semigroups
and determining information about them.
<p>
<a name = ""></a>
<li><code>IsSemigroup( </code><var>D</var><code> ) P</code>
<p>
returns <code>true</code> if the object <var>D</var> is a semigroup.
<a name = "I0"></a>
A <strong>semigroup</strong> is a magma (see <a href="CHAP033.htm">Magmas</a>) with associative multiplication.
<p>
<a name = ""></a>
<li><code>Semigroup( </code><var>gen1</var><code>, </code><var>gen2</var><code> ... ) F</code>
<a name = ""></a>
<li><code>Semigroup( </code><var>gens</var><code> ) F</code>
<p>
In the first form, <code>Semigroup</code> returns the semigroup generated by the
arguments <var>gen1</var>, <var>gen2</var>, ...,
that is, the closure of these elements under multiplication.
In the second form, <code>Semigroup</code> returns the semigroup generated by the
elements in the homogeneous list <var>gens</var>;
a square matrix as only argument is treated as one generator,
not as a list of generators.
<p>
It is <strong>not</strong> checked whether the underlying multiplication is associative,
use <code>Magma</code> (see <a href="CHAP033.htm#SSEC002.1">Magma</a>) and <code>IsAssociative</code> (see <a href="CHAP033.htm#SSEC004.7">IsAssociative</a>)
if you want to check whether a magma is in fact a semigroup.
<p>
<pre>
gap> a:= Transformation([2, 3, 4, 1]);
Transformation( [ 2, 3, 4, 1 ] )
gap> b:= Transformation([2, 2, 3, 4]);
Transformation( [ 2, 2, 3, 4 ] )
gap> s:= Semigroup(a, b);
<semigroup with 2 generators>
</pre>
<p>
<a name = ""></a>
<li><code>Subsemigroup( </code><var>S</var><code>, </code><var>gens</var><code> ) F</code>
<a name = ""></a>
<li><code>SubsemigroupNC( </code><var>S</var><code>, </code><var>gens</var><code> ) F</code>
<p>
are just synonyms of <code>Submagma</code> and <code>SubmagmaNC</code>, respectively
(see <a href="CHAP033.htm#SSEC002.7">Submagma</a>).
<p>
<pre>
gap> a:=GeneratorsOfSemigroup(s)[1];
Transformation( [ 2, 3, 4, 1 ] )
gap> t:=Subsemigroup(s,[a]);
<semigroup with 1 generator>
</pre>
<p>
<a name = ""></a>
<li><code>SemigroupByGenerators( </code><var>gens</var><code> ) O</code>
<p>
is the underlying operation of <code>Semigroup</code> (see <a href="CHAP049.htm">Semigroup</a>).
<p>
<a name = ""></a>
<li><code>AsSemigroup( </code><var>C</var><code> ) A</code>
<p>
If <var>C</var> is a collection whose elements form a semigroup
(see <a href="CHAP049.htm">IsSemigroup</a>) then <code>AsSemigroup</code> returns this semigroup.
Otherwise <code>fail</code> is returned.
<p>
<a name = ""></a>
<li><code>AsSubsemigroup( </code><var>D</var><code>, </code><var>C</var><code> ) O</code>
<p>
Let <var>D</var> be a domain and <var>C</var> a collection.
If <var>C</var> is a subset of <var>D</var> that forms a semigroup then <code>AsSubsemigroup</code>
returns this semigroup, with parent <var>D</var>.
Otherwise <code>fail</code> is returned.
<p>
<a name = ""></a>
<li><code>GeneratorsOfSemigroup( </code><var>S</var><code> ) A</code>
<p>
Semigroup generators of a semigroup <var>D</var> are the same as magma generators
(see <a href="CHAP033.htm#SSEC004.1">GeneratorsOfMagma</a>).
<p>
<pre>
gap> GeneratorsOfSemigroup(s);
[ Transformation( [ 2, 3, 4, 1 ] ), Transformation( [ 2, 2, 3, 4 ] ) ]
gap> GeneratorsOfSemigroup(t);
[ Transformation( [ 2, 3, 4, 1 ] ) ]
</pre>
<p>
<a name = ""></a>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code> ) F</code>
<a name = ""></a>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code>, </code><var>name</var><code> ) F</code>
<a name = ""></a>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>name1</var><code>, </code><var>name2</var><code>, ... ) F</code>
<a name = ""></a>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>names</var><code> ) F</code>
<a name = ""></a>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]infinity, </code><var>name</var><code>, </code><var>init</var><code> ) F</code>
<p>
Called in the first form, <code>FreeSemigroup</code> returns a free semigroup on
<var>rank</var> generators.
Called in the second form, <code>FreeSemigroup</code> returns a free semigroup on
<var>rank</var> generators, printed as <code></code><var>name</var><code>1</code>, <code></code><var>name</var><code>2</code> etc.,
that is, each name is the concatenation of the string <var>name</var> and an
integer from <code>1</code> to <var>range</var>.
Called in the third form, <code>FreeSemigroup</code> returns a free semigroup on
as many generators as arguments, printed as <var>name1</var>, <var>name2</var> etc.
Called in the fourth form, <code>FreeSemigroup</code> returns a free semigroup on
as many generators as the length of the list <var>names</var>, the <i>i</i>-th
generator being printed as <code></code><var>names</var><code>[<i>i</i>]</code>.
Called in the fifth form, <code>FreeSemigroup</code> returns a free semigroup on
infinitely many generators, where the first generators are printed
by the names in the list <var>init</var>, and the other generators by <var>name</var>
and an appended number.
<p>
If the extra argument <var>wfilt</var> is given, it must be either
<code>IsSyllableWordsFamily</code> or <code>IsLetterWordsFamily</code> or
<code>IsWLetterWordsFamily</code> or <code>IsBLetterWordsFamily</code>. The filter then
specifies the representation used for the elements of the free group
(see <a href="CHAP035.htm#SECT006">Representations for Associative Words</a>). If no such filter is
given, a letter representation is used.
<p>
<pre>
gap> f1 := FreeSemigroup( 3 );
<free semigroup on the generators [ s1, s2, s3 ]>
gap> f2 := FreeSemigroup( 3 , "generator" );
<free semigroup on the generators [ generator1, generator2, generator3 ]>
gap> f3 := FreeSemigroup( "gen1" , "gen2" );
<free semigroup on the generators [ gen1, gen2 ]>
gap> f4 := FreeSemigroup( ["gen1" , "gen2"] );
<free semigroup on the generators [ gen1, gen2 ]>
</pre>
<p>
<a name = ""></a>
<li><code>SemigroupByMultiplicationTable( </code><var>A</var><code> ) F</code>
<p>
returns the semigroup whose multiplication is defined by the square
matrix <var>A</var> (see <a href="CHAP033.htm#SSEC003.1">MagmaByMultiplicationTable</a>) if such a semigroup exists.
Otherwise <code>fail</code> is returned.
<p>
The following functions determine information
about semigroups:
<p>
<a name = ""></a>
<li><code>IsRegularSemigroup( </code><var>S</var><code> ) P</code>
<p>
returns <code>true</code> if <var>S</var> is regular---i.e. if every D class of <var>S</var> is regular.
<p>
<a name = ""></a>
<li><code>IsRegularSemigroupElement( </code><var>S</var><code>, </code><var>x</var><code> ) O</code>
<p>
returns <code>true</code> if <var>x</var> has a general inverse in <var>S</var>---i.e. there is an
element <i>y</i> ∈ <i>S</i> such that <i>xyx</i>=<i>x</i> and <i>yxy</i>=<i>y</i>.
<p>
<a name = ""></a>
<li><code>IsSimpleSemigroup( </code><var>S</var><code> ) P</code>
<p>
is <code>true</code> if and only if the semigroup has no proper ideals.
<p>
<a name = ""></a>
<li><code>IsZeroSimpleSemigroup( </code><var>S</var><code> ) P</code>
<p>
is <code>true</code> if and only if the semigroup has no proper ideals except for 0,
where <var>S</var> is a semigroup with zero.
If the semigroup does not find its zero, then a break-loop is entered.
<p>
<a name = ""></a>
<li><code>IsZeroGroup( </code><var>S</var><code> ) P</code>
<p>
is <code>true</code> if and only if the semigroup is a group with zero
adjoined.
<p>
<a name = ""></a>
<li><code>IsReesCongruenceSemigroup( </code><var>S</var><code> ) P</code>
<p>
returns <code>true</code> if <var>S</var> is a Rees Congruence semigroup, that is,
if all congruences of <var>S</var> are Rees Congruences.
<p>
<p>
<h2><a name="SECT001">49.1 Making transformation semigroups</a></h2>
<p><p>
Cayley's Theorem gives special status to semigroups of
transformations, and accordingly there are special functions
to deal with them, and to create them from other finite
semigroups.
<p>
<a name = "SSEC001.1"></a>
<li><code>IsTransformationSemigroup( </code><var>obj</var><code> ) P</code>
<a name = "SSEC001.1"></a>
<li><code>IsTransformationMonoid( </code><var>obj</var><code> ) P</code>
<p>
A transformation semigroup (resp. monoid) is a subsemigroup
(resp. submonoid) of the full transformation monoid.
Note that for a transformation semigroup to be a transformation monoid
we necessarily require the identity transformation to be an element.
<p>
<a name = "SSEC001.2"></a>
<li><code>DegreeOfTransformationSemigroup( </code><var>S</var><code> ) A</code>
<p>
The number of points the semigroup acts on.
<p>
<a name = "SSEC001.3"></a>
<li><code>IsomorphismTransformationSemigroup( </code><var>S</var><code> ) A</code>
<a name = "SSEC001.3"></a>
<li><code>HomomorphismTransformationSemigroup( </code><var>S</var><code>, </code><var>r</var><code> ) O</code>
<p>
IsomorphismTransformationSemigroup is a generic attribute which
is a transformation semigroup isomorphic to <var>S</var> (if such can
be computed). In the case of an fp- semigroup, a todd-coxeter
will be attempted. For a semigroup of endomorphisms of a finite
domain of <var>n</var> elements, it will be to a semigroup of transformations
of {1, …, <i>n</i>}. Otherwise, it will be the right regular
representation on <i>S</i> or <i>S</i><sup>1</sup> if <i>S</i> has no
MultiplicativeNeutralElement.
<p>
HomomorphismTransformationSemigroup
finds a representation of <var>S</var> as transformations of the set of
equivalence classes of the right congruence <var>r</var>.
<p>
<a name = "SSEC001.4"></a>
<li><code>IsFullTransformationSemigroup( </code><var>obj</var><code> ) P</code>
<p>
<a name = "SSEC001.5"></a>
<li><code>FullTransformationSemigroup( </code><var>degree</var><code> ) F</code>
<p>
Returns the full transformation semigroup of degree <var>degree</var>.
<p>
<p>
<h2><a name="SECT002">49.2 Ideals of semigroups</a></h2>
<p><p>
Ideals of semigroups are the same as ideals of the semigroup when
considered as a magma.
For documentation on ideals for magmas, see <code>Magma</code> (<a href="CHAP033.htm#SSEC002.1">Magma</a>).
<p>
<a name = "SSEC002.1"></a>
<li><code>SemigroupIdealByGenerators( </code><var>S</var><code>, </code><var>gens</var><code> ) O</code>
<p>
<var>S</var> is a semigroup, <var>gens</var> is a list of elements of <var>S</var>.
Returns the two-sided ideal of <var>S</var> generated by <var>gens</var>.
<p>
<a name = "SSEC002.2"></a>
<li><code>ReesCongruenceOfSemigroupIdeal( </code><var>I</var><code> ) A</code>
<p>
A two sided ideal <var>I</var> of a semigroup <var>S</var> defines a congruence on
<var>S</var> given by ∆∪<i>I</i> ×<i>I</i>.
<p>
<a name = "SSEC002.3"></a>
<li><code>IsLeftSemigroupIdeal( </code><var>I</var><code> ) P</code>
<a name = "SSEC002.3"></a>
<li><code>IsRightSemigroupIdeal( </code><var>I</var><code> ) P</code>
<a name = "SSEC002.3"></a>
<li><code>IsSemigroupIdeal( </code><var>I</var><code> ) P</code>
<p>
Categories of semigroup ideals.
<p>
<p>
<h2><a name="SECT003">49.3 Congruences for semigroups</a></h2>
<p><p>
An equivalence or a congruence on a semigroup is the
equivalence or congruence on the semigroup considered as a magma.
So, to deal with equivalences and congruences on semigroups,
magma functions are used.
For documentation on equivalences and congruences for magmas,
see <code>Magma</code> (<a href="CHAP033.htm#SSEC002.1">Magma</a>).
<p>
<a name = "SSEC003.1"></a>
<li><code>IsSemigroupCongruence( </code><var>c</var><code> ) P</code>
<p>
a magma congruence <var>c</var> on a semigroup.
<p>
<a name = "SSEC003.2"></a>
<li><code>IsReesCongruence( </code><var>c</var><code> ) P</code>
<p>
returns true precisely when the congruence <var>c</var> has at most one
nonsingleton congruence class.
<p>
<p>
<h2><a name="SECT004">49.4 Quotients</a></h2>
<p><p>
Given a semigroup and a congruence on the semigroup, one
can construct a new semigroup: the quotient semigroup.
The following functions deal with quotient semigroups in <font face="Gill Sans,Helvetica,Arial">GAP</font>.
<p>
<a name = "SSEC004.1"></a>
<li><code>IsQuotientSemigroup( </code><var>S</var><code> ) C</code>
<p>
is the category of semigroups constructed from another semigroup
and a congruence on it
<p>
Elements of a quotient semigroup are equivalence classes of
elements of <code>QuotientSemigroupPreimage(</code><var>S</var><code>)</code>
under the congruence <code>QuotientSemigroupCongruence(</code><var>S</var><code>)</code>.
<p>
It is probably most useful for calculating the elements of
the equivalence classes by using Elements or by looking at the
images of elements of the <code>QuotientSemigroupPreimage(</code><var>S</var><code>)</code> under
<code>QuotientSemigroupHomomorphism(</code><var>S</var><code>)</code>:<code>QuotientSemigroupPreimage(</code><var>S</var><code>)</code>
→ <var>S</var>.
<p>
For intensive computations in a quotient semigroup, it is probably
worthwhile finding another representation as the equality test
could involve enumeration of the elements of the congruence classes
being compared.
<p>
<a name = "SSEC004.2"></a>
<li><code>HomomorphismQuotientSemigroup( </code><var>cong</var><code> ) F</code>
<p>
for a congruence <var>cong</var> and a semigroup <var>S</var>.
Returns the homomorphism from <var>S</var> to the quotient of <var>S</var>
by <var>cong</var>.
<p>
<a name = "SSEC004.3"></a>
<li><code>QuotientSemigroupPreimage( </code><var>S</var><code> ) A</code>
<a name = "SSEC004.3"></a>
<li><code>QuotientSemigroupCongruence( </code><var>S</var><code> ) A</code>
<a name = "SSEC004.3"></a>
<li><code>QuotientSemigroupHomomorphism( </code><var>S</var><code> ) A</code>
<p>
for a quotient semigroup <var>S</var>.
<p>
<p>
<h2><a name="SECT005">49.5 Green's Relations</a></h2>
<p><p>
Green's equivalence relations play a very important role in semigroup
theory. In this section we describe how they can be used in <font face="Gill Sans,Helvetica,Arial">GAP</font>.
<p>
The five Green's relations are <var>R</var>, <var>L</var>, <var>J</var>, <var>H</var>, <var>D</var>:
two elements <var>x</var>, <var>y</var> from <var>S</var> are <var>R</var>-related if and only if
<i>xS</i><sup>1</sup> = <i>yS</i><sup>1</sup>, <var>L</var>-related if and only if <i>S</i><sup>1</sup><i>x</i>=<i>S</i><sup>1</sup><i>y</i> and <var>J</var>-related
if and only if <i>S</i><sup>1</sup><i>xS</i><sup>1</sup>=<i>S</i><sup>1</sup><i>yS</i><sup>1</sup>; finally, <i>H</i> = <i>R</i> ∧<i>L</i>, and
<i>D</i> = <i>R</i> °<i>L</i>.
<p>
Recall that relations <var>R</var>, <var>L</var> and <var>J</var> induce a partial order among
the elements of the semigroup: for two elements <var>x</var>, <var>y</var> from <var>S</var>,
we say that <var>x</var> is less than or equal to <var>y</var> in the order on <var>R</var>
if <i>xS</i><sup>1</sup> ⊆ <i>yS</i><sup>1</sup>;
similarly, <i>x</i> is less than or equal to <i>y</i> under <i>L</i> if
<i>S</i><sup>1</sup><i>x</i> ⊆ <i>S</i><sup>1</sup><i>y</i>;
finally <var>x</var> is less than or equal to <var>y</var> under <var>J</var> if
<i>S</i><sup>1</sup><i>xS</i><sup>1</sup> ⊆ <i>S</i><sup>1</sup><i>tS</i><sup>1</sup>.
We extend this preorder to a partial order on equivalence classes in
the natural way.
<p>
<a name = "SSEC005.1"></a>
<li><code>GreensRRelation( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.1"></a>
<li><code>GreensLRelation( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.1"></a>
<li><code>GreensJRelation( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.1"></a>
<li><code>GreensDRelation( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.1"></a>
<li><code>GreensHRelation( </code><var>semigroup</var><code> ) A</code>
<p>
The Green's relations (which are equivalence relations)
are attributes of the semigroup <var>semigroup</var>.
<p>
<a name = "SSEC005.2"></a>
<li><code>IsGreensRelation( </code><var>bin-relation</var><code> ) P</code>
<a name = "SSEC005.2"></a>
<li><code>IsGreensRRelation( </code><var>equiv-relation</var><code> ) P</code>
<a name = "SSEC005.2"></a>
<li><code>IsGreensLRelation( </code><var>equiv-relation</var><code> ) P</code>
<a name = "SSEC005.2"></a>
<li><code>IsGreensJRelation( </code><var>equiv-relation</var><code> ) P</code>
<a name = "SSEC005.2"></a>
<li><code>IsGreensHRelation( </code><var>equiv-relation</var><code> ) P</code>
<a name = "SSEC005.2"></a>
<li><code>IsGreensDRelation( </code><var>equiv-relation</var><code> ) P</code>
<p>
<a name = "SSEC005.3"></a>
<li><code>IsGreensClass( </code><var>equiv-class</var><code> ) P</code>
<a name = "SSEC005.3"></a>
<li><code>IsGreensRClass( </code><var>equiv-class</var><code> ) P</code>
<a name = "SSEC005.3"></a>
<li><code>IsGreensLClass( </code><var>equiv-class</var><code> ) P</code>
<a name = "SSEC005.3"></a>
<li><code>IsGreensJClass( </code><var>equiv-class</var><code> ) P</code>
<a name = "SSEC005.3"></a>
<li><code>IsGreensHClass( </code><var>equiv-class</var><code> ) P</code>
<a name = "SSEC005.3"></a>
<li><code>IsGreensDClass( </code><var>equiv-class</var><code> ) P</code>
<p>
return <code>true</code> if the equivalence class <var>equiv-class</var> is
a Green's class of any type, or of <var>R</var>, <var>L</var>, <var>J</var>, <var>H</var>, <var>D</var> type,
respectively, or <code>false</code> otherwise.
<p>
<a name = "SSEC005.4"></a>
<li><code>IsGreensLessThanOrEqual( </code><var>C1</var><code>, </code><var>C2</var><code> ) O</code>
<p>
returns <code>true</code> if the greens class <var>C1</var> is less than or equal to <var>C2</var>
under the respective ordering (as defined above), and <code>false</code> otherwise.
<p>
Only defined for R, L and J classes.
<p>
<a name = "SSEC005.5"></a>
<li><code>RClassOfHClass( </code><var>H</var><code> ) A</code>
<a name = "SSEC005.5"></a>
<li><code>LClassOfHClass( </code><var>H</var><code> ) A</code>
<p>
are attributes reflecting the natural ordering over the various Green's
classes. <code>RClassOfHClass</code> and <code>LClassOfHClass</code> return the <var>R</var> and
<var>L</var> classes respectively in which an <var>H</var> class is contained.
<p>
<a name = "SSEC005.6"></a>
<li><code>EggBoxOfDClass( </code><var>Dclass</var><code> ) A</code>
<p>
returns for a Green's D class <var>Dclass</var> a matrix whose rows represent R
classes and columns represent L classes. The entries are the H classes.
<p>
<a name = "SSEC005.7"></a>
<li><code>DisplayEggBoxOfDClass( </code><var>Dclass</var><code> ) F</code>
<p>
displays a ``picture'' of the D class <var>Dclass</var>, as an array of 1s and 0s.
A 1 represents a group H class.
<p>
<a name = "SSEC005.8"></a>
<li><code>GreensRClassOfElement( </code><var>S</var><code>, </code><var>a</var><code> ) O</code>
<a name = "SSEC005.8"></a>
<li><code>GreensLClassOfElement( </code><var>S</var><code>, </code><var>a</var><code> ) O</code>
<a name = "SSEC005.8"></a>
<li><code>GreensDClassOfElement( </code><var>S</var><code>, </code><var>a</var><code> ) O</code>
<a name = "SSEC005.8"></a>
<li><code>GreensJClassOfElement( </code><var>S</var><code>, </code><var>a</var><code> ) O</code>
<a name = "SSEC005.8"></a>
<li><code>GreensHClassOfElement( </code><var>S</var><code>, </code><var>a</var><code> ) O</code>
<p>
Creates the <var></var> class of the element <var>a</var> in the semigroup <var>S</var>
where <var></var> is one of L, R, D, J or H.
<p>
<a name = "SSEC005.9"></a>
<li><code>GreensRClasses( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.9"></a>
<li><code>GreensLClasses( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.9"></a>
<li><code>GreensJClasses( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.9"></a>
<li><code>GreensDClasses( </code><var>semigroup</var><code> ) A</code>
<a name = "SSEC005.9"></a>
<li><code>GreensHClasses( </code><var>semigroup</var><code> ) A</code>
<p>
return the <var>R</var>, <var>L</var>, <var>J</var>, <var>H</var>, or <var>D</var> Green's classes, respectively for
semigroup <var>semigroup</var>. EquivlanceClasses for a Green's relation lead to one of
these functions.
<p>
<a name = "SSEC005.10"></a>
<li><code>GroupHClassOfGreensDClass( </code><var>Dclass</var><code> ) A</code>
<p>
for a D class <var>Dclass</var> of a semigroup,
returns a group H class of the D class, or <code>fail</code> if there is no
group H class.
<p>
<a name = "SSEC005.11"></a>
<li><code>IsGroupHClass( </code><var>Hclass</var><code> ) P</code>
<p>
returns <code>true</code> if the Greens H class <var>Hclass</var> is a group, which in turn
is true if and only if <var>Hclass</var>^2 intersects <var>Hclass</var>.
<p>
<a name = "SSEC005.12"></a>
<li><code>IsRegularDClass( </code><var>Dclass</var><code> ) P</code>
<p>
returns <code>true</code> if the Greens D class <var>Dclass</var> is regular. A D class is
regular if and only if each of its elements is regular, which in turn is
true if and only if any one element of <var>Dclass</var> is regular. Idempotents
are regular since <i>eee</i>=<i>e</i> so it follows that a Greens D class containing
an idempotent is regular. Conversely, it is true that a regular D class
must contain at least one idempotent. (See <a href="biblio.htm#Howie76"><cite>Howie76</cite></a>, Prop. 3.2).
<p>
<p>
<h2><a name="SECT006">49.6 Rees Matrix Semigroups</a></h2>
<p><p>
In this section we describe <font face="Gill Sans,Helvetica,Arial">GAP</font> functions for Rees matrix semigroups
and Rees 0-matrix semigroups.
The importance of this construction is that
Rees Matrix semigroups over groups
are exactly the completely simple semigroups, and Rees 0-matrix
semigroups over groups are the completely 0-simple semigroups
<p>
Recall that a Rees Matrix semigroup is constructed from a semigroup (the
underlying semigroup), and a matrix.
A Rees Matrix semigroup element is a triple (<var>s</var>, <var>i</var>, <var>lambda</var>)
where <var>s</var> is an element of the underlying semigroup <var>S</var> and
<var>i</var>, <var>lambda</var> are indices.
This can be thought of as a matrix with zero everywhere
except for an occurrence of <var>s</var> at row <var>i</var> and column <var>lambda</var>.
The multiplication is defined by
(<i>i</i>, <i>s</i>, λ)*(<i>j</i>, <i>t</i>, μ) = (<i>i</i>, <i>s</i> <i>P</i><sub>λ<i>j</i></sub> <i>t</i>, μ) where
<i>P</i> is the defining matrix of the semigroup.
In the case that the underlying semigroup has a zero we can make the
ReesZeroMatrixSemigroup, wherein all elements whose <var>s</var> entry is the
zero of the underlying semigroup are identified to the unique zero of
the Rees 0-matrix semigroup.
<p>
<a name = "SSEC006.1"></a>
<li><code>ReesMatrixSemigroup( </code><var>S</var><code>, </code><var>matrix</var><code> ) F</code>
<p>
for a semigroup <var>S</var> and <var>matrix</var> whose entries are in <var>S</var>.
Returns the Rees Matrix semigroup with multiplication defined by
<var>matrix</var>.
<p>
<a name = "SSEC006.2"></a>
<li><code>ReesZeroMatrixSemigroup( </code><var>S</var><code>, </code><var>matrix</var><code> ) F</code>
<p>
for a semigroup <var>S</var> with zero, and <var>matrix</var> over <var>S</var>
returns the Rees 0-Matrix semigroup such that all elements
(<i>i</i>, 0, λ) are identified to zero.
<p>
The zero in <var>S</var> is found automatically. If
one cannot be found, an error is signalled.
<p>
<a name = "SSEC006.3"></a>
<li><code>IsReesMatrixSemigroup( </code><var>T</var><code> ) P</code>
<p>
returns <code>true</code> if the object <var>T</var> is a (whole) Rees matrix semigroup.
<p>
<a name = "SSEC006.4"></a>
<li><code>IsReesZeroMatrixSemigroup( </code><var>T</var><code> ) P</code>
<p>
returns <code>true</code> if the object <var>T</var> is a (whole) Rees 0-matrix semigroup.
<p>
<a name = "SSEC006.5"></a>
<li><code>ReesMatrixSemigroupElement( </code><var>R</var><code>, </code><var>a</var><code>, </code><var>i</var><code>, </code><var>lambda</var><code> ) F</code>
<a name = "SSEC006.5"></a>
<li><code>ReesZeroMatrixSemigroupElement( </code><var>R</var><code>, </code><var>a</var><code>, </code><var>i</var><code>, </code><var>lambda</var><code> ) F</code>
<p>
for a Rees matrix semigroup <var>R</var>, <var>a</var> in <code>UnderlyingSemigroup(</code><var>R</var><code>)</code>,
<var>i</var> and <var>lambda</var> in the row (resp. column) ranges of <var>R</var>,
returns the element of <var>R</var> corresponding to the
matrix with zero everywhere and <var>a</var> in row <var>i</var> and column <var>x</var>.
<p>
<a name = "SSEC006.6"></a>
<li><code>IsReesMatrixSemigroupElement( </code><var>e</var><code> ) C</code>
<a name = "SSEC006.6"></a>
<li><code>IsReesZeroMatrixSemigroupElement( </code><var>e</var><code> ) C</code>
<p>
is the category of elements of a Rees (0-) matrix semigroup.
Returns true if <var>e</var> is an element of a Rees Matrix semigroup.
<p>
<a name = "SSEC006.7"></a>
<li><code>SandwichMatrixOfReesMatrixSemigroup( </code><var>R</var><code> ) A</code>
<a name = "SSEC006.7"></a>
<li><code>SandwichMatrixOfReesZeroMatrixSemigroup( </code><var>R</var><code> ) A</code>
<p>
each return the defining matrix of the Rees (0-) matrix semigroup.
<p>
<a name = "SSEC006.8"></a>
<li><code>RowIndexOfReesMatrixSemigroupElement( </code><var>x</var><code> ) A</code>
<a name = "SSEC006.8"></a>
<li><code>RowIndexOfReesZeroMatrixSemigroupElement( </code><var>x</var><code> ) A</code>
<a name = "SSEC006.8"></a>
<li><code>ColumnIndexOfReesMatrixSemigroupElement( </code><var>x</var><code> ) A</code>
<a name = "SSEC006.8"></a>
<li><code>ColumnIndexOfReesZeroMatrixSemigroupElement( </code><var>x</var><code> ) A</code>
<a name = "SSEC006.8"></a>
<li><code>UnderlyingElementOfReesMatrixSemigroupElement( </code><var>x</var><code> ) A</code>
<a name = "SSEC006.8"></a>
<li><code>UnderlyingElementOfReesZeroMatrixSemigroupElement( </code><var>x</var><code> ) A</code>
<p>
For an element <var>x</var> of a Rees Matrix semigroup, of the form
<code>(</code><var>i</var><code>, </code><var>s</var><code>, </code><var>lambda</var><code>)</code>,
the row index is <var>i</var>, the column index is <var>lambda</var> and the
underlying element is <var>s</var>.
If we think of an element as a matrix then this corresponds to
the row where the non-zero entry is, the column where the
non-zero entry is and the entry at that position, respectively.
<p>
<a name = "SSEC006.9"></a>
<li><code>ReesZeroMatrixSemigroupElementIsZero( </code><var>x</var><code> ) P</code>
<p>
returns <code>true</code> if <var>x</var> is the zero of the Rees 0-matrix semigroup.
<p>
<a name = "SSEC006.10"></a>
<li><code>AssociatedReesMatrixSemigroupOfDClass( </code><var>D</var><code> ) A</code>
<p>
Given a regular <var>D</var> class of a finite semigroup, it can be viewed as a
Rees matrix semigroup by identifying products which do not lie in the
<var>D</var> class with zero, and this is what it is returned.
<p>
Formally, let <i>I</i><sub>1</sub> be the ideal of all J classes less than or equal to
<var>D</var>, <i>I</i><sub>2</sub> the ideal of all J classes <strong>strictly</strong> less than <var>D</var>,
and ρ the Rees congruence associated with <i>I</i><sub>2</sub>. Then <i>I</i>/ρ
is zero-simple. Then <code>AssociatedReesMatrixSemigroupOfDClass( </code><var>D</var><code> )</code>
returns this zero-simple semigroup as a Rees matrix semigroup.
<p>
<a name = "SSEC006.11"></a>
<li><code>IsomorphismReesMatrixSemigroup( </code><var>obj</var><code> ) A</code>
<p>
an isomorphism to a Rees matrix semigroup over a group (resp. zero
group).
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP048.htm">Previous</a>] [<a href ="CHAP050.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
191
