Column reduction of polynomial matrices : an iterative algorithm

Introduction Recently Beelen developed an algorithm, called KERPOL, to detennine a minimal basis for the kernel of a polynomial matrix (see Beelen [1], Beelen-Veltkamp [3]). In Beelen-Van den Hurk-Praagman [2] this algorithm is used to find a column reduced polynomial matrix, unimodularly equivalent to a given polynomial matrix. As reported already in Neven [7] this algorithm can be improved considerably, by exploiting the special structure of the polynomial map to which the algorithm KERPOL is applied. In the first place this speeds up the procedure at least by a factor 4, and makes it possible to achieve an iteration, instead starting from scratch at each new step. In this paper, we show that it, moreover, enables us to drop the assumption that the original matrix should have full column rank. In section 1 we give the basic definitions and recall the results from [2], section 2 is devoted to the structure indices of polynomial matrices. In section 3 we prove some results on the structure indices of the associated polynomials, and give the main result of this paper. Let us finish this introduction by pointing out some conceptual differences between this paper and its predecessors [1,2,3,4,7]. In the latter a polynomial matrix was interpreted as a mapping between spaces of rational functions. We think it is more natural to see a polynomial matrix as a mapping between two free modules over the ring of polynomials.