2026-08-11T20:18:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8166 2024-03-06T10:39:23Z ddc:004 open_access

Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time Ivanyos, Gábor Qiao, Youming Subrahmanyam, K Venkata invariant theory non-commutative rank null cone symbolic determinant identity testing semi-invariants of quivers Let {\mathcal B} be a linear space of matrices over a field {\mathbb spanned by n\times n matrices B_1, \dots, B_m. The non-commutative rank of {\mathcal B}$ is the minimum r\in {\mathbb N} such that there exists U\leq {\mathbb F}^n satisfying \dim(U)-\dim( {\mathcal B} (U))\geq n-r, where {\mathcal B}(U):={\mathrm span}(\cup_{i\in[m]} B_i(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 {\mathbb F}. Prior to our work, such an algorithm was only known over the rational number field {\mathbb Q}, a result due to Garg et al, [GGOW]. Our algorithm is constructive and produces a witness certifying the non-commutative rank, a feature that is missing in the algorithm from [GGOW]. Our result is built on techniques which we developed in a previous paper [IQS1], 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 [DM2] 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 [IQS1]. In this paper we improve on the constructive version of the regularity lemma from [IQS1] by removing a technical coprime condition that was assumed there. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gábor Ivanyos and Youming Qiao and K Venkata Subrahmanyam 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.55 urn:nbn:de:0030-drops-81667 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.55 eng https://creativecommons.org/licenses/by/3.0/legalcode