2
$\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$
8
  • $\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.
    Commented Jul 10, 2016 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.
    Commented Jul 10, 2016 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$ Commented Jul 10, 2016 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$ Commented Jul 11, 2016 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.
    Commented Jul 11, 2016 at 6:08

1 Answer 1

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$
6
  • $\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$ Commented Jul 11, 2016 at 16:01
  • $\begingroup$ Wikipedia contains all references you need. $\endgroup$ Commented Jul 11, 2016 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$ Commented Jul 11, 2016 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$ Commented Jul 11, 2016 at 19:42
  • $\begingroup$ Notice 1) The graph that the matrix describes is bipartite with rows of the matrix representing one bipartition and columns representing the other. 2) The cited result holds when the entries of the matrix are 0's and independent variables, but NOT when they are 0's and 1's. Consider the complete bipartite graph on 4 vertices. This trivially has a matching of size 2, but the associated 2x2 matrix with 0's and 1's would be all 1's, so the rank would be 1. References: [www.cc.gatech.edu/~rpeng/CS7540_S17/Jan10IntroMatching.pdf] [www.cc.gatech.edu/~rpeng/18434_S15/matchingTutteMatrix.pdf] $\endgroup$
    – j_v_wow_d
    Commented Apr 7, 2021 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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