Non-commutative Edmonds' problem and matrix semi-invariants

Introduction

The free skew field was first constructed by Amitsur , and alternative constructions were subsequently given by Bergman , Cohn , and Malcolmson . We refer the reader to by Hrubeš and Wigderson for a nice introduction to the free skew field from the perspective of algebraic computations. Cohn’s books serve as a comprehensive introduction to this topic.

2 Equivalent formulations of the non-commutative Edmonds problem

Like Edmonds’ problem, its non-commutative counterpart also has a long history, though in the literature, it often stated in a very different way. In 1973, Cohn first studied this problem from the perspective of understanding the free skew field, and showed it to be decidable in . In 2003, Gurvits posed this problem in his remarkable work on Edmonds’ problem . Recently, Hrubeš and Wigderson arrived at this problem in their study of non-commutative arithmetic circuits with divisions . Indeed, a very intriguing feature of the non-commutative Edmonds problem is the existence of several interesting equivalent formulations. Instead of relying on the free skew field, these formulations use either linear algebra, or concepts from invariant theory, or quantum information theory. They are scattered in the literature, so we collect them here, to illustrate the various facets of this problem, introduce some previous works, and motivate the study of the non-commutative Edmonds problem.

Some of these formulations make sense only subject to certain conditions. In such cases we indicate the conditions needed before that formulation.

Question: compute the maximum $c$ such that there exists a $c$-shrunk subspace.

Remark: Cohn showed that the non-commutative rank is not full if and only if there is a shrunk subspace . This was generalized by Fortin and Reutenauer[33, Theorem 1] who showed a precise relationship between non-commutative rank and the existence of $c$-shrunk subspaces. Their motivation to consider this problem was to connect matrices over linear forms on the one hand, and matrix spaces of low rank on the other. The latter topic was studied in e.g. . By , we can define the non-commutative rank of $\mathcal{B}$ as

Question: compute the maximum $c$ such that $P$ is rank $c$-decreasing.

Remark: Gurvits stated the problem of deciding whether $P$ is rank non-decreasing or not . His original motivation was to study Edmonds’ original (commutative) problem, and the main result in solves the case when the commutative and non-commutative rank coincide (see Theorem 3.1).

Question: decide whether or not $(B_{1},\dots,B_{m})$ is in the nullcone of $R(n,m)$.

That the original formulation is equivalent to (1) comes from . The equivalence between (1) and (3) is straightforward. The equivalence among decision versions of (1) and (2), and (4) can be obtained via the ring of matrix semi-invariants, as described in Section 1.3. One way to prove the equivalence between (1) and (2) is via Theorem 5.11.

To summarize, the non-commutative Edmonds problem can be derived naturally from the perspectives of quantum information theory,It remains to investigate the physical meaning for a super-operator to be rank non-decreasing though. and invariant theory. It is of great interest in non-commutative algebraic computation with divisions, and in the study of matrix spaces of low rank. Our motivation to study this is because a solution to the non-commutative Edmonds problem will throw light on its commutative counterpart. Shrunk subspaces form a natural and important witness for the singularity of a matrix space. Therefore, if the non-commutative Edmonds problem can be solved deterministically in polynomial time, it means that, for SDIT, the bottleneck lies in recognizing those singular matrix spaces without such witnesses. This connection will be detailed in Section 3.

3 Matrix semi-invariants

Formulation (1), (2) and (4) have a common origin, namely the invariant ring $R(n,m)$ described in (4). We shall call $R(n,m)$ the ring of matrix semi-invariants, as (1) it is closely related to the classical ring of matrix invariants (see below for the definition, and for the precise relationship between these two rings); and (2) it is the ring of semi-invariants of the representation of the $m$-Kronecker quiver with dimension vector $(n,n)$. Here, the $m$-Kronecker quiver is the quiver with two vertices $s$ and $t$, and $m$ arrows pointing from $s$ to $t$. When $m=2$, it is the classical Kronecker quiver. The reader is referred to for a description of the semi-invariants for arbitrary quivers.

