Theory of Computing
-------------------
Title     : A Deterministic PTAS for the Commutative Rank of Matrix Spaces
Authors   : Markus Blaeser, Gorav Jindal, and Anurag Pandey
Volume    : 14
Number    : 3
Pages     : 1-21
URL       : https://theoryofcomputing.org/articles/v014a003

Abstract
--------

We consider the problem of computing the commutative rank of a given
matrix space $B\subseteq F^{n\times n}$, that is, given a basis of
$B$, find a matrix of maximum rank in $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 $B\subseteq 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 B$ 
such that the rank of $A$ is at least $(1-\epsilon)$ 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 $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).