Non-commutative Edmonds’ problem and matrix semi-invariants

Publication Type:
Journal Article
Computational Complexity, 2017, 26 (3), pp. 717 - 763
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
noncommutative.pdfPublished Version656.33 kB
Adobe PDF
© 2016, Springer International Publishing. In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an n× n matrix T with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds’ problem: compute the rank of T over the free skew field. This problem has been proposed, sometimes in disguise, from several different perspectives in the study of, for example, the free skew field itself (Cohn in J Symbol Log 38(2):309–314, 1973), matrix spaces of low rank (Fortin-Reutenauer in Sémin Lothar Comb 52:B52f 2004), Edmonds’ original problem (Gurvits in J Comput Syst Sci 69(3):448–484, 2004), and more recently, non-commutative arithmetic circuits with divisions (Hrubeš and Wigderson in Theory Comput 11:357-393, 2015. doi:10.4086/toc.2015.v011a014). It is known that this problem relates to the following invariant ring, which we call the F-algebra of matrix semi-invariants, denoted as R(n, m). For a field F, it is the ring of invariant polynomials for the action of SL (n, F) × SL (n, F) on tuples of matrices—(A, C) ∈ SL (n, F) × SL (n, F) sends (B 1 , … , B m ) ∈ M(n, F) ⊕ m to (AB 1 C T , … , AB m C T ). Then those T with non-commutative rank < n correspond to those points in the nullcone of R(n, m). In particular, if the nullcone of R(n, m) is defined by elements of degree ≤ σ, then there follows a poly (n, σ) -time randomized algorithm to decide whether the non-commutative rank of T is full. To our knowledge, previously the best bound for σ was O(n2·4n2) over algebraically closed fields of characteristic 0 (Derksen in Proc Am Math Soc 129(4):955–964, 2001). We now state the main contributions of this paper:We observe that by using an algorithm of Gurvits, and assuming the above bound σ for R(n, m) over Q, deciding whether or not T has non-commutative rank <  n over Q can be done deterministically in time polynomial in the input size and σ.When F is large enough, we devise an algorithm for the non-commutative Edmonds problem which runs in time polynomial in (n + 1)!. Furthermore, due to the structure of this algorithm, we also have the following results.If the commutative rank and the non-commutative rank of T differ by a constant there exists a randomized efficient algorithm to compute the non-commutative rank of T. This improves upon a result of Fortin and Reutenauer, who gave a randomized efficient algorithm to decide whether the commutative and non-commutative ranks are equal.We show that σ≤ (n+ 1) !. This not only improves the bound obtained from Derksen’s work over algebraically closed field of characteristic 0 but, more importantly, also provides for the first time an explicit bound on σ for matrix semi-invariants over fields of positive characteristics. Furthermore, this does not require F to be algebraically closed.
Please use this identifier to cite or link to this item: