Computing the Hermite Form of a Matrix of Ore Polynomials
Computing the Hermite Form of a Matrix of Ore Polynomials
复制标题
计算 Ore 多项式矩阵的 Hermite 形式
DOI：
10.1016/j.jalgebra.2012.11.033
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Myung Sub Kim
中科院分区：
文献类型：
--
作者：
M. Giesbrecht;Myung Sub Kim
设F[n;σ，δ]是域（或斜域）F上的Ore多项式环，其中σ是F的自同构，δ是σ-导子.给定矩阵A∈F[f;σ，δ]m×n，我们给出了如何计算A的Hermite型H和使得UA=H的幺模矩阵U.该算法需要F中的多项式数量的操作，其依据是维度m和n以及A中的条目的次数（单位为m）。当F=k（z）时，对于某个域k，它还需要元素系数在z中的次数的时间多项式，并且如果k=Q，它还需要有理系数的位长度的时间多项式。显式分析的复杂性，特别是对重要的情况下，微分和移位多项式在Q（z）。为了实现我们的算法，我们应用Ore多项式环的Dieudonné行列式和拟行列式理论，得到H和U中元素的次数和大小的显式界。
Let F[∂;σ,δ] be the ring of Ore polynomials over a field (or a skew field) F, where σ is an automorphism of F and δ is a σ-derivation. Given a matrix A∈F[∂;σ,δ]m×n, we show how to compute the Hermite form H of A and a unimodular matrix U such that UA=H. The algorithm requires a polynomial number of operations in F in terms of the dimensions m and n, and the degrees (in ∂) of the entries in A. When F=k(z) for some field k, it also requires time polynomial in the degrees in z of the coefficients of the entries, and if k=Q it requires time polynomial in the bit length of the rational coefficients as well. Explicit analyses are provided for the complexity, in particular for the important cases of differential and shift polynomials over Q(z). To accomplish our algorithm, we apply the Dieudonné determinant and quasideterminant theory for Ore polynomial rings to get explicit bounds on the degrees and sizes of entries in H and U.