Transactions of the American Mathematical Society

Representation theory of finite semigroups, semigroup radicals and formal language theory

Author(s): Jorge Almeida; Stuart Margolis; Benjamin Steinberg; Mikhail Volkov
Journal: Trans. Amer. Math. Soc. 361 (2009), 1429-1461.
MSC (2000): Primary 20M30, 20M35, 20C15, 20C20, 68Q45, 68Q70
Posted: October 20, 2008
Retrieve article in: PDF

Abstract: In this paper we characterize the congruence associated to the direct sum of all irreducible representations of a finite semigroup over an arbitrary field, generalizing results of Rhodes for the field of complex numbers. Applications are given to obtain many new results, as well as easier proofs of several results in the literature, involving: triangularizability of finite semigroups; which semigroups have (split) basic semigroup algebras, two-sided semidirect product decompositions of finite monoids; unambiguous products of rational languages; products of rational languages with counter; and Černý's conjecture for an important class of automata.

1.: J. Almeida, ``Finite Semigroups and Universal Algebra'', Series in Algebra, 3, World Scientific, River Edge, NJ, 1994. MR 1331143 (96b:20069)
2.: J. Almeida, A syntactical proof of locality of DA, Internat. J. Algebra Comput. 6 (1996), 165-177. MR 1386073 (97b:20096)
3.: J. Almeida, S. W. Margolis, B. Steinberg and M. V. Volkov, Modular and threshold subword counting and matrix representations of finite monoids, in ``Words 2005, $5^{th}$ International Conference on Words, 13-17 September 2005, Acts'', eds. S. Brlek, C. Reutenauer, Publications du Laboratoire de Combinatoire et d' Informatique Mathématique, UQAM 36 (2005), 65-78.
4.: J. Almeida, S. W. Margolis and M. V. Volkov, The pseudovariety of semigroups of triangular matrices over a finite field, RAIRO Theoret. Inform. and Appl. 39 (2005), 31-48. MR 2132577 (2006a:20105)
5.: J. Almeida, S. W. Margolis, B. Steinberg and M. V. Volkov, Characterization of group radicals with an application to Mal'cev products, in preparation.
6.: D. S. Ananichev and M. V. Volkov, Some results on Černý type problems for transformation semigroups, in: ``Proceedings of the Workshop Semigroups and Languages'', eds. I. M. Araújo, M. J. J. Branco, V. H. Fernandes, G. M. S. Gomes, World Scientific, Singapore, 2004, 23-42. MR 2170751 (2006f:20075)
7.: F. Arnold, ``A linear algebra approach to synchronizing automata'', Master's Thesis, Carleton University, Ottawa, 2005.
8.: F. Arnold and B. Steinberg, Synchronizing groups and automata, Theoret. Comp. Sci. 359 (2006), 101-110. MR 2251603 (2007i:68081)
9.: K. Auinger and B. Steinberg, On the extension problem for partial permutations, Proc. Amer. Math. Soc. 131 (2003), 2693-2703. MR 1974324 (2004c:20102)
10.: P. Bidigare, P. Hanlon and D. Rockmore, A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. J. 99 (1999), 135-174. MR 1700744 (2000m:52032)
11.: A. Björner and F. Brenti, ``Combinatorics of Coxeter groups'', Graduate Texts in Mathematics, 231, Springer, New York, 2005. MR 2133266 (2006d:05001)
12.: K. Brown, Semigroups, rings, and Markov chains, J. Theoret. Probab. 13 (2000), 871-938. MR 1785534 (2001e:60141)
13.: K. Brown, Semigroup and ring theoretical methods in probability, in: ``Representations of Finite Dimensional Algebras and Related Topics in Lie Theory and Geometry'', ed. V. Dlab, Fields Inst. Commun., 40, Amer. Math. Soc., Providence, RI, 2004, 3-26. MR 2057147 (2005b:60118)
14.: J. Černý, Poznámka k homogénnym eksperimentom s konecnými automatami (A note on homogeneous experiments with finite automata), Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14 (1964), 208-216 [in Slovak]. MR 0168429 (29:5692)
15.: A. H. Clifford, Matrix representations of completely simple semigroups, Amer. J. Math. 64 (1942), 327-342. MR 0006551 (4:4a)
16.: A. H. Clifford and G. B. Preston, ``The Algebraic Theory of Semigroups'', Vol. 1, Mathematical Surveys, 7, Amer. Math. Soc., Providence, RI, 1961. MR 0132791 (24:A2627)
17.: L. Dubuc, Sur les automates circulaires et la conjecture de Černý, RAIRO Theoret. Inform. and Appl. 32 (1998), 21-34. MR 1657507 (99i:68082)
18.: S. Eilenberg, ``Automata, Languages and Machines'', Academic Press, New York, Vol. A, 1974; Vol. B, 1976. MR 0530382 (58:26604a); MR 0530383 (58:26604b)
19.: S. Eilenberg and M. P. Schützenberger, On pseudovarieties, Adv. Math. 19 (1976), 413-418. MR 0401604 (53:5431)
20.: J. A. Green, On the structure of semigroups, Annals Math. 54 (1951), 163-172. MR 0042380 (13:100d)
21.: R. L. Graham, On finite 0-simple semigroups and graph theory, Math. Systems Theory 2 (1968), 325-339. MR 0240228 (39:1580)
22.: T. E. Hall, The radical of the semigroup algebra of any finite semigroup over any field, J. Austral. Math. Soc. 11 (1970), 350-352. MR 0268302 (42:3201)
23.: J. Kari, Synchronizing finite automata on Eulerian digraphs, Theoret. Comput. Sci. 295 (2003), 223-232. MR 1964667 (2003m:68077)
24.: K. Krohn and J. Rhodes, Complexity of finite semigroups, Annals Math. 88 (1968), 128-160. MR 0236294 (38:4591)
25.: K. Krohn, J. Rhodes and B. Tilson, Lectures on the algebraic theory of finite semigroups and finite-state machines, Chapters 1, 5-9 (Chapter 6 with M. A. Arbib) of ``Algebraic Theory of Machines, Languages, and Semigroups'', ed. M. A. Arbib, Academic Press, New York, 1968.
26.: G. Lallement and M. Petrich, Irreducible matrix representations of finite semigroups Trans. Amer. Math. Soc. 139 (1969), 393-412. MR 0242973 (39:4300)
27.: T. Y. Lam, ``A First Course in Noncommutative Rings'', Graduate Texts in Mathematics, 131, 2nd ed., Springer, New York, 2001. MR 1838439 (2002c:16001)
28.: D. B. McAlister, Representations of semigroups by linear transformations, I, II, Semigroup Forum 2 (1971), 189-263; ibid. 2 (1971), 283-320. MR 0286910 (44:4117)
29.: W. D. Munn, On semigroup algebras, Proc. Cambridge Philos. Soc. 51 (1955), 1-15. MR 0066355 (16:561c)
30.: W. D. Munn, Matrix representations of semigroups, Proc. Cambridge Philos. Soc. 53 (1957), 5-12. MR 0082050 (18:489g)
31.: W. D. Munn, The Jacobson radical of a band ring, Math. Proc. Cambridge Philos. Soc. 105 (1989), 277-283. MR 974983 (89j:16034)
32.: J. Okniński, ``Semigroup Algebras'', Monographs and Textbooks in Pure and Applied Mathematics, 138, Marcel Dekker, Inc., New York, 1991. MR 1083356 (92f:20076)
33.: J. Okniński, ``Semigroups of Matrices'', Series in Algebra, 6, World Scientific, River Edge, NJ, 1998. MR 1785162 (2001g:20076)
34.: A. Ja. Ovsyannikov, O radikal'nosti fundamental'nykh idealov polugruppovykh kolec (On radical properties of augmentation ideals of semigroup rings), in ``Issledovanija Algebraicheskikh Sistem po Svojstvam ikh Podsistem'', ed. L. N. Shevrin, Ural State University, 1985, 119-127 (in Russian).
35.: D. S. Passman, ``The Algebraic Structure of Group Rings'', Pure and Applied Mathematics. Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1977. MR 470211 (81d:16001)
36.: P. Péladeau, Sur le produit avec compteur modulo un nombre premier, RAIRO Inform. Theoret. and Appl. 26 (1992), 553-564. MR 1195745 (93m:68104)
37.: J.-É. Pin, Sur un cas particulier de la conjecture de Černý, $5^{th}$ ICALP, Lect. Notes Comput. Sci., 62, Springer, Berlin, 1978, 345-352, MR 520853 (80d:68074)
38.: J.-É. Pin, Propriétés syntactiques du produit non ambigu, $7^{th}$ ICALP, Lect. Notes Comput. Sci. 85, Springer, Berlin, (1980), 483-499. MR 589026 (82e:68086)
39.: J.-É. Pin, On two combinatorial problems arising from automata theory, Annals Discrete Math. 17 (1983), 535-548. MR 841339 (87i:68040)
40.: J.-É. Pin, ``Varieties of Formal Languages'', Plenum, New York, 1986. MR 912694 (89a:68125)
41.: J.-É. Pin, H. Straubing and D. Thérien, Locally trivial categories and unambiguous concatenation, J. Pure Appl. Algebra 52 (1988), 297-311. MR 952084 (89h:68089)
42.: M. S. Putcha, ``Linear algebraic monoids'', London Math. Soc. Lect. Notes Series, 133, Cambridge University Press, Cambridge, 1988. MR 964690 (90a:20003)
43.: M. S. Putcha, Complex representations of finite monoids, Proc. London Math. Soc. 73 (1996), 623-641. MR 1407463 (97e:20093)
44.: M. S. Putcha, Complex representations of finite monoids, II: Highest weight categories and quivers, J. Algebra 205 (1998), 53-76. MR 1631310 (99f:20106)
45.: M. S. Putcha, Semigroups and weights for group representations, Proc. Amer. Math. Soc. 128 (2000), 2835-2842. MR 1691001 (2000m:20019)
46.: M. S. Putcha, Reciprocity in character theory of finite semigroups, J. Pure Appl. Algebra 163 (2001), 339-351. MR 1852124 (2002f:20111)
47.: N. R. Reilly and S. Zhang, Operators on the lattice of pseudovarieties of finite semigroups, Semigroup Forum 57 (1998), 208-239. MR 1634711 (99j:20066)
48.: L. E. Renner, ``Linear algebraic monoids'', Encyclopaedia of Mathematical Sciences, 134, Invariant Theory and Algebraic Transformation Groups, V. Springer, Berlin, 2005. MR 2134980 (2006a:20002)
49.: C. Reutenauer, Sur les variétés de langages et de monoïdes, Proc. Fourth GI Conf., Aachen, 1979, Lect. Notes Comp. Sci. 67, Springer, Berlin, 1979, 260-265. MR 568110 (82a:68154)
50.: J. Rhodes, A homomorphism theorem for finite semigroups, Math. Systems Theory 1 (1967), 289-304. MR 0223473 (36:6521)
51.: J. Rhodes, Characters and complexity of finite semigroups, J. Comb. Theory 6 (1969), 67-85. MR 0236293 (38:4590)
52.: J. Rhodes, Algebraic theory of finite semigroups: Structure numbers and structure theorems for finite semigroups, in: ``Semigroups'', ed. K. Folley, Academic Press, New York, 1969, 125-162. MR 0281817 (43:7531)
53.: J. Rhodes, Undecidability, automata and pseudovarieties of finite semigroups, Internat. J. Algebra Comput. 9 (1999), 455-473. MR 1723477 (2000j:20112)
54.: J. Rhodes and B. Tilson, The kernel of monoid morphisms, J. Pure Appl. Algebra 62 (1989), 227-268. MR 1026876 (92j:18005)
55.: J. Rhodes and P. Weil, Decomposition techniques for finite semigroups using categories, I, II, J. Pure Appl. Algebra 62 (1989), 269-284; ibid. 62 (1989), 285-312. MR 1026877 (91e:20043)
56.: J. Rhodes and Y. Zalcstein, Elementary representation and character theory of finite semigroups and its application in: ``Monoids and semigroups with applications'' (Berkeley, CA, 1989), ed. J. Rhodes, World Scientific, River Edge, NJ, 1991, 334-367. MR 1142387 (92k:20129)
57.: M. P. Schützenberger, On finite monoids having only trivial subgroups, Inform. Control 8 (1965), 190-194. MR 0176883 (31:1154)
58.: M. P. Schützenberger, Sur le produit de concatenation non ambigu, Semigroup Forum 13 (1976), 47-75. MR 0444824 (56:3171)
59.: I. Simon, ``Hierarchies of events of dot-depth one'', Ph.D. Thesis, University of Waterloo, 1972.
60.: I. Simon, Piecewise testable events, Proc. $2^{nd}$ GI Conf., Kaiserslautern, 1975, Lect. Notes Comp. Sci. 33, Springer, Berlin, 1975, 214-222. MR 0427498 (55:530)
61.: I. Simon, The product of rational languages, $20^{th}$ ICALP, Lect. Notes Comput. Sci. 700, Springer, Berlin, 1993, 430-444. MR 1252424 (94k:68117)
62.: B. Steinberg, Möbius functions and semigroup representation theory, J. Combin. Theory Ser. A 113 (2006), 866-881. MR 2231092 (2007c:20144)
63.: B. Steinberg, Möbius functions and semigroup representation theory. II: Character formulas and multiplicities, arXiv:math.CO/0607564, to appear, Advances in Math.
64.: H. Straubing, A generalization of the Schützenberger product of finite monoids, Theoret. Comput. Sci. 13 (1981), 137-150. MR 594057 (82a:20079)
65.: P. Tesson and D. Thérien, Diamonds are forever: The variety $\mathbf{DA}$ , in: ``Semigroups, Algorithms, Automata and Languages'', eds. G. M. S. Gomes, J.-É. Pin, P. V. Silva, World Scientific, River Edge, NJ, 2002, 475-499. MR 2023803 (2004j:68108)
66.: D. Thérien, Subword counting and nilpotent groups, in: ``Combinatorics on Words, Progress and Perspectives'', ed. L. J. Cummings, Academic Press, New York, 1983, 297-305. MR 910141 (88h:20041)
67.: B. Tilson, Appendix to ``Algebraic theory of finite semigroups: Structure numbers and structure theorems for finite semigroups'': On the -length of -solvable semigroups: Preliminary results, in: ``Semigroups'', ed. K. Folley, Academic Press, New York, 1969, 163-208. MR 0277636 (43:3369)
68.: B. Tilson, Depth decomposition theorem, Chapter XI in [18].
69.: B. Tilson, Categories as algebra: An essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), 83-198. MR 915990 (90e:20061)
70.: J. H. M. Wedderburn, Note on algebras, Annals Math. 38 (1937), 854-856. MR 1503377
71.: P. Weil, Closure of varieties of languages under products with counter, J. Comput. System Sci. 45 (1992), 316-339. MR 1193376 (94g:68065)
72.: Y. Zalcstein, Studies in the representation theory of finite semigroups, Trans. Amer. Math. Soc. 161 (1971), 71-87. MR 0283104 (44:337)

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20M30, 20M35, 20C15, 20C20, 68Q45, 68Q70

