An algorithm for unimodular completion over Laurent polynomial rings (Q947632): Difference between revisions

Let \(K\) be an infinite field, \(R=K[X_1^{\pm 1}, \ldots, X_s^{\pm 1}]\) a multivariate Laurent polynomial ring, and a vector \(v\in R^n\) whose entries generate the unit ideal in \(R\). The paper contains an efficient algorithm which constructs an invertible \(n\times n\) matrix \(M\) over \(K[X_1, \ldots, X_s]\), whose determinant is a monomial, such that \(Mv={}^t (1,0, \ldots, 0)\). The correctness is ensured by a generalization of Suslin's Lemma to Laurent polynomials. The sequential complexity of the algorithm is \(n^4d^{O(s^2)}\) field operations, where \(d\) is the maximum degree of the entries of \(v\), and is due to a clever change of variables which generates doubly monic Laurent polynomials without the exponential explosion of degrees encountered when working à la Nagata. The efficiency is improved by manipulating directly Laurent polynomials, without passing to ordinary polynomial ring as did \textit{H. Park} [J. Symb. Comput. 37, 209--226 (2004; Zbl 1047.94506)], and, unlike \textit{H. Park} and \textit{C. Woodburn} [J. Algebra 178, 277--298 (1995; Zbl 0841.19001)], eliminating all the variables at once.