1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Jul 10 '16 at 19:12
  • $\begingroup$ 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. $\endgroup$ – D.W. Jul 10 '16 at 19:13
  • $\begingroup$ 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. $\endgroup$ – Rick Decker Jul 10 '16 at 20:15
  • $\begingroup$ 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). $\endgroup$ – TheoryQuest1 Jul 11 '16 at 3:34
  • $\begingroup$ 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. $\endgroup$ – D.W. Jul 11 '16 at 6:08
4
$\begingroup$

The largest rank equals the size of a maximum matching of the corresponding bipartite graph, for which there are known efficient algorithms; see for example Wikipedia.

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.

$\endgroup$
  • $\begingroup$ Much thanks for the answer Prof. I don't have much experience in this. So, just to be clear on my part again, as I understand: Given an m×m matrix A. Whatever be the maximum possible rank for A (attainable by eliminating 1 entries), it can be computed efficently. If possible can you provide a pointer for some refrences. $\endgroup$ – TheoryQuest1 Jul 11 '16 at 16:01
  • $\begingroup$ Wikipedia contains all references you need. $\endgroup$ – Yuval Filmus Jul 11 '16 at 16:03
  • $\begingroup$ Prof., i had a doubt. If the Graph is a generic non bipartite Graph, we can use the Edmonds's matching algorithm for finding the Maximum Matching (as the wiki page points out) . Would the above argument (Maximum Achievable Rank = Maximum Matching) still hold for all such generic Graphs as well? $\endgroup$ – TheoryQuest1 Jul 11 '16 at 19:17
  • 1
    $\begingroup$ The graph is bipartite by definition. The rows are one bipartition, and the columns another. Each entry corresponds to a potential edge between the row vertex and the column vertex. $\endgroup$ – Yuval Filmus Jul 11 '16 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.