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>



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. 


