RAIRO - Theoretical Informatics and Applications

Research Article

Some decision problems on integer matrices

Christian Choffruta1 and Juhani Karhumäkia2

a1 L.I.A.F.A, Université Paris VII, Tour 55-56, 1 étage, 2 pl. Jussieu, 75 251 Paris Cedex, France; Christian.Choffrut@liafa.jussieu.fr

a2 Dept. of Mathematics and TUCS, University of Turku, 20014 Turku, Finland; Juhani.Karhumaki@cs.utu.fi


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 to a given finitely generated semigroup.

(Online publication March 15 2005)

Mathematics Subject Classification:

  • 20M05;
  • 68R15