Constructive non-commutative rank computation is in deterministic polynomial time

Publication Type:
Journal Article
Citation:
Computational Complexity, 2018, 27 (4), pp. 561 - 593
Issue Date:
2018-12-01
Filename Description Size
Ivanyos2018_Article_ConstructiveNon-commutativeRan.pdfPublished Version481.22 kB
Adobe PDF
Full metadata record
© 2018, Springer International Publishing AG, part of Springer Nature. We extend the techniques developed in Ivanyos et al. (Comput Complex 26(3):717–763, 2017) to obtain a deterministic polynomial-time algorithm for computing the non-commutative rank of linear spaces of matrices over any field. The key new idea that causes a reduction in the time complexity of the algorithm in Ivanyos et al. (2017) from exponential time to polynomial time is a reduction procedure that keeps the blow-up parameter small, and there are two methods to implement this idea: the first one is a greedy argument that removes certain rows and columns, and the second one is an efficient algorithmic version of a result of Derksen & Makam (Adv Math 310:44–63, 2017b), who were the first to observe that the blow-up parameter can be controlled. Both methods rely crucially on the regularity lemma from Ivanyos et al. (2017). In this note, we improve that lemma by removing a coprime condition there.
Please use this identifier to cite or link to this item: