Loughborough University
Browse
BelHalHarKarPotNJ.pdf (360.65 kB)

Matrix equations and Hilbert's tenth problem

Download (360.65 kB)
journal contribution
posted on 2013-04-04, 15:20 authored by Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumaki, Igor Potapov
We show a reduction of Hilbert's tenth problem to the solvability of the matrix equation Xi1 1 Xi2 2 Xik k = Z 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.

History

School

  • Science

Department

  • Computer Science

Citation

BELL, P.C. ... et al, 2008. Matrix equations and Hilbert's tenth problem. International Journal of Algebra and Computation, 18 (8), pp.1231-1241.

Publisher

© World Scientific Publishing

Version

  • AM (Accepted Manuscript)

Publication date

2008

Notes

Electronic version of an article published as in the International Journal of Algebra and Computation [© World Scientific Publishing Company]: http://www.worldscientific.com/doi/pdf/10.1142/S0218196708004925

ISSN

0218-1967

eISSN

1793-6500

Language

  • en