It is well-known that the matrix semi-invariant ring is finitely generated, by Hilbert’s celebrated work . This implies that there exists some integer $d$ such that those matrix semi-invariants of degree no more than $d$ define $R(n,m)$. This motivates the following definition.

$\beta(R(n,m))$ is the smallest integer $d$ such that $R(n,m)$ is generated by invariants of degree $\leq d$.

An explicit upper bound on $\beta(R(n,m))$ turns out to be particularly interesting for the purpose of the NCFullRank problem. As already suggested by Hrubeš and Wigderson , if $R(n,m)$ has a degree bound $\beta=\beta(R(n,m))$, one can do the following: take $m$ $d\times d$ variable matrices $Y_{1},\dots,Y_{m}$, $Y_{k}=(y^{(k)}_{i,j})$ and form the polynomial

Over algebraically closed fields of characteristic , by directly employing Derksen’s bounds for invariant rings satisfying certain general conditions , the following bound can be derived. For completeness we include a proof in Appendix A.

Over algebraically closed fields of characteristic , for $R(n,m)$, $\beta\leq\max\{2,3/8\cdot n^{4}\cdot\sigma^{2}\}$, and $\sigma\leq 1/4\cdot n^{2}\cdot 4^{n^{2}}$.

In particular, if $\sigma$ is polynomial in $n$, then $\beta$ is polynomial in $n$ as well.

Another reason to believe that Derksen’s bounds are far from optimal is that for certain small $m$ or $n$, explicit generating sets of $R(n,m)$ have been computed in e.g. . In these cases, elements of degree $\leq n^{2}$ generate the ring.We thank M. Domokos for pointing out this fact to us.

If we turn to positive characteristic fields then, to our best knowledge, no explicit bounds for $\beta(R(n,m))$ nor $\sigma(R(n,m))$ have been derived. Note here that the relation between $\beta$ and $\sigma$ as in Fact 1.2 is not known to hold, due to the assumption on the field properties there. This case is important, for example, in the application to identity testing, and division elimination for non-commutative arithmetic formulas with divisions over fields of positive characteristics . For $S(n,m)$ over fields of positive characteristics, the FFT was established by Donkin in . Over fields of positive characteristic an $O(n^{3})$ upper bound for $\sigma(S(n,m))$ can be derived from [12, Proposition 9], and in Domokos proved an upper bound $O(n^{7}m^{n})$ on $\beta(S(n,m))$.

4 Our results

In the previous sections, we defined the non-commutative Edmonds problem and the NCFullRank problem, and illustrated their connections to matrix semi-invariants. Indeed, our results suggest that progress on one topic helps to advance the other as well.

Our main result is an algorithm that solves the non-commutative Edmonds problem using formulation (2). To ease the presentation, we give an informal statement of the main theorem in Section 5 (Theorem 5.11) here, and discuss its two consequences.

In , Fortin and Reutenauer asked for “an algorithm which uses only linear-algebraic techniques.” Indeed, the algorithm for Theorem 1.4 may be viewed as one, though it relies on certain routines dealing with objects from cyclic field extensions and division algebras.

Secondly, we immediately obtain an explicit bound for $\sigma(R(n,m))$ as a consequence of Theorem 5.11. By Fact 1.2, we also get a bound on $\beta(R(n,m))$, over an algebraically closed field of characteristic . Its proof is also put after Theorem 5.11.

This improves the bounds in Fact 1.2 over algebraically closed fields of characteristic . More importantly, to the best of our knowledge, this provides an explicit bound for $\sigma(R(n,m))$ over fields of positive characteristic for the first time. Furthermore to get this bound we only assume the field size to be large enough, whereas Fact 1.2 requires our field to be algebraically closed.

We also obtain certain structural results for $R(n,m)$, which are reported in .

5 More previous works

