Blaeser, Markus ;
Jindal, Gorav ;
Pandey, Anurag
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces
Abstract
We consider the problem of commutative rank computation of a given matrix space. A matrix space is a (linear) subspace of the (linear) space of n x n matrices over a given field. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n, subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the noncommutative rank of matrix spaces in deterministic polynomial time. Since the noncommutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic 1/2approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.
We present a deterministic Polynomialtime approximation scheme (PTAS) for computing the commutative rank of a given matrix space B. More specifically, given a matrix space and a rational number e > 0, we give an algorithm, that runs in time O(n^(4 + 3/e)) and computes a matrix A in the given matrix space B such that the rank of A is at least (1e) times the commutative rank of B. The algorithm is the natural greedy algorithm. It always takes the first set of k matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size of the set k depends on e.
BibTeX  Entry
@InProceedings{blaeser_et_al:LIPIcs:2017:7519,
author = {Markus Blaeser and Gorav Jindal and Anurag Pandey},
title = {{Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {33:133:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7519},
URN = {urn:nbn:de:0030drops75194},
doi = {10.4230/LIPIcs.CCC.2017.33},
annote = {Keywords: Commutative Rank, Matrix Spaces, PTAS, Wong sequences}
}
2017
Keywords: 

Commutative Rank, Matrix Spaces, PTAS, Wong sequences 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

2017 