Article ID Journal Published Year Pages File Type
439068 Theoretical Computer Science 2010 6 Pages PDF
Abstract

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×22×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=B2A6B2A2BABABA2B2A2BAB2AB10A2BA2BA10=B2A6B2A2BABABA2B2A2BAB2 holds for the matrices above.1 Our algorithm turns out quite practical and allows us to settle also other related open questions posed in the mentioned article.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,