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
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Ivanyos2018_Article_ConstructiveNon-commutativeRan.pdf | Published Version | 481.22 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 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: