[This has been edited in response to comments from Fedor Petrov]


Suppose that $n=dm$ with $d,m>1$. Consider an $n\times n$ matrix $M$ such that


1. All diagonal entries are equal to one
2. Each row has $d$ ones, and all other entries are zero.


This can be seen as the adjacency matrix of a certain kind of directed graph; I am not sure whether that perspective is useful or not. Anyway, I will consider $M$ as a matrix over a finite field $\mathbb{Z}/p$, and I would like to prove that the rank is at least $m$ (which is achieved in the case where $M=J\_d\oplus\dotsb\oplus J\_d$ and $J\_d$ is the all one matrix ). Random experiments (with $m,d\leq 4$ and $p\in\{3,5,7\}$ and $\sim 10^5$ samples) suggests that the rank is always at least $m(d-1)$ with very high probability, but the above example shows that this is not always true. Does anyone know a proof that the rank is always at least $m$?



Lower bound on the rank of a graph
$m$ is a tight bound.


If the matrix be composed of $m$ blocks $d\times d$ with all 1's, its rank equals $m$.


For any $M$ satisfying your conditions, you may color $\{1, 2,\ldots,n\}$ in $d$ colors so that $M\_{i, j}=0$ for all $i<j$ of the same color (if $1, 2,\ldots,k-1$ are already colored, you may choose an appropriate color for $k$, since there exist at most $d-1$ forbidden colors). Then there exist $m$ numbers of the same color, and corresponding rows and columns form a unitriangular minor, thus rank of $M$ is not less than $m$.


