Abstract:
In this paper we study the Diophantine problem in the classical matrix groups $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$, $\mathrm{T}_n(R)$ and $\mathrm{UT}_n(R)$, $n\geqslant 3$, over an associative ring $R$ with identity. We show that if $G_n(R)$ is one of these groups, then the Diophantine problem in $G_n(R)$ is polynomial-time equivalent (more precisely, Karp equivalent) to the Diophantine problem in $R$. When $G_n(R)=\mathrm{SL}_n(R)$ we assume that $R$ is commutative. Similar results hold for $\mathrm{PGL}_n(R)$ and $\mathrm{PSL}_n(R)$ provided $R$ has no zero divisors (for $\mathrm{PGL}_n(R)$ the ring $R$ is not assumed to be commutative).
Fulltext:
PDF file (746 kB)
