Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I stumbled upon this while reviewing a Harvard lecture on abstract algebra. What I want to know is if these semigroups are known and, if so, what they are called. I've checked the assertions below for $n=1$ and $n=2,$ and think I can prove them for any natural $n$.

Consider all $n\times n$ matrices with entries that are zero or one and no more than one entry has value 1. Then these are closed under matrix multiplication, and the matrix with all zeros is a null element. There is no identity element.

So we have a semigoup that is not a monoid.

There are some interesting subsemigroups.

If you add the identity matrix you, of course, get a monoid.

These make good assigned work!

share|improve this question
What is the question? –  Jonas Meyer May 20 '12 at 1:58
Is your question whether these actually form a semigroup? Yes. If we let $E_{ij}$ denote the matrix with a $1$ in the $(i,j)$ component, then $E_{ij}E_{rs} = 0$ if $j\neq r$, and $E_{ij}E_{js}=E_{is}$, we have a semigroup with $0$. –  Arturo Magidin May 20 '12 at 3:05
@Jonas, Arturo, Isn't the question the second sentence? "What I want to know [is] if these semigroups are known and, if so, what the[y] are called." I think he is asking for a reference. –  alex.jordan May 20 '12 at 7:17
@alex.jordan More for terminology I think. I've edited the tags. (And answered the question.) –  user23211 May 20 '12 at 10:41
@alex.jordan ymar is right. My questions were: Is this well known? If so what are the semigroups called? –  Richard John Botting May 20 '12 at 14:11

1 Answer 1

up vote 5 down vote accepted

They are a special case of the so called Brandt semigroups (which are a special case of semigroups of Rees matrices). They are indeed quite important. One of their characterizations is as follows.

Definition of a Brandt semigroup

Let $(G,\cdot)$ be a group and $I$ be a set. We define $G^0$ to be the group $G$ with zero adjoined, that is the set $G\cup\{0\}$, where $0\not\in G,$ with the operation $\star$ defined thus:

$$a\star b=\begin{cases}a\cdot b & \text{ for } \{a,b\}\subseteq G;\\0 & \text{ for } \{a,b\}\not\subseteq G.\end{cases}$$

It is easy to see that $(G^0,\star)$ is a monoid and that $0$ is its zero element. I won't distinguish between $\star$ and $\cdot$ in the remaining part, and will just write $ab.$

We will say that a $I\times I$-matrix over $G^0$ is any function $A:I\times I\longrightarrow G^0$. It is of course good to imagine them as possibly infinite "square" arrays of elements of $G^0$.

Abusing the notation slightly, we will denote by $0$ the matrix whose all entries are $0$. For $g\in G$ and $i,j\in I,$ we will define $(g)_{ij}$ to be the matrix whose $ij$-th entry is $g$ and other entries are $0.$ We will also say that $(0)_{ij}=0$ for all $i,j\in I.$ Finally, let $$\mathscr M^0(G,I):=\{(g)_{ij}\,|\,g\in G,\,i,j\in I\}\cup\{0\}.$$ We define multiplication $\odot$ on this set by

$$ (a)_{ij}\odot (b)_{kl}= \begin{cases}(ab)_{il} & \text{ for } a\neq 0\neq b \text{ and } j=k; \\ 0 & \text { otherwise}.\end{cases} $$

It's easy to check that $\odot$ makes $\mathscr M^0(G,I)$ a semigroup. It is also easy to see that it is in fact what we would consider the "usual multiplication of matrices".

Now if we take $G$ to be the trivial group and $I=\{1,\ldots, n\},$ then $\mathscr M^0(G,I)$ is the semigroup you are asking about.

Alternate characterizations

There are several characterizations of these semigroups. The first comes from 1927 and was given by Brandt. Well, almost. Take $\mathscr M^0(G,I)$ and take away the zero matrix. What we obtain is not a semigroup, because not all products are defined. (As there are zero divisors in $\mathscr M^0(G,I).$) This is what Brandt defined, and his definition was axiomatic, having nothing to do with matrices. The "no-zero" approach is discussed here. Both the matrix approach and adding the zero element are later ideas, although Brandt probably realized that adding $0$ is possible -- he just didn't bother. His axioms were complicated and a thorough treatment of them can be found in the first volume of the book of Clifford and Preston on semigroups.

An important characterization was found by Clifford. Some definitions are necessary first. A semigroup $S$ is an inverse semigroup when for every $s\in S$ there exists a unique $t\in S$ such that $$\begin{eqnarray}sts=s,\\tst=t.\end{eqnarray}$$

Such semigroups are extremely important in semigroup theory. They provide a useful generalization of groups. We may note that in a group we have $$\begin{eqnarray}ss^{-1}s&=&s,\\s^{-1}ss^{-1}&=&s^{-1},\end{eqnarray}$$ and that there is no other $t$ in the group satisfying these equations.

An element $e$ of a semigroup is idempotent when $ee=e.$ The set of idempotents of a semigroup $S$ is denoted by $E(S).$ For every semigroup $S$ there is a natural order $\leq$ on $E(S)$ defined as follows. $$e\leq f\iff ef=fe=e.$$

An ideal of a semigroup $S$ is such a set $I$ that $$\begin{eqnarray}SI\subseteq I,\\IS\subseteq I.\end{eqnarray}$$ A semigroup with $0$ is $0$-simple if it has no proper non-zero ideals, and if its multiplication isn't zero.

A $0$-simple semigroup such that $E(S)\setminus\{0\}$ contains a minimal element is called completely $0$-simple. Such semigroups are also important, because they are quite "tame". (They can also be characterized as certain semigroups of matrices. It's a generalization of what I'm talking about. If you want to know more, look for "Rees's theorem".)

Clifford proved that Brandt semigroups are -- up to isomorphism -- exactly the completely $0$-simple inverse semigroups. That every Brandt semigroup has this property is not difficult to check. The converse requires some theory.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.