Computation of lattice isomorphisms and the integral matrix similarity problem

Abstract

Let $K$ be a number field, let $A$ be a finite-dimensional $K$-algebra, let $\mathrm{J}(A)$ denote the Jacobson radical of $A$, and let $\Lambda$ be an ${\mathcal{O}}_K$-order in $A$. Suppose that each simple component of the semisimple $K$-algebra $A/\mathrm{J}(A)$ is isomorphic to a matrix ring over a field. Under this hypothesis on $A$, we give an algorithm that given two $\Lambda$-lattices $X$ and $Y$, determines whether $X$ and $Y$ are isomorphic, and if so, computes an explicit isomorphism $X\to Y$. This algorithm reduces the problem to standard problems in computational algebra and algorithmic algebraic number theory in polynomial time. As an application, we give an algorithm for the following long-standing problem: given a number field $K$, a positive integer $n$ and two matrices $A,B\in {\mathrm{Mat}}_n({\mathcal{O}}_K)$, determine whether $A$ and $B$ are similar over ${\mathcal{O}}_K$, and if so, return a matrix $C\in {\mathrm{GL}}_n({\mathcal{O}}_K)$ such that $B=CA{C}^{-1}$. We give explicit examples that show that the implementation of the latter algorithm for ${\mathcal{O}}_K=\mathbb{Z}$ vastly outperforms implementations of all previous algorithms, as predicted by our complexity analysis.

37 pages; v3 revised and accepted version to appear in Forum of Mathematics, Sigma; v2 has many minor corrections and changes