Jorge Almeida
Affiliation: Departamento de Matemática Pura, Faculdade de Ciências, Universidade do Porto, 4169-007 Porto, Portugal
Email: jalmeida@fc.up.pt

Stuart Margolis
Affiliation: Department of Mathematics, Bar Ilan University, 52900 Ramat Gan, Israel
Email: margolis@math.biu.ac.il

Benjamin Steinberg
Affiliation: School of Mathematics and Statistics, Carleton University, Ottawa, Ontario, Canada K1S 5B6
Email: bsteinbg@math.carleton.ca

Mikhail Volkov
Affiliation: Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russia
Email: Mikhail.Volkov@usu.ru

DOI: 10.1090/S0002-9947-08-04712-0
PII: S 0002-9947(08)04712-0
Keywords: Representation theory, radicals, language theory
Received by editor(s): February 14, 2007
Posted: October 20, 2008
Additional Notes: The first author acknowledges the support of the Centro de Matemática da Universidade do Porto, financed by FCT through the programmes POCTI and POSI, with Portuguese and European Community structural funds
The second author acknowledges the support of the Excellency Center, ``Group Theoretic Methods for the Study of Algebraic Varieties'' of the Israeli Science Foundation and thanks Professor J.-É. Pin for inviting him to be a visitor to LIAFA
The third author acknowledges the support of NSERC
The fourth author acknowledges support from the Russian Foundation for Basic Research, grant 05-01-00540.
Copyright of article: Copyright 2008, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS