# Maximum rank in a class of $0\,$-$1$ partitioned matrices satisfying combinatorial constraints

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

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.
• Great, thank you! PS: Typo: I guess obviously you mean $\min(n,k^2)$ by writing $\max(n,k^2)$, right? – Penelope Benenati Apr 7 '18 at 17:28