×

The pseudovariety of semigroups of triangular matrices over a finite field. (English) Zbl 1086.20029

The main theorem of this paper is a description of the class \({T_p}^q\) of finite semigroups that are triangularizable over the field of characteristic \(p\) and order \(q\), as an intersection of well-known pseudovarieties of semigroups and, thereby, as the class of finite semigroups satisfying a certain set of pseudoidentities. The term ‘triangularizable’ means that the given semigroup is embeddable in the semigroup of all upper triangular \(n\times n\) matrices over the given field, for some positive integer \(n\). Thus it is not a priori obvious that \({T_p}^q\) is a pseudovariety at all, since such classes must be closed under homomorphisms.
Motivation for this general study comes from classic language-theoretic results that relate the class of piecewise testable semigroups, the \(\mathcal J\)-trivial semigroups, and the semigroups of upper triangular Boolean matrices, and from extensions to mod-\(p\) analogues for each of these three classes. The main theorem states that a finite semigroup belongs to \({T_p}^q\) if and only if (1) each of its regular \(\mathcal D\)-classes is a subsemigroup, (2) each of its subgroups is an extension of a \(p\)-group by an Abelian group of exponent dividing \(q-1\), and (3) each subgroup of the subsemigroup generated by its idempotents is a \(p\)-group.

MSC:

20M07 Varieties and pseudovarieties of semigroups
20M20 Semigroups of transformations, relations, partitions, etc.
68Q70 Algebraic theory of languages and automata
20M30 Representation of semigroups; actions of semigroups on sets

References:

