کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
439068 | 690428 | 2010 | 6 صفحه PDF | دانلود رایگان |

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.
Journal: Theoretical Computer Science - Volume 411, Issues 7–9, 28 February 2010, Pages 1115–1120