×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aguiar, M.; Mahajan, S., ()
[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] (), 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, () · 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, () · 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, (), 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. · 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, (), 3-26 · Zbl 1043.60055
[13] Clifford, A.; Preston, G., The algebraic theory of semigroups, () · 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 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, () · 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., ()
[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., (), viii+342
[27] V. Mazorchuk, B. Steinberg, Double Catalan monoids, J. Alg. Combin. Preprint arXiv:1105.5313 (in press). · 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. New York
[30] Putcha, M., ()
[31] Renner, L., Linear algebraic monoids, () · 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., ()
[35] Rhodes, J.; Zalcstein, Y., Elementary representation and character theory of finite semigroups and its application, (), 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. · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.