BelHalHarKarPotNJ.pdf (360.65 kB)
Matrix equations and Hilbert's tenth problem
journal contribution
posted on 2013-04-04, 15:20 authored by Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumaki, Igor PotapovWe 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 PublishingVersion
- AM (Accepted Manuscript)
Publication date
2008Notes
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/S0218196708004925ISSN
0218-1967eISSN
1793-6500Publisher version
Language
- en