论文标题
晶格同构的计算和积分矩阵相似性问题
Computation of lattice isomorphisms and the integral matrix similarity problem
论文作者
论文摘要
让$ k $为一个数字字段，让$ a $为有限维$ k $ -algebra，让$ \ m artrm {j}（a）$表示$ a $ a $的jacobson激进分子，让$λ$为$ \ nathcal {o \ nathcal {o} {o} _ {k} _ {k} $ - $ A $ A $ A $。假设Semisimple $ K $ -Algebra $ a/{\ Mathrm {j}（a）} $的每个简单组件与字段上的矩阵环是同构。根据$ a $的这一假设，我们给出了一种算法，该算法给出了两个$λ$ - lattices $ x $和$ y $，确定$ x $和$ y $是同构的，如果是的，则计算出明确的同构$ x \ x \ rightarrow y $。该算法将问题减少为多项式时间中计算代数和算法代数数理论的标准问题。作为应用程序，我们为以下长期存在的问题提供了算法：给定数字字段$ k $，一个正整数$ n $和两个矩阵$ a，b \ in \ mathrm {mat} _ {n} _ {n}（\ nathcal {o} _ {k} _ {k}）如果是这样，请返回一个矩阵$ c \ in \ mathrm {gl} _ {n}（\ mathcal {o} _ {k}）$，以至于$ b = cac^{ - 1} $。我们提供了明确的示例，表明后者算法的实现是$ \ Mathcal {o} _ {k} = \ Mathbb {Z} $极大地胜过所有先前算法的实现，如我们的复杂性分析所预测的那样。
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 $Λ$ 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 $Λ$-lattices $X$ and $Y$, determines whether $X$ and $Y$ are isomorphic, and if so, computes an explicit isomorphism $X \rightarrow 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= CAC^{-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.
