On the problem of freeness of multiplicative matrix semigroups
The following problem looking as a high-school exercise hides an unexpected difficulty. Do the matrices A=(2003)andB=(3505) satisfy any nontrivial equation with the multiplication symbol only? This problem was mentioned as open in Cassaigne et al. [J. Cassaigne, T. Harju, J. Karhumäki, On the undecidability of freeness of matrix semigroups, Internat. J. Algebra Comput. 9 (3–4) (1999) 295–305] and in a book by Blondel et al. [V. Blondel, J. Cassaigne, J. Karhumäki, Problem 10.3: Freeness of multiplicative matrix semigroups, in: V. Blondel, A. Megretski (Eds.), Unsolved Problems in Mathematical Systems and Control Theory, Princeton University Press, 2004, pp. 309–314] as an intriguing instance of a natural computational problem of deciding whether a given finitely generated semigroup of 2×2 matrices is free. In this paper we present a new partial algorithm for the latter which, in particular, easily finds that the following equation AB10A2BA2BA10=B2A6B2A2BABABA2B2A2BAB2 holds for the matrices above.11This equation has been obtained also by the mean of heavy computations by Cassaigne and Nicolas and reported earlier in the preprint  (see the remark in Section 1). Our algorithm turns out quite practical and allows us to settle also other related open questions posed in the mentioned article.