Vector Ambiguity and Freeness Problems in SL(2, Z)

Ko, Sang-Ki and Potapov, Igor (2018) Vector Ambiguity and Freeness Problems in SL(2, Z). FUNDAMENTA INFORMATICAE, 162 (2-3). pp. 161-182.

Text vector.pdf - Author Accepted Manuscript Download (145kB)

Abstract

We study the vector ambiguity problem and the vector freeness problem in SL(2;Z). 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;Z), 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.

Item Type:	Article
Uncontrolled Keywords:	matrix semigroup, special linear group, vector ambiguity, vector freeness, decidability, NP-completeness
Depositing User:	Symplectic Admin
Date Deposited:	29 Jun 2018 10:18
Last Modified:	19 Jan 2023 01:31
DOI:	10.3233/FI-2018-1719
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3023175