The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero 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
 A: (EDITED)
Changing one element can never decrease the rank by more than $1$, so changing $k$ elements can never decrease it by more than $k$.  For at least some cases we can arrange to decrease it by $k$.  For example,
$$ \pmatrix{1 & 1 & 1 & 1\cr 0 & 1 & 1 & 1\cr 0 & 1 & 1 & 0\cr 1 & 0 & 1 & 1 \cr}$$ has rank $4$, but changing the $(4,3)$ and $(2,4)$ entries from $1$ to $0$ gives you a matrix of rank $2$.  Using block matrices with copies of this on the diagonal, we find examples for all $n$ divisible by $4$ where the original matrix has $3n$ ones and rank $n$, and 
we can decrease the rank to $n/2$.
EDIT: Actually it seems there are examples for an $n \times n$ matrix with any even $n \ge 4$ where we can reduce the rank from $n$ to $2$ by changing $n-2$ $1$'s to $0$'s.  The $n \times n$ matrix with entries $1$ for $i+j$ even and $0$ for $i+j$ odd has rank $2$ (because there are only two different rows).
Change the $n-2$  entries in the first super-diagonal except in the first row, 
and we get an invertible matrix $A$: in fact its inverse (over $GF(2)$) has this block-matrix structure:
$$ \pmatrix{1 & u & t\cr t & v & 1\cr v^T & I & u^T\cr}$$
where
$$ t \equiv 1 + (n/2) \mod 2,\ u = [1,0,1,\ldots,0], \ v = [0,1,0,\ldots, 1]$$
Thus we can change $n-2$ $1$'s to $0$'s in $A$ and reduce the rank to $2$.
