Vector ambiguity and freeness problems in SL(2;Z)

Sang Ki Ko, Igor Potapov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish
Pages (from-to)161-182
Number of pages22
JournalFundamenta Informaticae
Issue number2-3
StatePublished - 2018


  • Decidability
  • Matrix semigroup
  • NP-completeness
  • Special linear group
  • Vector ambiguity
  • Vector freeness


Dive into the research topics of 'Vector ambiguity and freeness problems in SL(2;Z)'. Together they form a unique fingerprint.

Cite this