Trading Determinism for Noncommutativity in Edmonds' Problem

Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X=X_{1} \sqcup X_{2} \sqcup \ldots \sqcup X_{k}$</tex> be a partitioned set of variables such that the variables in each part <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X_{i}$</tex> are noncommuting but for any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$i\neq j$</tex>, the variables <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x\in X_{i}$</tex> commute with the variables <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x^{\prime}\in X_{j}$</tex>. Given as input a square matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> whose entries are linear forms over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{Q}\langle X\rangle$</tex> 〉, we consider the problem of checking if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> is invertible or not over the universal skew field of fractions of the partially commutative polynomial ring <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{Q}\langle X\rangle$</tex> [1]. In this paper, we design a deterministic polynomial-time algorithm for this problem for constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>. The special case <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k=1$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-tape weighted automata (for constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>) resolving a longstanding open problem [5], [6]. Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> 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].