Suppose given $M\in\{0,1\}^{n\times n}$ of rank $r$.
Assume that changing even a single $1$ to $0$ in $M$ raises rank. Does it follow that $M$ is permutationally equivalent to a block diagonal matrix with each block of rank $1$?
Assume that changing even a single $1$ to $0$ in $M$ lowers rank. Does it follow that $M$ is permutationally equivalent to a diagonal matrix?
posted: https://math.stackexchange.com/questions/1171495/probe-permutationally-matrix-extreme-properties
1) No. Idea is to take all columns satisfying certain linear relation (i.e. lying in a certain subspace.) Then changing 1 to 0 violates this relation, and there are no immediate reasons that new relation appears. Namely, we may take, say, $n=k^2$, $k\geq 2$, and columns $e_i+e_j$ where $1\leq i\leq k$, $k+1\leq j \leq 2k$. They all satisfy a relation $x_1+\dots+x_k=x_{k+1}+\dots+x_{2k}$, and any $k^2-1$ of them generate the space generated by this relation. Thus rank equals $2k-1$, and when we change 1 to 0 columns form a space of dimension $2k$.
2) Yes for matrices over the field of characterstic 0. Consider non-zero $r\times r$ minor. Clearly there are no 1's outside it. Thus all non-zero columns are linearly independent and we have to prove that each of them is a basic vector. Assume that there are $m$ 1's in some column (say, column $c$) and $m>1$. Let $c=\sum_{i\in I} e_i, |I|=m$. Replacing each of those 1's to 0 lowers rank, hence column $c-e_i$ is a linear combination of other columns of our matrix for any $i\in I$. Then $c=\frac1{m-1}\sum_{i\in I} (c-e_i)$ is also a linear combination of other columns. A contradiction.
On the other hand, if characteristic of the field equals $p>0$, we may consider invertible $(p+2)\times (p+2)$ matrix with 0-s on diagonal and 1-s outside diagonal. If you replace any 1 to 0 it becomes singular.
