Computation of lattice isomorphisms and the integral matrix similarity problem

2022/02/07 by Bley, Werner, Hofmann, Tommy, Johnston, Henri · 3 citations
#11R33 #11Y40 #16Z05 #20G30 #FOS: Mathematics #Group Theory (math.GR) #Number Theory (math.NT) #Rings and Algebras (math.RA)

paper · doi:10.48550/arxiv.2202.03526

Abstract

Let K be a number field, let A be a finite-dimensional K-algebra, let J(A) denote the Jacobson radical of A, and let Λ be an O_K-order in A. Suppose that each simple component of the semisimple K-algebra A/J(A) is isomorphic to a matrix ring over a field. Under this hypothesis on A, we give an algorithm that given two Λ-lattices X and Y, determines whether X and Y are isomorphic, and if so, computes an explicit isomorphism X → 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 ∈ Mat_n(O_K), determine whether A and B are similar over O_K, and if so, return a matrix C ∈ GL_n(O_K) such that B= CAC^-1. We give explicit examples that show that the implementation of the latter algorithm for O_K=ℤ vastly outperforms implementations of all previous algorithms, as predicted by our complexity analysis.

Cited by

• Exotic presentations of quaternion groups and Wall's D2 problem
• Determining unit groups and K₁ of finite rings
• On ideal class groups of totally degenerate number rings

Related

• Computing isomorphisms between lattices
• An identification system based on the explicit isomorphism problem
• Splitting full matrix algebras over algebraic number fields
• Computing explicit isomorphisms with full matrix algebras over \mathbbF_q(x)
• On the Lattice Isomorphism Problem