Constructive non-commutative rank computation is in deterministic polynomial time
- Publication Type:
- Conference Proceeding
- Citation:
- Leibniz International Proceedings in Informatics, LIPIcs, 2017, 67
- Issue Date:
- 2017-11-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Let B be a linear space of matrices over a field F spanned by n × n matrices B1, . . . ,Bm. The non-commutative rank of B is the minimum r € N such that there exists U < Fn satisfying dim(U) - dim(B(U)) n - r, where B(U) := span(Ui2€[m]Bi (U)). Computing the non-commutative rank generalizes some well-known problems including the bipartite graph maximum matching problem and the linear matroid intersection problem. In this paper we give a deterministic polynomial-Time algorithm to compute the non-commutative rank over any field F. Prior to our work, such an algorithm was only known over the rational number field Q, a result due to Garg et al, [20]. Our algorithm is constructive and produces a witness certifying the non-commutative rank, a feature that is missing in the algorithm from [20]. Our result is built on techniques which we developed in a previous paper [24], with a new reduction procedure that helps to keep the blow-up parameter small. There are two ways to realize this reduction. The first involves constructivizing a key result of Derksen and Makam [12] which they developed in order to prove that the null cone of matrix semi-invariants is cut out by generators whose degree is polynomial in the size of the matrices involved. We also give a second, simpler method to achieve this. This gives another proof of the polynomial upper bound on the degree of the generators cutting out the null cone of matrix semi-invariants. Both the invariant-Theoretic result and the algorithmic result rely crucially on the regularity lemma proved in [24]. In this paper we improve on the constructive version of the regularity lemma from [24] by removing a technical coprime condition that was assumed there.
Please use this identifier to cite or link to this item: