# Maximizing the rank of a binary matrix by zeroing matrix entries

Given a Square Binary Matrix.

The entries of the Matrix are the integers modulo 2 (i.e., GF(2)). The Rank of the Given Matrix is an Integer value R0.

What is the fastest known Algorithm to maximize the Rank of the matrix if the following operations are permitted:

1. Each 1 entry in the matrix can be replaced by a 0.
2. No 0 entry can be set to 1.

Approaches Tried:

Since Rank is the measure of number of independent vectors, the current attempt involved using a Gaussian elimination to simplify the matrix. The idea behind it was, if a larger Rank is possible we would be able to obtain the matrix for that Rank, by using the original and the simplified matrix. I am not sure if that is going to work.

Tried searching for some references, but not much success.

• Of course there's an algorithm; you can simply try all possibilities (though this could take exponential time). What is your real question? Are you working over the integers? the integers modulo 2 (i.e., $GF(2)$)? This choice leads to a different notion of "rank". I encourage you to edit the question to clarify what you're trying to achieve. Please take more care in formulating the question. What's the best approach you've come up with so far? What approaches have you considered? What progress have you made so far? – D.W. Jul 10 '16 at 19:12
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. – D.W. Jul 10 '16 at 19:13
• As @D.W. asked, are you using $GF(2)$ merely as a way to say the entries are 0 or 1, or do you intend to do all arithmetic in that field? It makes a difference, since it's not hard to find a 0/1 matrix which has rank 3 over $\mathbb{Q}$ and rank 2 over $GF(2)$, for instance. – Rick Decker Jul 10 '16 at 20:15
• Just the entries are in GF(2) as no matter what manipulations we do the result is a [0,1] matrix. We calculate the Rank using that resultant matrix, and do the airthmetic using integers (not rational numbers). – TheoryQuest1 Jul 11 '16 at 3:34
• I still don't see a clear answer to my question. The question says the entries are in GF(2) and says the entries are integers modulo 2 but later says it wants the integer rank - I find that confusing, since it seems you are saying two things that contradict each other. Pick one. Either you are using integers and you want the rank over the integers and the entries are restricted to be 0-or-1; or you are in GF(2) and want the rank over GF(2) and the entries are integers modulo 2. – D.W. Jul 11 '16 at 6:08

On the one hand, if the graph contains a matching of size $m$, then we can delete all other entries, thus obtaining a matrix in which an $m\times m$ minor is a permutation of the identity, and so of rank $m$. Thus the maximum achievable rank is at least the size of any matching.
On the other hand, suppose that by deleting entries of the original matrix $A$, we can obtain a matrix $B$ whose rank is $m$. The matrix $B$ must contain an $m\times m$ minor $C$ whose rank is $m$ (find a set of $m$ rows which form a basis for the row space, then a set of $m$ columns which form a basis for the column space). In particular, $\det C \neq 0$ and so there must be a "generalized diagonal" in $C$ which consists only of $1$s (since $\det C$ is the sum of the products of all generalized diagonals). This generalized diagonal appears already in $A$, and constitutes a matching of size $m$ in the corresponding graph.