2015/08/04 by Gábor Ivanyos, Ivanyos, Gábor, Youming Qiao +3 · 1 citation
Computer Science · Mathematics · #Advanced Operator Algebra Research #Advanced Topics in Algebra #Commutative Algebra (math.AC) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Rings and Algebras (math.RA)
paper · doi:10.48550/arxiv.1508.00690
openalex publication_date 2015/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1967, 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. It is known that this problem relates to the ring of matrix semi-invariants. In particular, if the nullcone of matrix semi-invariants 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