Semigroups of finite matrices.
Suppose σ is an equivalence on a set X and let E(X, σ) denote the semigroup (under composition) of all α: X → X such that σ ⊆ α ∘ α −1. Here we characterise Green’s relations and ideals in E(X, σ). This is analogous to recent work by Sullivan on K(V, W), the semigroup (under composition) of all linear transformations β of a vector space V such that W ⊆ ker β, where W is a fixed subspace of V.
Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension , questions 1) and 3) are undecidable. For dimension , they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs...
Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension 3, questions 1) and 3) are undecidable. For dimension 2, they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs...