×

Effective dimension of finite semigroups. (English) Zbl 1279.20077

The effective dimension of a finite semigroup \(S\) over a field \(K\) is the least number \(n\) such that \(S\) embeds into the semigroup of all \(n\times n\)-matrices over \(K\). The authors first observe that the effective dimension is effectively computable over any algebraically closed or real closed field and conjecture that computing the effective dimension of a finite 3-nilpotent semigroup over the field of complex numbers is NP-hard.
Then they proceed with computing the effective dimension within various classes of semigroups (including commutative inverse monoids, generalized group mapping semigroups, nilpotent semigroups, path semigroups, bands, cyclic semigroups). They also calculate the effective dimension for the classic transformation monoids and the monoid of all binary relations on an \(n\)-element set: over the field of complex numbers the monoid of all total (partial, partial injective) transformations has effective dimension \(n\) while the monoid of all binary relations has effective dimension \(2^n-1\).

MSC:

20M30 Representation of semigroups; actions of semigroups on sets
20M20 Semigroups of transformations, relations, partitions, etc.
20M05 Free semigroups, generators and relations, word problems
20M10 General structure theory for semigroups
68Q25 Analysis of algorithms and problem complexity
16G99 Representation theory of associative rings and algebras
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aguiar, M.; Mahajan, S., (Coxeter Groups and Hopf Algebras. Coxeter Groups and Hopf Algebras, Fields Institute Monographs, vol. 23 (2006), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 1106.16039
[2] Almeida, J.; Margolis, S.; Steinberg, B.; Volkov, M., Representation theory of finite semigroups, semigroup radicals and formal language theory, Trans. Amer. Math. Soc., 361, 3, 1429-1461 (2009) · Zbl 1185.20058
[3] (Arbib, M. A.; Krohn, K.; Rhodes, J. L., Algebraic Theory of Machines, Languages, and Semigroups (1968), Academic Press: Academic Press New York-London), With a major contribution by
[4] Arnold, F.; Steinberg, B., Synchronizing groups and automata, Theoret. Comput. Sci., 359, 101-110 (2006) · Zbl 1097.68054
[5] Babson, E.; Huisgen-Zimmermann, B.; Thomas, R., Generic representation theory of quivers with relations, J. Algebra, 322, 6, 1877-1918 (2009) · Zbl 1217.16013
[6] Benson, D. J., Basic representation theory of finite groups and associative algebras, (Cambridge University Press. Cambridge University Press, Cambridge Studies in Advanced Mathematics, vol. 30 (1998), Cambridge) · Zbl 0718.20001
[7] Berkovich, Y. G.; Zhmud, E. M., Characters of finite groups. Part 2. Translated from the Russian manuscript by P. Shumyatsky, V. Zobina and Berkovich, (Translations of Mathematical Monographs, 181 (1999), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0934.20008
[8] Bidigare, P.; Hanlon, P.; Rockmore, D., A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. J., 99, 1, 135-174 (1999) · Zbl 0955.60043
[9] Björner, A., Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries, (Building Bridges. Building Bridges, Bolyai Soc. Math. Stud., vol. 19 (2008), Springer: Springer Berlin), 165-203 · Zbl 1158.60344
[10] M. Brittenham, S.W. Margolis, J. Meakin, Subgroups of free idempotent generated semigroups: full linear monoid. Preprint arXiv:1009.5683; M. Brittenham, S.W. Margolis, J. Meakin, Subgroups of free idempotent generated semigroups: full linear monoid. Preprint arXiv:1009.5683 · Zbl 1177.20064
[11] Brown, K. S., Semigroups, rings, and Markov chains, J. Theoret. Probab., 13, 3, 871-938 (2000) · Zbl 0980.60014
[12] Brown, K. S., Semigroup and ring theoretical methods in probability, (Representations of Finite Dimensional Algebras and Related Topics in Lie Theory and Geometry. Representations of Finite Dimensional Algebras and Related Topics in Lie Theory and Geometry, Fields Inst. Commun., vol. 40 (2004), Amer. Math. Soc: Amer. Math. Soc Providence, RI), 3-26 · Zbl 1043.60055
[13] Clifford, A.; Preston, G., The algebraic theory of semigroups, (Vol. I. Mathematical Surveys, No. 7 (1961), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0178.01203
[14] Dickson, L. E., Representations of the general symmetric group as linear groups in finite and infinite fields, Trans. Amer. Math. Soc., 9, 2, 121-148 (1908) · JFM 39.0198.02
[15] Eilenberg, S., Automata, Languages, and Machines. Vol. B (1976), Academic Press: Academic Press New York · Zbl 0359.94067
[16] Farkas, D.; Snider, R., Simple augmentation modules, Quart. J. Math. Oxford Ser. (2), 45, 177, 29-42 (1994) · Zbl 0802.20006
[17] Ganyushkin, O.; Mazorchuk, V., Classical finite transformation semigroups. An introduction, (Algebra and Applications, 9 (2009), Springer-Verlag London, Ltd.: Springer-Verlag London, Ltd. London) · Zbl 1166.20056
[18] Ganyushkin, O.; Mazorchuk, V.; Steinberg, B., On the irreducible representations of a finite semigroup, Proc. Amer. Math. Soc., 137, 11, 3585-3592 (2009) · Zbl 1184.20054
[19] Hartshorne, R., (Algebraic Geometry. Algebraic Geometry, Graduate Texts in Mathematics, No. 52 (1977), Springer-Verlag: Springer-Verlag New York-Heidelberg) · Zbl 0367.14001
[20] Karpilovskii, G., The smallest degree of exact representation of abelian groups over certain fields of characteristic 0, Sibirsk. Mat. Zh., 11, 697-702 (1970)
[21] Kim, K. H.; Roush, F., Linear representations of semigroups of Boolean matrices, Proc. Amer. Math. Soc., 63, 2, 203-207 (1977) · Zbl 0329.20047
[22] Kleitman, D.; Rothschild, B.; Spencer, J., The number of semigroups of order \(n\), Proc. Amer. Math. Soc., 55, 1, 227-232 (1976) · Zbl 0324.05010
[23] Kovács, L., Semigroup algebras of the full matrix semigroup over a finite field, Proc. Amer. Math. Soc., 116, 4, 911-919 (1992) · Zbl 0765.16008
[24] Krohn, K.; Rhodes, J., Complexity of finite semigroups, Ann. of Math. (2), 88, 128-160 (1968) · Zbl 0162.03902
[25] Kudryavtseva, G.; Mazorchuk, V., On Kiselman’s semigroup, Yokohama Math. J., 55, 1, 21-46 (2009) · Zbl 1216.20044
[26] Marker, D., (Model Theory. An Introduction. Model Theory. An Introduction, Graduate Texts in Mathematics, vol. 217 (2002), Springer-Verlag: Springer-Verlag New York), viii+342 · Zbl 1003.03034
[27] V. Mazorchuk, B. Steinberg, Double Catalan monoids, J. Alg. Combin. Preprint arXiv:1105.5313; V. Mazorchuk, B. Steinberg, Double Catalan monoids, J. Alg. Combin. Preprint arXiv:1105.5313 · Zbl 1259.05190
[28] Okniński, J.; Putcha, M., Complex representations of matrix semigroups, Trans. Amer. Math. Soc., 323, 2, 563-581 (1991) · Zbl 0745.20057
[29] Petrich, M., Inverse Semigroups. Pure and Applied Mathematics (New York) (1984), A Wiley-Interscience Publication. John Wiley & Sons, Inc.: A Wiley-Interscience Publication. John Wiley & Sons, Inc. New York
[30] Putcha, M., (Linear Algebraic Monoids. Linear Algebraic Monoids, London Mathematical Society Lecture Note Series, vol. 133 (1988), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0647.20066
[31] Renner, L., Linear algebraic monoids, (Encyclopaedia of Mathematical Sciences. Encyclopaedia of Mathematical Sciences, Invariant Theory and Algebraic Transformation Groups, V, vol. 134 (2005), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1085.20041
[32] Rhodes, J., Some results on finite semigroups, J. Algebra, 4, 471-504 (1966) · Zbl 0163.02103
[33] Rhodes, J., Characters and complexity of finite semigroups, J. Combin. Theory, 6, 67-85 (1969) · Zbl 0165.33502
[34] Rhodes, J.; Steinberg, B., (The \(q\)-Theory of Finite Semigroups. The \(q\)-Theory of Finite Semigroups, Springer Monographs in Mathematics (2009), Springer: Springer New York) · Zbl 1186.20043
[35] Rhodes, J.; Zalcstein, Y., Elementary representation and character theory of finite semigroups and its application, (Monoids and Semigroups with Applications (Berkeley, CA, 1989) (1991), World Sci. Publ: World Sci. Publ River Edge, NJ), 334-367 · Zbl 0799.20062
[36] Rieffel, M., Burnside’s theorem for representations of Hopf algebras, J. Algebra, 6, 123-130 (1967) · Zbl 0166.01202
[37] Saliola, F. V., The quiver of the semigroup algebra of a left regular band, Internat. J. Algebra Comput., 17, 8, 1593-1610 (2007) · Zbl 1148.16024
[38] Saliola, F. V., The face semigroup algebra of a hyperplane arrangement, Canad. J. Math., 61, 4, 904-929 (2009) · Zbl 1195.52006
[39] Schein, B. M., Representations of generalized groups, Izv. Vyssh. Uchebn. Zaved. Mat., 3, 164-176 (1962) · Zbl 0228.20062
[40] G. Shafranova, Nilpotent subsemigroups of transformation semigroups, Ph.D. Thesis, Kyiv University, Kyiv, Ukraine, 2000.; G. Shafranova, Nilpotent subsemigroups of transformation semigroups, Ph.D. Thesis, Kyiv University, Kyiv, Ukraine, 2000. · Zbl 0977.20046
[41] Steinberg, B., Möbius functions and semigroup representation theory, J. Combin. Theory Ser. A, 113, 5, 866-881 (2006) · Zbl 1148.20049
[42] Steinberg, B., A theory of transformation monoids: combinatorics and representation theory, Electron. J. Combin., 17, 1 (2010), Research Paper 164, 56 pp. (electronic) · Zbl 1208.20059
[43] Steinberg, R., Complete sets of representations of algebras, Proc. Amer. Math. Soc., 13, 746-747 (1962) · Zbl 0114.25604
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.