The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero

Question

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

Answer 1

(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$.