Semigroups of finite matrices.
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...
*Research partially supported by INTAS grant 97-1644.Consider the Deligne-Simpson problem: give necessary and sufficient conditions for the choice of the conjugacy classes Cj ⊂ GL(n,C) (resp. cj ⊂ gl(n,C)) so that there exist irreducible (p+1)-tuples of matrices Mj ∈ Cj (resp. Aj ∈ cj) satisfying the equality M1 . . .Mp+1 = I (resp. A1+. . .+Ap+1 = 0). The matrices Mj and Aj are interpreted as monodromy operators and as matrices-residua of fuchsian systems on Riemann’s sphere. We give new examples...