Given an $n\times n$ matrix $A$, whose elements are over $GF\left(2\right)$ and all diagonal elements are $1$. There are $m\ (m\leq n^2-n)$ non-zero off-diagonal elements in $A$. If we are allowed to choose $k$ non-zero off-diagonal elements of $A$ and set them to $0$, then what is the minimum rank of $A$ over all $k\ (k\leq m)$ and all possible choices?

Denote the above minimum rank as $\text{mk}_2$, since the number of all possible choices (the size of the search spaces) is $2^m$, it's hard to determine $\text{mk}_2$ exactly. If we want to calculate $\text{mk}_2$ approximately, $e.g.$, find possible choices whose rank are less than $c\cdot \text{mk}_2$ or $\text{mk}_2+c$ ($c$ is a constant not increasing with $n$ and $m$), then what is the number of possible choices satisfying this demand?

Is there any structure that can be used to reduce the search spaces in the problem of determining $\text{mk}_2$ exactly? Is there any approximation algorithm that is guaranteed to get within a certain factor of $\text{mk}_2$ with polynomial complexity?

**Observations**:

If $A$ is block diagonal then the problem can be reduced by considering each block independently.

Considering $n=6$ in the example proposed by @Robert Israel, the matrix over $GF(2)$ is $$A= \left(\begin{matrix} 1&0&1&0&1&0\\ 0&1&1&1&0&1\\ 1&0&1&1&1&0\\ 0&1&0&1&1&1\\ 1&0&1&0&1&1\\ 0&1&0&1&0&1\\ \end{matrix}\right) \tag{2}.$$

The rank of $A$ is $6$. There are $16$ off-diagonal '1's in $A$. The $\text{mk}_2$ of $A$ is $2$ and the corresponding unique choice of off-diagonal '1's is given in @Robert Israel's answer.

Now we compute the number of choices that give different ranks for each $k\ (k=0,1,2,\dots,16)$. The results are given as follows:

The number of choices of off-diagonal '1's that give the corresponding ranks