The results in this paper suggest a new link between invariant theory and complexity theory. Connections between the two fields have been emerging in recent years. We have already alluded to the direct connection with non-commutative arithmetic circuits, in the work of Hrubeš and Wigderson above. In a series of papers titled geometric complexity theory (GCT) (see also ), Mulmuley and Sohoni pointed out possible deep connections between problems in invariant theory and complexity theory. GCT addresses the fundamental lower bound problems in complexity theory, e.g. the permanent versus determinant problem, by linking them to problems in representation theory and algebraic geometry. In particular, in , Mulmuley established a tight connection between derandomizing the Noether normalization lemma, and black-box derandomizing the polynomial identity test. The degree bounds of various invariant rings are of central importance in that work. We briefly remark that a polynomial bound for $\beta(R(n,m))$, if proven, will yield similar results as what the $n^{2}$ degree bound for $S(n,m)$ has yielded in .

Some earlier work on this problem was cited at the beginning of this article. Here we mention more related work.

Recall that one motivation to study Edmonds’ problem is due to its implications to certain combinatorial problems. This line of research mostly focuses in the case when the given matrices are of particular form, e.g. rank-1 and certain generalizations as used in bipartite graph matchings, or skew symmetric rank-2 and certain generalizations as used in general graph matchings.

Another line of research deals with matrix spaces that satisfy certain properties. Note that properties of matrix spaces should not depend on a particular basis. For example, we can define a property of matrix spaces as, “having a basis consisting of rank-$1$ matrices.” So if $\mathcal{B}$ has a basis consisting of rank-$1$ matrices, $\mathcal{B}$ may not necessarily be presented using this rank-$1$ basis. We are not aware of any result on the complexity of finding rank-$1$ generators for rank-$1$ spanned matrix spaces, if it is given by a basis consisting of not necessarily rank-$1$ matrices. We believe that the problem is hard. Thus the results in , which assume that the input is given by a rank-$1$ basis, do not translate to algorithms for rank-$1$ spanned matrix spaces.

Recall that the other major incentive to study Edmonds’ problem is to understand arithmetic circuit lower bounds via . We believe that for this goal, a better indication of progress is to use properties of matrix spaces, rather than properties of the given matrices. One reason is that, whether a matrix space contains a nonsingular matrix, is a property of matrix spaces. Another reason is that many properties of matrix spaces seem difficult to test algorithmically. Furthermore, note that in this paper we heavily rely on algorithmic techniques developed in and . This may be viewed as another evidence of the importance of working with properties of matrix spaces.

Recently, there was an interest in studying the semi-invariants of the $m$-Kronecker quivers due to its connection with the Kronecker coefficients , namely the multiplicities in the direct sum decompositions of the tensor products of two irreducible representations of symmetric groups. Giving a positive combinatorial description of these coefficients is considered to be one of the most important problems in the combinatorial representation theory of symmetric groups.

6 Update on recent progress

There have been some exciting developments since we posted a version of this paper on the arXiv.

Second, Derksen and Makam proved that $\sigma\leq n^{2}-n$ over large enough fields . Over fields of characteristic zero this implies $\beta(R(n,m))=O(n^{6})$, settling the question of whether there is a polynomial degree bound on the generators for this ring of invariants. To prove the upper bound on $\sigma(R(n,m))$, Derksen and Makam discover a concavity property of blow-ups, and rely crucially on Lemma 5.6 proved in this paper.

After appeared, in we show that the technique of Derksen and Makam can be constructivized. By combining that with the techniques in this paper, we obtain a constructive deterministic polynomial-time algorithm for computing the non-commutative rank over large enough fields. There we also present another independent proof of $\sigma(R(n,m))\leq n^{2}+n$. That argument also builds on Lemma 5.6 from this paper and is much simpler than the concavity argument of Derksen and Makam.

In Section 2 we present certain preliminaries. In Section 3 we give an exposition of the natural connection between commutative and the non-commutative Edmonds problem, and prove Proposition 1.3. In Section 4 we present an efficient construction of division algebras, to be used in proving the main technical lemma Lemma 5.4 . In Section 5 we prove the formal version of Theorem 1.4 (Theorem 5.11) and deduce Corollary 1.5 and 1.6.

Preliminaries

For the reader’s convenience, we collect the main notations in this section. Some of these were already introduced in the introduction.

2 The second Wong sequences

Let us introduce a key tool to be used in Section 5, called the secondThe first Wong sequence is the dual of the second one; this naming convention is due to Wong who in defined the two sequences for the special case $\mathcal{B}=\langle B\rangle$. (generalized) Wong sequence. This was used by Fortin and Reutenauer , and rediscovered by the first two authors with Karpinski and Santha in to solve Edmonds’ problem for rank-$1$ spanned matrix spaces over arbitrary fields.

For completeness we summarize the above discussion together as a fact.

Gurvits’ algorithm and Proposition 1.3

That is, while for the bipartite maximum matching problem, matchings and shrunk subsets are two sides of the same coin, in the linear algebraic setting, this coin splits into two problems: Edmonds’ original (commutative) problem asks to compute the maximum rank, and the non-commutative Edmonds problem asks to compute the maximum $c$ for the existence of a $c$-shrunk subspace.

Now we point out that several results on the (commutative) Edmonds problem can be viewed, and should be understood as, resolving the non-commutative counterpart. For this, note that shrunk subspaces are a natural witness for the singularity of matrix spaces: this construction can be dated back to 1930’s in T. G. Room’s book , and plays a key role in several results which solve special cases of Edmonds’ problem including .

A particular case of interest is rank-$1$ spanned matrix spaces: those matrix spaces that have a basis consisting of rank-$1$ matrices. For rank-$1$ spanned spaces, the analogue of Hall’s theorem holds , so the commutative and the non-commutative Edmonds problems coincide Therefore, the known results for rank-$1$ spanned spaces can be viewed as solving either the non-commutative Edmonds problem or the commutative one. In retrospect, the results for rank-$1$ spanned spaces rely on shrunk subspaces in such a critical way that they should be understood as solving NCFullRank rather than the commutative version for this special case:

The core of Gurvits’ algorithm is an iterative procedure called the operator Sinkhorn’s scaling procedure. When applied to a matrix space $\mathcal{B}$, this procedure converges, if and only if $\mathcal{B}$ has a shrunk subspace.

In fact, Gurvits’ algorithm works by assuming that an analogue of Hall’s theorem for perfect matchings holds.

It is clear that this algorithm runs in time polynomial in the input size and $\sigma$. Note that a linear basis of ${\mathcal{B}}^{[d]}$ can be constructed easily in time polynomial in the input size of $\mathcal{B}$ and $d$.

Efficient construction of division algebras

Division algebras, and efficient construction of such algebras with explicit matrix representations play a crucial role in the main technical lemma, Lemma 5.7, in this paper. In this section we present an efficient construction of such algebras based on Kummer extensions.

Let us first introduce some basic facts about central division algebras. Proofs of the these statements can be found in .

2 Constructing cyclic field extensions under a coprime condition

Our division algebras will be cyclic algebras, that is, non-commutative algebras constructed from cyclic extensions of fields. In this subsection we present an efficient construction of such field extensions, under the condition that the extension degree and the field characteristic are coprime.

3 Constructing cyclic division algebras

The following statement connects cyclic field extensions with central division algebras. It follows from Wedderburn’s theorem characterizing cyclic division algebras (see e.g. [50, Theorem (14.9)]) as shown on Page 221 of .

The following proposition is an algorithmic realization of Fact 4.3.

Combining Lemma 4.1 and Proposition 4.4, we immediately obtain the following.

4 Some algorithmic issues for actual applications

To put the above construction in action, we need to handle a few algorithmic problems as follows.

We explain what the above scheme entails in our actual tasks.

This can be achieved by combining division-free algorithms for computing the determinant by e.g. Kaltofen (see also for more such algorithms), and the parallel algorithm for computing the rank of a matrix by Mulmuley .

4.2 Computing the rank of matrices over a rational function field in few variables

Note that the matrices from Lemma 4.5 are matrices over a rational function field. Therefore we will need to compute the rank of matrices in such form.

