Solving systems of linear equations over polynomials (Q1082773): Difference between revisions

This is a generalization of an earlier work of the author and \textit{A. Bachem} [SIAM J. Comput. 8, 499-507 (1979; Zbl 0446.65015)]. In this article a polynomial-time algorithm to derive the Hermite normal form of an \(n\times n\) matrix A(x) of polynomials is given. The algorithm hinges on constructing and postmultiplying by a small multiplier matrix \(K^{(i)}\) for the ith stage of the algorithm then showing that at every stage of the algorithm the transformed matrix \(A^{(i)}\) satisfies: \(| A^{(i)}| =length\) of \(A^{(i)}\) viewed as an \(n^ 2\) vector, den (A\({}^{(i)})=\ell cm\{den (a_{11}),...,den (a_{nn})\}<(4nad)^{400n^{11}d^ 4}\), and deg (A)\(=\max \{\deg a_{ij}(x)\}\leq 2n^ 3d\) where n is the dimension of the original matrix A, a is its length, den is the denominator, \(\ell em\) is the least common multiple, and d is its degree. This algorithm is then generalized to accommodate rectangular matrices and to obtain the Smith normal form based on the algorithm given by the author and A. Bachem [loc. cit.].