We are given a matrix $M \in \{0,1\}^{n\times n}$ satisfying the following property.


The rows and columns of $M$ can be partitioned into $k$ *rowgroups* and $k$ *colgroups* respectively, such that **in each** block $B \subseteq M$ induced by these partitions, we have $0$ or more rows and $0$ or more columns of $B$ containing **only** entries equal to $0$, while **all** the remaining entries of $B$ are equal to $1$.


**Question**: What is the maximum rank of $M$?




---


I only know the maximum rank of $M$ is upper bounded by $k^2$.



Maximum rank in a class of $0\,$-$1$ partitioned matrices satisfying combinatorial constraints
The answer is $\min(n,k^2)$. 


The upper estimate: rank of $n\times n$ matrix does not exceed $n$, and rank of the sum of at most $k^2$ matrices of rank 1 does not exceed $k^2$.


Example: enumerate rows and columns from 0 to $n-1$ and partition the columns from 0 to $N-1:=\min(n,k^2)$ by the value of remainder modulo $k$; partition rows from 0 to $N-1$ by the value of quotient after division by $k$. Put 1's on the main diagonal at the places $0,1,\dots,N-1$ and zeroes at other places. This matrix has rank $N$ and it satisfies your condition: each block has at most one 1. 


