Non-commutative Edmonds' problem and matrix semi-invariants (Q2410690)

The \textit{non-commutative rank} of an \(n\times n\) matrix \(T\) of linear forms (in \(m\) indeterminates) over a field \(\mathbb{F}\) is the rank of \(T\) over the free skew-field (generated by the \(m\) indeterminates). The non-commutative Edmonds' problem asks for computing the non-commutative rank of \(T\). Note that \(T\) is given by an \(m\)-tuple of \(n\times n\) matrices over \(\mathbb{F}\). The non-commutative Edmonds' problem is closely related to the study of the ring of matrix semi-invariants (i.e. the ring of invariants of \(\mathrm{SL}(n,\mathbb{F})\times\mathrm{SL}(n,\mathbb{F})\) acting via left and right multiplication) on \(m\)-tuples of \(n\times n\) matrices over \(\mathbb{F}\). Denote by \(\sigma\) the minimal positive integer such that the nullcone for the above action is cut out by semi-invariants of degree at most \(\sigma\). The main results of the present paper are the following: (1) For \(\mathbb{F}=\mathbb{Q}\) there exists a deterministic algorithm to decide wether the non-commutative rank is smaller than \(n\) in time polynomial in the input size and \(\sigma\). (2) For \(\mathbb{F}\) large enough an algorithm is devised for the non-commutative Edmonds' problem which runs in time polynomial in \((n+1)!\). (3) Improving upon a result of \textit{M. Fortin} and \textit{C. Reutenauer} [Sémin. Lothar. Comb. 52, B52f, 12 p. (2004; Zbl 1069.15011)], the authors show a randomized efficient algorithm to compute the non-commutative rank of \(T\) under the assumption that its difference from the commutative rank is bounded by a constant. (4) For \(\mathbb{F}\) large enough the inequality \(\sigma\leq (n+1)!\) is proved. Along the way the authors discover a fact of independent interest as follows. For a subspace \(\mathcal{B}\) of the space \(M(n,\mathbb{F})\) of \(n\times n\) matrices and a positive integer \(d\), the \(d^{\mathrm{th}}\) tensor blow-up of \(\mathcal{B}\) is defined as \(\mathcal{B}^{(d)}=M(d,\mathbb{F})\otimes \mathcal{B}\), viewed as a subspace of \(M(dn,\mathbb{F})\). It is shown that the maximal possible rank of an element in \(\mathcal{B}^{(d)}\) is divisible by \(d\). The proof uses basic results on division rings. We mention finally that the paper gives a thorough description of various formulations of the non-commutative Edmonds' problem and the related literature.