Volume 14 (2018) Article 3 pp. 1-21
CCC 2017 Special Issue
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by
Received: July 15, 2017
Revised: December 22, 2017
Published: April 15, 2018
Download article from ToC site:
[PDF (271K)]    [PS (1404K)]    [PS.GZ (316K)]
[Source ZIP]
Keywords: approximation algorithm, algebraic complexity, commutative rank, matrix spaces, PTAS, Wong sequences
ACM Classification: F.2.2, I.1.2
AMS Classification: 68Q25, 68W25, 68W30

Abstract: [Plain Text Version]

We consider the problem of computing the commutative rank of a given matrix space $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$, that is, given a basis of $\mathcal{B}$, find a matrix of maximum rank in $\mathcal{B}$. This 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. Finding an efficient deterministic algorithm for 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 non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic ${1}/{2}$-approximation algorithm for the commutative rank. It is a natural question whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.

We present a deterministic polynomial-time approximation scheme (PTAS) for computing the commutative rank of a given matrix space. More specifically, given a matrix space $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$ and a rational number $\epsilon > 0$, we give an algorithm that runs in time $O(n^{4+3/\epsilon})$ and computes a matrix $A\in\mathcal{B}$ such that the rank of $A$ is at least $(1-\epsilon)$ times the commutative rank of $\mathcal{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 $k$ of the set depends on $\epsilon$.

A conference version of this paper appeared in the Proceedings of the 32nd Computational Complexity Conference (CCC'17).