Computing the Hermite form of a matrix of Ore polynomials (Q360186)

The Ore polynomials in pseudo-linear algebra are a natural algebraic structure which captures difference, \(q\)-difference, differential, and other non-commutative polynomial rings (see, e.g. [\textit{M. Bronstein} and \textit{M. Petkovšek}, Theor. Comput. Sci. 157, No. 1, 3--33 (1996; Zbl 0868.34004)]). In this paper, the authors consider canonical forms of matrices with entries from \(F[\partial; \sigma, \delta]\), the ring of Ore polynomials over a field or a skew field \(F\), where \(\sigma: F \rightarrow F\) is an automorphism of \(F\) and \(\delta: F \to F\) is a \(\sigma\)-derivation. That is, in the case of \(F\) being a skew field for any \(a\), \(b\in F\), \(\delta(a+b)=\delta(a)+\delta(b)\) and \(\delta(ab)=\sigma(a)\delta(b)+\delta(a)b\). Define in turn \(F[\partial; \sigma, \delta]\) as the set of usual polynomials in \(F[\partial]\) under the usual addition, but with multiplication defined via \(\partial a=\sigma(a)\partial +\delta(a)\). Given a matrix \(A\in F[\partial; \sigma, \delta]^{m\times n}\), the authors show how to compute the \(n\times n\) Hermite form \(H\) of \(A\) and a unimodular \(n\times m\) matrix \(U\) such that \(UA=H\), via some algorithm, which requires a polynomial number of operations in \(F\) in terms of the dimensions \(m\) and \(n\), and the degrees (in \(\partial\)) of the entries of \(A\). When \(F=k(z)\) for some field \(k\) (resp., \(k=\mathbb Q\)), it requires time polynomial in the degrees in \(Z\) of the coefficients of the entries (in the bit length of rational coefficients as well). Explicit analysis is provided for the complexity, in particular for the important cases of differential and shift polynomials over \(\mathbb Q(z)\). Furthermore, via their algorithm, explicit bounds on the degrees and sizes of entries in \(H\) and \(U\) are given as well.