Trading Determinism for Noncommutativity in Edmonds' Problem

Let$X=X_{1} \sqcup X_{2} \sqcup \ldots \sqcup X_{k}$be a partitioned set of variables such that the variables in each part$X_{i}$are noncommuting but for any$i\neq j$, the variables$x\in X_{i}$commute with the variables$x^{\prime}\in X_{j}$. Given as input a square matrix$T$whose entries are linear forms over$\mathbb{Q}\langle X\rangle$〉, we consider the problem of checking if$T$is invertible or not over the universal skew field of fractions of the partially commutative polynomial ring$\mathbb{Q}\langle X\rangle$[1]. In this paper, we design a deterministic polynomial-time algorithm for this problem for constant$k$. The special case$k=1$is the noncommutative Edmonds' problem (NSINGULAR) which has a deterministic polynomial-time algorithm by recent results [2]–[4]. En-route, we obtain the first deterministic polynomial-time algorithm for the equivalence testing problem of$k$-tape weighted automata (for constant$k$) resolving a longstanding open problem [5], [6]. Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set$X$is zero or not [6]. Decidability of this problem was established by Harju and Karhumäki [5]. Prior to this work, a randomized polynomial-time algorithm for this problem was given by Worrell [6] and, subsequently, a deterministic quasipolynomial-time algorithm was also developed [7].