Ivanyos, Gábor ;
Qiao, Youming ;
Subrahmanyam, K Venkata
Constructive NonCommutative Rank Computation Is in Deterministic Polynomial Time
Abstract
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 noncommutative 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
nr, where {\mathcal B}(U):={\mathrm span}(\cup_{i\in[m]} B_i(U)).
Computing the noncommutative rank generalizes some wellknown problems including the bipartite graph maximum
matching problem and the linear matroid intersection problem.
In this paper we give a deterministic polynomialtime algorithm to compute the
noncommutative 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 noncommutative 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 blowup 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 semiinvariants 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
semiinvariants.
Both the invarianttheoretic 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.
BibTeX  Entry
@InProceedings{ivanyos_et_al:LIPIcs:2017:8166,
author = {G{\'a}bor Ivanyos and Youming Qiao and K Venkata Subrahmanyam},
title = {{Constructive NonCommutative Rank Computation Is in Deterministic Polynomial Time}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {55:155:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8166},
URN = {urn:nbn:de:0030drops81667},
doi = {10.4230/LIPIcs.ITCS.2017.55},
annote = {Keywords: invariant theory, noncommutative rank, null cone, symbolic determinant identity testing, semiinvariants of quivers}
}
2017
Keywords: 

invariant theory, noncommutative rank, null cone, symbolic determinant identity testing, semiinvariants of quivers 
Seminar: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Issue date: 

2017 
Date of publication: 

2017 