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:
- Each 1 entry in the matrix can be replaced by a 0.
- No 0 entry can be set to 1.
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.