[1] J. Almeida , Implicit operations on finite \(J\)-trivial semigroups and a conjecture of I . Simon. J. Pure Appl. Algebra 69 ( 1990 ) 205 - 218 . Zbl 0724.08003 · Zbl 0724.08003 · doi:10.1016/0022-4049(91)90019-X
[2] J. Almeida , Finite Semigroups and Universal Algebra . World Scientific ( 1995 ). MR 1331143 | Zbl 0844.20039 · Zbl 0844.20039
[3] J. Almeida and A. Azevedo , Globals of pseudovarieties of commutative semigroups: the finite basis problem, decidability, and gaps . Proc. Edinburgh Math. Soc. 44 ( 2001 ) 27 - 47 . Zbl 0993.20035 · Zbl 0993.20035 · doi:10.1017/S0013091599000486
[4] J. Almeida and M.V. Volkov , Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety . J. Algebra Appl. 2 ( 2003 ) 137 - 163 . Zbl 1061.20050 · Zbl 1061.20050 · doi:10.1142/S0219498803000519
[5] A.H. Clifford and G.B. Preston , The Algebraic Theory of Semigroups . Amer. Math. Soc. Vol. I ( 1961 ); Vol. II ( 1967 ). Zbl 0111.03403 · Zbl 0111.03403
[6] R.S. Cohen and J.A. Brzozowski , Dot-depth of star-free events . J. Comp. Syst. Sci. 5 ( 1971 ) 1 - 15 . Zbl 0217.29602 · Zbl 0217.29602 · doi:10.1016/S0022-0000(71)80003-X
[7] S. Eilenberg , Automata , Languages and Machines. Academic Press, Vol. A ( 1974 ); Vol. B ( 1976 ). Zbl 0317.94045 · Zbl 0317.94045
[8] S. Eilenberg and M.P. Schützenberger , On pseudovarieties . Adv. Math. 19 ( 1976 ) 413 - 418 . Zbl 0351.20035 · Zbl 0351.20035 · doi:10.1016/0001-8708(76)90029-3
[9] D. Gorenstein , Finite Groups . 2nd edition, Chelsea Publishing Company ( 1980 ). MR 569209 | Zbl 0463.20012 · Zbl 0463.20012
[10] R.M. Guralnick , Triangularization of sets of matrices . Linear Multilinear Algebra 9 ( 1980 ) 133 - 140 . Zbl 0443.15006 · Zbl 0443.15006 · doi:10.1080/03081088008817359
[11] K. Henckell and J.-E. Pin , Ordered monoids and \(J\)-trivial monoids , in Algorithmic problems in groups and semigroups, edited by J.-C. Birget, S. Margolis, J. Meakin and M. Sapir. Birkhäuser ( 2000 ) 121 - 137 . Zbl 0946.20031 · Zbl 0946.20031
[12] P. Higgins , A proof of Simon’s theorem on piecewise testable languages . Theor. Comp. Sci. 178 ( 1997 ) 257 - 264 . Zbl 0901.68093 · Zbl 0901.68093 · doi:10.1016/S0304-3975(96)00230-7
[13] E.R. Kolchin , On certain concepts in the theory of algebraic matrix groups . Ann. Math. 49 ( 1948 ) 774 - 789 . Zbl 0037.18801 · Zbl 0037.18801 · doi:10.2307/1969399
[14] G. Lallement , Semigroups and Combinatorial Applications . John Wiley & Sons ( 1979 ). MR 530552 | Zbl 0421.20025 · Zbl 0421.20025
[15] H. Neumann , Varieties of groups . Springer-Verlag ( 1967 ). MR 215899 | Zbl 0251.20001 · Zbl 0251.20001
[16] J. Okniński , Semigroup of Matrices . World Scientific ( 1998 ). MR 1785162
[17] J.-E. Pin , Variétés de langages formels . Masson, 1984 [French; Engl. translation: Varieties of formal languages. North Oxford Academic (1986) and Plenum (1986)]. MR 752695 | Zbl 0636.68093 · Zbl 0636.68093
[18] J.-E. Pin and H. Straubing , Monoids of upper triangular matrices , in Semigroups. Structure and Universal Algebraic Problems, edited by G. Pollák, Št. Schwarz and O. Steinfeld. Colloquia Mathematica Societatis János Bolyai 39, North-Holland ( 1985 ) 259 - 272 . Zbl 0635.20028 · Zbl 0635.20028
[19] H. Radjavi and P. Rosenthal , Simultaneous Triangularization . Springer-Verlag ( 2000 ). MR 1736065 | Zbl 0981.15007 · Zbl 0981.15007 · doi:10.1007/978-1-4612-1200-3
[20] J. Reiterman , The Birkhoff theorem for finite algebras . Algebra Universalis 14 ( 1982 ) 1 - 10 . Zbl 0484.08007 · Zbl 0484.08007 · doi:10.1007/BF02483902
[21] I. Simon , Hierarchies of Events of Dot-Depth One . Ph.D. Thesis, University of Waterloo ( 1972 ).
[22] I. Simon , Piecewise testable events , in Proc. 2nd GI Conf. Lect. Notes Comp. Sci. 33 ( 1975 ) 214 - 222 . Zbl 0316.68034 · Zbl 0316.68034
[23] J. Stern , Characterization of some classes of regular events . Theor. Comp. Sci. 35 ( 1985 ) 17 - 42 . Zbl 0604.68066 · Zbl 0604.68066 · doi:10.1016/0304-3975(85)90003-9
[24] H. Straubing , On finite \(J\)-trivial monoids . Semigroup Forum 19 ( 1980 ) 107 - 110 . Article | Zbl 0435.20036 · Zbl 0435.20036 · doi:10.1007/BF02572507
[25] H. Straubing , Finite semigroup varieties of the form \(\mathbf{V}*\mathbf{D}\) . J. Pure Appl. Algebra 36 ( 1985 ) 53 - 94 . Zbl 0561.20042 · Zbl 0561.20042 · doi:10.1016/0022-4049(85)90062-3
[26] H. Straubing and D. Thérien , Partially ordered finite monoids and a theorem of I . Simon. J. Algebra 119 ( 1988 ) 393 - 399 . Zbl 0658.20035 · Zbl 0658.20035 · doi:10.1016/0021-8693(88)90067-1
[27] D. Thérien , Classification of finite monoids: the language approach . Theor. Comp. Sci. 14 ( 1981 ) 195 - 208 . Zbl 0471.20055 · Zbl 0471.20055 · doi:10.1016/0304-3975(81)90057-8
[28] D. Thérien , Subword counting and nilpotent groups , in Combinatorics on Words, Progress and Perspectives, edited by L.J. Cummings. Academic Press ( 1983 ) 297 - 305 . Zbl 0572.20052 · Zbl 0572.20052
[29] M.V. Volkov , On a class of semigroup pseudovarieties without finite pseudoidentity basis . Int. J. Algebra Computation 5 ( 1995 ) 127 - 135 . Zbl 0834.20058 · Zbl 0834.20058 · doi:10.1142/S0218196795000094
[30] M.V. Volkov and I.A. Goldberg , Identities of semigroups of triangular matrices over finite fields . Mat. Zametki 73 ( 2003 ) 502 - 510 [Russian; Engl. translation: Math. Notes 73 (2003) 474-481]. Zbl 1064.20056 · Zbl 1064.20056 · doi:10.1023/A:1023298919061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.