Effective dimension of finite semigroups. (Q1940207)

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\).