Rank of a Hankel matrix over \({\mathbb{Z}{}} [x_ 1,{\cdots{}},x_ r]\) (Q1205122)

This paper presents a modular algorithm for determining the rank of a Hankel matrix whose elements are multivariate polynomials over the integers. Such an \(n\times n\) matrix \(H_ n\) is generated by the set \(\{d_ 1,d_ 2,\dots,d_{2n-1}\}\), \(d_ i\in K\), where \(K\) is a unique factorization domain, through \(h_{i,j}=d_{i+j-1}\). If \(H_ n\) is generated by rational functions, its rank may be computed using the fact that its rank is the order of its largest nonsingular principal submatrix. The authors generalise this property to every Hankel matrix by means of an algorithm requiring \(\mathbb{O}(n^ 2)\) arithmetic operations. The algorithm is based on computation of a fundamental pair of solutions of a submatrix \(H_ m\) of \(H_ n\), namely \(w_ m\) and \(y_ m\) satisfying \(w_ m^ T H_ m=(d_{m+1},d_{m+2},\dots,d_{2m})\), \(y_ m^ T H_ m=(0,0,\dots,1)\). It is shown that when \(H_ n\) is over \(Z(x_ 1,\dots,x_ r)\), the worst case complexity is \(\mathbb{O}((n^{r+3} G^ r+ n^{r+2} G^{r+1})\ln n\ln^ 2 L)\), where \(G\) bounds the degree of the elements and \(L\) bounds the norm of \(H_ n\).