Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Matrix Equations and Hilbert's...

Matrix Equations and Hilbert's Tenth Problem

Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, Igor Potapov, Matrix Equations and Hilbert's Tenth Problem. International Journal of Algebra and Computation 18(8), 1231–1241, 2008.

http://dx.doi.org/10.1142/S0218196708004925

Abstract:

We show a reduction of Hilbert's tenth problem to the solvability of the matrix equation over non-commuting integral matrices, where Z is the zero matrix, thus proving that the solvability of the equation is undecidable. This is in contrast to the case whereby the matrix semigroup is commutative in which the solvability of the same equation was shown to be decidable in general.

The restricted problem where k = 2 for commutative matrices is known as the "A-B-C Problem" and we show that this problem is decidable even for a pair of non-commutative matrices over an algebraic number field.

BibTeX entry:

@ARTICLE{jBeHaHaKaPo08a,
  title = {Matrix Equations and Hilbert's Tenth Problem},
  author = {Bell, Paul and Halava, Vesa and Harju, Tero and Karhumäki, Juhani and Potapov, Igor},
  journal = {International Journal of Algebra and Computation},
  volume = {18},
  number = {8},
  pages = {1231–1241},
  year = {2008},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication