
\documentstyle[11pt]{article}
\textwidth 12.7cm
\textheight 21.5cm
\pagestyle{empty}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\begin{document}

\huge
\noindent
{\bf Products of Idempotents in Finite Full Transformation Semigroups}
\normalsize
\\
\\
\large
\noindent {\bf John M. Howie}\\
University of St. Andrews \\
St. Andrews, Scotland, U.K. KY16 9SS\\
\\
{\bf Robert B. McFadden}\\
Department of Mathematical Sciences\\
Northern Illinois University\\
Dekalb, IL 60115, USA\\
mcfadden@mcs.anl.gov
\\

\Large
\noindent
{\bf Abstract}
\normalsize
\\

\noindent
Each singular element $ \alpha $ of the full transformation semigroup on 
a
finite set is generated by the idempotents of defect one.
The length of the shortest expression of $ \alpha $ as a product of such
idempotents is given by the gravity function $ g( \alpha ) $.
We use certain consequences of a result by
Tatsuhiko Saito to explore connections between the defect and the 
gravity of
$ \alpha $, and then determine the
number of elements that have maximum gravity.
Finally, we obtain formulae for the number of
elements of small gravity.  Such elements must have defect 1, and we 
determine
their number within each $ \cal H $-class.
Many of the results obtained were suggested, and
all have been verified, by programs written in PROLOG, a logic 
programming
language very well suited for algebraic calculations.

\section{Introduction}
Let $ T_{n} $ be the full transformation semigroup on the set
$ X_{n} = \{1, \ldots ,n\} $, that is, the set of all maps $ \alpha : 
X_{n}
\rightarrow X_{n} $ under the operation of composition.  Associated with 
each
$ \alpha $ in $ T_{n} $ is a digraph $ \Gamma (\alpha) $ whose vertices 
are $
1,2,...,n $ and where $ (i,j) $ is a (directed) edge if and only if $ 
i\alpha
= j $.  Each connected component $ \Omega $ of $ \Gamma(\alpha) $ has a 
{\em
core} $ K(\Omega) $ defined by the property that $ x ( \in \Omega ) $ is 
in $
K(\Omega) $ if and only if there exists $ p > 0 $ such that $ x\alpha^p 
= x $.
In the terminology of \cite{howie:products}, $ \Omega $ is called
{\em standard} if $ 1 < | K(\Omega) | < | \Omega | $,
{\em acyclic} if $ 1 = | K(\Omega) | < | \Omega | $,
{\em cyclic} if $ 1 < | K(\Omega) | = | \Omega |$, and
{\em singleton} if $ 1 = | K(\Omega) |
= |\Omega| $.

The union of all the cores $ K(\Omega) $ may reasonably be called the 
{\em
core} of $ \alpha $ and written $ k(\alpha) $.  In fact,
\[
k(\alpha) = \bigcap_{r \geq 1} \rm im(\alpha^{r}).
\]
For every $ x $ in $ X_{n} $ the {\em $ \alpha $-height} of $ x $ is 
defined
as min $ \{   r : x\alpha^{r} \in  k(\alpha) \} $.

A {\em group element} $ \alpha $ of $ T_{n} $ is one that lies in 
maximal
subgroup of $ T_{n} $.  It is well-known that $ \alpha $ is a group 
element if
and only if the image $ \rm im(\alpha) $ is a transversal of the 
equivalence $
\rm ker(\alpha) $ ( = $ \{(x,y) : x\alpha = y\alpha \} ) $.  
Equivalently, $
\alpha $ is a group element of $ T_{n} $ if and only if
$ \alpha |_{ \rm im(\alpha)} $
is one-to-one.

The concept of a group element is related to that of $ \alpha $-height 
by the
following result.

\begin{lemma}
An element $ \alpha $ of $ T_{n} $ is a group element if and only if 
every $x$
in $ X_{n} $ has $ \alpha $-height 0 or 1.
\end{lemma}

{\em Proof:}  It is clear that $k( \alpha ) \subseteq \rm im( \alpha ) $ 
and
 that
$ \alpha |_{ k( \alpha )} $ is one-to-one.  If every $x$ in $ X_{n} $ 
has
$ \alpha $-height 0 or 1, then $k( \alpha ) = \rm im( \alpha ) $; hence,
$ \alpha |_{\rm im( \alpha )} $ is one-to-one and so  $ \alpha $  is a 
group
element.

Conversely, suppose that there exists $x$ in $ X_{n} $ with  $ \alpha 
$-height
$ h \geq 2 $.  Let $x$ be in a component $\Omega$ (say), where $ | 
K(\Omega) |
= k$.  Then
\[
(x  \alpha^{h - 1})  \alpha  = ( x  \alpha^{h + k - 1})  \alpha ~~
( = x  \alpha^{h}).
\]

Thus, $ \alpha |_{\rm im( \alpha )} $ is not one-to-one and so $ \alpha 
$ is
not a group element. $ \Box $

The symmetric group $ S_{n} $ is of course contained in $ T_{n} $, but 
we
shall here be concerned with $ T_{n} \setminus S_{n} $, the subsemigroup 
of $
T_{n} $ consisting of all {\em singular} self-maps of $ X_{n} $.  We 
shall
denote this semigroup by $ Sing_{n} $.

For $ \alpha $ in $ Sing_{n} $ we define $ c(\alpha) $ to be the number 
of
cyclic components in $ \Gamma(\alpha) $ and $ f(\alpha) $ to be the 
number of
fixed points of $ \alpha $.  In fact $ f(\alpha) $ ( $ = | { x \in X_{n} 
:
x\alpha = x } | $ ) is the number of acyclic components plus the number 
of
singleton components.

Let $ E $ denote the set of idempotents in $ Sing_{n} $ and let $ E_{1} 
$
be the subset of $ E $ consisting of all idempotents $ \alpha $ such 
that $ |
\rm im(\alpha) | = n - 1 $.  It has been known for some
time\cite{howie:products} that $ E $, and even $ E_{1} $, is a set of
generators for $ Sing_{n} $.

In \cite{iwahori:length} and \cite{howie:products} the function $ g : 
Sing_{n}
\rightarrow {\bf N} $ given by \[ g(\alpha) = n + c(\alpha) - f(\alpha) 
\]
was shown to be of interest.  Following \cite{iwahori:length} we call it
the {\em gravity} of $ \alpha $.  For
each $ \alpha $ in $ Sing_{n} $ the shortest product of idempotents from 
$
E_{1} $ that equals $ \alpha $ is of length $ g(\alpha) $.  In other 
words,
\[ \alpha \in E_{1}^{g(\alpha)} , \alpha \not\in E_{1}^{g(\alpha) - 1}. 
\]
Thus in example 1, where $ g(\alpha) = 9 + 1 - 2 = 8 $, we can conclude 
that $
\alpha \in E_{1}^{8} $ but  $ \alpha \not\in E_{1}^{7} $.

\section*{Acknowledgements}

This research was
supported in part by the Applied Mathematical Sciences subprogram of
the office of Energy Research, U.S. Department of Energy, under
contract W-31-109-Eng-38.


\begin{thebibliography}{99}

\bibitem{howie:products}
John~M. Howie.
\newblock Products of idempotents in finite full transformation 
semigroups.
\newblock {\it Proc. Royal Soc. Edinburgh A.}, 86:243--254, 1980.

\bibitem{iwahori:length}
Nobuko Iwahori.
\newblock A length formula in a semigroup of mappings.
\newblock {\it J. Fac. Sci. Univ. Tokyo, Sec. 1A Math.}, 24:255--260, 
1977.

\end{thebibliography}

\end{document}