In particular, if $k$ is a constant – $k=2$ as used in Lemma 5.3 for the procedure in Lemma 5.7 – then the above procedure runs in polynomial time.

Finding a nonsingular matrix in blow-ups

After some preparation, we prove the main technical lemma called the regularity lemma for blow-ups. Then we prove Theorem 5.11 (the formal version of Theorem 1.4), and Corollaries 1.5 and 1.6 follow easily.

If $\mathcal{A}={\mathcal{B}}^{\{d\}}$ has an $s$-shrunk subspace, then $\mathcal{A}$ has an $s^{\prime}$-shrunk subspace where $s^{\prime}\geq s$ such that $d$ divides $s^{\prime}$, and $\mathcal{B}$ has an $s^{\prime}/d$-shrunk subspace.

2 Regularity of blow-ups

We first present a version of the regularity lemma in which a matrix division algebra as in Lemma 4.5 is assumed to be part of the input.

Using Remark 4.2 and Lemma 4.5 we immediately obtain the following results.

To see all the ingredients together, we give an expanded description in Algorithm 1.

Induction on $d^{\prime}$ and $d$. Assume first that $d^{\prime}=d+1$. Then $\frac{d+1}{d}\leq\frac{n+1}{n}<\frac{r}{r-1}$, whence $(d+1)(r-1)<dr$. Therefore, if we embed ${\mathcal{B}}^{\{d\}}$ into ${\mathcal{B}}^{\{d+1\}}$ then $A$ has rank $rd>(r-1)(d+1)$ and Lemma 5.7 applies. Proceed with $(d+2,d+1)$ in place of $(d+1,d)$. ∎

We close this subsection with two open problems.

It is an interesting problem to investigate whether (the non-constructive version of) the regularity lemma would hold over small fields. Giving a proof not relying on division algebras might be a progress in this direction.

Corollary 5.8 probably remains true for $d<n$. However, we do not see how to prove it.

3 Incrementing rank via blow-up

We present the algorithm formally as Algorithm 2.

We now explain some implementation details of the algorithm.

We would like to thank Mátyás Domokos, Bharat Adsul, Ketan Mulmuley, Partha Mukhopadhyay and K. N. Raghavan for discussions related to this work. Part of the work was done when Youming was visiting the Simons Institute for the program Algorithms and Complexity in Algebraic Geometry and when Gábor was visiting the Centre for Quantum Technologies, National University of Singapore. Research of the first author was also supported in part by the Hungarian National Research, Development and Innovation Office – NKFIH, Grants NK105645 and 115288. Youming’s research was supported by the Australian Research Council DECRA DE150100720.

References

Appendix A Derksen’s bound applied to R​(n,m)𝑅𝑛𝑚R(n,m)

We just need to indicate certain parameters for the matrix semi-invariants that are used in Derksen’s bound.

Suppose a group $G$ acts on a vector space $V$ rationally, and let $R$ be the resulting invariant ring. Theorem 1.1 in shows that the degree bound is upper bounded by $\max(2,3/8\cdot s\cdot\sigma(R)^{2})$, where $\sigma$ is the degree bound for defining the nullcone, and $s$ is the dimension of $R$.

$s$ is upper bounded by the number of variables. Therefore for $R(m,n)$, $s\leq mn^{2}\leq n^{4}$.

$\sigma(R)$ is then upper bounded by $H^{t-m}A^{m}$, where $t$ is the number of variables used to define $G$ as above, $m=\dim(G)$, $H$ is the maximum degree over polynomials defining $G$, and $A$ is the maximum degree over polynomials defining the action. So for $R(n,m)$, $t=2n^{2}$, $m=2n^{2}-2$, $H=n$, and $A=2$. It follows that $\sigma(R(n,m))\leq n^{2}\cdot 2^{2n^{2}-2}$.

Therefore $R(n,m)$ is generated by elements of degree $\leq 3/128\cdot n^{8}\cdot 16^{n^{2}}$. ∎