License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.55
URN: urn:nbn:de:0030-drops-81667
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8166/
Go to the corresponding LIPIcs Volume Portal

Ivanyos, Gábor ; Qiao, Youming ; Subrahmanyam, K Venkata

Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time

pdf-format:
LIPIcs-ITCS-2017-55.pdf (0.6 MB)

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 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.



BibTeX - Entry

@InProceedings{ivanyos_et_al:LIPIcs:2017:8166,
  author =	{G{\'a}bor Ivanyos and Youming Qiao and K Venkata Subrahmanyam},
  title =	{{Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{55:1--55:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8166},
  URN =		{urn:nbn:de:0030-drops-81667},
  doi =		{10.4230/LIPIcs.ITCS.2017.55},
  annote =	{Keywords: invariant theory, non-commutative rank, null cone, symbolic determinant identity testing, semi-invariants of quivers}
}

Keywords: invariant theory, non-commutative rank, null cone, symbolic determinant identity testing, semi-invariants of quivers
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI