Affiliations: [a] Artificial Intelligence Research Center, Korea Electronics Technology Institute, 22 Daewangpangyo-ro, Gyeonggi-do, 13488, Republic of Korea, sangkiko@keti.re.kr | [b] Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom, sangkiko@liverpool.ac.uk
Correspondence:
[*]
Address for correspondence: Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom
Abstract: We study the vector ambiguity problem and the vector freeness problem in SL(2, ℤ). Given a finitely generated n × n matrix semigroup S and an n-dimensional vector x, the vector ambiguity problem is to decide whether for every target vector y = Mx, where M ∈ S, M is unique. We also consider the vector freeness problem which is to show that every matrix M which is transforming x to Mx has a unique factorization with respect to the generator of S. We show that both problems are NP-complete in SL(2, ℤ), which is the set of 2 × 2 integer matrices with determinant 1. Moreover, we generalize the vector ambiguity problem and extend to the finite and k-vector ambiguity problems where we consider the degree of vector ambiguity of matrix semigroups.
Keywords: matrix semigroup, special linear group, vector ambiguity, vector freeness, decidability, NP-completeness
