Complexity of solving linears systems in the rings of differential operators

D. Yu. Grigor'ev

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 5, Tome 192 (1991), pp. 47-60

Résumé

Let $\mathcal{A}_n=F[X_1,\dots,X_n,D_1,\dots,D_n]$ be Weyl algebra over a field $F$, i.e. the following relations hold: $X_iX_j=X_jX_i$, $D_iD_j=D_jD_i$, $X_iD_i=D_iX_i-1$, $X_iD_j=D_jX_i$ for $i\ne j$. Denote also by $\mathcal{K}_n=F(X_1,\dots,X_n)[D_1,\dots,D_n]\supset\mathcal{A}_n$ the ring of differential operators. Any element $a\in\mathcal{A}_n$ can be uniquely written in the form $a=\sum\limits_{I,J}a_{I,J}D_n^{i_n}\dots D_1^{i_1}X_1^{j_n}\dots X_1^{j_1}$, where $a_{I,J}\in F$, define $\mathrm{deg}(a)=\max\limits_{a_{I,J}\ne0}\{i_n+\dots+i_1+j_n+\dots+j_1\}$. In a similar way any element $b\in\mathcal{K}_n$ can be represented in the form $b=b_1b_2^{-1}$ where $b_1\in\mathcal{A}_n$ can a polynomial $b_2\in F[X_1,\dots,X_n]$ has the least possible degree, we define $\mathrm{deg}(b)=\max\{\mathrm{deg}(b_1),\mathrm{deg}(b_2)\}$. Let $\mathcal{R}$ be either $\mathcal{A}_n$ or $\mathcal{K}_n$. Consider a linear system $\sum\limits_{1\leqq l\leqq s}u_{k,l}V_l=w_k$, $1\leqq k\leqq m$, where $u_{k,l}, w_k\in\mathcal{R}$. Assume that $\mathrm{deg}(u_{k,l}),\mathrm{deg}(w_k)$. The main theorem of the paper states that provided the system is solvable over $\mathcal{R}$, it has a solution $V_1,\dots,V_s\in\mathcal{R}$ such that $\mathrm{deg}(V_l)\leqq(md)^{2^{O(n)}}$, $1\leqq l\leqq s$. Remark that for the case of the ring of polynomials $\mathcal{R}=F[X_1,\dots,X_n]$ the bound in lemma was well known [11], but one cannot generalize the proof directly, since the rings $\mathcal{A}_n$, $\mathcal{K}_n$ are noncommutative. We say that $m\times m$ matrix $B$ (over $\mathcal{A}_n$) is left quasi-inverse to $m\times m$ matrix $C$ (over $\mathcal{A}_n$) if $BC$ has a diagonal form with nonzero diagonal entries. In this case we call $B$ (and also $C$) nonsingular matrix. For a matrix (over $\mathcal{A}_n$) we define its rank as the maximal size of its nonsingular submatrices. Denote by $\mathcal{D}_n$ the skew-field of quotients of $\mathcal{A}_n$ (see [6]). The core of the construction is the following lemma. For $m\times s$ matrix $(u_{k,l})$ over $\mathcal{A}_n$ of the rank $r$ there is $m\times m$ nonsingular matrix $A$ over $\mathcal{D}_n$ and $s\times s$ permuting matrix $P$ such that the matrix $A(u_{k,l})P$ has a trapezium shape with nonzero rows, moreover $\mathrm{deg}(A(u_{k,l})P)\leqq O(nmd)$. Furthermore, we need a kind of the normalization lemma for the ring $\mathcal{A}_n$. Since the group of linear transformations of $\mathcal{A}_n$, coincides with the symplectic group $S_{P_{2n}}$, the normalization lemma follows from the transitivity of $S_{P_{2n}}$. Ihe main theorem is proved by induction on $n$. For the ring $\mathcal{K}_n$ the proof of the main theorem proceeds in a similar way, even easier, since the group of linear transformations of $\mathcal{K}_n$, is isomorphic to $GL_n$.